Pojęcia podstawowe - struktury danych, algorytmy i projektowanie algorytmów. Analiza i ocena efektywności algorytmów. Algorytmy sortowania. Rekurencja: obliczenia rekurencyjne i reku-rencyjne wykreślanie krzywych, niebezpieczeństwa rekurencji. Drzewa. Grafy. Dynamiczne struktury danych, ich reprezentacja i operacje z nimi związane. Algorytmy aproksymacyjne. Al-gorytmy równoległe.

30 godz.

- Wprowadzenie: Idea stosowania narzędzi informatycznych do rozwiązywania problemów. Eta-py: specyfikacja problemu, identyfikacja struktury danych, analiza warunków rozwiązania, wybór metody i narzędzi, budowa algorytmu, kodowanie algorytmu w wybranym języku progra-mowania, opracowanie dokumentacji eksploatacyjnej (2). Pojęcia podstawowe; definicja algorytmu i jego cech: stabilności, szybkości i złożoności obliczeniowej (złożoność oczekiwana i złożoność pesymistyczna). Reprezentacja problemów i algorytmów: opis słowny, lista kroków, schemat blokowy, drzewo algorytmu, pseudokod. Grafy i drzewa-rodzaje. (2). Podstawowe struktury danych: standardowe typy proste, typy okrojone, tablice, rekordy, zbiory. Reprezentacja tablic, rekordów i zbiorów. Plik sekwencyjny. Teksty.(2) Algorytmy sortowania; sortowanie przez wstawianie, przez wybór, przez prostą zamianę, przez podział, sortowanie bą-belkowe, sortowanie drzewiaste. Metoda ,dziel i zwyciężaj. Porównywanie metod sortowania - ocena efektywności algorytmów. Algorytmy Heapsort i Quicksort -analiza(3). Rekurencja: metoda podstawiania, metoda iteracyjna, metoda rekurencji uniwersalnej. Przykłady: rekurencyjne obliczenia potęgi, wartości wielomianu, silni, rekursywny ciąg Fibonacciego. Rekurencyjny algorytm Euklidesa obliczanie NWD(2). Rekurencyjne wykreślanie wzorów geometrycznych np: krzywe Hilberta, krzywa Sierpińskiego. Niebezpieczeństwa rekurencji; nieskończona rekurencja, nieuzasadniona rekurencja, ogólne zasady eliminowania rekurencji (3). Dynamiczne struktury dany - listy: tworzenie, przeglądanie, scalanie, usuwanie wybranego elementu (2). Stos / kolejka, listy dwukierunkowe wraz z podstawowymi operacjami (2). Dyna-miczne struktury danych - struktury drzewiaste; drzewa binarne: tworzenie, przeglądanie i inne operacje (2). Dynamiczne struktury danych-drzewa niebinarne i podstawowe operacje (2). Dynamiczne struktury danych- grafy, przeszukiwanie w głąb, przeszukiwanie wszerz (2); minimalne drzewa rozpinające, najkrótsze ścieżki z jednym źródłem, najkrótsze ścieżki między wszystkimi parami wierzchołków (2), maksymalny przepływ i inne algorytmy aproksymacyjne (2). Algorytmy równoległe (2).

15 godz.

30 godz.

Porównanie metod sortowania tablic - analiza złożoności algorytmów (2). Przykłady algoryt-mów iteracyjnych i rekurencyjnych - ocena i porównanie złożoności obliczeniowej (2). Wykreśl-nie krzywych geometrycznych (2). Listy jedno- i dwukierunkowe (2). Stos / kolejka: przetwarza-nie danych (2). Struktury drzewiaste: tworzenie, przeglądanie, usuwanie poddrzewa oraz wybra-nego elementu (2). Grafy: tworzenie, przeszukiwanie w głąb, przeszukiwanie wszerz, minimalne drzewa rozpinające, najkrótsze ścieżki z jednym źródłem, najkrótsze ścieżki między wszystkimi parami wierzchołków, maksymalny przepływ (3).

01. H.T. Cormen, Ch. L. Leiserson, R.L Rivest , Wprowadzenie do algortmów, WNT, Warszawa 2001
02. M.M.Sysło, Algorytmy, WSiP, Warszawa 1999
03. N. Wirth, Algorytmy + Struktury Danych= Programy, WNT, Warszawa 1980, 1999, 2000-
04. R.Stephens, Algorytmy i struktury danych z przykładami w Delphi, Wyd. HELION, Gliwice 2000
05. P. Wróblewski, Algorytmy, struktury danych i techniki programowania, Wyd. HELION, 1996
06. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, Warszawa 1996