1. SylabUZ
2. Faculty of Computer Science, Electrical Engineering and Automatics
3. winter term 2022/2023
4. Computer Science - First-cycle Erasmus programme
5. Theoretical foundations of computer science

Generate PDF for this page

Theoretical foundations of computer science - course description

Aim of the course

• familiarize students with the basic concepts of theoretical computer science, like algorithm, computational complexity, formal language and grammar, deterministic and nondeterministic finite-state automata.
• gaining basic skills in determining the complexity of algorithms, proving halting property and partial correctness of algorithms.
• intruducing main concepts of automata, languages and computation theory, e.g. Chomsky hierarchy, Church-Turing thesis, P and NP complexity classes.
• familiarize students with parallel computation theory.

Prerequisites

Save changes

Algorithms and Data Structures, Computational Logic, Linear Algebra, Mathematical Analysis.

Scope

Algorithms and their properties: correctness, partial correctness, halting property; proving correctnes and the halting property.

Computational complexity of algorithms (worst and average case complexity). Upper and lower bound on the compexity of an algorithmic problem, inherent complexity and the complexity gap. Determining the complexity of algorithms. Notation for asymptotic growth rates.

Foundations of automata theory, languages and computation: grammars and languages, finite automata, regular languages and regular expressions, context-free grammars and context-free languages, normal forms of grammars, derivation trees, pushdown automata, context-sensitive languages and linear bounded automata, Turing machines and recursively enumerable languages, the Chomsky hierarchy.

Counter automatons and Turing machines. Accepting vs deciding. Time and space complexity. Random access machine. Classes of algorithmic problems: P, NP NP-complete and PSPACE. Proving NP-completeness. Open problems on computational complexity. Limits of computabiliity and decidability. Church-Turing thesis.

Parallel and probabilistic algorithms. Product complexity. Chandra-Stockmeyer parallel computation thesis. Nick's class. RNC algorithms.

 

Teaching methods

Lectures: conventional lectures

Exercises: whiteboard problem solving, presentations, discussions

 

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Lectures:  the passing condition is to obtaing a positive grade from the final exam.

Exercises: the passing condition is to obtain a positive grade from all tests.

Course: it is necesssary to pass both lectures and exercises.

Calculation of the final grade: lecture 50% + exercises 50%

Recommended reading

1. Cormen T. H., Leiserson C. E., Rivest R. L.: Introduction to algorithms, MIT Press, Boston, 1994
2. Aho A. V., Hopcroft J. E., Ullman J.D.: Algorithms and Data Structures, Addison-Wesley Longman Publishing Co., Inc. Boston 1983
3. Dasgupta S., Papadimitriou Ch., Vazirani U.: Algorithms, McGraw-Hill, New York 2008
4. Harel D.: Algorithmics, the Spirit of Computing, Addison-Wesley Publ., Reading, 1987
5. Hopcroft J. E., Ullmann J.D.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publ., Reading, 2003

Further reading

1. Graham R.L., Knuth D.E., Patashnik O.: Matematyka konkretna, PWN, Warszawa, 2002
2. Papadimitriou C. H.: Złożoność obliczeniowa, Helion, Gliwice, 2012
3. Ross K. A., Wright C. R. B.: Matematyka dyskretna, PWN, Warszawa, 2000

Notes

Modified by dr hab. inż. Piotr Borowiecki, prof. UZ (last modification: 21-04-2022 01:01)