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:
    • poprawność pełna i częściowa, własność stopu,
    • funkcja miary dla wywołań rekurencyjnych,
  • 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.

---

Poniżej under construction

• Instrukcje while-programów:
  • pusta, przypisania, warunkowa, iteracji, wyboru, czytania, pisania, wywołania procedury
  • składnia i semantyka powyższych instrukcji
  • obliczenia skończone i nieskończone
  • błędy obliczeń
  • przykłady algorytmów
• Asercje w programach i niezmienniki pętli:
  • formuły Hoare'a
  • uzasadnianie poprawności programów
  • własność stopu i metody jej dowodzenia
• Typy danych:
  • tablice
  • pliki
  • typy wskaźnikowe
• Pliki:
  • pliki o dostępie bezpośrednim
  • pliki tekstowe
• 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. S.Alagić, M.Arbib, Projektowanie programów poprawnych i dobrze zbudowanych, Wydawnictwa Naukowo - Techniczne 1982
2. L. Banachowski, A.Kreczmar, Elementy analizy algorytmów, Wydawnictwa Naukowo - Techniczne 1987
3. T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wprowadzenie do algorytmiki, Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
4. D.E.Knuth, Sztuka programowania komputerów tom 3, Wydawnictwa Naukowo-Techniczne, Warszawa 2002.
5. N.Wirth, Wstęp do programowania systematycznego, Wydawnictwa Naukowo - Techniczne 1999.
6. N.Wirth, Algorytmy+Struktury danych=Programy, Wydawnictwa Naukowo-Techniczne, Warszawa 2001.