Wstęp do programowania (podejście funkcyjne)
Informacje ogólne
Kod przedmiotu: | 1000-211bWPF |
Kod Erasmus / ISCED: |
11.301
|
Nazwa przedmiotu: | Wstęp do programowania (podejście funkcyjne) |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: | |
Punkty ECTS i inne: |
(brak)
|
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%). |
Właścicielem praw autorskich jest Uniwersytet Warszawski.