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

Languages, automata and computations

General data

Course ID: 1000-214bJAO
Erasmus code / ISCED: 11.302 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (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:

* 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
Selected timetable range:
Navigate 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, 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
Selected timetable range:
Navigate 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)
Examination: Examination
Course descriptions are protected by copyright.
Copyright by University of Warsaw.
Krakowskie Przedmieście 26/28
00-927 Warszawa tel: +48 22 55 20 000 https://uw.edu.pl/ contact accessibility statement USOSweb 7.0.3.0 (2024-03-22)