Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 64: | Linia 64: | ||
* [[Algorytmy i struktury danych/Wstęp: poprawność i złożoność algorytmu|Wstęp: poprawność i złożoność algorytmu]] ([[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]]) | ||
* [[Algorytmy i struktury danych/Wstęp: podstawowe techniki algorytmiczne i struktury danych|Wstęp: podstawowe techniki algorytmiczne i struktury danych]] ([[ASD Ćwiczenia 2|Ćwiczenia]]) | * [[Algorytmy i struktury danych/Wstęp: podstawowe techniki algorytmiczne i struktury danych|Wstęp: podstawowe techniki algorytmiczne i struktury danych]] ([[ASD Ćwiczenia 2|Ćwiczenia]]) | ||
* [[ASD Moduł 3| Sortowanie przez porównania: BubleSort, SelectionSort i InsertionSort]] ([[ASD Ćwiczenia 3|Ćwiczenia]]) | * [[Algorytmy i struktury danych/ASD Moduł 3| Sortowanie przez porównania: BubleSort, SelectionSort i InsertionSort]] ([[ASD Ćwiczenia 3|Ćwiczenia]]) | ||
* [[ASD Moduł 4| Sortowanie przez porównania: HeapSort, MergeSort i QuickSort ]] ([[ASD Ćwiczenia 4|Ćwiczenia]]) | * [[Algorytmy i struktury danych/ASD Moduł 4| Sortowanie przez porównania: HeapSort, MergeSort i QuickSort ]] ([[ASD Ćwiczenia 4|Ćwiczenia]]) | ||
* [[ASD Moduł 5| Sortowanie: dolna granica, sortowanie pozycyjne]] ([[ASD Ćwiczenia 5|Ćwiczenia]]) | * [[Algorytmy i struktury danych/ASD Moduł 5| Sortowanie: dolna granica, sortowanie pozycyjne]] ([[ASD Ćwiczenia 5|Ćwiczenia]]) | ||
* [[Algorytmy_i_struktury_danych/Selekcja| Selekcja]] ([[ASD Ćwiczenia 6|Ćwiczenia]]) | * [[Algorytmy_i_struktury_danych/Selekcja| Selekcja]] ([[ASD Ćwiczenia 6|Ćwiczenia]]) | ||
* [[Algorytmy_i_struktury_danych/Wyszukiwanie| Wyszukiwanie]] ([[ASD Ćwiczenia 7|Ćwiczenia]]) | * [[Algorytmy_i_struktury_danych/Wyszukiwanie| Wyszukiwanie]] ([[ASD Ćwiczenia 7|Ćwiczenia]]) | ||
| Linia 72: | Linia 72: | ||
* [[Algorytmy_i_struktury_danych/Kolejki priorytetowe| Kolejki priorytetowe]] ([[ASD Ćwiczenia 9|Ćwiczenia]]) | * [[Algorytmy_i_struktury_danych/Kolejki priorytetowe| Kolejki priorytetowe]] ([[ASD Ćwiczenia 9|Ćwiczenia]]) | ||
* [[Algorytmy_i_struktury_danych/Find-Union| Find-Union]] ([[ASD Ćwiczenia 10|Ćwiczenia]]) | * [[Algorytmy_i_struktury_danych/Find-Union| Find-Union]] ([[ASD Ćwiczenia 10|Ćwiczenia]]) | ||
* [[ASD Moduł 11| Algorytmy grafowe - najkrótsze ścieżki]] ([[ASD Ćwiczenia 11|Ćwiczenia]]) | * [[Algorytmy i struktury danych/ASD Moduł 11| Algorytmy grafowe - najkrótsze ścieżki]] ([[ASD Ćwiczenia 11|Ćwiczenia]]) | ||
* [[ASD Moduł 12| Algorytmy grafowe - przeszukiwanie w głąb]] ([[ASD Ćwiczenia 12|Ćwiczenia]]) | * [[Algorytmy i struktury danych/ASD Moduł 12| Algorytmy grafowe - przeszukiwanie w głąb]] ([[ASD Ćwiczenia 12|Ćwiczenia]]) | ||
* [[Algorytmy i struktury danych/Algorytmy tekstowe I| Algorytmy tekstowe I]] ([[ASD Ćwiczenia 13|Ćwiczenia]]) | * [[Algorytmy i struktury danych/Algorytmy tekstowe I| Algorytmy tekstowe I]] ([[ASD Ćwiczenia 13|Ćwiczenia]]) | ||
* [[Algorytmy_i_struktury_danych/Algorytmy_tekstowe_II| Algorytmy tekstowe II]] ([[ASD Ćwiczenia 14|Ćwiczenia]]) | * [[Algorytmy_i_struktury_danych/Algorytmy_tekstowe_II| Algorytmy tekstowe II]] ([[ASD Ćwiczenia 14|Ćwiczenia]]) | ||
* [[ASD Moduł 15| NP-zupełność]] ([[ASD Ćwiczenia 15|Ćwiczenia]]) | * [[Algorytmy i struktury danych/ASD Moduł 15| NP-zupełność]] ([[ASD Ćwiczenia 15|Ćwiczenia]]) | ||
=== Literatura === | === Literatura === | ||
# ''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. | # ''Wprowadzenie do algorytmów'', Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004. | ||
Wersja z 12:43, 18 wrz 2006
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
- Wojciech Rytter,
- Krzysztof Diks
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
- Wstęp: poprawność i złożoność algorytmu (Ćwiczenia)
- Wstęp: podstawowe techniki algorytmiczne i struktury danych (Ćwiczenia)
- Sortowanie przez porównania: BubleSort, SelectionSort i InsertionSort (Ćwiczenia)
- Sortowanie przez porównania: HeapSort, MergeSort i QuickSort (Ćwiczenia)
- Sortowanie: dolna granica, sortowanie pozycyjne (Ćwiczenia)
- Selekcja (Ćwiczenia)
- Wyszukiwanie (Ćwiczenia)
- Słowniki (Ćwiczenia)
- Kolejki priorytetowe (Ćwiczenia)
- Find-Union (Ćwiczenia)
- Algorytmy grafowe - najkrótsze ścieżki (Ćwiczenia)
- Algorytmy grafowe - przeszukiwanie w głąb (Ćwiczenia)
- Algorytmy tekstowe I (Ćwiczenia)
- Algorytmy tekstowe II (Ćwiczenia)
- NP-zupełność (Ćwiczenia)
Literatura
- 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.
