Teoria obliczeń 2401-K-S2-1-TO

Przedstawiane zostaną teoretyczne podstawy zagadnienia modelowania obliczeń. Uczestnicy zapoznają się z zagadnieniami formalnego modelowania pojęcia efektywnej procedury za pomocą maszyny Turinga, kluczowym pojęciem funkcji obliczalnej, kwestią szacowania ilości kroków obliczenia oraz problemami nierozstrzygalnymi takimi jak problem stopu, obliczalności języka uniwersalnego i równości gramatyk bezkontekstowych. Omówione zostanie pojęcie złożoności obliczeniowej stanowiące podstawę dla oceny algorytmu pod względem pamięci lub czasu koniecznych do jego wykonania. Ogólnie można mówić o wielkości zasobów komputera potrzebnych do wykonania danego algorytmu uniezależniając klasyfikację algorytmu od konkretnej maszyny, na której się go implementuje.
W szczególności kurs stanowi wprowadzenie do teorii automatów, języków formalnych i logiki lingwistycznej. Zaprezentowane zostanie pojęcie języka akceptowanego przez automat na przykładzie języków regularnych i automatów skończonych. Dla skończonych automatów wskazany zostanie również niedeterministyczny model obliczeń. Udowodniona więc będzie równoważność automatów deterministycznych i niedeterministycznych. Studenci poznają lemat o pompowaniu dla języków regularnych i bezkontekstowych. Przedstawione zostaną też negatywne wyniki dotyczące akceptowania przez automaty języków. Omówiona zostanie hierarchia gramatyk pochodząca od Chomsky’ego oraz poruszana będzie kwestia lokalizacji języków naturalnych w tejże hierarchii.

W ramach zajęć omawiane są następujące tematy:

Wykład:
1. Automaty w kontekście zagadnienia obliczalności.
2. Złożoność obliczeniowa
3. Języki regularne i automaty skończone
4. Niedeterministyczne automaty skończone
5. Języki nieregularne i lemat o pompowaniu dla tych języków.
6. Gramatyki bezkontekstowe – definicja i przykłady
7. Automaty ze stosem
8. Lemat o pompowaniu dla języków bezkontekstowych
9. Maszyna Turinga – definicja, przykłady i rodzaju
10. Złożoność obliczeniowa i czasowa
11. Podstawowe klasy złożoności

