3969672840

Forma zaliczenia', zaliczenie laboratorium + egzamin

Cel kształcenia'. Zapoznanie studentów z podstawowymi technikami

konstrukcji algorytmów.

Treści kształcenia'. Wprowadzenie do przedmiotu: algorytm, pojęcia podstawowe, algorytmizacja, metody zapisu algorytmu, schematy blokowe, sieci działań. Meta-algorytmy, metoda dziel i zwyciężaj, metoda kolejnych uściśleń - przykłady. Algorytmy elementarne, algorytmy wyszukiwania oraz inne. Złożoność obliczeniowa algorytmu, klasy złożoności, zarys metod badania poprawności. Podstawowe struktury danych i metody ich implementacji: tablice, rekordy, listy, kolejki oraz stosy, zbiory, grafy, składy (sterty). Operacje na podstawowych strukturach danych - przegląd operacji i ich implementacja. Równania rekurencyjne. eliminacja rekurencji. Metody sortowania wewnętrznego (pamięć o dostępie swobodnym) - przegląd algorytmów, implementacja metod, porównanie. Metody sortowania zewnętrznego (pamięć o dostępie sekwencyjnym) - przegląd algorytmów, implementacja metod, porównanie. Struktury drzewiaste, rodzaje struktur drzewiastych, podstawowe operacje i strategie przeszukiwania, równoważenie (wyważanie) drzew. Tablice z haszowaniem, metody rozpraszania, projektowanie i implementacja tablic z haszow'aniem.

Literatura:

A. V. Aho. J. E. Hopcroft, J. D. Ullman. Projektowanie i analiza algorytmów komputerowych, PWN. Warszawa 1983.

A. Drozdek, D. L. Simon, Struktury danych w języku C\ WNT 1996

L.    Banachowski, A. Kreczmar, Elementy analizy algorytmów, WN-T.

Warszawa 1992.

David Harel, Rzecz o istocie informatyki: Algorytmika, WNT 2001,

D. Knuth, Sztuka programowania. 1.1-3. WNT 2002,

Ch. Papadimitriou, Złożoność obliczeniowa, WNT 2002,

M.    M. Syslo, Algorytmy. WSiP, Warszawa 1997.

N.    Wirth, Algorytmy+struktury danych = programy, WNT 2001.

A. Drozdek, D. L. Simon, Struktury danych w języku C. WNT, 1996

11.3-2F-B14-WDP Wstęp do programowania

wykład 30 godz., 15 konw.. lab. 30 godz.