1. SylabUZ
2. Faculty of Computer Science, Electrical Engineering and Automatics
3. winter term 2021/2022
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 theoretical terms of computer science, like algorithm, formal languages, context-free grammar, deterministic and non-deterministic finite automata,
• learning basic skills in assigning of complexity class of algorithms, proof of algorithms halting problem and partial correctness
• familiarize students with Church-Turing thesis, easy and hard problems as well as NP, NP-complex and NP-hard problems,
• familiarize students with basic terms of parallel algorithms theory.

Prerequisites

Save changes

Algorithms and data structures, Computational logic, Foundations of discrete systems, Mathematical analysis.

Scope

Introduction: algorithm and its properties, asymptotic notation.

Algorithmic correctness: correct algorithm, partial correctness, semantic correctness, halting problem.

Foundations of automata theory and languages: finite automata and regular expressions, context-free grammars, automata with stack and context-free languages.

Simple algorithmic models:. Church-Turing thesis, Turing machine and its variants. Random access machine. Counting programms.

Algorithmic complexity: Time and space complexity of algorithms, pessimistic and average complexity. Top and bottom limit of complexity, natural complexity. Open and close algorithmic problems, algorithmic wound.

Algorithmic problems classification: easy and hard problems, logarithmic, polynomial, NP, NP-complez and expotential problems. Decidability and undecidability.

Parallel and probabilistic algorithms. Produkt complexity, nets. Thesis about parallel calculations. Nick class. RNC algoriithms..

 

Teaching methods

Lecture: traditional lecture.

Exercises: accounting exercises

 

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Lecture  - to pass written exam.

Exercises - to pass two written tests

 

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. Ben Ari M.: Logika matematyczna w informatyce, WNT, Warszawa, 2005
2. Graham R.L., Knuth D.E., Patashnik O.: Matematyka konkretna, PWN, Warszawa, 2002
3. Papadimitriou C. H.: Złożoność obliczeniowa, Helion, Gliwice, 2012
4. Ross K. A., Wright C. R. B.: Matematyka dyskretna, PWN, Warszawa, 2000
5. Wróblewski P.: Algorytmy, struktury danych i języki programowania, Helion, Gliwice, 1997

Notes

Modified by prof. dr hab. inż. Andrzej Obuchowicz (last modification: 14-07-2021 11:42)