Metody programowania: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 56: Linia 56:
 
# [[MP_Listy|Moduł 3]] [[MP_Ćwiczenia2|Ćwiczenia do modułu 3]] (drzewa)
 
# [[MP_Listy|Moduł 3]] [[MP_Ćwiczenia2|Ćwiczenia do modułu 3]] (drzewa)
 
# Moduł 4 [[MP_Ćwiczenia3|Ćwiczenia do modułu 4]] (stosy i kolejki)
 
# Moduł 4 [[MP_Ćwiczenia3|Ćwiczenia do modułu 4]] (stosy i kolejki)
 +
# Moduł 5 [[MP_Ćwiczenia5|Ćwiczenia do modułu 5]] (programowanie zachłanne)
 +
# Moduł 6 [[MP_Ćwiczenia6|Ćwiczenia do modułu 6]] (programowanie dynamiczne)

Wersja z 19:58, 11 sie 2006

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

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. Algorytmy+Struktury danych=Programy, N.Wirth, Wydawnictwa Naukowo - Techniczne 2001.
  2. Wprowadzenie do algorytmiki, T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wydawnictwa Naukowo - Techniczne 2004.
  3. Sztuka programowania komputerów tom 3, D.E.Knuth, Wydawnictwa Naukowo - Techniczne 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)