- Nazwa przedmiotu:
- Algorytmy zaawansowane
- Koordynator przedmiotu:
- prof. dr hab. inż. Zbigniew Lonc
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia II stopnia
- Program:
- Informatyka i Systemy Informacyjne
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- 1120-IN000-MSP-0121
- Semestr nominalny:
- 1 / rok ak. 2023/2024
- Liczba punktów ECTS:
- 3
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 1. godziny kontaktowe – 52 h; w tym
a) obecność na wykładach – 30 h
b) obecność na zajęciach projektowych – 15 h
c) konsultacje – 5 h
d) obecność na egzaminie – 2 h
2. praca własna studenta – 35 h; w tym
a) przygotowanie do zajęć projektowych – 15 h
b) przygotowanie do egzaminu, w tym zapoznanie się z literaturą – 20 h
Razem 87 h, co odpowiada 3 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 zajęciach projektowych – 15 h
3. konsultacje – 5 h
4. obecność na egzaminie – 2 h
Razem 52 h, co odpowiada 2 pkt. ECTS
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 1. obecność na zajęciach projektowych – 15 h
2. przygotowanie do zajęć projektowych – 15 h
Razem 30 h, co odpowiada 1 pkt. ECTS
- 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
- Charakterystyka W01
- Posiada wiedzę o zaawansowanej algorytmice, strukturach danych i metodach tworzenia algorytmów
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe:
I2_W02
Powiązane charakterystyki obszarowe:
P7U_W, I.P7S_WG.o
- Charakterystyka W02
- Posiada szeroką wiedzę w zakresie teorii grafów
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe:
I2_W01
Powiązane charakterystyki obszarowe:
P7U_W, I.P7S_WG.o
Profil ogólnoakademicki - umiejętności
- Charakterystyka U01
- Potrafi projektować wydajne algorytmy i uzasadniać ich poprawność
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane charakterystyki kierunkowe:
I2_U03
Powiązane charakterystyki obszarowe:
- Charakterystyka U02
- Potrafi przeprowadzić analizę czasowej złożoności obliczeniowej algorytmu
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane charakterystyki kierunkowe:
I2_U03
Powiązane charakterystyki obszarowe:
- Charakterystyka U03
- Potrafi wykorzystać wiedzę matematyczną do analizy i optymalizacji rozwiązań informatycznych
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane charakterystyki kierunkowe:
I2_U02
Powiązane charakterystyki obszarowe:
- Charakterystyka U04
- Potrafi pracować indywidualnie, w zespole oraz kierować niedużym zespołem
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane charakterystyki kierunkowe:
I2_U11
Powiązane charakterystyki obszarowe:
- Charakterystyka U05
- Potrafi projektować algorytmy wielowątkowe i analizować ich wydajność
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane charakterystyki kierunkowe:
I2_U04
Powiązane charakterystyki obszarowe:
Profil ogólnoakademicki - kompetencje społeczne
- Charakterystyka K01
- Ma świadomość odpowiedzialności za wspólnie realizowane zadania w ramach pracy zespołowej
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane charakterystyki kierunkowe:
I2_K05
Powiązane charakterystyki obszarowe:
- Charakterystyka K02
- Jest świadomy roli wiedzy w rozwiązywaniu problemów i rozumie potrzebę zasięgania opinii ekspertów
Weryfikacja: ocena projektu programistycznego, w tym terminowości
Powiązane charakterystyki kierunkowe:
I2_K02
Powiązane charakterystyki obszarowe: