Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowania
Strona główna

Teoria obliczalności

Informacje ogólne

Kod przedmiotu: 1000-I1TOB
Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Teoria obliczalności
Jednostka: Wydział Matematyki i Informatyki
Grupy:
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: polski
Wymagania wstępne:

Podstawowe wiadomości z zakresu matematyki i informatyki obejmujące teorię zbiorów, matematykę dyskretną, teorię języków formalnych, teorię algorytmów oraz programowanie.

Rodzaj przedmiotu:

przedmiot obowiązkowy

Całkowity nakład pracy studenta:

30h - wykład,

30h - ćwiczenia,

50h - praca własna - bieżące przygotowanie do zajęć, studiowanie literatury

35h - praca własna - przygotowanie do egzaminu

5h - zaliczenie ćwiczeń i egzamin

Razem 150h,

6pkt. ECTS

Efekty uczenia się - wiedza:

Student

W1: ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie teorii obliczalności (KW_02). W szczególności zna i rozumie:

* uniwersalne modele obliczeń

* maszyny licznikowe

* maszyny Turinga

* pojęcie rozstrzygalności i częściowej rozstrzygalności

* przykłady rozstrzygalnych, nierozstrzygalnych oraz częściowo rozstrzygalnych problemów w informatyce

* pojęcie złożoności obliczeniowej algorytmu (czasowej i pamięciowej)

* klasy złożoności obliczeniowej i relacje między nimi

* pojęcie trudności i zupełności problemów obliczeniowych

* przykłady trudnych i zupełnych problemów obliczeniowych

W2: zna podstawowe metody projektowania i analizowania algorytmów (projektowanie strukturalne, rekurencja, złożoność obliczeniowa) (KW_04)

Efekty uczenia się - umiejętności:

Student potrafi:

U1: potrafi wykorzystać wiedzę matematyczną oraz informatyczną do formułowania, analizowania i rozwiązywania problemów obliczeniowych (KU_01), w szczególności:

w szczególności

* odróżniać problemy rozstrzygalne i częściowo rozstrzygalne od nierozstrzygalnych

* dowodzić obliczalność, rozstrzygalność oraz częściową rozstrzygalność typowych problemów matematycznych

* dowodzić trudność i zupełność problemów obliczeniowych przez sprowadzenie do znanych problemów obliczeniowych

U2: potrafi projektować oraz analizować rozwiązania problemów obliczeniowych pod kątem ich poprawności i złożoności obliczeniowej (KU_07)

U3: potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie; (KU_02)

Efekty uczenia się - kompetencje społeczne:

Student:

KK1: skutecznie przekazuje innym swoje myśli w zrozumiały sposób (KK_02)

KK2: właściwie posługuje się terminologią fachową (KK_02)

KK3: potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę (KK_02)

KK4: rozumie potrzebę ciągłego uczenia się i doskonalenia swoich umiejętności (KK_03)

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)

Skrócony opis:

Przedmiot dla studiów I stopnia na kierunku informatyka. Jego celem jest: prezentacja formalizacji pojęcia obliczalności, omówienie podstawowych problemów nierozstrzygalnych w informatyce (stopu, wejścia, wyjścia, itp.) i matematyce (X problemu Hilberta, itp.) oraz przedstawienie podstawowych wyników teorii złożoności obliczeniowej.

Pełny opis:

W ramach przedmiotu omawiane będą m.in. następujące zagadnienia:

  1. Obliczalność – pojęcia podstawowe
  2. Maszyny licznikowe
  3. Funkcje częściowo rekurencyjne
  4. Maszyny Turinga
  5. Pojęcie rozstrzygalności, częściowej rozstrzygalności oraz nierozstrzygalności problemów obliczeniowych
  6. Przykłady problemów rozstrzygalnych, częściowo rozstrzygalnych oraz nierozstrzygalnych
  7. Czasowa i pamięciowa złożoność obliczeniowa
  8. Problemy trudne i zupełne
Literatura:

  • Michael Sipser Wprowadzenie do teorii obliczeń
  • Antonii Kościelski Teoria obliczeń. Wykłady z matematycznych podstaw informatyki
  • Christos H. Papadimitriou Złożoność obliczeniowa
  • David Harel Rzecz o istocie informatyki: algorytmika
  • John E. Hopcroft, Jeffrey D. Ullman Wprowadzenie do teorii automatów, języków i obliczeń
Metody i kryteria oceniania:

Laboratorium: kolokwia pisemne

Wykład: egzamin pisemny

Zajęcia w cyklu "Semestr zimowy 2021/22" (zakończony)

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Marcin Piątkowski
Prowadzący grup: Kamila Barylska, Anna Gogolińska, Marcin Piątkowski
Strona przedmiotu: https://plas.mat.umk.pl/moodle/course/view.php?id=1883
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2022/23" (zakończony)

Okres: 2022-10-01 - 2023-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Marcin Piątkowski
Prowadzący grup: Kamila Barylska, Mariusz Kaniecki, Marcin Piątkowski
Strona przedmiotu: https://plas.mat.umk.pl/moodle/course/view.php?id=1883
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Marcin Piątkowski
Prowadzący grup: Kamila Barylska, Mariusz Kaniecki, Marcin Piątkowski
Strona przedmiotu: https://plas.mat.umk.pl/moodle/course/view.php?id=1883
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - 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.
ul. Jurija Gagarina 11, 87-100 Toruń tel: +48 56 611-40-10 https://usosweb.umk.pl/ kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)