Ćwiczenia:
1. Projektowanie automatów skończonych.
2. Suma, konkatenacja i funkcja `*’ jako operacje regularne
3. Przykłady języków regularnych i automaty skończone
4. Równoważność deterministycznych i niedeterministycznych automatów skończonych
5. Zastosowanie lematu o pompowaniu dla języków regularnych
6. Projektowanie gramatyk bezkontekstowych i normalna postać Chomsky’ego
7. Równoważność automatów ze stosem z gramatykami bezkontekstowymi
8. Zastosowanie lemat o pompowaniu dla języków bezkontekstowych
9. Projektowanie maszyn Turinga
10. Przykłady problemów z klas P, NP i problemów NP-zupełnych

Całkowity nakład pracy studenta

1. Godziny realizowane z udziałem nauczycieli: godziny kontaktowe przewidziane w planie studiów: 30 godzin ćwiczeń, 30 godzin wykładów 2. Czas poświęcony na pracę indywidualną studenta/słuchacza/uczestnika kursu potrzebny do pomyślnego zaliczenia przedmiotu, tj. wcześniejsze przygotowanie i uzupełnienie notatek; zebranie i wybór odpowiednich materiałów do zajęć, wymagane powtórzenie materiału, pisanie prac, projektów, czytanie literatury: 60 godzin 3. Czas wymagany do przygotowania się i do uczestnictwa w procesie oceniania (w egzaminie i kolokwiach): 30 godzin Łącznie: 150 godzin - 5 punktów ECTS

Efekty uczenia się - wiedza

W1: zna podstawowe pojęcia teorii obliczeń i rozumie ich znaczenie dla procesów poznawczych, w zakresie teoria złożoności obliczeniowej zna związki zachodzące między najważniejszymi klasami złożoności - K_W02 (zna szczegółową terminologię dyscyplin wchodzących w skład kognitywistyki w języku polskim, subdyscypliny w wybranym języku obcym). W2: zna sformułowania podstawowych twierdzeń teorii obliczalności wyrażających związek między wybranymi klasami języków w hierarchii Chomsky’ego a formalnymi modelami obliczeń, potrafi podać ich uzasadnienie - K_W05 (ma wiedzę w zakresie aktualnie dyskutowanych w literaturze kierunkowej problemów z jednej z dziedzin nauki i dyscypliny naukowej wchodzących w skład nauk kognitywnych).

Efekty uczenia się - umiejętności

U1: potrafi rozpoznać standardowe przypadki problemów z podstawowych klas złożoności - K_U03 (twórczo wykorzystuje wiedzę z dyscyplin wchodzących w skład kognitywistyki i metodologiczną w formułowaniu hipotez i konstruowaniu krytycznych argumentacji) U2: potrafi wskazać przykłady języków nieregularnych dowodząc stosownego negatywnego wyniku o nieakceptowaniu języka przez automaty z danej klasy - K_U06 (określa stopień doniosłości (relewancji) stawianych tez dla badanego problemu lub argumentacji) U3: potrafi konstruować automaty skończone i stosowe celem rozstrzygnięcia miejsca danego języka w hierarchii Chomsky’ego - K_U09 (precyzyjnie formułuje w mowie i na piśmie złożone problemy kognitywistyczne, stawia tezy i krytycznie je komentuje)

Efekty uczenia się - kompetencje społeczne

K1: posiada umiejętność ścisłego formułowania myśli i jasnego komunikowania abstrakcyjnych zagadnień z teorii obliczeń - K_K01 (zna zakres posiadanej przez siebie wiedzy i posiadanych umiejętności, rozumie potrzebę ciągłego dokształcania się i rozwoju zawodowego), K2: kształtuje umiejętność analizowania problemów, ścisłego formułowania własnych stwierdzeń, ich dowodzenia oraz krytycznego namysłu nad uzyskanymi konkluzjami, świadomie kształtuje proces badawczy - K_K02 (samodzielnie podejmuje i inicjuje działania profesjonalne; planuje i organizuje ich przebieg).

Metody dydaktyczne

Metody dydaktyczne podające: wykład problemowy, wykład informacyjny, wykład konwersacyjny. Metody dydaktyczne poszukujące: ćwiczeniowa

Metody dydaktyczne podające

- wykład informacyjny (konwencjonalny)
- wykład konwersatoryjny
- wykład problemowy

Metody dydaktyczne poszukujące

- ćwiczeniowa

Rodzaj przedmiotu

kanon (atrybut wycofany)

Wymagania wstępne

Podstawowa wiedza z zakresu matematyki i logiki w szczególności teorii zbiorów, teorii relacji i funkcji

Koordynatorzy przedmiotu

Krystyna Mruczek-Nasieniewska

Kryteria oceniania

Metody oceniania:
egzamin pisemny - W02, W05, U06, U09

Kolokwium – U03, U06, U09
Aktywność – K01, K02

Kryteria oceniania (obowiązują zarówno w przypadku zaliczenia ćwiczeń na podstawie kolokwium, jak i wykładu na podstawie egzaminu):
ocena bdb. - od 90% (włącznie) - do 100%
ocena db.+ - od 80% (włącznie) - do 90% (wyłącznie),
ocena db. - od 70% (włącznie) - do 80% (wyłącznie),
ocena dst.+ - od 60% (włącznie) - do 70% (wyłącznie),
ocena dst. - od 45% (włącznie) - do 60% (wyłącznie).

Praktyki zawodowe

Brak

Literatura

1. J. E. Hopcroft i J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN Warszawa, 2003.
2. Sipser Michael, Wprowadzenie do teorii obliczeń, WNT, War-szawa, 2009
3. Christos H. Papadimitriou, Złożoność obliczenia, Wydawnictwo Naukowo-Techniczne, Warszawa 2002
4. T. Krasiński "Automaty i języki formalne", Wydawnictwo Uniwersytetu Łódzkiego, Łódź 2007

Więcej informacji

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 2401-K-S2-1-TO w USOSweb