Wstęp do programowania (podejście funkcyjne)

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

Oto tematy kolejnych zajęć:

1) Wstęp:

- historia powstania pojęcia algorytm,

- pojęcie algorytmu,

- przykłady algorytmów i języków programowania w otaczającym nas Świecie,

- pojęcie dziedziny algorytmicznej.

2) Podstawy języka programowania:

- BNF -- meta-notacja do opisu składni języka,

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

3) Dekompozycja problemu i weryfikacja programów:

- specyfikacja problemu, warunek początkowy i końcowy,

- częściowa poprawność i własność stopu,

- zasady weryfikacji programów,

- przykłady weryfikacji.

4) Struktury danych:

- typy wbudowane,

- konstruktory i wzorce,

- produkty kartezjańskie,

- listy,

- deklaracje typów,

- rekordy,

- typy wariantowe (drzewa),

- wyjątki.

5) Budowanie abstrakcji za pomocą danych:

- konstruktory, selektory i modyfikatory,

- poziomy i bariery abstrakcji,

- przykłady.

6) Procedury wyższych rzędów:

- typy proceduralne i polimorfizm,

- przykłady,

- procedury wyższych rzędów i listy,

- zastosowania procedur wyższych rzędów.

7) Semantyka operacyjna programów funkcyjnych (uproszczona):

- środowiska i ramki,

- semantyka definicji globalnych,

- reprezentacja danych i procedur,

- wywoływanie procedur,

- rekurencja ogonowa,

- semantyka definicji lokalnych,

- odśmiecanie.

8) Analiza złożoności:

- rachunek rzędów funkcji,

- koszt czasowy i pamięciowy,

- koszt zamortyzowany

- przykłady.

9) Metoda "dziel i zwyciężaj":

- metoda "dziel i zwyciężaj",

- przykłady.

10) Moduły,

- struktury,

- sygnatury,

- łączenie struktur i sygnatur,

- zasady wyodrębniania modułów.

11) Funktory,

- proste funktory,

- funktory wyższych rzędów,

- przykłady.

12) Programowanie imperatywne:

- referencje,

- sekwencyjne złożenie instrukcji (;),

- pętle,

- tablice,

- przykłady

- funkcyjnie czy imperatywnie?

13) Imperatywne wskaźnikowe struktury danych:

- przykłady.

14) Weryfikacja programów imperatywnych -- logika Hoare'a.

- while-programy,

- logika Hoare'a,

- niezmienniki pętli,

- funkcja miary i własność stopu,

- przykłady.

15) Przeszukiwanie z nawrotami (ang. back-tracking):

- obcinanie gałęzi i inne ulepszenia,

- przykłady.

16) Spamiętywanie,

- technika spamiętywnia,

- ogólny spamiętywacz,

- przykłady.

17) Programowanie dynamiczne:

- przykłady.

18) Programowanie zachłanne:

- kody Huffmana,

- inne przykłady.

19) Przeszukiwanie grafów:

- przeszukiwanie wszerz,

- przeszukiwanie wgłąb,

20) Reprezentacja danych w komputerze:

- stałe całkowite i rzeczywiste

- reprezentacje binarne stało i zmiennopozycyjne

- systemy znak-moduł i uzupełnieniowy

- kodowanie uzupełnieniowe do dwójki, kodowanie moduł-znak, kodowanie z przesunięciem, kodowanie liczb ułamkowych wg IEEE-754 (pojedyncza i podwójna

precyzja), ASCII, ISO-8859, UTF-8, EBCDIC

- rachunek zmiennopozycyjny, pojęcie zakresu i błędu zaokrągleń

21) Procedury dużo wyższych rzędów:

- definicja typów danych za pomocą procedur,

- liczby naturalne Church'a,

- operator punktu stałego i definicje rekurencyjne.

22) Strumienie.

Wiedza:

- Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie programowania, algorytmów, złożoności i funkcyjnego paradygmatu programowania (K_W02).

- Zna podstawowe konstrukcje programistyczne oraz pojęcia składni i semantyki funkcyjnego języka programowania (K_W03).

- Zna podstawowe metody projektowania, analizowania i programowania algorytmów (K_W04), w szczególności:

- definicje stałych i funkcji, w tym definicje lokalne,

- rekurencję i rekurencję ogonową,

- λ-abstrakcję,

- wyrażenia warunkowe,

- dopasowywanie wzorców,

- funkcje wyższych rzędów,

- metodę dziel i rządź,

- przeszukiwanie z nawrotami,

- programowanie dynamiczne,

- programowanie zachłanne,

- pojęcie poprawności,

- metodę niezmienników.

- Zna podstawowe struktury danych i wykonywane na nich operacje (K_W05), w szczególności:

- typy proste,

- krotki,

- listy,

- typy wariantowe, w tym typy wyliczeniowe, unie i drzewa,

- sposób realizacji struktur danych (wskaźniki) i kwestie związane ze współdzieleniem struktur danych,

- modyfikowalne struktury danych (rekordy, referencje, tablice).

- Zna sposób obliczania programów funkcyjnych oraz pojęcia:

- środowiska,

- współdzielenia struktur danych,

- odśmiecania, oraz

- wynikającej z tego złożoności czasowej i pamięciowej programów funkcyjnych (analiza ilościowa).

- Ma ogólną wiedzę na temat funkcyjnego i imperatywnego paradygmatu programowania (K_W09).

- Zna pojęcia poprawności i częściowej poprawności programów oraz techniki ich dowodzenia (K_W13).

Umiejętności:

- Potrafi zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań o średnim poziomie złożoności (K_U01).

- Potrafi pisać, uruchamiać i testować programy w wybranym środowisku programistycznym (K_U05).

- Potrafi tworzyć proste programy w wybranym języku funkcyjnym.

- Umie czytać ze zrozumieniem programy zapisane w wybranym języku funkcyjnym.

- Potrafi deklaratywnie ujmować działanie procedur (co jest ich rezultatem, a nie jak go osiągają) oraz sprawdzać ich poprawność.

- Projektuje, analizuje pod kątem poprawności i złożoności obliczeniowej oraz programuje algorytmy; wykorzystuje podstawowe techniki algorytmiczne i struktur danych (K_U07).

- Posługuje się przyjętymi formatami reprezentacji różnego rodzaju danych stosownie do sytuacji (liczby, tablice, tekst) pamiętając o ich ograniczeniach, np. związanych z arytmetyką komputera (K_U09).

- Potrafi się posługiwać standardowymi funkcjami wyższego rzędu.

- Ocenia przydatność paradygmatu funkcyjnego i imperatywnego i potrafi dobrać właściwy paradygmat programowania do różnego rodzaju problemów. (K_U20).

- Potrafi ocenić, na podstawowym poziomie, przydatność rutynowych metod i narzędzi informatycznych oraz wybrać i zastosować właściwą metodę i narzędzia do typowych zadań informatycznych (K_U22).

- Potrafi -- zgodnie z zadaną specyfikacją -- zaprojektować oraz zrealizować prosty system informatyczny, używając właściwych metod, technik i narzędzi (K_U23).

- Potrafi testować proste programy stworzone przez siebie.

Kompetencje:

- Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia (K_K01).

- Potrafi pracować indywidualnie, w tym także potrafi zarządzać swoim czasem oraz podejmować zobowiązania i dotrzymywać terminów (K_K05).

- Umie abstrakcyjnie i twórczo myśleć, oraz wychwytywać abstrakcje powtarzających się wzorców i schematów.

- Umie deklaratywnie patrzeć na problemy i zadania – tj. odróżniać cel który chcemy osiągnąć, od sposobu jego osiągania.