Teoria obliczalności 1000-I1TOB

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

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)

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)

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)

- wykład informacyjny (konwencjonalny)

przedmiot obligatoryjny

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.

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

• Strona przedmiotu 1000-I1TOB w USOSweb