Teoretyczne podstawy informatyki (2015/2016)

Wykład: piatek 8-10, sala 604.

Ćwiczenia: piatek 10-12, sala 604.

Konsultacje: sroda 15-16, piatek 14:15-15:15, pok. 502

Egzamin poprawkowy: 1.09 (czwartek) godz. 10:00, sala 604.

Wykład ten jest wprowadzeniem do teorii jezyków formalnych, automatów oraz zlożonosci obliczeniowej i obejmuje między innymi następujace zagadnienia:
1. Automaty skończone. Języki i gramatyki regularne.
2. Automaty ze stosem. Języki i gramatyki bezkontekstowe.
3. Maszyny Turinga. Zbiory rekurencyjne i rekurencyjnie przeliczalne.
4. Klasy złożoności obliczeniowej.

Literatura pomocnicza:

J. E. Hopcroft i J. D. Ullman, Wprowadzenie do teorii automatów, językow i obliczeń.
D. C. Kozen, Automata and Computability.

ZALICZENIE PRZEDMIOTU
W semestrze planuję trzy kolokwia (8.04, 13.05 i 3.06). Z każdego kolokwium można będzie uzyskać maksymalnie 20 pkt. Minimalna liczba punktów potrzebnych do zaliczenia ćwiczen to 24. Progi na wyższe oceny: 3.5 od 30 pkt, 4.0 od 36 pkt, 4.5 od 42 pkt i 5.0 od 48 pkt. Za aktywnosć na ćwiczeniach moge podniesę ocenę o pół stopnia (pod warunkiem uzyskania przynajmniej 24 pkt z kolokwiow). Wyklad kończy sie egzaminem, którego zasady zostana podane poźniej.

Listy zadań:

  • Lista nr 1

  • Lista nr 2

  • Lista nr 3

  • Lista nr 4

  • Lista nr 5

  • Lista nr 6

  • Lista nr 7

  • Zadanie 2 z listy nr 5

  • Roman Wencel