| Nr | Data | Treść | Literatura |
| 1 | 21-02-2004 | Pojęcie algorytmu. Poprawność algorytmów. Przykłady problemów algorytmicznych i algorytmów. Metody dowodzenia poprawności algorytmów. | Poprawność: [Har] 104, [Per] 43, [BDR] 23 |
| 2 | 28-02-2004 | Złożoność algorytmów. Złożoność czasowa i pamięciowa algorytmów. Rząd wielkości funkcji, notacja asymptotyczna. Koszt pesymistyczny, średni. Przykłady: Wyszukiwanie liniowe i binarne. |
Złożoność: [BDR] 13-17 Wysz. binarne: [Har] 141, [Per] 20 Notacja asymp.: [BDR] 17, [Cor] 31, 45 |
| 3 | 06-03-2004 | Proste struktury danych. Listy jedno- i dwukierunkowe. Przykłady prostych operacji na listach. Stosy. Kolejki FIFO. Definicja grafu; przykłady. Implementacja grafów (macierz sąsiedztwa, listy sąsiedztwa); operacje dodawania i usuwania krawędzi w grafie. | Zmienne dynamiczne: [Wir] 186 Listy, Kolejki, Stosy: [Wir] 192, [BDR] 25, [Cor] 236 Grafy: [BDR] 28, [Cor] 113, 526 |
| 4 | 13-03-2004 | Zaawansowane struktury danych. Definicja drzewa. Implementacja drzew (drzewa binarne, o stałym stopniu, lewy syn - prawy brat). Drzewa BST. Informacja o zrównoważonych drzewach BST. Wykorzystanie drzew BST do problemu słownika. | Drzewa: [BDR] 33, [Cor] 117, 249, [Wir] 211 Drzewa BST: [BDR] 105, [Wir] 211, [Cor] 284 Drzewa zrównoważone: [BDR] 113, [Wir] 237 |
| 5 | 20-03-2004 | Metody projektowania efektywnych algorytmów. Opis najważniejszych metod projektowania algorytmów wraz z przykładami. Algorytmy zachłanne - algorytm Kruskala; Backtracking - 8 hetmanów. |
Backtracking: [Wir] 158 Programowanie zachłanne: [BDR] 41, [Cor] 375, [Har] 100 alg. Kruskala[Cor] |
| 6 | 27-03-2004 | Metody projektowania efektywnych algorytmów cd. Dziel i zwyciężaj - Mergesort; programowanie dynamiczne - Najdłuższy wspólny podciąg |
Dziel i zwyciężaj: [Cor] 32, [BDR] 40, 86, [Har] 97 Prog. dynam.: [BDR] 40, 190 [Cor] 346 |
| 7 | 03-04-2004 | Zaawansowane struktury danychProblem kolejki priorytetowej. Rozwiązanie z użyciem kopców binarnych. Sortowanie kopcowe (heapsort). |
Kopce: [BDR] 70, [Cor] 173, [Per] 136 |
| - | 17-04-2004 | NIE MA WYKŁADU! | |
| 8 | 24-04-2004 | Algorytmy sortowania. Przegląd algorytmów sortowania: Insertionsort (przypomnienie), Selectionsort, Mergesort (przypomnienie), QuickSort i złożoność oczekiwana, Heapsort (przypomnienie), sortowanie przez zliczanie, pozycyjne. Stabilne algorytmy sortowania. Informacja o dolnym ograniczeniu dla problemu sortowania przez porównania. |
Sortowanie [BDR] 49, [Wir] 73, [Cor] 173 |
| 9 | 08-05-2004 |
Algorytmy selekcji.
Algorytmy selekcji: wyszukiwanie binarne (przypomnienie), algorytm Hoare'a. Algorytmy teorioliczbowe. NWD: algorytm Euklidesa (zwykły, binarny) |
Selekcja [BDR] 83, [Wir] 101, [Cor] 220 NWD i alg. Euklidesa [Cor] 905 |
| 10 | 15-05-2004 | Algorytmy grafowe. Przeszukiwanie wszerz. Zastosowanie: najkrótsze ścieżki. Przeszukiwanie grafu w głąb. Zastosowania: spójne składowe, sortowanie topologiczne, 2-kolorowanie. Algorytm Dijkstry. |
Algorytmy grafowe [Cor], [BDR] Przeszukiwanie wszerz [Cor] 530, [BDR] 32 Przeszukiwanie w głąb [Cor] 539, [BDR] 31 alg. Dijkstry [BDR] 254, [Cor] 593 |
| 11 | 22-05-2004 | Algorytmy geometryczne. Problem przynależności. Wypukła otoczka (dziel i rządź, alg. Jarvisa, alg. przyrostowy). | [BDR] 258, [Cor] 990 |
| 12 | 29-05-2004 | Algorytmy tekstowe. Wyszukiwanie wzorca: algorytm naiwny i algorytm Knutha-Morrisa-Pratta. |
[BDR] 164 [Cor] 972 |
| 13 | 05-06-2004 | NP-zupełność, Klasy złożoności P, NP, problemy NP-zupełnych. Problem P=NP. Przykłady problemów NP-zupełnych. |
NP - zupełność [Cor] 1022-1068, [Har] 175-190 |
| 14 | 12-06-2004 | Algorytmy aproksymacyjne, Problemy off-line i on-line. Przykłady algorytmów off-line: Alg. Gavrilla dla problemu min. pokrycia wierzchołkowego, Alg. dla problemu komiwojażera z nierównością trójkąta. | alg. aproks. [Cor] 1073 |
| 15 | 19-06-2004 | Rozwiązywanie zadań olimpijskich Przykłady zadań pochodzących z Olimpiad Informatycznych. Sposób oceniania zadań przez jurorów. Techniki rozwiązywania. |
[OI1]-[OI10] http://www.oi.edu.pl |