Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Analiza algorytmów
Koordynator przedmiotu:
Andrzej PAJĄK
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne
Kod przedmiotu:
AAL
Semestr nominalny:
5 / rok ak. 2015/2016
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
udział w wykładach 30 godz. udział w spotkaniach projektowych 15 godz. przygotowanie do sprawdzianu i egzaminu 30 godz. samodzielna realizacja projektów 45 godz.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
udział w wykładach 30 godz. udział w spotkaniach projektowych 15 godz. w sumie 45 godz. co daje ok. 1,5 ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
udział w spotkaniach projektowych 15 godz. samodzielna realizacja projektów 45 godz. w sumie 60 godz. co daje 2 ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt30h
  • Lekcje komputerowe0h
Wymagania wstępne:
Brak
Limit liczby studentów:
40
Cel przedmiotu:
Prezentacja, w możliwie pragmatycznym ujęciu, głównych pojęć, metod i wyników analizy złożoności i projektowania algorytmów obliczeniowych.
Treści kształcenia:
Treść wykładu Wprowadzenie do tematyki (2h). Problemy algorytmizowalne, algorytmy i programy, modele obliczeń; klasy złożoności problemów i algorytmów sekwencyjnych; rozmiar problemu, złożoność czasowa i pamięciowa; złożoność pesymistyczna, oczekiwana, zamortyzowana, oszacowania asymptotyczne; redukowalność algorytmów, kres górny złożoności, kres dolny i algorytmy optymalne. Techniki analizy (4h). Notacja asymptotyczna. Elementarne techniki analizy złożoności pesymistycznej i oczekiwanej; równania rekurencyjne liniowe jednorodne i niejednorodne, twierdzenie o rozwiązaniu równania z niejednorodnością wielomianowo-wykładniczą. Równania dekompozycji, postać kanoniczna Bentleya-Hakena-Saxe'a rozwiązywania równań dekompozycji. Funkcje tworzące. Przykłady analizy - algorytmy i struktury podstawowe (4h). Algorytmy Karatsuby i Strassena; analiza złożoności operacji dla kopców binarnych (heaps), algorytm selekcji, liniowy algorytm z medianą median, badanie ograniczenia dolnego dla operacji selekcji. Operacje na zbiorach, algorytmy UNION-FIND,zastosowania w problemach równoważności, algorytm Kruskala, dla drzew rozpinających. Dekompozycja wielowymiarowa (6h). Schemat dekompozycji i omiatania dla problemów geometrycznych, problemy globalne i przepytywania. Dominacja punktów w zbiorach wielowymiarowych; wyznaczanie punktów ekstremalnych. Problemy związane z metrykami (analiza bliskości). Przeszukiwanie zakresowe, drzewa dychotomiczne, k-d drzewa i drzewa zakresowe. Usuwanie degeneracji w problemach geometrycznych. Problemy optymalizacji (6h). Metody rozwiązywania i złożoność problemów optymalizacji. Metoda odrywania i algorytmy zachłanne. Algorytmy Kruskala, Prima, Dijkstry. Pojecie matroidu. Programowanie dynamiczne w problemach sieciowych i drzewach szukania, algorytm Floyda. Algorytmy szukania z nawrotami, metoda rozgałęzień i ograniczeń, algorytm Little'a dla problemu komiwojażera. Algorytm Helda-Karpa dla grafów nieskierowanych. Metoda transformacji dziedziny (2h). Dyskretna transformata Fouriera w dziedzinie zespolonej; FFT w ciałach skończonych i szybkie mnożenie wielomianów; szybkie mnożenie wielkich liczb. Klasy złożoności (2h). Modele obliczeń; problemy decyzyjne, obliczeniowe i optymalizacyjne. Model niedeterministyczny, klasy P i NP, problemy NP-trudne i NP-zupełne, problemy spełnialności, twierdzenie Cooka, technika dowodzenia przynależności problemów do klasy NPC, przykłady problemów w klasie NP. Klasyfikacja Gareya. Algorytmy aproksymacyjne (2h). Terminologia. Aproksymacje dla problemu minimalnego pokrycia wierzchołkowego grafu. Aproksymacje dla problemu komiwojażera (TSP), algorytm Christofidesa, ulepszanie iteracyjne. Twierdzenie o niemocy. Mataheurystyki, symulowane wyżarzanie, metodyka GRASP, tabu search, algorytmy genetyczne i ewolucyjne, algorytmy mrówkowe. Zakres projektu W ramach projektu studenci opracowują algorytmy dla zadanych problemów wymagających użycia kilku algorytmów podstawowych i przeprowadzają analizę złożoności pesymistycznej oraz pomiary czasu. Proponowane problemy projektowe dotyczą algorytmów geometrycznych, kombinatorycznych, optymalizacji, przetwarzania tekstów, symulacji sterowanej zdarzeniami, przetwarzania w grafach.
Metody oceny:
sprawdziany; projekt semestralny; egzamin
Egzamin:
tak
Literatura:
1. Cormen T, Leiserson Ch, Rivest R: Wprowadzenie do algorytmów, WNT, Warszawa 1997, 2001, 2004. 2. Aho A.V, Hopcroft J.E, Ullman J.D: Projektowanie i Analiza Algorytmów, Helion, Gliwice 2003. 3. Sedgewick R: Algorytmy w C++ (1999); Algorytmy w C++: grafy (2003), ReadMe, Warszawa. 4. Reingold E.M., Nievergelt J., Deo N. : Algorytmy Kombinatoryczne, WNT, Warszawa 1985. Literatura uzupełniająca 1. Skiena S, Revilla M: Wyzwania programistyczne, WSiP, Wwa 2004. 2. Lipski W.: Kombinatoryka dla Programistów, WNT, Warszawa 1982; 2004. 3. Banachowski L., Kreczmar A., Rytter W.: Analiza Algorytmów i Struktur Danych, WNT, Warszawa 1987; 1989. 4. Sysło M., Deo N., Kowalik J.: Algorytmy Optymalizacji Dyskretnej, PWN, Warszawa 1993; 1999.
Witryna www przedmiotu:
https://studia.elka.pw.edu.pl/priv/12L/AAL.A/
Uwagi:
Brak

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt AAL_W01
ma uporządkowaną wiedzę na temat podstawowych pojęć związanych z analizą złożoności obliczeniowej algorytmów, technik analizy z wykorzystaniem równań rekurencyjnych liniowych i równań dekompozycji
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_W11
Powiązane efekty obszarowe: T1A_W03
Efekt AAL_W02
ma uporządkowaną wiedzę na temat złożoności quasioptymalnych algorytmów podstawowych (szukanie, sortowanie, selekcja)
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_W11
Powiązane efekty obszarowe: T1A_W03
Efekt AAL_W03
ma uporządkowaną wiedzę na tematmetody dekompozycji wielowymiarowej dla problemów geometrycznych w zbiorach punktów
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_W11, K_W19
Powiązane efekty obszarowe: T1A_W03, T1A_W07
Efekt AAL_W04
ma uporządkowaną wiedzę na tematmetod optymalizacji dyskretnej z użyciem strategii zachłannej, programowania dynamicznego, rozgałęzień i ograniczeń
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_W09, K_W11, K_W19
Powiązane efekty obszarowe: T1A_W04, T1A_W03, T1A_W07
Efekt AAL_W05
ma uporządkowaną wiedzę na tematmetody transformacji dziedziny, w tym FFT
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_W19
Powiązane efekty obszarowe: T1A_W07
Efekt AAL_W06
ma uporządkowaną wiedzę na tematnajważniejszych klas złożoności i metod aproksymacji rozwiązań problemów NP-trudnych
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_W09, K_W11
Powiązane efekty obszarowe: T1A_W04, T1A_W03

