Teoretyczne podstawy informatyki 3.4.KRK.12SX.TPI
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 PRIME. Związki pomiędzy klasami złożoności. (K)
NP-zupełność. Przykład problemu obliczeniowo trudnego. (K)
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
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.
Kryteria oceniania
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
• (L) zaliczenie z oceną: ustalenie oceny zaliczeniowej na podstawie ocen cząstkowych otrzymywanych w trakcie trwania semestru z pisemnych sprawdzianów;
• (K) zaliczenie z oceną: ustalenie oceny zaliczeniowej na podstawie aktywności na zajęciach i ocen z prac domowych;
• (W) zaliczenie z oceną: ustalenie oceny zaliczeniowej na podstawie obecności na zajęciach oraz ocen końcowych z laboratorium i konwersatorium;
C. Podstawowe kryteria
• (W), (L), (K) - uzyskanie pozytywnej oceny zaliczeniowej
Literatura
M. Sipser, Wprowadzenie do teorii obliczeń, WNT, 2009.
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.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: