Algorithms and data structures

2020Z

Kod przedmiotu2320S1-ALGO
Punkty ECTS 4,5
Typ zajęć Ćwiczenia laboratoryjne
Wykład
Przedmioty wprowadzająceMatematyka dyskretna
Wymagania wstępneZnajomość podstawowych struktur matematycznych jak zbiory, grafy, drzewa
Opis ćwiczeń1. Pojęcie algorytmu. 2. Przykłady wstępne: sortowanie naiwne, struktury danych: tablica, pojęcie złożoności, notacja o, omega, theta. 3. Sortowanie efektywne przez porównanie: merge sort, idea divide and conquer, rekurencja.4. Kres dolny złożoności sortowania przez porównanie, sortowanie liniowe. 5. Struktury danych: listy, kolejki, stosy, zastosowania: notacja polska. 6. Struktury danych: drzewa, drzewa binarne, drzewa BST. 7. Operacje na drzewach binarnych, porządki pre-, in- i postorder. 8. Struktura kopca, heapsort. 9. Struktury danych: grafy, grafy ważone 10. Optymalne obiekty w grafach: najkrótsze ścieżki, drzewa rozpinające, algorytmy Dijkstry, Kruskala i Prima. 11. Idea programowania dynamicznego, przykłady: problem LCS, algorytm Floyda-Warshalla. 12. Idea klas złożoności, klasy P i NP. 13. Przyklady problemów NP i problemów NPcomplete, redukcja wielomianowa. 14. Problemy klasy hard. 15. Test zaliczeniowy
Opis wykładów1. Pojęcie algorytmu. 2. Przykłady wstępne: sortowanie naiwne, struktury danych: tablica, pojęcie złożoności, notacja o, omega, theta. 3. Sortowanie efektywne przez porównanie: merge sort, idea divide and conquer, rekurencja.4. Kres dolny złożoności sortowania przez porównanie, sortowanie liniowe. 5. Struktury danych: listy, kolejki, stosy, zastosowania: notacja polska. 6. Struktury danych: drzewa, drzewa binarne, drzewa BST. 7. Operacje na drzewach binarnych, porządki pre-, in- i postorder. 8. Struktura kopca, heapsort. 9. Struktury danych: grafy, grafy ważone 10. Optymalne obiekty w grafach: najkrótsze ścieżki, drzewa rozpinające, algorytmy Dijkstry, Kruskala i Prima. 11. Idea programowania dynamicznego, przykłady: problem LCS, algorytm Floyda-Warshalla. 12. Idea klas złożoności, klasy P i NP. 13. Przyklady problemów NP i problemów NPcomplete, redukcja wielomianowa. 14. Problemy klasy hard. 15. Podsumowanie.
Cel kształceniaCelem kształcenia jest wprowadzenie do teorii algorytmów dla matematyków - na kanwie znanych struktur matematycznych przedstawione są algorytmy dla maszynowego rozwiązywania klasycznych problemów sortowania, przeszukiwania, znajdowania obiektów optymalnych jak najkrótsze ścieżki, drzewa minimalne. Uświadomi to studentom związki matematyki i informatyki i da im narzędzia do korzystania w pracy własnej i dydaktycznej.
Literatura podstawowa1) Piotr Wróblewski, Algorytmy, struktury danych i techniki programowania. Wydanie V, Helion, 2015
Literatura uzupełniająca
UwagiW trakcie ćwiczeń 2-3 krótkie testy przygotowujące do testu zaliczeniowego.