Website
Curriculum

Modul CS4501-KP12, CS4501

Algorithmics, Logic and Computational Complexity (ALK14)

Duration:


2 Semester
Turnus of offer:


each summer semester
Credit points:


12
Course of studies, specific field and terms:
  • Master Entrepreneurship in Digital Technologies 2020 (advanced module), technology field computer science, Arbitrary semester
  • Master Computer Science 2019 (optional subject), advanced module, Arbitrary semester
  • Master IT-Security 2019 (advanced module), Elective Computer Science, 1st or 2nd semester
  • Master Entrepreneurship in Digital Technologies 2014 (advanced module), technology field computer science, 2nd and/or 3rd semester
  • Master Computer Science 2014 (advanced module), advanced curriculum, 2nd and/or 3rd semester
Classes and lectures:
  • Seminar Algorithmics, Logic and Computational Complexity (seminar, 2 SWS)
  • Algorithmics, Logic and Computational Complexity (exercise, 2 SWS)
  • Algorithmics, Logic and Computational Complexity (lecture, 4 SWS)
Workload:
  • 40 Hours work on an individual topic with written and oral presentation
  • 40 Hours exam preparation
  • 160 Hours private studies and exercises
  • 120 Hours in-classroom work
Contents of teaching:
  • recent results in algorithmics and complexity theory
  • communication and circuit complexity
  • structural and descriptive complexity theory
  • algorithmic game theory
  • nonstandard computing models
  • understanding logics as a tool
Qualification-goals/Competencies:
  • the students can demonstrate a deep knowledge of concepts and methods for algorithm design and complexity analysis.
  • They are able to classify algorithmic problems and to select appropriate strategies for their solution
  • They are able to model complex problem settings appropriately.
  • They can assess and explain the importance of lower bounds for applications.
Grading through:
  • Oral examination
Requires:
Responsible for this module:
Teachers:
Literature:
  • R. Reischuk: Einführung in die Komplexitätstheorie - Teubner, 1990
  • S. Arora, B. Barak: Computational Complexity - Cambridge UP 2009
  • C. Papadimitriou: Computational Complexity - Addison-Wesley, 1994
  • M. Huth, M. Ryan: Logic in Computer Science - Cambridge University. Press 2004
  • D. Kozen: Theory of Computation - Springer, 2006
Language:
  • German and English skills required
Notes:

Admission requirements for taking the module:
- None (the competencies under

Letzte Änderung:
14.2.2024