Metody programowania

Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin)

Opis

Celem zajęć jest prezentacja technik programistycznych i struktur danych wykorzystywanych w programowaniu w małej i średniej skali.

Sylabus

Autor

• Piotr Chrząstowski-Wachtel — Uniwersytet Warszawski

Wymagania wstępne

• Wstęp do programowania

Zawartość

• 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

1. N.Wirth, Algorytmy+Struktury danych=Programy, Wydawnictwa Naukowo-Techniczne, Warszawa 2001.
2. T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wprowadzenie do algorytmiki, Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
3. D.E.Knuth, Sztuka programowania komputerów tom 3, Wydawnictwa Naukowo-Techniczne, Warszawa 2002.

Moduły

1. Rekursja
2. Moduł 2 Ćwiczenia do modułu 2 (listy)
3. Moduł 3 Ćwiczenia do modułu 3 (drzewa)
4. Moduł 4 Ćwiczenia do modułu 4 (stosy i kolejki)
5. Moduł 5 Ćwiczenia do modułu 5 (programowanie zachłanne)
6. Moduł 6 Ćwiczenia do modułu 6 (programowanie dynamiczne)