Informacje ogólne

Typ:obowiazkowy

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.