Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wstęp do programowania (podejście funkcyjne)

Informacje ogólne

Kod przedmiotu: 1000-211bWPF Kod Erasmus / ISCED: 11.301 / (brak danych)
Nazwa przedmiotu: Wstęp do programowania (podejście funkcyjne)
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obowiązkowe dla I roku informatyki
Przedmioty obowiązkowe dla I roku JSIM
Punkty ECTS i inne: 13.00
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 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 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.

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

Zajęcia w cyklu "Semestr zimowy 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-01-26
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 60 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 60 godzin więcej informacji
Koordynatorzy: Marcin Kubica
Prowadzący grup: Jacek Chrząszcz, Wojciech Jaworski, Marcin Kubica, Łukasz Mazurek, Mirosława Miłkowska, Jakub Pawlewicz, Piotr Wygocki
Strona przedmiotu: http://smurf.mimuw.edu.pl/drupal6/?q=wstep_do_programowania_funkcyjny
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2018/19" (w trakcie)

Okres: 2018-10-01 - 2019-01-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 60 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 60 godzin więcej informacji
Koordynatorzy: Marcin Kubica
Prowadzący grup: Jacek Chrząszcz, Wojciech Jaworski, Marcin Kubica, Mirosława Miłkowska, Jakub Pawlewicz, Michał Startek, Daria Walukiewicz-Chrząszcz, Maciej Zielenkiewicz, Wiktor Zuba
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.