Attribut:Beschreibung

===Description=== This lecture is aiming at providing basic skills in reading, understanding, and evaluating scientific articles, and in presenting scientific results in presentations and publications. It includes topics like citations and bibliographic data in scientific publications, selection of topics, examples, and results for an oral presentation, preparation of slides and other materials for oral presentations as well as selecting, structuring, and writing scientific articles. The lecture will include practical training in reading and reviewing scientific articles, in preparing and giving presentations, and in setting up and writing short scientific articles. The topics will be selected from Computational Logic. Hence, some familiarity with propositional and first-order logic is assumed. ===Schedule=== The lecture will take place on Mondays 4.DS (1pm - 2:30pm) and on Thursdays 6. DS (4:40pm - 6:10pm) in room '''APB E005'''. The lecture will start on Monday, 9th April, 2018. 21.6. Presentation about the reviews The reviews will be graded to obtain the 1st mark 28.6. Slides 2.7. Presentations (one group) 5.7. Presentations (two groups) Presentation on 2.7/5.7. will be graded to obtain the 2nd mark ===UPDATE (2.7.2018)=== Last week of the Semester 20.7. Short Presentations (graded) 3rd Assignment: Give a short introductory presentation (10-15 minutes) about one of the following topics: 1) Decision Tree Learning 2) Backpropagation 3) Inductive Logic Programming 4) Bayesian Networks 5) Satisfiability Modulo Theories 6) Algorithm Configuration 7) Support Vector Machines No shared topics. Each students has to select an individual topic / different each. Presentations will be graded to obtain the 3rd mark. The presentations will be on Jul 20, starting at 10am in our lab. ===UPDATE END=== ===Lecture Slides=== * [https://iccl.inf.tu-dresden.de/w/images/8/81/Introduction2018-1_%2809.04.2018%29.pdf Introduction] * [https://iccl.inf.tu-dresden.de/w/images/0/06/AssessingPapers-1_%2823.04.2018%29.pdf Assessing Papers] * [https://iccl.inf.tu-dresden.de/w/images/5/5b/GivingTalks.pdf How to Give a Good Research Talk]

This lecture is aiming at providing basic skills in reading, understanding, and evaluating scientific articles, and in presenting scientific results in presentations and publications. It includes topics like citations and bibliographic data in scientific publications, selection of topics, examples, and results for an oral presentation, preparation of slides and other materials for oral presentations as well as selecting, structuring, and writing scientific articles. The lecture will include practical training in reading and reviewing scientific articles, in preparing and giving presentations, and in setting up and writing short scientific articles. The topics will be selected from Computational Logic. Hence, some familiarity with propositional and first-order logic is assumed. == Dates == The lectures and exercise classes generally take place on the following dates: * Lecture: Tuesday, DS3 (11:10–12:40) in room APB E005 * Exercise: Tuesday DS5 (14:50–16:20) in room APB E001 * '''Due to preparations for Output 2019, there will be no exercise on 2019-06-18''' == Mock Conference on Academic Skills in Computer Science == We are conducting a mock conference to demonstrate the paper submission and reviewing process. Submissions are currently open, see [[Media:asics2019-exercise-09-more-advanced-latex.pdf|Exercise 9.4]] for details. +

Due to the current COVID19 situation, this course will be held virtually until further notice. The content of the lecture will be made available as videos (i.e. slideshows with audio comments). The first uploads are now available. See below for the format of the tutorials. This lecture is aiming at providing basic skills in reading, understanding, and evaluating scientific articles, and in presenting scientific results in presentations and publications. It includes topics like citations and bibliographic data in scientific publications, selection of topics, examples, and results for an oral presentation, preparation of slides and other materials for oral presentations as well as selecting, structuring, and writing scientific articles. The lecture will include practical training in reading and reviewing scientific articles, in preparing and giving presentations, and in setting up and writing short scientific articles. The topics will be selected from Computational Logic. Hence, some familiarity with propositional and first-order logic is assumed. == Dates == The lectures and exercise classes generally take place on the following dates: * Lecture: Monday, DS2 (09:20–10:50) in room APB E005 * Exercise: Tuesday DS5 (14:50–16:20) in room APB E001 == Exercises & Tutorials == This course is about teaching skills, and thus the focus of most exercises lies on *doing* something rather than on obtaining a specific answer. Frequently, exercises will not have a single correct solution, but rather allow for multiple different strategies. Hence, please work through the tasks on each week's exercise sheet on your own. Feel free to discuss any questions you might have on the [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/23234641950/CourseNode/101485805123021 OPAL Forum]. We will discuss each exercise sheet during the following week's exercise session, in the form of an interactive meeting. * The next interactive discussion session will be on 2020-07-14, starting 14:50 using the [https://selfservice.zih.tu-dresden.de/link.php?meeting_id=2373&pin=df95eb46e67f92cb7efebb79a9d657796fee6fda4a66fde74c6bc3e56feefcfd BigBlueButton] service. == Mock Conference on Academic Skills in Computer Science == We are conducting a mock conference to demonstrate the paper submission and reviewing process. Submissions and Reviews are now closed. == Examinations == Examinations will take the form of a 20-minute oral exam. We plan to conduct the examinations primarily in the last week of July, i.e., between 2020-07-27 and 2020-07-31. Please contact [mailto:sebastian.rudolph@tu-dresden.de Prof. Rudolph] to schedule an exam date.

This lecture is aiming at providing basic skills in reading, understanding, and evaluating scientific articles, and in presenting scientific results in presentations and publications. It includes topics like citations and bibliographic data in scientific publications, selection of topics, examples, and results for an oral presentation, preparation of slides and other materials for oral presentations as well as selecting, structuring, and writing scientific articles. The lecture will include practical training in reading and reviewing scientific articles, in preparing and giving presentations, and in setting up and writing short scientific articles. The topics will be selected from Computational Logic. Hence, some familiarity with propositional and first-order logic is assumed. +

Problem solving and search is a central topic in Artificial Intelligence. This course presents several techniques to solve in general difficult problems. The course covers the following '''topics''': *Basic Concepts *Uninformed vs Informed Search *Local Search, Stochastic Hill Climbing, Simulated Annealing *Tabu Search *Answer Set Programming *Constraint Satisfaction *Evolutionary Algorithms, Genetic Algorithms *Structural Decomposition Techniques (Tree/Hypertree Decompositions) The course does not cover topics in the area of Machine Learning and Neural Networks. NOTE: This course was previously named Problem Solving and Search in Artificial Intelligence. The contents of former PSSAI and APSS are identical, and therefore students can only take one of the two courses. ===Learning Outcomes=== *The students should identify why typical AI problems are difficult to solve *The students will analyze different algorithms and methods for AI problems and identify when their application is appropriate *The connections between the (graph) structure and the complexity of a problem should become clear, as well as which methods can be used to tackle the problem *In the tutorials, the students will analyze different problems and develop solutions for them. ===Prerequisites=== *Basic knowledge of theoretical computer science and Logic. *Good English skills: both the teaching and examination will be exclusively in English. ===Organisation=== The goals can be acquired by studying the lecture material and solving the exercises of the tutorials. The lectures will be held on Mondays DS2 (09.20 - 10.50 am) and the tutorials on Tuesdays DS2. Please check the schedule for changes. The slides of the lectures and exercises of the tutorials will be uploaded in this page, in each corresponding session. Announcement: because of the COVID-19 pandemic we will provide the materials for self-learning on the planned dates for lectures and we will have online live sessions for the tutorials. The lecture videos will be uploaded in OPAL and I invite you to use the forum to ask questions and share your exercise solutions. Please, register for the course on the OPAL site: https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/29670014985?6 ===Examination=== This year, due to the exceptional COVID-19 pandemic, the exam will be written and online, on the OPAL-ONYX platform. It will mostly consist of single and multiple-choice questions as well as some quick exercises. There will be no oral examinations. As a consequence, regarding complex examinations held jointly with another examiner: - Students who wish to take a complex examination jointly with another examiner need to look for the main examiner. Due to the large number of registered students in PSSAI, I kindly request you to find another main examiner. - In principle, PSSAI will only offer separate partial examinations (Teilprüfungen) this semester. Please follow this link to get the instructions for the examination: https://iccl.inf.tu-dresden.de/w/images/c/c0/Examination.pdf

Problem solving and search is a central topic in Artificial Intelligence. This course presents several techniques to solve in general difficult problems. The course covers the following '''topics''': *Basic Concepts *Uninformed vs Informed Search *Local Search, Stochastic Hill Climbing, Simulated Annealing *Tabu Search *Answer Set Programming *Constraint Satisfaction *Evolutionary Algorithms, Genetic Algorithms *Structural Decomposition Techniques (Tree/Hypertree Decompositions) The course does not cover topics in the area of Machine Learning and Neural Networks. NOTE: This course was previously named Problem Solving and Search in Artificial Intelligence. The contents of former PSSAI and APSS are identical, and therefore students can only take one of the two courses. ===Learning Outcomes=== *The students should identify why typical AI problems are difficult to solve *The students will analyze different algorithms and methods for AI problems and identify when their application is appropriate *The connections between the (graph) structure and the complexity of a problem should become clear, as well as which methods can be used to tackle the problem *In the tutorials, the students will analyze different problems and develop solutions for them. ===Prerequisites=== *Basic knowledge of theoretical computer science and Logic. *Good English skills: both the teaching and examination will be exclusively in English. ===Organisation=== The goals can be acquired by studying the lecture material and solving the exercises of the tutorials. The lectures will be held on Mondays DS1 (07.30 - 09.00 am) and the tutorials on Mondays DS2 (09.20 - 10.50 am). Please check the schedule for changes. The lectures will consist of videos and other materials that will be uploaded online. The tutorials will be online live sessions via BigBlueButton (no recordings of these sessions will be uploaded). The slides of the lectures and exercises of the tutorials will be uploaded in OPAL, for each corresponding session. The lecture videos will also be uploaded in OPAL and I invite you to use the forum to ask questions and share your exercise solutions. Please, register for the course on the OPAL site: https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/32014761984/CourseNode/101501861298687

Problem solving and search is a central topic in Artificial Intelligence. This course presents several techniques to solve in general difficult problems. The course covers the following '''topics''': *Basic Concepts *Uninformed vs Informed Search *Local Search, Stochastic Hill Climbing, Simulated Annealing *Tabu Search *Answer Set Programming *Constraint Satisfaction *Evolutionary Algorithms, Genetic Algorithms *Structural Decomposition Techniques (Tree/Hypertree Decompositions) The course does not cover topics in the area of Machine Learning and Neural Networks. NOTE: This course was previously named Problem Solving and Search in Artificial Intelligence. The contents of former PSSAI and APSS are identical, and therefore students can only take one of the two courses. ===Learning Outcomes=== *The students should identify why typical AI problems are difficult to solve *The students will analyze different algorithms and methods for AI problems and identify when their application is appropriate *The connections between the (graph) structure and the complexity of a problem should become clear, as well as which methods can be used to tackle the problem *In the tutorials, the students will analyze different problems and develop solutions for them. ===Prerequisites=== *Basic knowledge of theoretical computer science and Logic. *Good English skills: both the teaching and examination will be exclusively in English. ===Organisation=== The goals can be acquired by studying the lecture material and solving the exercises of the tutorials. The lectures will be held asynchronously. The lectures will consist of videos and other materials that will be uploaded online. The tutorials will be offered on-site on Mondays DS2 and DS3, and as online live sessions via BigBlueButton on Mondays DS2 (link: https://bbb.tu-dresden.de/b/luc-ao0-hnh-0wo ; no recordings of these sessions will be uploaded). The slides of the lectures and exercises of the tutorials will be uploaded in OPAL, for each corresponding session. The lecture videos will also be uploaded in OPAL and I invite you to use the forum to ask questions and share your exercise solutions. Please, register for the course on the OPAL site: https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/34558738433/CourseNode/101501861298687

Problem solving and search is a central topic in Artificial Intelligence. This course presents several techniques to solve in general difficult problems. The course covers the following '''topics''': *Basic Concepts *Uninformed vs Informed Search *Local Search, Stochastic Hill Climbing, Simulated Annealing *Tabu Search *Constraint Satisfaction Problems *Evolutionary Algorithms, Genetic Algorithms *Answer Set Programming *Structural Decomposition Techniques (Tree/Hypertree Decompositions) The course does not cover topics in the area of Machine Learning and Neural Networks. NOTE: This course was previously named Problem Solving and Search in Artificial Intelligence. The contents of former PSSAI and APSS are identical, and therefore students can only take one of the two courses. ===Learning Outcomes=== *The students should identify why typical AI problems are difficult to solve *The students will analyze different algorithms and methods for AI problems and identify when their application is appropriate *The connections between the (graph) structure and the complexity of a problem should become clear, as well as which methods can be used to tackle the problem *In the tutorials, the students will analyze different problems and develop solutions for them. ===Prerequisites=== *Basic knowledge of theoretical computer science and Logic. *Good English skills: both the teaching and examination will be exclusively in English. ===Organisation=== The goals can be acquired by studying the lecture material and solving the exercises of the tutorials. The slides of the lectures and exercises of the tutorials will be uploaded in OPAL, for each corresponding session. We invite you to use the forum to ask questions and share your exercise solutions. Please, register for the course on the OPAL site: https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/36566368264/ +

Problem solving and search is a central topic in Artificial Intelligence. This course presents several techniques to solve in general difficult problems. The course covers the following '''topics''': *Basic Concepts *Uninformed vs Informed Search *Local Search, Stochastic Hill Climbing, Simulated Annealing *Tabu Search *Constraint Satisfaction Problems *Evolutionary Algorithms, Genetic Algorithms *Answer Set Programming *Structural Decomposition Techniques (Tree/Hypertree Decompositions) The course does not cover topics in the area of Machine Learning and Neural Networks. NOTE: This course was previously named Problem Solving and Search in Artificial Intelligence. The contents of former PSSAI and APSS are identical, and therefore students can only take one of the two courses. ===Learning Outcomes=== *The students should identify why typical AI problems are difficult to solve *The students will analyze different algorithms and methods for AI problems and identify when their application is appropriate *The connections between the (graph) structure and the complexity of a problem should become clear, as well as which methods can be used to tackle the problem *In the tutorials, the students will analyze different problems and develop solutions for them. ===Prerequisites=== *Basic knowledge of theoretical computer science and Logic. *Good English skills: both the teaching and examination will be exclusively in English. ===Organisation=== The goals can be acquired by studying the lecture material and solving the exercises of the tutorials. The slides of the lectures and exercises of the tutorials will be uploaded in OPAL, for each corresponding session. We invite you to use the forum to ask questions and share your exercise solutions. Please, register for the course on the OPAL site: https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/39148716041 ===Exam=== Key information: There are two forms of examination: Students of the CMS master and exchange students: *The written exam will take place on the 28th of July, 2023 at the TU Dresden campus. There is no possibility to take the exam remotely. *You must register in Selma or with your examination office. In the future, you will also need to register on the OpalExam platform. A link will be provided for this. Students with complex examinations: *Please, schedule your oral exams with Ramona Behling (ramona.behling@tu-dresden.de).

Advanced Topics in Complexity Theory +

Problem solving and search is a central topic in Artificial Intelligence. This course presents several techniques to solve in general difficult problems. The course covers the following '''topics''': *Basic Concepts *Uninformed vs Informed Search *Local Search, Stochastic Hill Climbing, Simulated Annealing *Tabu Search *Constraint Satisfaction Problems *Evolutionary Algorithms, Genetic Algorithms *Answer Set Programming *Structural Decomposition Techniques (Tree/Hypertree Decompositions) The course does not cover topics in the area of Machine Learning and Neural Networks. NOTE: This course was previously named Problem Solving and Search in Artificial Intelligence. The contents of former PSSAI and APSS are identical, and therefore students can only take one of the two courses. ===Learning Outcomes=== *The students should identify why typical AI problems are difficult to solve *The students will analyze different algorithms and methods for AI problems and identify when their application is appropriate *The connections between the (graph) structure and the complexity of a problem should become clear, as well as which methods can be used to tackle the problem *In the tutorials, the students will analyze different problems and develop solutions for them. ===Prerequisites=== *Basic knowledge of theoretical computer science and Logic. *Good English skills: teaching will be exclusively in English. ===Organisation=== The goals can be acquired by studying the lecture material and solving the exercises of the tutorials. The slides of the lectures and exercises of the tutorials will be uploaded in OPAL, for each corresponding session. We invite you to use the forum to ask questions and share your exercise solutions. Please, register for the course on the OPAL site: https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/41672212497 ===Exam=== Key information: There are two forms of examination: Students of the CMS master and exchange students: *There will be a written exam. Dates and information will follow during the semeser. There is no possibility to take the exam remotely. *You must register in Selma or with your examination office. Students with complex examinations: *Please, schedule your oral exams with Ramona Behling (ramona.behling@tu-dresden.de).

==Overview== This lecture discusses some advanced topics of complexity theory. Currently planned topics are * Approximation Complexity * Interactive Proof Systems * Counting Complexity The course will be self-contained, but some prior knowledge about the fundamental notions of complexity theory is required. Additional prerequisites will be discussed in the exercises. ==Details== ===Approximation Complexity=== Computational complexity tries to assess the complexity of solving problems. Usually, those problems are represented as ''decision problems''. However, for practical applications, it is often more convenient to consider ''optimization problems,'' where solutions are sought that minimize or maximize a certain objective function. Clearly, solving optimization problems is not easier than solving the corresponding decision problem. On the other hand, for optimization problems we can ask for ''approximate'' solutions whose value is within a certain range of the optimal value. This gives rise to the rich field of ''Approximation Algorithms''. In this lecture, we shall introduce the basic notions of approximation algorithms and discuss some classical examples. Intuitively, approximating the solution of a problem "could" be easier than solving the real problem. However, it has been shown that for some problems computing an approximate solution within a certain bound of the optimal value is NP-hard. While this can be shown for some problems directly, a much deeper result is needed to show this for a wide range of problems. This result is the famous ''PCP-Theorem'' stating a characterization of NP in terms of probabilistically checkable proofs with. We shall state this theorem and show how it relates to the hardness of approximation of certain problems. ===Interactive Proof Systems=== Among the many possible definitions of the complexity class NP, the following characterization based on ''computation by interaction'' is one of the most interesting: a language L is in NP if and only if there exist a ''prover'' P and a polynomial-time ''verifier'' V such that * if x ∈ L, then P can send a ''proof'' to V of polynomial length that V will accept, and * if x ∈ L, then whatever proof of polynomial length P sends to V, it will be rejected. This definition gives inspiration to new complexity classes based on ''computation by interaction'', such as ''interactive proof systems'' (IP), ''Merlin-Arthur protocols'' (MA and AM), and ''Multiprover interactive protocols'' (MIP). In those protocols, the prover always has unrestricted computation power (Merlin), while the verifier does not (Arthur). However, the verifier is allowed to be correct with high probability (i.e., in BPP). It is interesting to see how this approach allows to view computation in a new and fruitful way: the developments in interactive protocols finally lead to the discovery of the PCP Theorem. In this part of the lecture, we shall investigate the power of these alternative approaches to computation. We shall see that some famous problems can be characterized nicely using interactive proofs systems. In addition, we shall show that IP = PSpace, and we also shall discuss MIP = NExpTime. Finally, if time permits, we shall also investigate the connection between interactive protocols and cryptography, in particular ''zero knowledge proofs''. ===Counting Complexity=== Sometimes knowing whether a solution exists or not is not sufficient. Instead, one may be interested in the exact ''number of solution'' a problem has. This is for example the case if one wants to estimate probabilities by random sampling. In complexity theory, this is formalized by the notion of ''counting problems''. The corresponding class #P contains problems like #SAT and #CYCLE, which ask for the number of satisfying assignments or for the number of cycles in a directed graph, respectively. It is clear that when we can solve the counting version of a problem, we can also solve it decision variant. However, the converse does not seem to be true: while we can decide in polynomial time whether a directed graph has a cycle, it is true that if we can solve #CYCLE in polynomial time, then P = NP. In this part of the lecture, we shall investigate counting problems in more detail. We shall see that there are natural connections to randomized complexity classes like PP. We shall discuss the notion of #P-complete problems, and shall show that (not surprisingly) #SAT of one of those problems. In addition, we shall also prove Valiant's Theorem that computing the permanent of a 0-1 matrix is also #P-complete. Finally, we shall discuss the proof (maybe not in detail) of Toda's Theorem that every problem in the polynomial hierarchy can be solved in polynomial time with access to an oracle for #SAT.

Algorithmic Game Theory +

=== Exam Inspection Session === On Monday, the 28th of August, at 14:00h in room 2040 we organize an exam inspection session open to everyone who took the exam. There you will have the chance to review the exam problems and your given answers. === General Introduction === Game Theory is a multi-disciplinary and pervasive field that is concerned with how strategic decision making can be formally modelled and analysed. In this course, we will approach the subject from a computer science perspective and also address how game theory can be approached computationally, e.g. consider how computers can be programmed to play games, or analyse the computational complexity of various game-theoretic notions. === Dates and times === The lecture takes place ''in a hybrid fashion'' on Mondays, DS3, in APB E005 (where seats will be available on a first-come, first-serve basis) and via [https://tu-dresden.zoom.us/j/69584540329?pwd=dUlkSVdDclJzV05FMUtWK2ZlYWZSUT09 Zoom]. Similarly, the exercise sessions take place on Mondays, DS6, in APB E005, and can be accessed virtually via [https://bbb.tu-dresden.de/b/jon-d1i-tuf-xo7 BigBlueButton]. The online-whiteboard used during the exercise sessions can be accessed via [https://miro.com/app/board/uXjVMUK3QQI=/?share_link_id=435028256828 Miro]. Keep in mind that the notes on the whiteboard are not necessarily complete and do not serve as sample solutions. === Topics === * Noncooperative games in normal form * Noncooperative games in extensive form * Search in game trees * Games with missing information * Evolutionary game theory * The Game Description Language and General Game Playing * Cooperative Games === Exam === For CMS students and students wishing to use this course for modules INF-B-510 or INF-B-520, there will be a written exam (60min), on 27th July at 07:30hrs in [https://navigator.tu-dresden.de/etplan/bar/01/raum/141901.0020 BAR/SCHÖ/E]. For anyone else (INF-VERT-2/6, INF-BAS-2/6, INF-PM-FOR, IST) the exam will be oral. To obtain an exam slot, please contact Ms. Ramona Behling.

Algorithmic Game Theory +

Game Theory is a multi-disciplinary and pervasive field that is concerned with how strategic decision making can be formally modelled and mathematically analysed. In this course, we will approach the subject from a computer science perspective and -- in addition to covering the foundational aspects -- also address how game theory can be approached computationally, e.g. consider how computers can be programmed to play games, or analyse the computational complexity of various game-theoretic notions. === Dates and times === The lecture takes place as follows: * Mondays, DS3, [https://navigator.tu-dresden.de/raum/145803.0980 SCH/A316]. Exercise sessions are offered at the following times: * Tuesdays, DS6, APB/E006 * Thursdays, DS4, APB/E005 * Thursdays, DS5, APB/E006 Exercises start in the week of the first lecture, i.e. on 16th/18th April. === Topics === * Noncooperative games in normal form * Noncooperative games in extensive form * Search in game trees * Games with missing information * Evolutionary game theory * The Game Description Language and General Game Playing * Cooperative Games === Exam === For CMS students and students wishing to use this course for modules INF-B-510 or INF-B-520, there will be a written exam (90min). For anyone else (INF-VERT-2/6, INF-BAS-2/6, INF-PM-FOR, IST) the exam will be oral. To obtain an exam slot, please contact Ms. Ramona Behling. +

Automata and Logic +

An advanced course on the interplay between languages, algebraic structures, and logic. See http://lat.inf.tu-dresden.de/teaching/ss2015/AL/ +

Automata and Logic +

See https://tu-dresden.de/ing/informatik/thi/lat/studium/lehrveranstaltungen/wintersemester-2018-2019/automata-and-logic +

Automata and Logic +

This course considers finite automata that work on finite or infinite words and trees. The course concentrates on the connection between these automata and logics that play an important role in computer science, such as first-order logic, monadic second-order logic, and propositional dynamic logic; in particular, it will be shown how closure and decidability results for the automata can be used to obtain decidability results for these logics. More information can be found [https://tu-dresden.de/ing/informatik/thi/lat/studium/lehrveranstaltungen/wintersemester-2020-2021/automata-and-logic here]. +

C

This course covers the fundamental concepts as well as advanced topics of complexity theory. Key topics are: * '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration * '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic * '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems * '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL * '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem * '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy * '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem) * '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem ===Legacy=== The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course. +

This course covers the fundamental concepts as well as advanced topics of complexity theory. Key topics are: * '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration * '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic * '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems * '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL * '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem * '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy * '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem) * '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem * '''Quantum Computing:''' Quantum circuits, BQP, some basic results ===Acknowledgements=== The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course. Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden. ===Schedule and Location=== All dates are published on this page (see ''Dates & Materials'' above) * The weekly lecture sessions will take place on Tuesdays DS3 (11:10 to 12:40), and Wednesdays DS6 (16:40 to 18:10). * The weekly exercise session will take place on Tuesdays DS5 (14:50 to 16:20). ::The first exercise will take place in the second week, i.e., on 17 Oct 2017 * All sessions will take place in room APB/E005. * '''Important:''' There will be no lectures or exercises in the third week (24th and 25th Oct 2017)

This course covers the fundamental concepts as well as advanced topics of complexity theory. Key topics are: * '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration * '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic * '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems * '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL * '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem * '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy * '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem) * '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem * '''Quantum Computing:''' Quantum circuits, BQP, some basic results ===Acknowledgements=== The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course. Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden. ===Schedule and Location=== All dates will be published on this page (see ''Dates & Materials'' above) * The weekly lecture sessions will take place on Mondays DS2 (9.20 - 10.50) and Tuesdays DS2 (9.20 - 10.50). * The weekly exercise session will take place on Wednesdays DS3 (11.10 - 12.40). * Monday lecture sessions will take place in room APB/E008. All other lecture and exercise sessions will take place in room APB/E005. * '''Important:''' There will be neither lectures nor exercises on the first week of the semester. Therefore, the first lecture of this course will be on Monday, 15th of October.