Elementy algorytmiki: problem i jego specyfikacja; algorytm i różne
sposoby jego zapisu.
Elementy analizy algorytmów. Rozmiar danych, złożoność obliczeniowa
(czasowa i pamięciowa). Typy złożoności: pesymistyczna, optymistyczna,
średnia. Notacja asymptotyczna, rzędy wielkości funkcji.
Algorytmy iteracyjne i rekurencyjne; metoda dziel i zwyciężaj.
Algorytmy klasyczne w tym m.in.:
- obliczania pochodnej wielomianu za pomocą schematu Hornera,
- algorytmy Euklidesa w wersji iteracyjnej i rekurencyjnej wraz z
zastosowaniami,
- operujące na liczbach (badania pierwszości liczby, zamiany
reprezentacji liczb między pozycyjnymi systemami liczbowymi, działań na
ułamkach z wykorzystaniem NWD i NWW),
- operujące na tekstach (porównywania tekstów, wyszukiwania wzorca w
tekście metodą naiwną, szyfrowania tekstu metodą Cezara i
przestawieniową),
- wyszukiwania elementów w dowolnej tablicy (algorytm sekwencyjny) oraz w
tablicy uporządkowanej (metoda wyszukiwania binarnego)
- sortujące (sortowanie przez wstawianie, przez wybieranie, bąbelkowe,
przez scalanie, szybkie),
- znajdowania określonego elementu w zbiorze: maksymalnego, lidera oraz
idola,
- generowania liczb pierwszych metodą sita Eratostenesa,
- jednoczesnego wyszukiwania elementu najmniejszego i największego
(algorytm iteracyjny oraz rekurencyjny wykorzystujący metodę dziel i
zwyciężaj),
- szybkiego potęgowania liczb w wersji iteracyjnej i rekurencyjnej,
- problem wież z Hanoi (rozwiązanie rekurencyjne).
Różne metody i techniki programowania:
- podejście zachłanne (wydawania reszty najmniejszą liczbą nominałów,
pakowanie plecaka),
- programowanie dynamiczne (pakowanie plecaka, szukania najdłuższego
wspólnego podciągu),
- algorytmy z nawrotami (problem n-hetmanów).
Implementacja poznanych algorytmów w wybranym języku programowania
wysokiego poziomu.