Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria algorytmów i obliczeń
Koordynator przedmiotu:
dr hab. inż. Władysław Homenda
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
7 / rok ak. 2012/2013
Liczba punktów ECTS:
6
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. godziny kontaktowe - 65 h; w tym a. obecność na wykładach – 30 h b. obecność na ćwiczeniach – 15 h c. obecność na laboratoriach – 15 h d. konsultacje – 5 h 2. przygotowanie do zajęć – 100 h, w tym a. przygotowanie do wykładów – 15 h b. przygotowanie do ćwiczeń – 20 h c. dodatkowo przygotowanie do sprawdzianów pisemnych – 20 h d. przygotowanie do zajęć laboratoryjnych – 45 h Razem nakład pracy studenta 165 h = 6 pkt. ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1. obecność na wykładach – 30 h 2. obecność na ćwiczeniach – 15 h 3. obecność na laboratoriach – 15 h 4. konsultacje z prowadzącymi zajęcia – 5 h Razem 30+15+15+5 = 65 h, co odpowiada 3 pkt. ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
1. obecność na ćwiczeniach – 15 h 2. obecność na laboratoriach – 15 h 3. przygotowanie do ćwiczeń – 20 h 4. przygotowanie do sprawdzianów pisemnych – 20 h 5. przygotowanie do zajęć laboratoryjnych – 45 h Razem 15+15+20+20+45= 115 h, co odpowiada 4 pkt. ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia15h
  • Laboratorium15h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Wstęp do lingwistyki matematycznej i teorii automatów Algorytmy i struktury danych
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Celem przedmiotu jest przekazanie wiedzy z teorii algorytmów, złożoności, rozstrzygalności, charakteryzacji klas problemów. Po ukończeniu kursu studenci powinni posiadać wiedzę i umiejętności sformułowane w tabeli efektów kształcenia.
Treści kształcenia:
Program wykładu: A. Rozstrzygalność problemów Języki rekurencyjne, rekurencyjnie przeliczalne i nierekurencyjne, problemy rozstrzygalne, częściowo rozstrzygalne i nierozstrzygalne. Modele obliczeń: maszyny Turinga, maszyny RAM. Równoważność modeli obliczeń. Teoria funkcji rekursywnych: rekursja pierwotna, operacja minimum efektywnego, funkcje pierwotnie rekursywne, rekurencyjne i rekurencyjnie przeliczalne. Obliczalność i częściowa obliczalność w sensie Turinga. Hipoteza Churcha.. B) Złożoność algorytmów Złożoność czasowa algorytmów. Klasy problemów: P, QL, NQL, NPI, NP, co-NP. Twierdzenie Cooka. Równoważność modeli obliczeń w sensie złożoności czasowej. Złożoność pamięciowa algorytmów. Klasy problemów DLOG, POLYLOG, P. Twierdzenie Sawitcha. C) Przykłady problemów   Program ćwiczeń: Rozwiązywanie zadań dotyczących zagadnień prezentowanych na wykładzie.   Program laboratorium Rozwiązywanie problemów NP-zupełnych za pomocą algorytmów dokładnych i aproksymacyjnych.
Metody oceny:
Do zaliczenia przedmiotu wymagane jest zaliczenie części teoretycznej i praktycznej w bieżącym semestrze. Zaliczenie części teoretycznej na podstawie końcowej pracy pisemnej. Zaliczenie części laboratoryjnej na podstawie rozwiązania przydzielonego problemu w czasie semestru. Wymagana jest obecność na zajęciach laboratoryjnych w celu kontroli realizacji zdania laboratoryjnego.
Egzamin:
nie
Literatura:
Hopcroft J.E. Ullman J.D., Wprowadzenie do teorii automatów, języków i obliczeń, WNT Homenda W., Elementy lingwistyki matematycznej i teorii automatów, WPW Papadimitriou C. H., Złożonośćc obliczeniowa, WNT, Warszawa Hennie F., Introduction to computability, Addison-Wesley
Witryna www przedmiotu:
brak
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt W01
Zna teoretyczne modele obliczeniowe: maszyny Turinga, gramatyki nieograniczone, maszyny RAM, funkcje rekurencyjne, jest świadomy uniwersalności modeli obliczeń i pojęcia obliczalności.
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny,
Powiązane efekty kierunkowe: K_W01, K_W07
Powiązane efekty obszarowe: T1A_W01, T1A_W03
Efekt W02
Zna podstawowe pojęcia teorii obliczalności: rozstrzygalność, częściowa rozstrzygalność, komplementarność częściowej rozstrzygalności, nierozstrzygalność.
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny,
Powiązane efekty kierunkowe: K_W04, K_W08
Powiązane efekty obszarowe: T1A_W03, T1A_W04
Efekt W03
Zna podstawowe pojęcia teorii złożoności: problemy jako przeliczalne zbiory zadań, algorytmy i ich złożoność, sposoby określania rozmiarów zadań, kryteria wyznaczania złożoności, równoważność klas problemów, języków i funkcji naturalnych.
Weryfikacja: sprawdzian pisemny,
Powiązane efekty kierunkowe: K_W04, K_W08, K_W10
Powiązane efekty obszarowe: T1A_W03, T1A_W04, T1A_W07

