SylabUZ

Wygeneruj PDF dla tej strony

Algorytmy i struktury danych - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Algorytmy i struktury danych
Kod przedmiotu 11.3-WK-MATP-ASD-L-S14_pNadGenGC85Q
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Matematyka
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. licencjata
Semestr rozpoczęcia semestr zimowy 2017/2018
Informacje o przedmiocie
Semestr 5
Liczba punktów ECTS do zdobycia 5
Typ przedmiotu obieralny
Język nauczania polski
Sylabus opracował
  • dr Florian Fabiś
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Laboratorium 30 2 - - Zaliczenie na ocenę
Wykład 30 2 - - Egzamin

Cel przedmiotu

Zdobycie wiedzy i umiejętności w zakresie analizy algorytmów. Znajomość i umiejętność implementacji algorytmów sortowania i selekcji, algorytmów wyszukiwania, podstawowych algorytmów grafowych.

Wymagania wstępne

Znajomość podstawowego kursu z analizy i algebry liniowej. Umiejętność programowania komputerów w zakresie programowania strukturalnego.

Zakres tematyczny

Wykład

  1. Wprowadzenie. Algorytmy i ich złożoność obliczeniowa i pamięciowa. Semantyczna poprawność algorytmu. Badanie poprawności algorytmów. (2 godz.)
  2. Asymptotyka. Rzędy wielkości funkcji. Szacowanie sum. (2 godz.)
  3. Metody projektowania efektywnych algorytmów. Rekurencja, zasada „dziel i zwyciężaj”, algorytmy zachłanne, programowanie dynamiczne. (2 godz.)
  4. Algorytmy sortowania i selekcji. Algorytmy sortowania wewnętrznego i zewnętrznego. Algorytm szybkiej selekcji. (4 godz.)
  5. Algorytmy wyszukiwania. Wyszukiwanie: liniowe, binarne, interpolacyjne. (2 godz.)
  6. Struktury danych dla słownika. Wektor charakterystyczny, haszowanie, drzewa poszukiwań binarnych. (4 godz.)
  7. Wyszukiwanie zewnętrzne. B – drzewa. (2 godz.)
  8. Algorytmy grafowe. Reprezentacje komputerowe grafów. Przechodzenie drzew, przechodzenie grafów, wyznaczanie minimalnego drzewa rozpinającego. Najkrótsze ścieżki. (4 godz.)
  9. Algorytmy tekstowe: problem wyszukiwania wzorca, drzewa sufiksowe i grafy podsłów. (4 godz.)
  10. Algorytmy geometryczne: problem przynależności, wypukła otoczka, metoda zamiatania. (4 godz.)

Laboratorium

  1. Wyznaczanie złożoności obliczeniowej i pamięciowej algorytmów. (4 godz.)
  2. Badanie poprawności algorytmów. (4 godz.)
  3. Algorytmy sortowania i selekcji. (4 godz.)
  4. Struktury danych dla zbiorów. (6 godz.)
  5. Algorytmy grafowe. (6 godz.)
  6. Algorytmy tekstowe i algorytmy geometryczne. (6 godz.)

Metody kształcenia

Wykład: wykład problemowy.

Laboratorium: ćwiczenia laboratoryjne w pracowni komputerowej – implementacja i testowanie wybranych algorytmów. Każdy student w trakcie semestru musi zrealizować cztery projekty. Każdy z projektów polegać będzie na zaimplementowaniu wskazanego przez prowadzącego algorytmu do rozwiązania konkretnego praktycznego zadania, napisaniu do tego programu, przetestowaniu go oraz przedstawieniu dokumentacji zgodnie z zadaną specyfikacją. Nad dwoma z tych czterech projektów studenci będą pracowali w grupach 2-3 osobowych. Ponadto studenci na zajęcia będą pisali programy implementujące różne inne algorytmy.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

Wykład. Egzamin weryfikujący efekty kształcenia w zakresie wiedzy i umiejętności. Egzamin składa się z dwóch części, pisemnej i ustnej. Warunkiem przystąpienia do części ustnej jest uzyskanie 30% punktów z części pisemnej. Uzyskanie 50% punktów z części pisemnej gwarantuje uzyskanie pozytywnej oceny.

Laboratorium. Ocena końcowa jest wystawiana na podstawie punktów uzyskanych na zajęciach. Punkty uzyskuje się za: napisane na zajęciach sprawdziany, zrealizowane na zajęciach projekty, aktywność na zajęciach.

Na ocenę z przedmiotu składa się ocena z laboratorium (50%) oraz ocena z egzaminu (50%). Warunkiem przystąpienia do egzaminu jest pozytywna ocena z laboratorium. Warunkiem zaliczenia przedmiotu jest pozytywna ocena z egzaminu.

Literatura podstawowa

  1. Aho A., Hopcroft J.E., Ullman J.D.,: Projektowanie i analiza  algorytmów komputerowych, PWN, Warszawa 1983.
  2. Banachowski L., Diks K.,  Rytter W., Algorytmy i struktury danych, WNT, Warszawa 1996.
  3. Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.

Literatura uzupełniająca

  1. Lipski W.: Kombinatoryka dla programistów, WNT, 2007.
  2. Knuth D. : Sztuka programowania, t. 1-3, WNT, Warszawa 2001.
  3. Wróblewski P.: Algorytmy, struktury danych i techniki programowania, wyd. II popr., Helion, 2001.

Uwagi


Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 09-04-2017 16:24)