Politechnika
Warszawska

Katalog
ECTS

Nazwa przedmiotu:

Algorytmy zaawansowane

Koordynator przedmiotu:

Dr inż. Konstanty Junosza-Szaniawski

Status przedmiotu:

Obowiązkowy

Poziom kształcenia:

Studia II stopnia

Program:

Informatyka i Systemy Informacyjne

Grupa przedmiotów:

Wspólne

Kod przedmiotu:

Semestr nominalny:

1 / rok ak. 2019/2020

Liczba punktów ECTS:

4

Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:

1. godziny kontaktowe – 45 h; w tym a. obecność na wykładach – 30 h b. obecność na ćwiczeniach – 0 h c. obecność na zajęciach projektowych – 15 h 2. przygotowanie do ćwiczeń – 0 h 3. przygotowanie do zajęc projektowych – 15 h 4. zapoznanie się z literaturą – 5 h 5. konsultacje – 5 h 6. przygotowanie do egzaminu i obecność na egzaminie – 30 h Łączny nakład pracy studenta wynosi 100 h co odpowiada 4 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 – 0 h 3. obecność na zajęciach projektowych – 15 h 4. konsultacje – 5 h Razem 50 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 I, matematyka dyskretna II, algorytmy i struktury danych

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:

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. 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 W2_01

posiada wiedzę o zaawansowanej algorytmice, strukturach danych i metodach tworzenia algorytmów.
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: CC_W11, SI_W11
Powiązane charakterystyki obszarowe:

Charakterystyka W2_02

posiada szeroką wiedzę w zakresie teorii grafów
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: CC_W01, SI_W03
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka U2_01

potrafi projektować wydajne algorytmy i uzasadniać ich poprawność
Weryfikacja: Ocena projektu
Powiązane charakterystyki kierunkowe: CC_U09, SI_U09
Powiązane charakterystyki obszarowe:

Charakterystyka U2_02

Potrafi przeprowadzić analizę czasowej złożoności obliczeniowej algorytmu
Weryfikacja: Ocena projektu
Powiązane charakterystyki kierunkowe: CC_U09, SI_U09
Powiązane charakterystyki obszarowe:

Charakterystyka U2_03

potrafi wykorzystać wiedzę matematyczną do analizy i optymalizacji rozwiązań informatycznych
Weryfikacja: Ocena projektu
Powiązane charakterystyki kierunkowe: CC_U06, SI_U06
Powiązane charakterystyki obszarowe:

Charakterystyka U2_04

potrafi pracować indywidualnie, w zespole oraz kierować niedużym zespołem
Weryfikacja: Ocena projektu
Powiązane charakterystyki kierunkowe: CC_U02, SI_U02
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka K2_01

ma świadomość odpowiedzialności za wspólnie realizowane zadania w ramach pracy zespołowej
Weryfikacja: Ocena projektu
Powiązane charakterystyki kierunkowe: SI_K04, CC_K04
Powiązane charakterystyki obszarowe: