Menü
Positionsanzeige
Inhalt

[ INBIPVOBEKO ] VL Computability and Complexity
Versionsauswahl
Es ist eine neuere Version 2025W dieser LV im Curriculum Master's programme Artificial Intelligence 2025W vorhanden.
(*) Unfortunately this information is not available in english.
Workload Education level Study areas Responsible person Hours per week Coordinating university
3 ECTS B2 - Bachelor's programme 2. year Mathematics Wolfgang Schreiner 2 hpw Johannes Kepler University Linz
Detailed information
Original study plan Bachelor's programme Computer Science 2013W
Objectives The goal of this course is the communication of the basics of theoretical computer science (computability theory and complexity theory). Students shall learn the essential models of computability and their relationships and realize that there are limits of computability (not computable functions, not decidable problems). Furthermore students experience the basic notions of asymptotic complexity and the fundamental classes of problem complexity and learn the limits of feasible computability (NP-complete problems). The course is complemented by a presentation of basic techniques of practical complexity analysis of iterative and recursive algorithms.
Subject Finite automata, nondeterminism and determinization, minimization, regular languages, regular expressions and their conversion from/to finite automata, Turing machines, Random Access Machines, Loop- and While-Programs, primitive and mu-recursive functions, further Turing-complete computability models, the halting problem, problem reduction, further undecidable problems.

Complexity measures, worst-time complexity and average complexity, asymptotic complexity, complexity classes; relationship between different complexity models, problem complexity, NP-complete problems; exemplary complexity analysis of iterative and recursive algorithms, solving of sums and recurrences, analysis of randomized programs, amortised analysis.

Criteria for evaluation Written exam.
Methods Classical lecture.
Language (*)Deutsch, bei Bedarf Englisch
Study material
  • Wolfgang Schreiner: "Computability and Complexity" (Lecture Notes).
  • Dirk W. Hoffmann: Theoretische Informatik (in German).
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation.
  • Michael Sipser: Introduction to the Theory of Computation.
  • Thomas H. Cormen et al: Introduction to Algorithms.
Changing subject? No
Corresponding lecture (*)INBPCVOFOG2: VO Formale Grundlagen 2 (3 ECTS)
On-site course
Maximum number of participants -
Assignment procedure Direct assignment