Teoria obliczeń
Informacje ogólne
Kod przedmiotu: | 2401-K-S2-1-TO |
Kod Erasmus / ISCED: |
(brak danych)
/
(0228) Interdyscyplinarne programy i kwalifikacje związane z naukami humanistycznymi
|
Nazwa przedmiotu: | Teoria obliczeń |
Jednostka: | Katedra Kognitywistyki |
Grupy: |
Kognitywistyka - s2 - 1 rok |
Punkty ECTS i inne: |
4.00
|
Język prowadzenia: | polski |
Wymagania wstępne: | Podstawowa wiedza z zakresu matematyki i logiki w szczególności teorii zbiorów, teorii relacji i funkcji |
Rodzaj przedmiotu: | kanon |
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) |
Metody dydaktyczne poszukujące: | - ćwiczeniowa |
Skrócony opis: |
Kurs poświęcony jest wprowadzeniu do teorii obliczeń i automatów. Uczestnicy zapoznają się z podstawowymi ideami i modelami teorii obliczeń. Przedstawione zostaną pojęcia automatu skończonego, automatu ze stosem, automatu deterministycznego i niedeterministycznego, maszyny Turinga, obliczalności, języka akceptowanego przez dany automat oraz klasy złożoności. |
Pełny opis: |
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 |
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 |
Metody i 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 |
Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)
Okres: | 2022-02-21 - 2022-09-30 |
Przejdź do planu
PN WT ŚR WYK
CW
CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Krystyna Mruczek-Nasieniewska | |
Prowadzący grup: | Krystyna Mruczek-Nasieniewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Wykład - Egzamin |
Zajęcia w cyklu "Semestr letni 2022/23" (zakończony)
Okres: | 2023-02-20 - 2023-09-30 |
Przejdź do planu
PN WT ŚR WYK
CW
CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Krystyna Mruczek-Nasieniewska | |
Prowadzący grup: | Krystyna Mruczek-Nasieniewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Wykład - Egzamin |
Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)
Okres: | 2024-02-20 - 2024-09-30 |
Przejdź do planu
PN WT ŚR WYK
CW
CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Krystyna Mruczek-Nasieniewska | |
Prowadzący grup: | Krystyna Mruczek-Nasieniewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Wykład - Egzamin |
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.