Algorytmy i struktury danych


Informacje ogólne

Typ:obowiazkowy
Kierunek:Informatyka studia licencjackie
Semestr:3
Wymiar zajęć:30h wykładu i 30h ćwiczeń
Punkty ECTS:8

Program

  • Pojęcia wstępne: poprawność semantyczna, złożoność czasowa pesymistyczna i oczekiwana.
  • Sortowanie przez porównania. Algorytmy o złożoności kwadratowej, o złożoności liniowo-logarytmicznej (heapsort), o średniej złożoności liniowo-logarytmicznej (quicksort). Twierdzenia o ograniczeniach dolnych złożoności czasowej pesymistycznej i oczekiwanej.
  • Sortowanie w czasie liniowym.
  • Podstawowe struktury danych: listy, stosy, kolejki. Implementacje przy użyciu tablic i struktur dowiązaniowych.
  • Struktury danych dla operacji słownikowych (wstaw, usuń, szukaj): tablice z haszowaniem, drzewa poszukiwań binarnych, drzewa zrównoważone, B-drzewa.
  • Metody konstruowania efektywnych algorytmów: metoda "dziel i zwyciężaj", programowanie dynamiczne (najdłuższy wpólny podciąg), algorytmy zachłanne (kody Huffmana).
  • Przykłady algorytmów grafowych (najkrótsze scieżki w grafie).

Sposób zaliczenia

Ćwiczenia: zaliczenie na podstawie sumy punktów uzyskanych z dwóch pisemnych kolokwiów plus ewentualne dodatkowe punkty za aktywność na zajęciach.
Egzamin: pisemny, składający się z dwóch części: teoria, algorytmy.

Literatura

  • T. H. Cormen, C. E. Leiserson, L. R. Rivest, C. Stein - Wprowadzenie do algorytmów, WNT 2007.
  • L. Banachowski, K. Diks, W. Rytter - Algorytmy i struktury danych, WNT 1996.