Teoretyczne podstawy informatyki

obowiązkowe

Prezentacja podstawowych teoretycznych modeli obliczeń, ich możliwości i ograniczeń oraz wprowadzenie w podstawowe zagadnienia teorii złożoności obliczeniowej.

A. Problematyka wykładu / B. Problematyka konwersatorium (K) C. Problematyka laboratorium (L)

Pojęcie języka. Deterministyczne i niedeterministyczne automaty skończone. (L)

Wyrażenia i języki regularne. Gramatyki regularne, równoważność z automatami. (L)

Lemat o pompowaniu. Języki nieregularne. (K)

Gramatyki i języki bezkontekstowe, własności języków bezkontekstowych. Gramatyki języków programowania. Stosowane notacje. (L) Automaty ze stosem. Równoważność gramatyk bezkontekstowych i automatów ze stosem. (L)

Lemat o pompowaniu dla języków bezkontekstowych. (K)

Niedeterministyczna wielotaśmowa maszyna Turinga. Modele ograniczone maszyny Turinga. (L)

Maszyna uniwersalna. Obliczalność. Teza Churcha. Problem stopu. Problemy nierozstrzygalne. (K)

Pamięciowa i czasowa złożoność obliczeniowa. Problemy SAT i PRIMES. Związki pomiędzy klasami złożoności. (K)

NP-zupełność. Przykład problemu obliczeniowo trudnego. (K)

M. Sipser, Wprowadzenie do teorii obliczeń, WNT, 2009. Lepiej nowe wydanie: Wydawnictwo Naukowe PWN, 2024.

Literatura uzupełniająca:

1. J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, Nowe wydanie, Warszawa 2005.

2. Ch. H. Papadimitriou, Złożoność obliczeniowa, WNT, 2002.

Wiedza:

• Definiuje deterministyczne i niedeterministyczne automaty skończone.

• Definiuje zbiór wyrażeń regularnych nad ustalonym alfabetem.

• Definiuje automat ze stosem i gramatykę bezkontekstową.

• Zna własności domknięcia klasy języków regularnych i klasy języków bezkontekstowych na operacje regularne.

• Zna podstawowe warianty maszyn Turinga (jednotaśmowa, wielotaśmowa, niedeterministyczna).

• Zna pojęcie problemu nierozstrzygalnego.

• Definiuje problemy SAT i PRIMES.

• Definiuje złożoność obliczeniową problemu.

• Wymienia podstawowe klasy złożoności obliczeniowej.

Umiejętności:

• Konstruuje automat skończony i pisze wyrażenie regularne dla prostych języków regularnych.

• Przekształca niedeterministyczny automat skończony na automat deterministyczny.

• Konstruuje automat równoważny danemu wyrażeniu regularnemu.

• Konstruuje automat ze stosem i pisze gramatykę bezkontekstową dla prostych języków bezkontekstowych.

• Podaje przykłady języków, które nie są regularne lub nie są bezkontekstowe.

• Konstruuje jedno- i wielotaśmową maszynę Turinga.

• Podaje przykład problemu nierozstrzygalnego.

• Podaje przykład problemu NP-zupełnego.

• Potrafi zwięźle przedstawić pytanie „ czy P= NP ?”

Kompetencje społeczne (postawy):

• Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia.

• Potrafi odpowiednio określić priorytety służące realizacji określonego zadania informatycznego (laboratorium).

• Postępuje etycznie w zakresie wykorzystania efektów pracy innych osób.

• Rozumie potrzebę popularnego przedstawiania laikom wybranych osiągnięć informatyki teoretycznej.

Forma i sposób zaliczenia oraz podst. kryteria oceny lub wymagania egzaminacyjne - na ogólnych zasadach określonych w programie kształcenia; w szczególności:

A. Sposób zaliczenia

• zaliczenie z oceną

B. Formy zaliczenia

• (W, K, L) ustalenie oceny zaliczeniowej na podstawie ocen cząstkowych otrzymywanych w przeciągu semestru za prace kontrolne, wystąpienia ustne, domowe prace pisemne i wykonanie zadań nieobowiązkowych.

C. Podstawowe kryteria

• (W) obecność na zajęciach;

• (K) aktywność na zajęciach i ocena prac domowych;

• (L) pozytywna ocena pisemnych prac kontrolnych.

Przy ocenie będą też brane pod uwagę przedstawione rozwiązania nieobowiązkowych zadań problemowych.