MIMINF:Algorytmy i struktury danych: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Diks (dyskusja | edycje)
538 edycji
Rytter (dyskusja | edycje)
830 edycji
 
(Nie pokazano 6 wersji utworzonych przez 2 użytkowników)
Linia 2: Linia 2:
Wykład (30 godzin) + ćwiczenia (30 godzin) + laboratorium (30 godzin)
Wykład (30 godzin) + ćwiczenia (30 godzin) + laboratorium (30 godzin)
== Opis ==
== Opis ==
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych. Doskonalenie praktycznych umiejętnosci w projektowaniu i programowaniu  poprawnych i wydajnych algorytmow oraz w posługiwaniu się gotowymi bibliotekami algorytmów i struktur danych.


== Sylabus ==
== Sylabus ==
=== Autorzy ===
=== Autorzy ===  
* Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki Informatyki i Mechaniki


=== Wymagania wstępne ===
=== Wymagania wstępne ===
Linia 19: Linia 19:
* Podstawowe zasady analizy algorytmów:
* Podstawowe zasady analizy algorytmów:
** poprawność
** poprawność
** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana)
** złożoność obliczeniowa algorytmu (czasowa i pamieciowa, pesymistyczna i oczekiwana, koszt zamortyzowany)
**koszt zamortyzowany: metoda potencjału
** złożoność problemu algorytmicznego a złożoność algorytmu - dolne granice, metody analizy złożoności
* Podstawowe techniki i struktury:
* Metody projektowania wydajnych algorytmów:
**metoda ''dziel i zwyciężaj''
** metoda ''dziel i zwyciężaj''
**metoda zachłanna
** algorytmy zachłanne
**pogramowanie dynamiczne
** pogramowanie dynamiczne
**transformacyjna konstrukcja algorytmu  
** przeszukiwanie z nawrotami i metoda podziału i ograniczeń
**elementarne struktury danych: stosy, kolejki, listy
** transformacyjna konstrukcja algorytmu  
* Sortowanie:
* Sortowanie:
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
** sortowanie przez porównania (sortowanie przez wstawianie - ''InsertionSort'', sortowanie szybkie - ''QuickSort'', sortowanie przez scalanie - ''MergeSort'')
** proste kolejki priorytetowe: kopce binarne
** proste kolejki priorytetowe: kopce binarne
**HeapSort  
** sortowanie kopcowe - ''HeapSort''
** sortowanie pozycyjne
** sortowanie pozycyjne
** złożoność problemu sortowania
** złożoność problemu sortowania
Linia 36: Linia 36:
** algorytm Hoare'a
** algorytm Hoare'a
** algorytm ''magicznych piątek''
** algorytm ''magicznych piątek''
* Wyszukiwanie i proste słowniki:
* Wyszukiwanie i słowniki:
** wyszukiwanie liniowe i binarne
** wyszukiwanie liniowe i binarne
** prosty słownik: drzewa poszukiwań binarnych
** drzewa wyszukiwań binarnych, zrównoważone drzewa wyszukiwań binarnych (AVL, drzewa czerwono-czarne, drzewa typu ''splay'')
** haszowanie
** haszowanie (funkcje haszujące, haszowanie uniwersalne, metody rozwiązywania kolizji, haszowanie doskonałe)
* Efektywne implementacje słownika:
** drzewa AVL
** drzewa typu ''splay''
** B-drzewa
** B-drzewa
* Złożone struktury danych:
*Kolejki priorytetowe:
** wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego
**złączalne kolejki priorytetowe (kopce dwumianowe i Fibonacciego)
** efektywne sumowanie zbiorów rozłącznych
**algorytm Dijkstry
* Algorytmy grafowe:
*Problem "Find-Union" i jego zastosowania
** DFS i jego zastosowania
*Algorytmy grafowe:
** problemy ścieżkowe -- Algorytm Dijkstry
**komputerowe reprezentacje grafów
**metody przeszukiwania grafów i ich zastosowania - najkrótsze ścieżki, spójność, dwuspójność, silna spójność, sortowanie topologiczne 
** problemy ścieżkowe
** minimalne drzewo rozpinające
** minimalne drzewo rozpinające
** najliczniejsze skojarzenia w grafach dwudzielnych
* Wyszukiwanie wzorca w tekstach:
* Wyszukiwanie wzorca w tekstach:
** prefikso-sufiksy
** prefikso-sufiksy
Linia 57: Linia 57:
**tablice sufiksowe
**tablice sufiksowe
**drzewa sufiksowe
**drzewa sufiksowe
* NP-zupełność:
** klasa NP
** problemy NP-trudne i NP-zupełne


