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

Podstawy teorii obliczalności

Informacje ogólne

Kod przedmiotu: 1000-ZiPTO Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Podstawy teorii obliczalności
Jednostka: Wydział Matematyki i Informatyki
Grupy: Informatyka, studia inżynierskie 1 stopnia, 3 rok, nst.
Przedmioty z polskim językiem wykładowym
Punkty ECTS i inne: 8.00
Język prowadzenia: polski
Wymagania wstępne:

Znajomość podstawowych pojęć algorytmiki (Podstawy programowania oraz Algorytmy i struktury danych) oraz podstaw matematyki współczesnej (Matematyka dla informatyków I oraz II)

Rodzaj przedmiotu:

przedmiot obowiązkowy

Całkowity nakład pracy studenta:

30h – wykłady klasyczne

5h – wykłady zdalne

2h – egzamin

30h – ćwiczenia klasyczne

15h – projekt wykonywany zdalnie

60h – pracy własnej (ćwiczenia)

60h – studia literatury (wykład)

20h – przygotowanie do egzaminu


RAZEM: 222 godziny

8 punktów ECTS


Efekty uczenia się - wiedza:

Po ukończeniu kursu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia inżynierskie):


(W1) ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie problematyki obliczalności, języków formalnych i automatów (K_W02)

(W2) ma pogłębioną wiedzę teoretyczną w zakresie złożoności obliczeniowej (K_W04)


Efekty uczenia się - umiejętności:

Po ukończeniu kursu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia inżynierskie):


(U1) potrafi zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania prostych zadań związanych informatyką (K_U01)

(U2) potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, (K_U02)

(U3) potrafi analizować pod kątem poprawności i złożoności obliczeniowej problemy i algorytmy (K_U07)


Efekty uczenia się - kompetencje społeczne:

Po ukończeniu kursu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia inżynierskie):


(K1) Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny (K_K04)

(K2) Jest nastawiony na nieustanne zdobywanie nowej wiedzy, umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych (K_K06)


Metody dydaktyczne:

Jest to klasyczny przedmiot z zakresu informatyki teoretycznej – z wykładem zawierającym precyzyjne dowody przedstawianych faktów oraz ćwiczeniami mającymi na celu głębsze zrozumienie omawianych pojęć.

• Metody dydaktyczne podające:

o wykład informacyjny (konwencjonalny)

• Metody dydaktyczne poszukujące:

o ćwiczeniowa

o referatu

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- projektu

Metody dydaktyczne w kształceniu online:

- metody ewaluacyjne

Skrócony opis:

Celem przedmiotu jest przedstawienie podstawowych zagadnień teorii języków formalnych, teorii obliczalności oraz teorii złożoności obliczeniowej

Pełny opis:

1. Języki regularne i bezkontekstowe

1.1 Wyrażenia regularne, automaty jako akceptory jezyków

1.2 Twierdzenie Kleene’ego

1.3 Klasyfikacja gramatyk Chomsky’ego

1.4 Parsery dla gramatyk bezkontekstowych (algorytm CYK)

2. Różne definicje obliczalności

2.1 Funkcje obliczalne wg Kleene’ego

2.2 Maszyna Turinga

2.3 Maszyna RAM

2.4 Hipoteza Churcha

3. Problemy nierozstrzygalne - przykłady

3.1 Problem stopu dla maszyn Turinga

3.2 Przykłady funkcji nierekurencyjnych

3.3 Twierdzenie Rice’a

3.4 Nierozstrzygalność problemu słów

3.5 X problem Hilberta

4. Złożoność obliczeniowa, przykłady problemów o różnej złożoności

4.1 Skala złożoności

4.2 P = NP ?

Literatura:

1) Wprowadzenie do teorii obliczeń, M. Sipser

2) Wprowadzenie do teorii automatów języków i obliczeń, J.E.Hopcroft, J.D. Ullman

3) Złożoność obliczeniowa, Ch. H. Papadimitriou

4) Skrypty UMK do wykładów i ćwiczeń z przedmiotów Teoria Języków Formalnych oraz Teoria Obliczalności (K. Barylska, Ł. Mikulski, M. Piątkowski)

5) Wykłady zdalne dostępne na platformie Moodle kursu

Metody i kryteria oceniania:

Zaliczenie ćwiczeń na ocenę oraz egzamin.

Ćwiczenia zaliczane na ocenę na podstawie dwóch kolokwiów

• kolokwium 1 – języki regularne i bezkontekstowe (W1, U1);

• kolokwium 2 – obliczalność, rozstrzygalność i złożoność obliczeniowa (W1+W2, U1 + U3);

• projekt związany ze skanerami i parserami (W1, U2, K1+K2).

Egzamin pisemny (W1+W2, U1+U3, K1).

Praktyki zawodowe:

nie dotyczy

Zajęcia w cyklu "Rok akademicki 2019/20" (w trakcie)

Okres: 2019-10-01 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 35 godzin, 30 miejsc więcej informacji
Wykład, 35 godzin, 50 miejsc więcej informacji
Koordynatorzy: Kamila Barylska
Prowadzący grup: Kamila Barylska, Mariusz Kaniecki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Rok akademicki 2020/21" (jeszcze nie rozpoczęty)

Okres: 2020-10-01 - 2021-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 35 godzin, 30 miejsc więcej informacji
Wykład, 35 godzin, 50 miejsc więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
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.