Algorytmy i struktury danych 0600-IS1-2ASD
Wykład (WYK) Rok akademicki 2018/19

- Zna podstawowe pojęcia i podejścia dotyczące projektowania i analizy algorytmów. K_W03

- Zna podstawowe struktury danych i związane z nimi algorytmy, przykłady zastosowań oraz sposoby implementacji. K_W03

- Zna podstawowe problemy algorytmiczne (sortowanie, wyszukiwanie wzorca i in.) oraz wybrane metody ich rozwiązywania. K_W03

- Rozumie konieczność ciągłego dokształcania się. K_K02

Metody sprawdzenia osiągnięcia efektów kształcenia (wykład):

- sprawdzian pisemny i ustny

Kryteria zaliczenia wykładu:

- uzyskanie z egzaminu co najmniej 50% punktów

Warunkiem przystąpienia do egzaminu jest uprzednie zaliczenie ćwiczeń.

01. Podstawowe pojęcia algorytmiki. Metody opisywania algorytmów.

02. Podstawowe struktury danych i metody ich implementowania: tablica, lista, stos, kolejka, kolejka priorytetowa, zbiór.

03. Grafy i drzewa oraz metody ich reprezentowania (macierze sąsiedztwa, macierze incydencji, listy incydencji). Sterta.

04. Rekursja i przykłady jej użycia. Metoda powrotów.

05. Złożoność algorytmu oraz podstawowe problemy i metody związane z jej szacowaniem. Notacja "Big-Oh" i pokrewne.

06. Podejścia do rozwiązywania problemów algorytmicznych. Technika "dziel i zwyciężaj". Programowanie dynamiczne.

07. Algorytmy zachłanne. Algorytmy z nawrotami. Wyszukiwanie wyczerpujące "brute-force".

08. Poprawność programów. Niezmienniki pętli i problem stopu.

09. Problemy wyszukiwania i sortowania oraz przegląd rozwiązań.

10. Problemy wyszukiwania i dopasowania wzorca oraz przegląd rozwiązań.

11. Podstawowe operacje na grafach i drzewach.

12. Złożone struktury drzewiaste. Drzewa BST i AVL.

13. Tablice z haszowaniem. Funkcje mieszające.

14. Zaawansowane zagadnienia złożoności obliczeniowej. Klasy złożoności problemów P i NP.

Wykład (30 h)