MIMINF:Wstęp do programowania (potok funkcyjny)

Forma zajęć

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

Opis

Jest to podstawowy przedmiot wprowadzający w dziedzinę informatyki. Poświęcony jest on głównie programowaniu i podstawom tworzenia algorytmów. Kurs obejmuje:

• podstawowe pojęcia, takie jak: algorytm, program, specyfikacja, weryfikacja,
• zasady projektowania i tworzenia algorytmów: zasady abstrakcji, dekompozycji problemów,
• podstawy wnioskowania o programach: weryfikacja programów, analiza złożoności programów,
• podstawowe struktury danych,
• techniki tworzenia algorytmów: dziel i zwyciężaj, programowanie zachłanne, dynamiczne i przeszukiwanie z nawrotami.

Całości towarzyszy nauka wybranego funkcyjnego języka programowania (Ocaml).

Sylabus

Autor

• Marcin Kubica — Uniwersytet Warszawski, Instytut Informatyki

Zawartość

• Pojęcie algorytmu:
  • historia powstania pojęcia algorytmu,
  • bliższe spojrzenie na przykładowy algorytm (rozwiązywanie równań kwadratowych metodą Al-Chuwarizmiego),
  • przykłady algorytmów i języków programowania w otaczającym nas Świecie,
  • pojęcie dziedziny algorytmicznej.

• Podstawy języka programowania:
  • sposób opisu składni języka programowania -- formalizm Backusa-Naura (wariant gramatyk bezkontekstowych dostosowany do praktycznych zastosowań),
  • przyrostowy tryb pracy kompilatora,
  • wyrażenia i sposób ich obliczania,
  • wartości logiczne i wyrażenia warunkowe if-then-else,
  • definicje procedur:
    • $\lambda$-abstrakcja,
    • procedury rekurencyjne,
    • rekurencja ogonowa,
  • definicje lokalne.

• Dekompozycja problemu, specyfikacja i weryfikacja programów funkcyjnych:
  • warunek początkowy i końcowy,
  • zasady dowodzenia poprawności,
  • dowodzenie poprawności procedur rekurencyjnych:
    • funkcja miary dla wywołań rekurencyjnych i własność stopu,
    • poprawność pełna i częściowa,
  • przykłady weryfikacji.

• Typy danych:
  • proste typy wbudowane,
  • konstruktory i wzorce,
  • produkty kartezjańskie,
  • listy,
  • deklaracje typów,
  • rekordy,
  • typy wariantowe (drzewa),
  • wyjątki.

• Budowanie abstrakcji za pomocą danych:
  • konstruktory, selektory i modyfikatory,
  • bariery abstrakcji,
  • przykłady.

• Procedury wyższych rzędów:
  • przykłady,
  • procedury wyższych rzędów i listy,
  • zastosowania procedur wyższych rzędów.

• Model obliczeń programów funkcyjnych (uproszczona semantyka operacyjna):
  • Środowiska i ramki,
  • Semantyka definicji globalnych,
  • Reprezentacja danych i procedur,
  • Aplikacja procedur,
  • Rekurencja ogonowa,
  • Semantyka definicji lokalnych,
  • Odśmiecanie.

• Analiza złożoności:
  • rzędy funkcji,
  • asymptotyczny koszt pesymistyczny,
  • koszt czasowy i pamięciowy,
  • koszt zamortyzowany
  • przykłady analizy kosztów algorytmów,

• Metoda dziel i zwyciężaj:
  • metoda inkrementacyjna,
  • podział binarny,
  • przykłady: różne algorytmy sortowania,
  • quick-sort -- przykład analizy kosztu oczekiwanego.

• Moduły i funktory:
  • pojęcie modułu i enkapsulacji,
  • struktury,
  • sygnatury i zależności między strukturami i sygnaturami,
  • funktory,
  • funktory wyższych rzędów.

• Konstrukcje imperatywne:
  • referencje,
  • tablice,
  • sekwencyjne złożenie instrukcji (;),
  • pętle,
  • przykłady ilustrujące charakter programowania imperatywnego i jego połączenie z programowaniem funkcyjnym.

• Imperatywne wskaźnikowe struktury danych:
  • dwustronne kolejki ze scalaniem i odwracaniem,
  • drzewa find-union.

• Dowodzenie poprawności programów imperatywnych:
  • logika Hoare'a,
  • niezmienniki pętli,
  • funkcja miary dla pętli while i własność stopu,
  • częściowa i pełna poprawność programów,
  • przykłady weryfikacji.

• Przeszukiwanie przestrzeni rozwiązań:
  • przeszukiwanie z nawrotami (ang. back-tracking):
  • obcinanie gałęzi przeszukiwania,
  • przykłady, w tym:
    • problem ośmiu hetmanów,
    • algorytm mini-max,
    • $\alpha$-$\beta$-obcięcie,
  • inne sposoby przeszukiwania niż z nawrotami,
  • przykład -- drzewa and-or.

• Technika spamiętywania:
  • struktury słownikowe i ich przykładowa implementacja,
  • spamiętywanie i uniwersalny spamiętywacz,
  • przykłady zastosowania.

• Programowanie dynamiczne:
  • uogólnienie problemu i tablicowanie wyników,
  • przykłady zastosowania (z wykorzystaniem różnych struktur danych do tablicowania).

• Programowanie zachłanne:
  • zasada programowania zachłannego,
  • przykłady (w tym kody Huffmana).

Opcjonalne zaawansowane wykłady ("na deser"):

• Wyszukiwanie i algorytm Knutha-Morrisa-Pratta (KMP):
  • naiwny algorytm wyszukiwania wzorca,
  • algorytm KMP,
  • zastosowanie algorytmu KMP do wyszukiwania wzorców.

• Procedury dużo wyższych rzędów:
  • odraczanie (uleniwianie) obliczeń,
  • proceduralna definicja różnych typów danych,
  • liczby naturalne Churcha.

• Strumienie:
  • pojęcie strumienia,
  • implementacja strumieni,
  • procedury przekształcające strumienie,
  • przykłady strumieni,
  • definicje uwikładne strumieni,
  • przykłady.

Literatura

1. H. Abelson, G. J. Sussman, Struktura i interpretacja programów komputerowych, WNT 2002.
2. L. Banachowski, A. Kreczmar, Elementy analizy algorytmów, WNT 1987.
3. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmiki, WNT 2004.
4. M. Kubica, Wstęp do programowania i Metody programowania, notatki do wykładów, [1]
5. X. Leroy, The Objective Caml system, [2].
6. W. Lipski, Kombinatoryka dla programistów, WNT 2004.
7. N. Wirth, Algorytmy+Struktury danych=Programy, WNT 2001.