Languages, automata and computations
General data
Course ID: | 1000-214bJAO |
Erasmus code / ISCED: |
11.302
|
Course title: | Languages, automata and computations |
Name in Polish: | Języki, automaty i obliczenia |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Obligatory courses for 2nd grade Computer Science Obligatory courses for 2nd grade JSIM (3I+4M) Obligatory courses for 2nd grade JSIM (3M+4I) |
ECTS credit allocation (and other scores): |
5.00
|
Language: | Polish |
Type of course: | obligatory courses |
Requirements: | Algorithms and data structures 1000-213bASD |
Short description: |
Basic computation models (automata, grammars and Turing machines). Chomsky hierarchy. Mathematical description of computability; the limits of computability; and a brief introduction to computational complexity. |
Full description: |
- Elements of formal languages: words, languages, regular expressions. - Finite automata and the Kleene theorem on effective equivalence of finite automata and regular expressions. - Automata optimisation constructions - determinisation, minimalisation. - Context-free languages: grammars and their normal forms. - Equivalence of context-free grammars and nondeterministic pushdown automata. - Necessary conditions for regular and context-free languages: pumping lemmas. - Algorithmic questions: emptiness and membership for automata and grammars. - Example applications of automata and grammars. - Universal computation models: Turing machines and variants. - Limits of computability: undecidability of the halting problem, examples of practical undecidable problems. -Conclusion: classification of grammars and computation models in the Chomsky hierarchy. - Introduction to complexity theory: P and NP. - The Cook-Levin theorem on NP-completeness of SAT. - The P=/=NP conjecture and its practical implications, information on positive applications of hard computational problems, e.g. in cryptography. |
Bibliography: |
1. J. E. Hopcroft, R. Motwani, J. D. Ullman, ntroduction to Automata Theory, Languages, and Computation, Addison Wesley, 2000 2. Ch. Papadimitriou, Computational Complexity, Addison Wesley, 199 |
Learning outcomes: |
(in Polish) Wiedza - absolwent zna i rozumie: - podstawy teorii języków formalnych (języki, wyrażenia regularne, gramatyki) i formalnych modeli obliczeniowych (automaty, automaty ze stosem, maszyny Turinga) (K_W12) Umiejętności - absolwent potrafi: - zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań (K_U01), - pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02), - samodzielnie planować i realizować własne uczenie się przez całe życie (K_U09), - definiować języki formalne z pomocą gramatyk i automatów oraz operować abstrakcyjnymi modelami obliczeń ze szczególnym uwzględnieniem maszyn Turinga (K_U11), Kompetencje społeczne - absolwent jest gotów do: - uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03) |
Assessment methods and assessment criteria: |
* 4 homework problems, 5 pts each. * 8 online tests jointly for 8 pts. * final exam for ~30 pts. * star problems allowing students to get additional points. To be allowed for the first-term exam, at least 14 pts are required (this threshold might be lowered). The final grade in the first term is 1/10 of the sum of all the points (rounded down to 0.5). Second-term final exam will be resulting in a final grade (without any impact from the above score). |
Classes in period "Summer semester 2023/24" (in progress)
Time span: | 2024-02-19 - 2024-06-16 |
Navigate to timetable
MO TU CW
CW
W CW
WYK
TH CW
CW
CW
FR CW
CW
CW
|
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Sławomir Lasota | |
Group instructors: | Tomasz Gogacz, Łukasz Kamiński, Sławomir Lasota, Filip Mazowiecki, Paweł Parys, Michał Skrzypczak, Jerzy Tyszkiewicz, Daria Walukiewicz-Chrząszcz | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Classes in period "Summer semester 2024/25" (future)
Time span: | 2025-02-17 - 2025-06-08 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Sławomir Lasota | |
Group instructors: | Tomasz Gogacz, Łukasz Kamiński, Sławomir Lasota, Paweł Parys, Marcin Przybyłko, Michał Skrzypczak, Jerzy Tyszkiewicz, Daria Walukiewicz-Chrząszcz | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.