Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Analiza algorytmów

Informacje ogólne

Kod przedmiotu: 103D-INIIT-ISP-AAL Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Analiza algorytmów
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Algorytmy i języki - albo - Projektowanie systemów )-Inżynieria systemów informatycznych-inż.-EITI
( Algorytmy i języki programowania )-Inżynieria systemów informatycznych-inż.-EITI
( Przedmioty techniczne )---EITI
Punkty ECTS i inne: 4.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

AAL

Numer wersji:

4

Skrócony opis:

Prezentacja, w możliwie pragmatycznym ujęciu, głównych pojęć, metod i wyników analizy złożoności algorytmów obliczeniowych.

Pełny opis:

Prezentacja, w możliwie pragmatycznym ujęciu, głównych pojęć, metod i wyników analizy złożoności algorytmów obliczeniowych.



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


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). Technologia. 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.

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.



Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (w trakcie)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 66 miejsc więcej informacji
Wykład, 30 godzin, 66 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Grzegorz Blinowski, Kamil Deja, Łukasz Skonieczny, Paweł Zawistowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. letni" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 20 miejsc więcej informacji
Wykład, 30 godzin, 20 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Łukasz Skonieczny, Bartłomiej Twardowski, Paweł Zawistowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 66 miejsc więcej informacji
Wykład, 30 godzin, 66 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Łukasz Skonieczny, Tomasz Trzciński, Bartłomiej Twardowski, Paweł Zawistowski, Kamil Żbikowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. letni" (zakończony)

Okres: 2018-02-19 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 20 miejsc więcej informacji
Wykład, 30 godzin, 20 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Paweł Radziszewski, Łukasz Skonieczny
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. zimowy" (zakończony)

Okres: 2017-10-01 - 2018-02-18
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 66 miejsc więcej informacji
Wykład, 30 godzin, 66 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Łukasz Skonieczny
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. letni" (zakończony)

Okres: 2017-02-20 - 2017-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 24 miejsc więcej informacji
Wykład, 30 godzin, 24 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Łukasz Skonieczny
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. zimowy" (zakończony)

Okres: 2016-10-01 - 2017-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 65 miejsc więcej informacji
Wykład, 30 godzin, 65 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Łukasz Skonieczny
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. letni" (zakończony)

Okres: 2016-02-23 - 2016-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Łukasz Skonieczny
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. zimowy" (zakończony)

Okres: 2015-10-01 - 2016-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 62 miejsc więcej informacji
Wykład, 30 godzin, 62 miejsc więcej informacji
Koordynatorzy: Łukasz Skonieczny
Prowadzący grup: Łukasz Skonieczny
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. letni" (zakończony)

Okres: 2015-02-23 - 2015-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 36 miejsc więcej informacji
Wykład, 30 godzin, 36 miejsc więcej informacji
Koordynatorzy: Andrzej Pająk
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. zimowy" (zakończony)

Okres: 2014-09-29 - 2015-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 37 miejsc więcej informacji
Wykład, 30 godzin, 37 miejsc więcej informacji
Koordynatorzy: Andrzej Pająk
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2013/2014 - sem. letni" (zakończony)

Okres: 2014-02-24 - 2014-09-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 23 miejsc więcej informacji
Wykład, 30 godzin, 23 miejsc więcej informacji
Koordynatorzy: Andrzej Pająk
Prowadzący grup: Andrzej Pająk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.