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

Teoria obliczalności

Informacje ogólne

Kod przedmiotu: 1000-I1TOB Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Teoria obliczalności
Jednostka: Wydział Matematyki i Informatyki
Grupy: Inf., I st., stacjonarne, 3 rok, przedmioty obowiązkowe
Informatyka, studia I stopnia, 3 rok
Informatyka, studia inżynierskie 1 stopnia, 3 rok
Przedmioty z polskim językiem wykładowym
Wszystkie przedmioty z WMiI
Punkty ECTS i inne: 6.00
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:

kanon

Całkowity nakład pracy studenta:

30h - wykład,

4h - egzamin,

30h - ćwiczenia,

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

35h - praca własna - przygotowanie do egzaminu


Razem 149h,

5pkt. ECTS

Efekty uczenia się - wiedza:

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

* uniwersalne modele obliczeń

* maszyny licznikowe

* maszyny Turinga

* sieci Petriego

* 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

Efekty uczenia się - umiejętności:

Student potrafi:

* zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania prostych zadań związanych z informatyką;

* 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;

* ocenić, na podstawowym poziomie, przydatność rutynowych metod i narzędzi informatycznych oraz wybrać i zastosować właściwą metodę i narzędzia do typowych zadań informatycznych;

* 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

Efekty uczenia się - kompetencje społeczne:

1. Kreatywność: Student myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań

2. Sumienność i dokładność: Student jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegóły; jest systematyczny.

3. Komunikatywność: Student skutecznie przekazuje innym swoje myśli w zrozumiały sposób; właściwie posługuje się terminologią fachową; potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę.

4. Dążenie do rozwoju: Student jest nastawiony na nieustanne zdobywanie nowej wiedzy, umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych.

5. Wytrwałość i konsekwencja: Student pracuje systematycznie i posiada umiejętność pozytywnego podejścia do trudności stojących na drodze do realizacji założonego celu; dotrzymuje terminów.c

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:

  1. Obliczalność – pojęcia podstawowe
  2. Maszyny licznikowe
  3. Funkcje częściowo rekurencyjne
  4. Maszyny Turinga
  5. Sieci Petriego
  6. Pojęcie rozstrzygalności, częściowej rozstrzygalności oraz nierozstrzygalności problemów obliczeniowych
  7. Przykłady problemów rozstrzygalnych, częściowo rozstrzygalnych oraz nierozstrzygalnych
  8. Czasowa i pamięciowa złożoność obliczeniowa
  9. 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:

Zaliczenie ćwiczeń na ocenę oraz egzamin pisemny.

Zajęcia w cyklu "Semestr zimowy 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-02-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
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
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

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

Okres: 2018-10-01 - 2019-02-24
Wybrany podział planu:


powiększ
zobacz plan zajęć
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
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2019/20" (zakończony)

Okres: 2019-10-01 - 2020-02-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 25 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, Mariusz Kaniecki, Marcin Piątkowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2020/21" (jeszcze nie rozpoczęty)

Okres: 2020-10-01 - 2021-02-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 25 miejsc więcej informacji
Wykład, 30 godzin, 150 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.