SylabUZ
Nazwa przedmiotu | Theoretical foundations of computer science |
Kod przedmiotu | 11.3-WE-INFP-TFCS-Er |
Wydział | Wydział Informatyki, Elektrotechniki i Automatyki |
Kierunek | WIEiA - oferta ERASMUS / Informatyka |
Profil | - |
Rodzaj studiów | Program Erasmus pierwszego stopnia |
Semestr rozpoczęcia | semestr zimowy 2018/2019 |
Semestr | 3 |
Liczba punktów ECTS do zdobycia | 6 |
Typ przedmiotu | obowiązkowy |
Język nauczania | angielski |
Sylabus opracował |
|
Forma zajęć | Liczba godzin w semestrze (stacjonarne) | Liczba godzin w tygodniu (stacjonarne) | Liczba godzin w semestrze (niestacjonarne) | Liczba godzin w tygodniu (niestacjonarne) | Forma zaliczenia |
Wykład | 30 | 2 | - | - | Egzamin |
Ćwiczenia | 30 | 2 | - | - | Zaliczenie na ocenę |
Algorithms and data structures, foundation of disdrete systems, mathematical analysis.
Principle informations: algorithm and its properties, asymptotic notations. Algorithm correctness.
Principles of automaton and languages theory: finite automatons and regular terms, context-free gramars, pushdown automaton and context-free languages.
Primitive algorithmic models: Church-Turing thesis and its variants, Turing machine and its variants, random access memory machine, counter machine.
Algorithms effectiveness measures: space and time complexity, pessimistic and average complexity, bottom and upper limit of complexity, natural complexity, algorithmically open and closed problems.
Classification of algorithmic problems: logarihmic, polynomial, NP, NP-complex, NP-hard and expotencial class; open problems connected with algorithmic problems classification; proving of NP complexity; undecidable problems.
Parallel and probabilistic algorithms, stable and expanding parallelism, product complexity. Nets: parallelism with stable connections. Thesis about parallel calculations, Nick class.
Probabilistic algorithms for chosen standard algorithmic problems. probabilistic complexity classes.
Lecture, exercise classes.
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
Lecture – the passing condition is to obtain positive marks from written or oral tests conducted at least once per semester.
Exercice classes – the passing condition is to obtain positive marks from all exercises and tests conducted during the semester.
Calculation of the final grade: lecture 50% + exercice classes 50%
Zmodyfikowane przez prof. dr hab. inż. Andrzej Obuchowicz (ostatnia modyfikacja: 27-03-2018 22:51)