Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria algorytmów i obliczeń
Koordynator przedmiotu:
prof. nzw. dr hab. Jarosław Grytczuk
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
3 / rok ak. 2009/2010
Liczba punktów ECTS:
6
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
Matematyka Dyskretna, Algorytmy i struktury danych, Teoria Algorytmów i Obliczeń I
Limit liczby studentów:
Cel przedmiotu:
Poznanie zaawansowanych algorytmów i struktur danych, metod konstruowania algorytmów, technik dowodzenia ich poprawności i analizy złożoności obliczeniowej.
Treści kształcenia:
Wykład: 1) Wybrane techniki konstruowania algorytmów. a) Algorytmy zachłanne: problemy szeregowania zadań, kody Huffmana, przybliżone pakowanie. b) Programowanie dynamiczne: zastosowanie do liczenia rekursji, mnożenie łańcucha macierzy, problem najdłuższego wspólnego podciągu, optymalna triangulacja wielokątów. c) Algorytmy „dziel i zdobywaj”: dyskusja złożoności takich algorytmów, problem najbliższych punktów, problem mnożenia liczb całkowitych, problem mnożenia macierzy. d) Mnożenie wielomianów i szybka transformata Fouriera. e) Algorytmy teorii liczb: znajdowanie dużych liczb pierwszych, rozkład liczby na czynniki. f) Wybrane algorytmy geometrii obliczeniowej. 2) Algorytmy przybliżone problemów optymalizacji dyskretnej. a) Rodzaje algorytmów przybliżonych. b) Przykłady: problemy pakowania, problem komiwojażera, problem plecakowy. 3) NP-zupełność problemów przybliżonego rozwiązania problemów optymalizacyjnych: problem plecakowy, problem maksymalnego zbioru niezależnego w grafie i minimalnego pokrycia, problemy kolorowania w grafach, problem komiwojażera.   Projekt: Implementacja i badanie własności omawianych algorytmów.    
Metody oceny:
Na ocenę końcową składa się wynik z egzaminu końcowego (60%) oraz z zadania projektowego (40%). Razem 100 pkt. Ocena 3.0 – 50-59 pkt, 3.5 – 60-69 pkt, 4.0 – 70-79 pkt, 4.5 – 80-89 pkt, 5.0 – 90-100 pkt. Aby uzyskać pozytywną ocenę należy zdobyć więcej niż połowę punktów zarówno z egzaminu końcowego, jak i z zadania projektowego.    
Egzamin:
Literatura:
L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 1997. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, WNT, 2000. M. R. Garey, D. S. Johnson, Computers and Intractability, Freeman 1979.  
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się