Metody programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 45: | Linia 45: | ||
** problem plecakowy | ** problem plecakowy | ||
** optymalne mnożenie wielu macierzy. | ** optymalne mnożenie wielu macierzy. | ||
=== Literatura === | === Literatura === | ||
Wersja z 08:30, 15 cze 2006
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
Podstawowy przedmiot informatyczny drugiego semestru studiów. Celem zajęć jest prezentacja nieco bardziej zaawansowanych technik programistycznych i struktur danych.
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żnic
- 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.
