Metody programowania

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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. Stosy i kolejki(Ćwiczenia:stosy i kolejki)
  5. (Ćwiczenia:programowanie zachłanne)
  6. (Ćwiczenia:programowanie dynamiczne)