University of Warsaw - Central Authentication System
Strona główna

Languages, automata and computations

General data

Course ID: 1000-214bJAO
Erasmus code / ISCED: 11.302 The subject classification code consists of three to five digits, where the first three represent the classification of the discipline according to the Discipline code list applicable to the Socrates/Erasmus program, the fourth (usually 0) - possible further specification of discipline information, the fifth - the degree of subject determined based on the year of study for which the subject is intended. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
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 Basic information on ECTS credits allocation principles:
  • the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS;
  • the student’s weekly hourly workload is 45 h;
  • 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes;
  • weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS;
  • work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load.
view allocation of credits
Language: Polish
Type of course:

obligatory courses
Requirements:

Algorithms and data structures 1000-213bASD
Discrete mathematics 1000-212bMD
Foundations of mathematics 1000-211bPM
Introductory programming 1000-211bWPI
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:

The final grade is determined by the number of points from homework assignments and tests (50%), and the exam (50%).

Classes in period "Summer semester 2024/25" (past)

Time span: 2025-02-17 - 2025-06-08
Selected timetable range:
Go to timetable
Type of class:
Classes, 30 hours more information
Lecture, 30 hours more information
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)
Credit: Examination

Classes in period "Summer semester 2025/26" (future)

Time span: 2026-02-16 - 2026-06-07

Selected timetable range:
Go to timetable
Type of class:
Classes, 30 hours more information
Lecture, 30 hours more information
Coordinators: Sławomir Lasota
Group instructors: Tomasz Gogacz, Jędrzej Kołodziejski, Sławomir Lasota, Marcin Przybyłko, Michał Skrzypczak, Jerzy Tyszkiewicz, Daria Walukiewicz-Chrząszcz
Students list: (inaccessible to you)
Credit: Course - Examination
Lecture - Examination
Course descriptions are protected by copyright.
Copyright by University of Warsaw.
ul. Banacha 2
02-097 Warszawa tel: +48 22 55 44 214 https://www.mimuw.edu.pl/ contact accessibility statement site map USOSweb 7.1.2.0-a1f734a9b (2025-06-25)