Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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: 5.00 LUB 4.00 (zmienne w czasie)
zobacz reguły punktacji
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)
- wykład konwersatoryjny
- wykład problemowy

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 2017/18" (zakończony)

Okres: 2018-02-26 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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
Skrócony opis:

identyczne jak w części A

Pełny opis:

identyczne jak w części A

Literatura:

identyczne jak w części A

Zajęcia w cyklu "Semestr letni 2018/19" (zakończony)

Okres: 2019-02-25 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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 2019/20" (zakończony)

Okres: 2020-02-29 - 2020-09-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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 2020/21" (zakończony)

Okres: 2021-02-22 - 2021-09-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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 2021/22" (jeszcze nie rozpoczęty)

Okres: 2022-02-21 - 2022-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.