Profil ogólnoakademicki - umiejętności

Efekt U01
Potrafi podać i uzasadnić charakterystykę przestrzeni problemów ze względu na ich rozstrzygalność, potrafi uzasadnić jakościową równoważność wybranych modeli obliczeń.
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny
Powiązane efekty kierunkowe: K_U01, K_U02, K_U04, K_U05, K_U08, K_U14
Powiązane efekty obszarowe: T1A_U09, T1A_U09, T1A_U09, T1A_U01, T1A_U08, T1A_U16, T1A_U09, T1A_U15
Efekt U02
Potrafi skonstruować algorytmy rozwiązania prostych problemów w różnych modelach obliczeń, potrafi uzasadnić jakościową równoważność modeli obliczeniowych, potrafi uzasadnić ilościową równoważność wybranych modeli obliczeń.
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny
Powiązane efekty kierunkowe: K_U01, K_U02, K_U04, K_U09, K_U11
Powiązane efekty obszarowe: T1A_U09, T1A_U09, T1A_U09, T1A_U09, T1A_U09, T1A_U14, T1A_U15
Efekt U03
Potrafi podać i uzasadnić charakterystykę przestrzeni problemów rozstrzygalnych ze względu na złożoność algorytmów rozwiązania problemów: klasy P, NP, coNP, NPC, Pspace, NPspace, relacje między tymi klasami.
Weryfikacja: sprawdzian pisemny, przygotowanie rozwiązanie problemu z hierarchii złożoności (opis problemu, sformułowanie, dowód poprawności i analiza złożoności obliczeniowej algorytmów rozwiązania problemu, przygotowanie programu)
Powiązane efekty kierunkowe: K_U01, K_U09, K_U11, K_U14, K_U23
Powiązane efekty obszarowe: T1A_U09, T1A_U09, T1A_U09, T1A_U14, T1A_U15, T1A_U09, T1A_U15, T1A_U09, T1A_U16

Profil ogólnoakademicki - kompetencje społeczne

Efekt K01
Jest w stanie w sposób prosty wyjaśnić podstawowe zagadnienia teorii obliczalności, praktyczne ograniczenia metod obliczeniowych i teoretyczne granice obliczalności.
Weryfikacja: udział w dyskusji,
Powiązane efekty kierunkowe: K_K01, K_K02, K_K04, K_K05, K_K07
Powiązane efekty obszarowe: T1A_K01, T1A_K01, T1A_K02, T1A_K05, T1A_K03, T1A_K04, T1A_K07