Uniwersytet Warszawski, Wydział Nauk Ekonomicznych - Centralny System Uwierzytelniania
Strona główna

Wstęp do programowania (podejście funkcyjne)

Informacje ogólne

Kod przedmiotu: 1000-211bWPF
Kod Erasmus / ISCED: 11.301 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (brak danych)
Nazwa przedmiotu: Wstęp do programowania (podejście funkcyjne)
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy:
Punkty ECTS i inne: (brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Skrócony 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).

Pełny opis:

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.

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.

Efekty uczenia się:

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

Metody i 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%).

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski, Wydział Nauk Ekonomicznych.
ul. Długa 44/50
00-241 Warszawa
tel: +48 22 55 49 126 https://www.wne.uw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)