Metody programowania

From Studia Informatyczne

Spis treści

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. (Ćwiczenia rekursja)
  2. Listy(Ćwiczenia:listy)
  3. Drzewa(Ćwiczenia:drzewa)
  4. (Ćwiczenia:stosy i kolejki)
  5. (Ćwiczenia:programowanie zachłanne)
  6. (Ćwiczenia:programowanie dynamiczne)