# Attribut:Beschreibung

Aus International Center for Computational Logic

A

===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. +

<span style="color:red;">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.</span>
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.
<b>Announcement:</b> 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

==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.

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

See https://tu-dresden.de/ing/informatik/thi/lat/studium/lehrveranstaltungen/wintersemester-2018-2019/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.

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.
* <b>Important:</b> as indicated in the class calendar below, the lecture sessions start on the 15th of October. Furthermore, there will be no exercise sessions on the 6th, 13th, and 20th of November.

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 +

== Oral Examinations (News!!!) ==
In '''Summer 2022''', we offer <s>two days</s> one day for oral examinations: <s>'''July 21'''</s> (fully booked) and '''August 2'''.
== Contents ==
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
===Mode of Teaching and Registration===
The sessions are taught in presence, using a large enough room at TU Dresden. Starting from 22 Nov 2022, the lecture is also streamed live via Zoom, so that students can join while in Covid quarantine or if unable to attend due to the general pandemic situation. The link can be found in Opal under "Links" (see below) and can also be found (or requested anew) in the Matrix chat group.
The course generally does not require a special registration and there is no limit for participants. However, students in programmes that use the Selma system (esp. students in CMS Master) will need to register there to obtain credits. Additionally, we kindly ask you to enroll in the '''[https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/32320454689 OPAL course]''' so we can contact you, should the need arise.
Most of the materials will be freely available world-wide.
===Contact===
Besides the regular meetings in the lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.
===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).
* '''All lecture and exercise sessions''' will take place in room APB/E005.
* '''Important:''' Stay informed about [https://tu-dresden.de/tu-dresden/gesundheitsmanagement/information-regarding-covid-19-coronavirus-sars-cov-2/tud-corona-ticker# current covid-19 regulations of TU Dresden]. In particular, participants need to provide a certificate of vaccination or recovery, or a current negative test.

===Description ===
This is a reading group and we will discuss the book '''Conditional Reasoning''' by Raymond Nickerson.
An electronic version of the book is accessible
via the university network [http://www.oxfordscholarship.com/view/10.1093/acprof:oso/9780190202996.001.0001/acprof-9780190202996 here] or [https://katalogbeta.slub-dresden.de/id/0020753017/#detail here].
===Schedule ===
* the reading group will take place in room APB2008
* the reading group will take place on Wednesday 3.DS (11:10 - 12:40) and Thursday, 4.DS (13:00 - 14:30)
===Material===
* The dissertation on mechanical turk can be found [http://www.l3s.de/~gadiraju/Ujwal-PhdThesis.pdf here].
* The book on human reasoning by Keith Stenning and Michel van Lambalgen can be found [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.3539&rep=rep1&type=pdf here]. Chapter 3 is on the selection task including explanations for the choices given by participants. +

==Various Courses KRR Group==
For details on courses from knowledge representation and reasoning group, we refer to OPAL.
Find the courses at:
Denken als Berechnung
https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/26275741716/CourseNode/101413612795102?50
Human Reasoning and the Weak Completion Semantics
https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/26275741715/CourseNode/101413612795102?51
Logic and Science of Computational Logic Repetition
https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/26275741714/CourseNode/101413612795102?52
Knowledge Representation and Reasoning Seminar
https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/26275741713/CourseNode/101419626293623?53 +

D

Databases are a key technology in computer science that brings together fascinating theoretical topics and highly relevant practical applications. The goal of this lecture is to give an extended introduction to this interesting field, with a special focus on database query languages, their expressive power, and computational complexity. The lecture will introduce the relational datamodel, and then discuss theoretical and practical aspects of a variety of query languages:
* first-order logic as a query language and the relational algebra
* conjunctive queries and their unions
* navigational queries: path queries
* Datalog and its relatives
The lecture focuses on core principles that apply to many types of databases alike (relational, graph-based, semantic web). Some important query answering algorithms are presented, too, but otherwise the details of database implementation and administration are not covered.
===Prerequisites===
An undergraduate-level knowledge of predicate logic, regular languages, and algorithmic and computational complexity is required. The lecture will connect with other topics in the Computer Science and Computational Logic curriculum, such as relational databases, logic programming, and Semantic Web technologies – familiarity with these topics is not required to follow the lecture.
===Time plan===
The general time plan is as follows:
* Lectures: each Thursday in DS4 (13:00–14:30)
* Exercises: each Monday in DS3 (11:10–12:40)
However, there will be some exceptions that will be announced in the lecture:
* The first lecture is on Monday, 04 April 2016.
* '''<span style="color:red">The lecture on Thursday, 9 June, will be in DS3 (from 11:10) in room [[APB 3027/en|APB 3027]], since the afternoon is reserved for OUTPUT.DD 2016.</span>'''
* The lecture on Thursday, 16 June, will be held by [[Sebastian Rudolph/en|Sebastian Rudolph]].
* The exercise session on Monday, 4 July, will be held by [[Tomáš Masopust/en|Tomáš Masopust]].
===Legacy===
This course has first been taught at TU Dresden in the form of the 2015 lecture [[Foundations_of_Databases_and_Query_Languages_(SS2015)/en|Foundations of Databases and Query Languages]]. The plan for this year's course will be very similar.
The structure of some of the lectures of this course is inspired by the course ''Theory of Data and Knowledge Bases'' in the version given by [https://www.cs.ox.ac.uk/people/georg.gottlob/ Georg Gottlob] and [http://www.cs.ox.ac.uk/people/thomas.lukasiewicz/ Thomas Lukasiewicz] at the University of Oxford.