Menü
Positionsanzeige
Inhalt

[ INBIPVOBEKO ] VL Computability and Complexity
Versionsauswahl
Es ist eine neuere Version 2021W dieser LV im Curriculum Master's programme Artificial Intelligence 2023W 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 2021S
Objectives The goal of this course is the communication of the basics of theoretical computer science (computability theory and complexity theory). Students learn the essential models of computability and their relationships and can formulate problem solutions in these models. They realize that there are limits of computability and can recognize not computable functions and 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). Finally students can apply the basic techniques of practical complexity analysis to 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 at the end of the semester.
Methods Slide-based presentation with blackboard examples.
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
Further information https://risc.jku.at/courses/
Corresponding lecture (*)INBPCVOFOG2: VO Formale Grundlagen 2 (3 ECTS)
On-site course
Maximum number of participants -
Assignment procedure Direct assignment