Metody Programowania
Forma kursu:Opis kursu:
Treści programowe:
- Rekurencja:
- rekurencyjne wyrażanie pojęć
- zastosowania i implementacja
- dowodzenie poprawności procedur rekurencyjnych
- Programowanie z nawrotami:
- przeszukiwanie pełnej przestrzeni stanów
- ucinanie rekursji
- Metoda dziel i rządź:
- metoda inkrementacyjna
- podział binarny
- Dynamiczne struktury danych:
- typy wskaźnikowe
- wskaźnikowa realizacja list
- podstawowe operacje na listach
- listy jednokierunkowe, dwukierunkowe i cykliczne
- atrapy i strażnicy
- Liniowe struktury danych: stosy i kolejki:
- implementacja tablicowa i listowa
- implementacja grafu za pomocą list sąsiedztwa
- algorytmy DFS i BFS
- Drzewa:
- implementacja drzew dowolnego rzędu
- drzewa binarne
- obiegi drzew
- konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP)
- Programowanie zachłanne:
- algorytm Huffmana
- Metoda spamiętywania:
- programowanie dynamiczne
- problem plecakowy
- optymalne mnożenie wielu macierzy
Literatura:
- N.Wirth, Algorytmy+Struktury danych=Programy, Wydawnictwa Naukowo-Techniczne, Warszawa 2001.
- T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wprowadzenie do algorytmiki, Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
- D.E.Knuth, Sztuka programowania komputerów tom 3, Wydawnictwa Naukowo-Techniczne, Warszawa 2002.