Powrót |
| Algorytm: definicja, cechy algorytmu. Projektowanie algorytmu. Metody konstrukcji algorytmu. Klasy zadań algorytmicznych. Rekurencja. Metoda dziel i zwyciężaj. Algorytmy zachłanne. Programowanie dynamiczne. Redukcja. |
| Analiza algorytmów. Złożoność obliczeniowa. Przykłady analizy algorytmów. |
| Dynamiczne struktury danych: listy, stos, kolejki, drzewo, graf. Podstawowe operacje. |
| Sortowanie. Metody proste: bąbelkowe, sortowanie przez wstawianie, sortowanie przez selekcję, grzebieniowe, Shella. Szybkie metody sortowania: przez scalanie, kopcowe, szybkie. Metody hybrydowe: sortowanie hybrydowe, introspektywne. Inne metody sortowania: pozycyjne, przez zliczanie, kubełkowe. |
| Wyszukiwanie, statystyki pozycyjne i sortowanie częściowe. Przeszukiwanie sekwencji: sekwencyjne, binarne, interpolacyjne. Statystyki pozycyjne: wyznaczenie minimum/maksimum, wyznaczenie k-tej statystyki pozycyjnej, sortowanie częściowe, częściowy heap-sort, selekcja on-line, quick-select-sort, częściowy quick-sort, chunk-sort |
| Tablice mieszające. Funkcje mieszające: cechy dobrej funkcji haszującej, przegląd funkcji mieszających. Usuwanie kolizji: metoda łańcuchowa, adresowanie otwarte. |
| Wyszukiwanie wzorca. Algorytm naiwny. Algorytm Rabina-Karpa. Algorytm Knutha-Morrisa-Pratta. Algorytm Boyer-Moore'a. Algorytm oparty o automat skończony. |
| Drzewa. Kolejki priorytetowe: implementacja kopcowa. Drzewa poszukiwań binarnych: wyszukiwanie, wstawianie i usuwanie węzłów. Drzewa AVL: drzewa zrównoważone, rotacje, wstawianie węzłów, usuwanie węzłów. Drzewa czerwono-czarne: wstawianie węzła, usuwanie węzła. |
Powrót |