5851989882

Kod przedmiotu			Liczb \ i-unktów LCTS
Nazwa przedmiotu	Algorytmy i struktury danych
Jednostka prowadząca	Instytut Matematyki i Informatyki
Kierunek studiów, specjalność	Chemia studia stacjonarne I stopnia - nauczycielska chemia z informatyką
Rok, semestr,			Formy zajęć			Punkty ECTS
formy zajęć i liczba godzin	Rok	Semestr	wyk/ad	konwersatorium/ ćwiczenia	Laboratorium
	II	VI	30		15
Kierownik i realizatorzy	Dr Bożena Woźna-Szcześniak, mgr Agnieszka Zbrzezny
Przedmioty wprowadzające i wymagania wstępne	Podstawy informatyki, Podstawy programowania
Za/ożenia i cele nauczania	Celem wykładu jest zapoznanie studentów z podstawowym zestawem algorytmów realizujących zadania typu wyszukiwanie, sortowanie, oraz z najczęściej wykorzystywanymi strukturami danych: stosami, kolejkami, słownikami, kolejkami priorytetowymi, grafami i drzewami. Przedstawione zostaną również zasadnicze problemy algorytmiki związane z analizą poprawności i kosztu algorytmów. Wykład uzupełniony jest o laboratorium, na którym studenci będą implementować i testować poznane na wykładzie metody algorytmiczne.
Ramowy program przedmiotu	1.    Podstawowe zasady analizy algorytmów: poprawność, złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana). 2.    Podstawowe techniki projektowania algorytmów: 1.    metoda dziel i zwyciężaj, rekurencja 2.    metoda zachłanna 3.    programowanie dynamiczne 3.    Sortowanie: przez wstawianie, przez wybieranie, bąbelkowe, przez scalanie, szybkie, przez kopcowanie, pozycyjne. 4.    Abstrakcyjne struktury danych i ich implementacje: listy, stosy, kolejki, drzewa poszukiwań binarnych, kopce binarne, kolejki priorytetowe, grafy. 5.    Algorytmy grafowe: 1.    DFS i jego zastosowania 2.    BFS i jego zastosowania 3.    Sortowanie topologiczne 4.    problemy ścieżkowe — Algorytm Dijkstry 5.    minimalne drzewo rozpinające 6.    Algorytm Warshalla 7.    Algorytm Floyda 6.    Wyszukiwanie wzorca w tekstach: algorytm naiwny, algorytm Knutha-Morisa-Pratta, algorytm Boyera-Moora 7.    Algorytmy kompresji danych
Forma i warunki zaliczenia przedmiotu	Zaliczenie laboratorium (2 kolokwia). Egzamin teoretyczny z wykładu.
Metody dydaktyczne	Wykład, prezentacja multimedialna, symulacja
Literatura podstawowa i uzupe/niająca	1.    Banachowski L., Diks K., Rytter W. Algorytmy i struktury danych. WNT, Warszawa, 1996. 2.    Cormen T.H., Leiserson Ch.E., Rivest R.L. Wprowadzenie do algorytmów. WNT, Warszawa, 1997.