Liczba godzin zajęć dydaktycznych:15 godzin wykładów
5 godzin laboratoriów
Prerekwizyty:
Analiza matematyczna: ciągi, szeregi, zbieżność, reguła
de L'Hopitala, pojecie całki.
Matematyka Dyskretna: podstawy rachunku zdań,
kwantyfikatory, dowody indukcyjne, operacje na zbiorach, relacje, funkcje, podstawy
kombinatoryki, podstawowe własności grafów i drzew.
Metody probabilistyczne i
statystyka: elementarny rachunek
prawdopodobieństwa, wartość oczekiwana, prawdopodobieństwo warunkowe (do wzoru Bayes'a
włącznie).
Metody programowania: znajomość podstaw
programowania obiektowego wraz z praktyczna znajomością języka programowania wysokiego
poziomu zorientowanego obiektowo (np. Java lub C++);
Algorytmy i struktury danych: złożoność obliczeniowa,
notacja "duże O"; weryfikacja poprawności; podstawowe struktury danych: tablice,
struktury wskaźnikowe; podstawowe algorytmy: wyszukiwanie, sortowanie; rekurencja.
Założenia i cele przedmiotu:
Celem przedmiotu jest zaznajomienie
słuchaczy z metodami programowania na poziomie abstrakcyjnych typów
danych wraz z ich praktycznymi zastosowaniami. Mimo ze przedmiot
należy do grupy Programowanie, bazować on będzie na pojęciach
matematycznych oraz teoretycznych. Po zaliczeniu przedmiotu, studenci
powinni posiąść dyscyplinę programowania która umożliwi im
stosunkowo łatwe i klarowne rozwiązywanie złożonych problemów.
Wykład ilustrowany będzie ciekawymi zastosowaniami w informatyce i
sztucznej inteligencji. Nacisk będzie położony na wyrobienie
praktycznych umiejętności i wzbudzenie zainteresowania tematyka
przedmiotu a nie na jego aspekty teoretyczno-formalne.
Metody dydaktyczne:
Część wykładowa przedmiotu
jest prezentowana w formie klasycznego wykładu audytoryjnego, z użyciem
środków multimedialnych i interakcyjnych narzędzi programowania. W części laboratoryjnej
studenci będą implementować zadane programy w zintegrowanym
środowisku programowym.
Forma i warunki zaliczenia
przedmiotu:
Warunkami zaliczenia przedmiotu
są:
obecność na wykładach, kodowanie i wykonywanie zadanych
programów w laboratoriach, oraz zdanie pisemnego egzaminu końcowego składającego sie z zadania
laboratoryjnego, którego rozwiązanie wymagać będzie umiejętności programowania
obiektowego z użyciem abstrakcyjnych typów danych.
Syllabus
Poniedzialek
Wyklad:
Godzina 1: Przeglad preliminariow matematycznych; definiowanie przez indukcje, listy, drzewa, grafy, zbiory.
Godzina 2:
Wprowadzenie do jezyka programowania Java; klasy, obiekty, i metody;
specyfika wywolan przez wartosc; techniczne uwagi n.t. rekursji.
Godzina 3: Pojecie abstrakcyjnego typu danych - przyklad wstepny.
Laboratorium:
Godzina 4: Wprowadzenie do zintegrowanego srodowiska programowania; uruchomienie pierwszego programu.
Wtorek
Wyklad:
Godzina 1: Abstrakcyjne typy danych: LIST (lista), QUEUE (kolejka), i STACK (stos).
Godzina 2: Abstrakcyjne typy danych: TREE (drzwewo).
Godzina 3: Szacowanie zlozonosci obliczeniowej drzew; zastosowania.
Laboratorium:
Godzina 4: Przeszukiwanie drzew.
Sroda
Wyklad:
Godzina 1: Abstrakcyjne typy danych: GRAPH (graf) i DIAGRAPH (graf skierowany)
Godzina 2: Przeszukiwanie grafow z zastosowaniami.
Godzina 3: Wyszukiwanie punktow artykulacji grafu; grafy dwuczesciowe; kolorowanie grafow.
Laboratorium:
Godzina 4: Wyszukiwanie cykli w grafach
Czwartek
Wyklad:
Godzina 1: Abstrakcyjne typy danych SET (zbior).
Godzina 2: Implementacja zbiorow metoda drzew; zlozonosc obliczeniowa.
Godzina 3: Adaptacyjne metody implementacji zbiorow; zlozonosc obliczeniowa.
Laboratorium:
Godzina 4: Konstrukcja optymalnego drzewa pokrywajacego wierzcholki zadanego grafu.
Piatek
Wyklad:
Godzina 1: Zastosowania w sztucznej inteligencji i sieciach komputerowych.
Godzina 2: Szacowanie zlozonosci problemow; ograniczenia teoretyczne praktycznej rozwiazywalnosci.
Egzamin:
Godzina 3, 4: Egzamin pisemny - projekt i implementacja wykonywalnego programu z uzyciem abstrakcyjnych typow danych.
Ocena z egzaminu zalezec bedzie od jakosci, poprawnosci, zlozonosci, i kompletnosci implementacji.
Literatura podstawowa:
Notatki z wykładu - będą
udostępnione dla studentów na Internecie.
Podręcznik do programowania w
języku Java (do indywidualnego wyboru przez studentów; rowniez dostepny na Internecie).
Klasyczna literatura uzupełniająca
(nieobowiązkowa):
Aho, A. V., Hopcroft, J.E., Ullman,
J.D. (1983). "Data Structures and
Algorithms." Addison-Wesley.
Knuth D.E. (1997). "The
Art of Computer Programming, Volume 1: Fundamental Algorithms."
Addison-Wesley.
Knuth D.E. (1998). "The
Art of Computer Programming, Volume 3: Sorting and Searching."
Addison-Wesley.
Standish, T. A. (1998).
"Data Structures in Java." Addison-Wesley.
