Metody programowania

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Podstawowy przedmiot informatyczny drugiego semestru studiów, mający zapoznać studentów z pojęciem algorytmu i programu. Celem zajęć jest nauczenie projektowania, zapisywania, dowodzenia poprawności i uwzględniania złożoności algorytmów.

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.

1.Algorytmy+Struktury danych=Programy, N.Wirth, WNT 2001. 2.Wprowadzenie do algorytmiki, T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, WNT 2000. 3.Algorytmy w C++, R.Sedgewick, MIKON 2001 4.D. Knuth, Sztuka programowania komputerów, tom 3, WNT 2002

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, WNT 2002