Co wypadałoby zawczasu wiedzieć, aby zrozumieć zamieszczony tu materiał? Zgłaszanie błędów 1. Co to są algorytmy i dlaczego warto poświęcać im uwagę? Poprawność Użytkowanie zasobów Algorytmy komputerowe dla niekomputerowców Algorytmy komputerowe dla komputerowców 2. Jak opisywać i oceniać algorytmy komputerowe Jak opisywać algorytmy komputerowe Jak charakteryzować czasy działania Niezmienniki pętli Rekursja 3. Algorytmy sortowania i wyszukiwania Wyszukiwanie binarne Sortowanie przez wybieranie Sortowanie przez wstawianie Sortowanie przez scalanie Sortowanie szybkie 4. Dolne ograniczenie sortowania i sposoby jego przezwyciężenia Reguły sortowania Dolne ograniczenie sortowania przez porównania Pokonywanie ograniczenia dolnego w sortowaniu przez zliczanie Sortowanie pozycyjne 5. Skierowane grafy acykliczne Skierowane grafy acykliczne Sortowanie topologiczne Jak reprezentować graf skierowany Czas działania sortowania topologicznego Ścieżka krytyczna w diagramie PERT Najkrótsza ścieżka w skierowanym grafie acyklicznym 6. Najkrótsze ścieżki Algorytm Dijkstry Prosta realizacja tablicowa Realizacja z kopcem binarnym Realizacja z użyciem kopca Fibonacciego Algorytm Bellmana-Forda Algorytm Floyda-Warshalla 7. Algorytmy napisowe Najdłuższy wspólny podciąg Zamiana napisu na inny Dopasowywanie napisów 8. Podstawy kryptografii Proste szyfry podstawieniowe Kryptografia z kluczem symetrycznym Podkładka jednorazowa Szyfry blokowe i łańcuchowanie Uzgadnianie wspólnych informacji Kryptografia z kluczem jawnym Kryptosystem RSA Jak wykonywać działania arytmetyczne na wielkich liczbach Jak znajdować duże liczby pierwsze Jak znaleźć liczbę względnie pierwszą z inną Jak obliczyć odwrotność multiplikatywną w arytmetyce modularnej Jak szybko podnieść liczbę do potęgi całkowitej Wykazanie, że funkcje FP i FS są wzajemnie odwrotnymi Kryptosystemy hybrydowe Obliczanie liczb losowych 9. Kompresja danych Kody Huffmana Adaptacyjne kody Huffmana Faksy Kompresja LZW Ulepszenia LZW 10. Trudne (?) problemy Brązowe furgonetki Klasy P i NP oraz NP-zupełność Problemy decyzyjne i redukcje Problem matka Próbnik problemów NP-zupełnych Spełnialność 3-CNF Klika Pokrycie wierzchołkowe Cykl Hamiltona i ścieżka Hamiltona Komiwojażer Najdłuższa ścieżka prosta Suma podzbioru Podział Plecak Ogólne strategie Przechodź od ogółu do szczegółu Skorzystaj z ograniczeń problemu, który redukujesz Poszukuj przypadków specjalnych Wybierz odpowiedni problem do redukcji Ustanawiaj duże nagrody i kary Projektuj gadżety Perspektywy Problemy nierozstrzygalne