=== Literatura ===
=== Literatura ===
# ''Algorytmy i struktury danych'', L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
# L. Banachowski, K. Diks, W. Rytter, ''Algorytmy i struktury danych'', Wydawnictwa Naukowo - Techniczne, 2006.
# ''Wprowadzenie do algorytmów'', Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
# Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,  ''Wprowadzenie do algorytmów'', Wydawnictwa Naukowo - Techniczne, 2004.

Aktualna wersja na dzień 20:21, 29 paź 2006

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin) + laboratorium (30 godzin)

Opis

Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych. Doskonalenie praktycznych umiejętnosci w projektowaniu i programowaniu poprawnych i wydajnych algorytmow oraz w posługiwaniu się gotowymi bibliotekami algorytmów i struktur danych.

Sylabus

Autorzy

  • Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki Informatyki i Mechaniki

Wymagania wstępne

  • Wstęp do programowania
  • Matematyka dyskretna
  • Podstawy matematyki
  • Analiza matematyczna 1
  • Geometria z algebrą liniową

Zawartość

  • Podstawowe zasady analizy algorytmów:
    • poprawność
    • złożoność obliczeniowa algorytmu (czasowa i pamieciowa, pesymistyczna i oczekiwana, koszt zamortyzowany)
    • złożoność problemu algorytmicznego a złożoność algorytmu - dolne granice, metody analizy złożoności
  • Metody projektowania wydajnych algorytmów:
    • metoda dziel i zwyciężaj
    • algorytmy zachłanne
    • pogramowanie dynamiczne
    • przeszukiwanie z nawrotami i metoda podziału i ograniczeń
    • transformacyjna konstrukcja algorytmu
  • Sortowanie:
    • sortowanie przez porównania (sortowanie przez wstawianie - InsertionSort, sortowanie szybkie - QuickSort, sortowanie przez scalanie - MergeSort)
    • proste kolejki priorytetowe: kopce binarne
    • sortowanie kopcowe - HeapSort
    • sortowanie pozycyjne
    • złożoność problemu sortowania
  • Selekcja:
    • algorytm Hoare'a
    • algorytm magicznych piątek
  • Wyszukiwanie i słowniki:
    • wyszukiwanie liniowe i binarne
    • drzewa wyszukiwań binarnych, zrównoważone drzewa wyszukiwań binarnych (AVL, drzewa czerwono-czarne, drzewa typu splay)
    • haszowanie (funkcje haszujące, haszowanie uniwersalne, metody rozwiązywania kolizji, haszowanie doskonałe)
    • B-drzewa
  • Kolejki priorytetowe:
    • złączalne kolejki priorytetowe (kopce dwumianowe i Fibonacciego)
    • algorytm Dijkstry
  • Problem "Find-Union" i jego zastosowania
  • Algorytmy grafowe:
    • komputerowe reprezentacje grafów
    • metody przeszukiwania grafów i ich zastosowania - najkrótsze ścieżki, spójność, dwuspójność, silna spójność, sortowanie topologiczne
    • problemy ścieżkowe
    • minimalne drzewo rozpinające
    • najliczniejsze skojarzenia w grafach dwudzielnych
  • Wyszukiwanie wzorca w tekstach:
    • prefikso-sufiksy
    • algorytm Knutha-Morisa-Pratta
  • Tekstowe struktury danych:
    • tablice sufiksowe
    • drzewa sufiksowe

Literatura

  1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, Wydawnictwa Naukowo - Techniczne, 2006.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, Wydawnictwa Naukowo - Techniczne, 2004.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=MIMINF:Algorytmy_i_struktury_danych&oldid=64799”