Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy zaawansowane
Koordynator przedmiotu:
Dr Michał Tuczyński
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-INMSI-MSP-0009
Semestr nominalny:
2 / rok ak. 2015/2016
Liczba punktów ECTS:
4
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ń
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z zaawansowanymi metodami projektowania algorytmów, dowodzenia ich poprawności oraz obliczania złożoności. W szczególności student po zaliczeniu przedmiotu powinien znać: - algorytmy zachłanne, kody Huffmana, matroidy, - programowanie dynamiczne, problem mnożenia łańcucha macierzy, - algorytmy dziel i zdobywaj, mnożenie liczb całkowitych, mnożenie macierzy, znajdowanie pary najbliższych punktów, - zaawansowane algorytmy grafowe, problem maksymalnego skojarzenia w grafie, - algorytmy aproksymacyjne, schematy aproksymacji, problem sumy podzbioru.
Treści kształcenia:
Algorytmy zachłanne, kody Huffmana, matroidy, programowanie dynamiczne, mnożenie łańcucha macierzy, usuwanie rekursji, algorytmy dziel i zdobywaj, szacowanie złożoności obliczeniowej algorytmów, mnożenie liczb całkowitych, mnożenie macierzy, algorytmy geometrii obliczeniowej, znajdowanie pary najbliższych punktów, konstruowanie domknięcia wypukłego, problem wyszukiwania wzorca, algorytmy aproksymacyjne.
Metody oceny:
Na ocenę końcową składają się: punkty za egzamin końcowy (60%) oraz punkty za projekt programistyczny (40%).
Egzamin:
tak
Literatura:
1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 1997. 2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, WNT, 2000. 3. M. R. Garey, D. S. Johnson, Computers and Intractability, Freeman 1979. 4. M. A. Weiss, Data Structures and Algorithms in C++, Adison Wesley 1999.
Witryna www przedmiotu:
brak
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt W2_01
Posiada wiedzę o zaawansowanej algorytmice, strukturach danych i metodach tworzenia algorytmów
Weryfikacja: egzamin
Powiązane efekty kierunkowe: CC_W11, SI_W11
Powiązane efekty obszarowe: ,
Efekt W2_02
Posiada szeroką wiedzę w zakresie teorii grafów
Weryfikacja: egzamin
Powiązane efekty kierunkowe: CC_W01, SI_W03, SI_W01
Powiązane efekty obszarowe: , ,

Profil ogólnoakademicki - umiejętności

Efekt U2_01
Potrafi projektować wydajne algorytmy i uzasadniać ich poprawność
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane efekty kierunkowe: CC_U09, SI_U09
Powiązane efekty obszarowe: ,
Efekt U2_02
Potrafi przeprowadzić analizę czasowej złożoności obliczeniowej algorytmu
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane efekty kierunkowe: CC_U09, SI_U09
Powiązane efekty obszarowe: ,
Efekt U2_03
Potrafi wykorzystać wiedzę matematyczną do analizy i optymalizacji rozwiązań informatycznych
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane efekty kierunkowe: CC_U06, SI_U06
Powiązane efekty obszarowe: ,
Efekt U2_04
Potrafi pracować indywidualnie, w zespole oraz kierować niedużym zespołem
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane efekty kierunkowe: CC_U02, SI_U02
Powiązane efekty obszarowe: ,

Profil ogólnoakademicki - kompetencje społeczne

Efekt K2_01
Ma świadomość odpowiedzialności za wspólnie realizowane zadania w ramach pracy zespołowej
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane efekty kierunkowe: CC_K04, SI_K04
Powiązane efekty obszarowe: ,