Algorytmy i struktury danych

Treści kształcenia

Dane i operacje na danych, pojęcie typu. Poprawność algorytmu. Metody układania algorytmów: zstępująca, „dziel i rządź”, programowanie dynamiczne, algorytmy zachłanne, z nawrotami. Wyszukiwanie i sortowanie. Abstrakcyjne struktury danych (lista, stos, kolejka, słownik, kolejka priorytetowa) i metody ich realizacji. Struktury drzewiaste. Grafy, sposoby ich reprezentacji, podstawowe algorytmy grafowe. Złożoność obliczeniowa problemów, złożoność czasowa i pamięciowa algorytmów, złożoność w najgorszym przypadku i złożoność średnia. Klasy problemów decyzyjnych: P, NP, NP-zupełne, silnie NP-zupełne. Weryfikacja poprawności algorytmów. W ramach zajęć laboratoryjnych studenci implementują poznane algorytmy, w szczególności: sortowania, programowania dynamicznego, rekurencyjne, przeszukiwania grafu wszerz i w głąb.

Efekty kształcenia - umiejętności i kompetencje

Student zna teoretyczne pojęcia oraz praktyczne problemy związane z algorytmami i strukturami danych. Potrafi napisać program i przeanalizować jego złożoność obliczeniową.