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.
• 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:
    • algorytm Euklidesa,
    • metoda Newtona liczenia pierwiastków kwadratowych.

---

Poniżej under construction

• Języki formalne:
  • alfabet, składnia i semantyka
  • gramatyki bezkontekstowe jako narzędzie definiowania składni
  • definiowanie semantyki przez interpretację wyrażeń poprawnych składniowo
• Reprezentacja liczb w komputerze:
  • stałe całkowite i rzeczywiste
  • reprezentacje binarne stało- i zmiennopozycyjne
  • systemy znak-moduł i uzupełnieniowy
  • rachunek zmiennopozycyjny — pojęcie zakresu i błędu zaokrągleń
• Zmienne i wyrażenia:
  • typ zmiennej i wartościowanie zmiennych
  • wyrażenia arytmetyczne i logiczne: składnia i semantyka
• 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
  • rekordy
  • zbiory
  • pliki
  • typy wyliczeniowe i okrojone
  • typy wskaźnikowe
• Pliki:
  • pliki o dostępie bezpośrednim
  • pliki tekstowe
• Funkcje i procedury:
  • składnia i semantyka
  • sposoby przekazywania parametrów: przez wartość i przez zmienną
  • widoczność zmiennych w zagnieżdżonych procedurach
• Miary złożoności algorytmów:
  • koszty algorytmu: czasowy i pamięciowy, pesymistyczny i średni
  • rozmiar danych
  • przykłady wyznaczania kosztów
  • koszt zamortyzowany
• 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ż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.