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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Walen (dyskusja | edycje)
177 edycji
 
(Nie pokazano 71 wersji utworzonych przez 7 użytkowników)
Linia 6: Linia 6:
== Sylabus ==
== Sylabus ==
=== Autorzy ===
=== Autorzy ===
* Wojciech Rytter,
* Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Krzysztof Diks
* Adam Malinowski — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
* Tomasz Waleń — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki


=== Wymagania wstępne ===
=== Wymagania wstępne ===
Linia 16: Linia 18:


=== Zawartość ===
=== Zawartość ===
* Podstawowe zasady analizy algorytmów
* Podstawowe zasady analizy algorytmów:
** poprawność
** poprawność
** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, koszt zamortyzowany)
** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana)
** złożoność problemu algorytmicznego
**koszt zamortyzowany: metoda potencjału
* Sortowanie
* Podstawowe techniki i struktury:
**metoda ''dziel i zwyciężaj''
**metoda zachłanna
**pogramowanie dynamiczne
**transformacyjna konstrukcja algorytmu
**elementarne struktury danych: stosy, kolejki, listy
* Sortowanie:
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
** HeapSort i kopce binarne
** proste kolejki priorytetowe: kopce binarne
**HeapSort
** sortowanie pozycyjne
** złożoność problemu sortowania
** złożoność problemu sortowania
** sortowanie pozycyjne
* Selekcja:
* Selekcja
** algorytm Hoare'a
** algorytm Hoare'a
** algorytm ''magicznych piątek''
** algorytm ''magicznych piątek''
* Wyszukiwanie
* Wyszukiwanie i proste słowniki:
** liniowe
** wyszukiwanie liniowe i binarne
** binarne
** prosty słownik: drzewa poszukiwań binarnych
** drzewa poszukiwań binarnych
** haszowanie
** haszowanie
* Złożone struktury danych
* Efektywne implementacje słownika:
** słowniki i ich implementacje - zrównoważone drzewa poszukiwań binarnych, drzewa typu ''splay'', B-drzewa
** drzewa AVL
** kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego
** drzewa typu ''splay''
** sumowanie zbiorów rozłącznych
** B-drzewa
* Algorytmy grafowe
*  Złożone struktury danych:
** wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego
** efektywne sumowanie zbiorów rozłącznych
* Algorytmy grafowe:
** DFS i jego zastosowania
** DFS i jego zastosowania
** problemy ścieżkowe -- Algorytm Dijkstry
** problemy ścieżkowe -- Algorytm Dijkstry
** minimalne drzewo rozpinające
** minimalne drzewo rozpinające
* Algorytmy tekstowe
* Wyszukiwanie wzorca w tekstach:
** wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora
** prefikso-sufiksy
** kompresja tekstów
** algorytm Knutha-Morisa-Pratta
* NP-zupełność
*Tekstowe struktury danych:
**tablice sufiksowe
**drzewa sufiksowe
* NP-zupełność:
** klasa NP
** klasa NP
** problemy NP-trudne i NP-zupełne
** problemy NP-trudne i NP-zupełne
Linia 50: Linia 64:
=== Moduły===
=== Moduły===


