Attribut:Beschreibung
Aus International Center for Computational Logic
C
This course offers advanced topics in the field of verification and model checking. It is meant for students enrolled in the Master's program “Computational Modeling and Simulation”. The tasks are usually taken from our current projects and cover programming and theoretical problems as well.
This course is in English.
=== Registration ===
Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/48422027280 via Opal] is required until April 14.
=== Prerequisites ===
* Profound knowledge in model checking, acquired in the lecture “Model Checking” or similar courses at other universities
* Solid foundations in algorithms and data structures, in automata theory and formal languages as well as in complexity theory
* Basic mathematical foundations
* Programming skills in Java or C/C++ are beneficial, unless you are interested in a purely theoretical topic
=== Dates ===
All enrolled participants will be notified about the initital meeting by e-mail.
=== Exam and Creditability ===
'''Master Computational Modeling and Simulation'''
* [http://studies.inf.tu-dresden.de/modforms/index.php?r=modules/view&id=CMS-PRO CMS-PRO]: exam according to module description
=== Contact ===
In case of organisational questions, please contact [[Sascha Klüppelholz]]. +
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.
== Oral Examinations (News!!!) ==
In '''Summer 2023''', we offer two days for oral examinations: '''July 17''' and '''July 28'''.
== 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 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.
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) in [[APB E008]] and Tuesdays DS2 (9.20 - 10.50) in [[APB E005]].
* The weekly exercise session will take place on Wednesdays DS3 (11.10 - 12.40) in [[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].
== Announcements ==
* Regarding the oral examinations, please register with your respective examination offices and, afterward, make an appointment with [[Kati Domann]].
== 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 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.
Most of the materials will be freely available world-wide.
===Contact===
Besides the regular meetings in the lectur(Habs heute auch nochmal in der Übung erwähnt.)

es 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) in [[REC C118]] (Recknagelbau C118, Haeckelstraße 3) and Tuesdays DS2 (9.20 - 10.50) in [[APB E005]].
* The weekly exercise session will take place on '''Wednesdays DS3 (11.10 - 12.40)''' in [[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].
== News ==
* if you want to take an exam this semester, please register with your examination office (presumably done though [https://selma.tu-dresden.de/ Selma])
* the preferred, yet not guaranteed, examination date is '''10th February 2025''' and '''14th February 2025'''; please contact [[Kati Domann]] for scheduling a date and time
== 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 course generally does not require a special registration and there is no participant limit. However, students in programmes that use the Selma system (esp. students in CMS Master) will need to register there to obtain credits.
Most of the materials will be freely available worldwide.
===Examination Dates and Mode===
The registration and scheduling for exams depend on the module they are for. All students need to contact the [[Wissensbasierte_Systeme/en|KBS secretary]] to arrange time slots for their oral exams, or the secretary of another chair in the case of another main examiner. The preferred dates for oral exams are '''10th February 2025''' and '''14th February 2025'''. Although we cannot generally accommodate wishes for specific dates, students with justified time constraints during the examination period can still let us know as early as possible.
Students taking Complexity Theory as part of any '''other module''' should contact the secretary of the main examiner to find a date. If the main examiner is Markus Krötzsch, the preferred date will also be '''10th February 2025''' and '''14th February 2025'''.
===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===
This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS2 (9.20 - 10.50) in [[APB E009]] and Tuesdays DS2 (9.20 - 10.50) in [[APB E005]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[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].
Modern computer systems are often multi-threaded or even fully distributed over several machines and geographical locations. Instead of the well-known sequential computational models (e.g., Turing machines, λ-calculus, etc.), the key notion for describing concurrent computations is that of a ***process***. In this course, we study several phenomena occurring in concurrent computations by means of process calculi, for which we will define and analyze their formal semantics. As one of the key aspects, we ask when two processes are considered to be equivalent. +
=== News ===
* Oral exams are offered on '''July 19, 2023''' and '''August 7, 2023'''. Please contact [mailto:secretary_wbs@mailbox.tu-dresden.de Kati Domann] to arrange an appointment.
* Our first lecture on '''April 4, 2023 at 1pm''' takes place in room APB 3027 (3rd floor of APB).
=== Course Description ===
Modern computer systems are often multi-threaded or even fully distributed over several machines and geographical locations. Instead of the well-known sequential computational models (e.g., Turing machines, λ-calculus, etc.), the key notion for describing concurrent computations is that of a ''process''. In this course, we study several phenomena occurring in concurrent computations by means of process calculi, for which we will define and analyze their formal semantics. As one of the key aspects, we ask when two processes are considered to be equivalent. Subsequently, we give an (incomplete) list of topics we strive for throughout the course.
* From sequential to parallel processes (LTS, CCS)
* Bisimulation and Coinduction
* From sequential to concurrent processes (Petri nets)
* Mobile processes (the π-calculus)
* Expressive power of process calculi
* Data-Aware Processes
=== Contact ===
If you have questions regarding the course, feel free to ask in the matrix chat or via email to the teacher of the course.
=== Schedule and Location ===
The course is taught in two sessions per week, one on '''Tuesdays DS4 (13.00-14.30)''' and '''Wednesdays DS3 (11.10-12.40)'''. We're currently planning the course sessions as on-site events. If necessary, we can retract to an Online mode, probably using BigBlueButton. Exercises are intertwined with the lecture.
=== Acknowledgments ===
The first part of the lecture is based on the exposition '''Introduction to Bisimulation and Coinduction''' by Davide Sangiorgi. The [http://www.cs.unibo.it/~sangio/BisCoindBOOKS/slides.html slides] Davide provides were an inspiration for the lecture material. The slides titled ''Part II'' have been used in the lectures on coinduction.
=== News ===
* On '''July 31st''' and '''August 6th''', I offer slots for your oral examinations. Please contact our secretary, [[Kati Domann]], to get your date and time slot. If you're looking for a complex exam (with more than one examiner), these dates are generally not applicable since all examiners must be available. In that case, you must still request an examination date.
=== Course Description ===
Modern computer systems are often multi-threaded or even fully distributed over several machines and geographical locations. Instead of the well-known sequential computational models (e.g., Turing machines, λ-calculus, etc.), the key notion for describing concurrent computations is that of a ''process''. In this course, we study several phenomena occurring in concurrent computations using process calculi, for which we will define and analyze their formal semantics. As one of the key aspects, we ask when two processes are considered to be equivalent. Subsequently, we give an (incomplete) list of topics we strive for throughout the course.
* From sequential to parallel processes (LTS, CCS)
* Bisimulation and Coinduction
* From sequential to concurrent processes (Petri nets)
* Mobile processes (the π-calculus)
* Expressive power of process calculi
* Data-Aware Processes
=== Contact ===
If you have questions regarding the course, feel free to ask in the matrix chat or via email to the teacher of the course.
=== Schedule and Location ===
The course is taught in two sessions per week, one on '''Tuesdays DS2 (9.20-10.50)''' and '''Wednesdays DS3 (11.10-12.40)'''. All the sessions take place in [[APB E005]]. We're currently planning the course sessions as on-site events. If necessary, we can retract to an Online mode, probably using Zoom. Exercises are intertwined with the lecture.
=== Acknowledgments ===
The first part of the lecture is based on the exposition '''Introduction to Bisimulation and Coinduction''' by Davide Sangiorgi. The [http://www.cs.unibo.it/~sangio/BisCoindBOOKS/slides.html slides] Davide provides were an inspiration for the lecture material. The slides titled ''Part II'' have previously been used in lectures on coinduction.
=== Course Description ===
Modern computer systems are often multi-threaded or even fully distributed over several machines and geographic locations. Instead of computation (e.g., in Turing machines, λ-calculus, etc.), the key notion for describing concurrent computations is ''interaction'' leading to the concept of ''processes''. In this course, we study several phenomena occurring in concurrent computations using process calculi, for which we will define and analyze their formal semantics. As one of the key aspects, we ask when two processes are considered to be equivalent. Subsequently, we give an (incomplete) list of topics we strive for throughout the course.
* From sequential to parallel processes (LTS, CCS)
* Bisimulation and Coinduction
* From sequential to concurrent processes (Petri nets)
* Mobile processes (the π-calculus)
* Expressive power of process calculi
* Data-Aware Processes
=== Contact ===
If you have questions about the course, feel free to ask in the matrix chat or email the teacher(s).
=== Schedule and Location ===
The course is taught in two sessions per week,
* weekly lecture sessions will happen on '''Mondays DS4 (13.00-14.30)'''
* weekly exercise sessions happen on '''Tuesdays DS3 (11.10-12.40)'''.
All the sessions take place in [[APB E005]]. We're currently planning the course sessions as on-site events. If necessary, we can retract to an Online mode, probably using Zoom. +
===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.
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 data model, 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
* query answering under database dependencies
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.
===Schedule and Location===
UPDATE: All the three lectures on the 19th of June will take place in room APB 1004.
* The weekly lecture sessions will take place on Tuesdays DS2 (9:20 to 10:50) and DS3 (11:10 to 12:40).
* The weekly exercise session will take place on Tuesdays DS5 (14:50 to 16:20).
* The first exercise session will take place in the second week, i.e., on 17 April 2017.
* All sessions will take place in room APB/E005 except for the lectures on the 19th of June, which will take place in room APB 1004.
===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.
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 data model, 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
* query answering under database dependencies
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.
===Schedule and Location===
All sessions will take place in room APB/E005. The default arrangement is as follows:
* The weekly lecture sessions will take place on Tuesday DS2 (9:20 to 10:50) and Friday DS5 (2:50 to 4:20).
* The weekly exercise session will take place on Wednesday DS3 (11:10 to 12:40).
'''In some weeks, the Wednesday exercises will be swapped with the Friday lectures'''
Exceptions:
* The first exercise session will take place in the second week on 12 April 2019.
* There will NOT be a lecture on the 5th of April.
===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]] and the 2018 lecture [[Database_Theory_(SS2018)/en|Database Theory]]. 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.
<b>Announcement:</b> because of the COVID-19 pandemic, the schedule and location of this lecture have changed quite a bit. For more information have a look at the corresponding section below.
===Course Description===
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 data model, 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
* query answering under database dependencies
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===
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.
===Schedule and Location===
Because of the ongoing COVID-19 pandemic, we have decided to transform this lecture into an online course. If the university reopens later on during the semester, we will probably revert to a standard, in-person lecture. For now, we will be doing the following:
<ul>
<li> Every week on Tuesday, we will publish two videos with the weekly lectures. </li>
<li> Every week on Monday, we will post one video with the weekly exercises. </li>
<li> The videos with the lectures and exercises will be posted on this webpage under the "Dates and Materials" tab. </li>
<li> Every week, we will host a "live session" in which the students can ask us questions. This session, which will take place on Wednesdays from 11:10 to 12:40, can be joined using this [https://selfservice.zih.tu-dresden.de/l/link.php?meeting_id=9342&pin=5340315e link] (if you cannot access the chatroom, do send us an email). </li>
<li> We have set up an [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/23201546268/CourseNode/101474205796011 online forum] using Opal in which the students can post questions and discuss topics related to this course.</li>
<li> Note that we will neither post an exercise video nor host a "live session" in the first week of the semester. That is, we will only post two videos with the weekly lectures in the first week. </li>
</ul>
When the university reopens, we will follow this schedule:
* The weekly lecture sessions will take place on Tuesdays from 14:50 to 16:20 and Wednesdays from 11:10 to 12:40.
* The weekly exercise session will take place on Tuesdays from 11:10 to 12:40.
All sessions will take place in room APB/E005.
===Legacy===
This course has first been taught at TU Dresden by Prof. Dr. [[Markus Krötzsch]] in the form of the 2015 lecture [[Foundations_of_Databases_and_Query_Languages_(SS2015)/en|Foundations of Databases and Query Languages]], the 2018 lecture [[Database_Theory_(SS2018)/en|Database Theory]], and the 2019 lecture [[Database_Theory_(SS2019)/en|Database Theory]]. The plan for this year's course will be somewhat 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.
