Wstęp do programowania (podejście funkcyjne) 1000-211bWPF
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.
Rodzaj przedmiotu
Efekty kształcenia
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 w zaawansowanym stopniu podstawowe konstrukcje programistyczne (przypisanie, instrukcje sterujące, wywoływanie podprogramów i przekazywanie parametrów) oraz pojęcia składni i semantyki języków programowania (K_W03).
* Zna podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, metoda dziel i rządź, programowanie z nawrotami, poprawność, metoda niezmienników, złożoność obliczeniowa) (K_W04).
* Zna podstawowe struktury danych i wykonywane na nich operacje (reprezentacja danych liczbowych, arytmetyka i błędy zaokrągleń, tablice, napisy, zbiory, rekordy, pliki, wskaźniki i referencje, struktury wskaźnikowe, listy, stosy, kolejki, drzewa i grafy) (K_W05).
* 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.
* Zna pojęcia poprawności i częściowej poprawności programów oraz techniki ich dowodzenia.
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 czytać ze zrozumieniem programy zapisane w języku programowania imperatywnego (K_U05).
* Potrafi pisać, uruchamiać i testować programy w wybranym środowisku programistycznym.
* 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.
* 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.
* 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.
* 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.
* Potrafi - zgodnie z zadaną specyfikacją - zaprojektować oraz zrealizować prosty system informatyczny, używając właściwych metod, technik i narzędzi.
* Potrafi testować proste programy stworzone przez siebie.
Kompetencje społeczne:
* Student jest gotów do krytycznej oceny posiadanej wiedzy i odbieranych treści (K_K01).
* Student jest gotów do pracy z zachowaniem uczciwości intelektualnej w działaniach własnych i innych osób; przestrzegania zasad etyki zawodowej i wymagania tego od innych oraz dbałości o dorobek i tradycje zawodu informatyka (K_K02).
* Student jest gotów do uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03).
Kryteria oceniania
O dopuszczeniu do egzaminu w I terminie i ewentualnej propozycji oceny końcowej (zwolnieniu z egzaminu) decydują:
- kolokwia (60%),
- wyniki za programy zaliczeniowe z laboratorium (30%),
- wyniki za przegląd kodu (code review) (10%),
- dodatkowa premia przyznawana przez wykładowcę (max 10%),
przy czym:
- programy zaliczeniowe z laboratorium muszą być przeglądane i oddawane systematycznie w podanych terminach,
- wynik z laboratorium za programy zaliczeniowe musi wynosić przynajmniej 50%;
w przeciwnym przypadku nie ma możliwości zaliczenia przedmiotu.
W przypadku propozycji oceny końcowej i udziału w egzaminie, o ocenie końcowej decyduje wynik z egzaminu.
Do egzaminu w II terminie zostaną dopuszczeni studenci, którzy uzyskali wynik z laboratorium za programy zaliczeniowe przynajmniej 50%.
O ocenie w II terminie decydują:
- wyniki: egzaminu (60%),
- programów zaliczeniowych z laboratorium (30%),
- wyniki za przegląd kodu (code review) (10%).
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. A. Hunt, D. Thomas, Pragmatyczny programista, WNT 2009
4. M. Kubica, Wstęp do programowania i Metody programowania, notatki do wykładów,
5. X. Leroy, The Objective Caml system, .
6. N. Wirth, Algorytmy+Struktury danych=Programy, WNT 2001.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: