Metody programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 14: | Linia 14: | ||
=== Zawartość === | === Zawartość === | ||
* Rekurencja | * Rekurencja: | ||
** rekurencyjne wyrażanie pojęć | ** rekurencyjne wyrażanie pojęć | ||
** zastosowania i implementacja | ** zastosowania i implementacja | ||
** dowodzenie poprawności procedur rekurencyjnych | ** dowodzenie poprawności procedur rekurencyjnych | ||
* Programowanie z nawrotami | * Programowanie z nawrotami: | ||
** przeszukiwanie pełnej przestrzeni stanów | ** przeszukiwanie pełnej przestrzeni stanów | ||
** ucinanie rekursji | ** ucinanie rekursji | ||
* Metoda dziel i rządź | * Metoda ''dziel i rządź'': | ||
** metoda inkrementacyjna | ** metoda inkrementacyjna | ||
** podział binarny | ** podział binarny | ||
* Dynamiczne struktury danych | * Dynamiczne struktury danych: | ||
** typy wskaźnikowe | ** typy wskaźnikowe | ||
** wskaźnikowa realizacja list | ** wskaźnikowa realizacja list | ||
| Linia 30: | Linia 30: | ||
** listy jednokierunkowe, dwukierunkowe i cykliczne | ** listy jednokierunkowe, dwukierunkowe i cykliczne | ||
** atrapy i strażnicy | ** atrapy i strażnicy | ||
* Liniowe struktury danych: stosy i kolejki | * Liniowe struktury danych: stosy i kolejki: | ||
** implementacja tablicowa i listowa | ** implementacja tablicowa i listowa | ||
** implementacja grafu za pomocą list sąsiedztwa | ** implementacja grafu za pomocą list sąsiedztwa | ||
** algorytmy DFS i BFS | ** algorytmy DFS i BFS | ||
* Drzewa | * Drzewa: | ||
** implementacja drzew dowolnego rzędu | ** implementacja drzew dowolnego rzędu | ||
** drzewa binarne | ** drzewa binarne | ||
** obiegi drzew | ** obiegi drzew | ||
** konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP) | ** konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP) | ||
* Programowanie zachłanne | * Programowanie zachłanne: | ||
** algorytm Huffmana | ** algorytm Huffmana | ||
* Metoda spamiętywania | * Metoda spamiętywania: | ||
** programowanie dynamiczne | ** programowanie dynamiczne | ||
** problem plecakowy | ** problem plecakowy | ||
** optymalne mnożenie wielu macierzy | ** optymalne mnożenie wielu macierzy | ||
=== Literatura === | === Literatura === | ||
Wersja z 19:33, 27 wrz 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 — 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
- Algorytmy+Struktury danych=Programy, N.Wirth, Wydawnictwa Naukowo - Techniczne 2001.
- Wprowadzenie do algorytmiki, T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wydawnictwa Naukowo - Techniczne 2004.
- Sztuka programowania komputerów tom 3, D.E.Knuth, Wydawnictwa Naukowo - Techniczne 2002.
Moduły
- Rekursja
- Moduł 2 Ćwiczenia do modułu 2 (listy)
- Moduł 3 Ćwiczenia do modułu 3 (drzewa)
- Moduł 4 Ćwiczenia do modułu 4 (stosy i kolejki)
- Moduł 5 Ćwiczenia do modułu 5 (programowanie zachłanne)
- Moduł 6 Ćwiczenia do modułu 6 (programowanie dynamiczne)