Profil ogólnoakademicki - umiejętności

Efekt AAL_U01
potrafi znaleźć asymptotykę i rozwiązanie dokładne równania rekurencyjnego liniowego
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_U02
Powiązane efekty obszarowe: T1A_U08, T1A_U09
Efekt AAL_U02
potrafi rozwiązać nietrywialny problem obliczeniowy i ocenić złożoność asymptotyczną algorytmu
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_U01, K_U05
Powiązane efekty obszarowe: T1A_U09, T1A_U01, T1A_U15
Efekt AAL_U03
potrafi zaplanować i przeprowadzić systematyczne testowanie algorytmu i pomiary czasu wykonania
Weryfikacja: projekt semestralny
Powiązane efekty kierunkowe: K_U02, K_U13, K_U19
Powiązane efekty obszarowe: T1A_U08, T1A_U09, T1A_U16, T1A_U16
Efekt AAL_U04
potrafi rozpoznać stosowalność i wykorzystać odpowiednią metodę do rozwiązania problemu optymalizacji dyskretnej
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_U20
Powiązane efekty obszarowe: T1A_U13, T1A_U15
Efekt AAL_U05
potrafi rozpoznać i potwierdzić przynależności problemu do klasy NP-trudnych lub NP-zupełnych
Weryfikacja: projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_U01, K_U02
Powiązane efekty obszarowe: T1A_U09, T1A_U08, T1A_U09
Efekt AAL_U06
potrafi zaproponować metodę aproksymacji dla problemu NP-trudnego
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe: K_U02, K_U13
Powiązane efekty obszarowe: T1A_U08, T1A_U09, T1A_U16
Efekt AAL_U07
potrafi przestrzegać przyjętego stylu kodowania i dokumentowania projektów algorytmicznych
Weryfikacja: projekt semestralny
Powiązane efekty kierunkowe: K_U13, K_U20
Powiązane efekty obszarowe: T1A_U16, T1A_U13, T1A_U15

Profil ogólnoakademicki - kompetencje społeczne

Efekt AAL_K01
potrafi planować działania projektowe wg wymaganego terminu
Weryfikacja: projekt semestralny
Powiązane efekty kierunkowe: K_K04
Powiązane efekty obszarowe: T1A_K04
Efekt AAL_K02
potrafi samodzielnie pozyskiwać poszerzające informacje o rozwiązywanym problemie
Weryfikacja: projekt semestralny
Powiązane efekty kierunkowe: K_K01
Powiązane efekty obszarowe: T1A_K01