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: | |
Punkty ECTS i inne: |
6.00
|
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:
|
Literatura: |
|
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 |
Przejdź do planu
PN WT LAB
LAB
ŚR LAB
LAB
CZ LAB
PT WYK
|
Typ zajęć: |
Laboratorium, 30 godzin, 16 miejsc
Wykład, 30 godzin, 150 miejsc
|
|
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 |
Przejdź do planu
PN WT LAB
LAB
LAB
LAB
ŚR CZ PT WYK
|
Typ zajęć: |
Laboratorium, 30 godzin, 16 miejsc
Wykład, 30 godzin, 150 miejsc
|
|
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 |
Przejdź do planu
PN WT WYK
LAB
ŚR LAB
CZ PT LAB
LAB
LAB
|
Typ zajęć: |
Laboratorium, 30 godzin, 16 miejsc
Wykład, 30 godzin, 150 miejsc
|
|
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 |
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.