* [[ASD Moduł 1| Wstęp]] ([[ASD Ćwiczenia 1|Ćwiczenia]])
* [[Algorytmy i struktury danych/Wstęp: poprawność i złożoność algorytmu|Wstęp: poprawność i złożoność algorytmu]] ([[ASD Ćwiczenia 1|Ćwiczenia]])
* [[ASD Moduł 2| ???]] ([[ASD Ćwiczenia 2|Ćwiczenia]])
* [[Algorytmy i struktury danych/Wstęp: elementarne techniki algorytmiczne i struktury danych|Wstęp: elementarne techniki algorytmiczne i struktury danych]] ([[ASD Ćwiczenia 2|Ćwiczenia]])
* [[ASD Moduł 3| ???]] ([[ASD Ćwiczenia 3|Ćwiczenia]])
* [[Algorytmy i struktury danych/Sortowanie - BubbleSort, SelectionSort, InsertionSort| Sortowanie przez porównania: BubleSort, SelectionSort i InsertionSort]] ([[ASD Ćwiczenia 3|Ćwiczenia]])
* [[ASD Moduł 4| ???]] ([[ASD Ćwiczenia 4|Ćwiczenia]])
* [[Algorytmy i struktury danych/Sortowanie: MergeSort, HeapSort i QuickSort| Sortowanie przez porównania: MergeSort, HeapSort i QuickSort ]] ([[ASD Ćwiczenia 4|Ćwiczenia]])
* [[ASD Moduł 5| ???]] ([[ASD Ćwiczenia 5|Ćwiczenia]])
* [[Algorytmy i struktury danych/Sortowanie: dolna granica i sortowanie pozycyjne| Sortowanie: dolna granica, sortowanie pozycyjne]] ([[ASD Ćwiczenia 5|Ćwiczenia]])
* [[ASD Moduł 6| ???]] ([[ASD Ćwiczenia 6|Ćwiczenia]])
* [[Algorytmy_i_struktury_danych/Selekcja| Selekcja]] ([[ASD Ćwiczenia 6|Ćwiczenia]])
* [[ASD Moduł 7| ???]] ([[ASD Ćwiczenia 7|Ćwiczenia]])
* [[Algorytmy_i_struktury_danych/Wyszukiwanie| Wyszukiwanie]] ([[ASD Ćwiczenia 7|Ćwiczenia]])
* [[ASD Moduł 8| ???]] ([[ASD Ćwiczenia 8|Ćwiczenia]])
* [[Algorytmy_i_struktury_danych/Słowniki| Słowniki]] ([[ASD Ćwiczenia 8|Ćwiczenia]])
* [[ASD Moduł 9| ???]] ([[ASD Ćwiczenia 9|Ćwiczenia]])
* [[Algorytmy_i_struktury_danych/Kolejki priorytetowe| Kolejki priorytetowe]] ([[ASD Ćwiczenia 9|Ćwiczenia]])
* [[ASD Moduł 10| ???]] ([[ASD Ćwiczenia 10|Ćwiczenia]])
* [[Algorytmy_i_struktury_danych/Find-Union| Find-Union]] ([[ASD Ćwiczenia 10|Ćwiczenia]])
* [[ASD Moduł 11| ???]] ([[ASD Ćwiczenia 11|Ćwiczenia]])
* [[Algorytmy i struktury danych/Algorytmy grafowe - najlżejsze ścieżki| Algorytmy grafowe - najlżejsze ścieżki]] ([[ASD Ćwiczenia 11|Ćwiczenia]])
* [[ASD Moduł 12| ???]] ([[ASD Ćwiczenia 12|Ćwiczenia]])
* [[Algorytmy i struktury danych/Przeszukiwanie grafów| Algorytmy grafowe - przeszukiwanie grafów]] ([[ASD Ćwiczenia 12|Ćwiczenia]])
* [[ASD Moduł 13| ???]] ([[ASD Ćwiczenia 13|Ćwiczenia]])
* [[Algorytmy i struktury danych/Algorytmy tekstowe I| Algorytmy tekstowe I]] ([[ASD Ćwiczenia 13|Ćwiczenia]])
* [[ASD Moduł 14| ???]] ([[ASD Ćwiczenia 14|Ćwiczenia]])
* [[Algorytmy_i_struktury_danych/Algorytmy_tekstowe_II| Algorytmy tekstowe II]] ([[ASD Ćwiczenia 14|Ćwiczenia]])
* [[ASD Moduł 15| ???]] ([[ASD Ćwiczenia 15|Ćwiczenia]])
* [[Algorytmy i struktury danych/NP-zupełność| NP-zupełność]] ([[ASD Ćwiczenia 15|Ćwiczenia]])


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

Aktualna wersja na dzień 09:29, 2 sty 2007

Forma zajęć

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

Opis

Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.

Sylabus

Autorzy

  • Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Adam Malinowski — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Tomasz Waleń — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

Wymagania wstępne

  • Wstęp do programowania
  • Metody programowania
  • Matematyka dyskretna
  • Logika i teoria mnogości

Zawartość

  • Podstawowe zasady analizy algorytmów:
    • poprawność
    • złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana)
    • koszt zamortyzowany: metoda potencjału
  • Podstawowe techniki i struktury:
    • metoda dziel i zwyciężaj
    • metoda zachłanna
    • pogramowanie dynamiczne
    • transformacyjna konstrukcja algorytmu
    • elementarne struktury danych: stosy, kolejki, listy
  • Sortowanie:
    • sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
    • proste kolejki priorytetowe: kopce binarne
    • HeapSort
    • sortowanie pozycyjne
    • złożoność problemu sortowania
  • Selekcja:
    • algorytm Hoare'a
    • algorytm magicznych piątek
  • Wyszukiwanie i proste słowniki:
    • wyszukiwanie liniowe i binarne
    • prosty słownik: drzewa poszukiwań binarnych
    • haszowanie
  • Efektywne implementacje słownika:
    • drzewa AVL
    • drzewa typu splay
    • B-drzewa
  • Złożone struktury danych:
    • wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego
    • efektywne sumowanie zbiorów rozłącznych
  • Algorytmy grafowe:
    • DFS i jego zastosowania
    • problemy ścieżkowe -- Algorytm Dijkstry
    • minimalne drzewo rozpinające
  • Wyszukiwanie wzorca w tekstach:
    • prefikso-sufiksy
    • algorytm Knutha-Morisa-Pratta
  • Tekstowe struktury danych:
    • tablice sufiksowe
    • drzewa sufiksowe
  • NP-zupełność:
    • klasa NP
    • problemy NP-trudne i NP-zupełne

Moduły

Literatura

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