Informatyka MIMUW

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).

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,
• 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.

• 1. Wstęp (wersja klasyczna)
• 1. Wstęp (wersja Agile)
• 2. Podstawy Ocamla
• 3 i 4. Dekompozycja problemu, weryfikacja rozwiazania
• 5 i 6. Struktury danych
• 7. Moduły i bariery abstrakcji
• 8. Procedury wyzszych rzedów jako abstrakcje konstrukcji programistycznych
• 9. Procedury wyzszych rzedów oraz listy i drzewa
• 10 i 11. Model obliczen
• 12 i 13. Analiza kosztów
• 14 i 15. Zasada ,,dziel i rządź'' i analiza złożoności
• 16. Funktory
• 17. Programowanie imperatywne
• 18. Imperatywne wskaźnikowe struktury danych
• 19 i 20. Logika Hoare'a -- dowodzenie poprawności programów imperatywnych
• 21. Przeszukiwanie grafów
• 22. Przeszukiwanie z nawrotami (backtracking)
• 23 i 24. Technika spamiętywania i programowanie dynamiczne
• 25 i 26. Programowanie zachłanne
• 27. Wyszukiwanie wzorców w tekście
• 28. Tablica sufiksowa

• 1. Wstęp
• 2. Procedury operujące na liczbach
• 3. Rekurencja ogonowa
• 4 i 5. Listy
• 6. Struktury danych
• 7. Moduły
• 8. Procedury wyższych rzędów
• 9 i 10. Procedury wyższych rzędów i listy
• 11. Procedury wyższych rzędów i drzewa
• 12. Złożoność czasowa i pamięciowa
• 13. Zastosowanie sortowania
• 14. Koszt zamortyzowany
• 15. Funktory
• 16. Programowanie imperatywne
• 17. Imperatywne wskaźnikowe struktury danych
• 18. Logika Hoare'a
• 19. Przeszukiwanie grafów
• 20. Przeszukiwanie z nawrotami (ang. backtracking)
• 21 i 22. Spamiętywanie i programowanie dynamiczne
• 23 i 24: Programowanie zachłanne
• 25 i 26: Programowanie dynamiczne, zachłanne i back-tracking -- powtórzenie
• 27: Wyszukiwanie wzorców w tekście

Materiały wprowadzające:

1. Pierwszy kontakt z Ocamlem oraz
   Wprowadzenie do Linuksa
2. Warsztat programisty
3. Wprowadzenie do modułów w Ocamlu
4. Listy na przykładzie wielomianów
5. Automatyzacja kompilacji: program make

Programy zaliczeniowe:

0. Arytmetyka przybliżonych wartości (zadanie próbne)
1. Drzewa lewicowe
2. Origami
3. Modyfikacja drzew
4. Sortowanie topologiczne

• Strona główna Ocaml'a
• Instrukcja (Resources -> Objective Caml manual)
• Tutorial
• Tutorial Jane Street
• Jak powinien wyglądać kod w Ocamlu?
• Developing Applications With OCaml -- książka
• Real World OCaml -- książka
• Listy dyskusyjne
• W szczególności lista dla poczatkujacych dostępna on-line bez żadnego zapisywania się (przynajmniej do czytania).
• Dużo ładnie napisanego kodu w Ocamlu (a jakże: kod ocamla)
• FAQ