Wyższa Szkoła Technologii Informatycznych w Katowicach
Zagadnienia tematyczne z przedmiotu Algorytmy i struktury danych
Algorytmy i struktury danych
Pojęcie typu danych.
Proste typy danych - liczbowe, znakowe, logiczne.
Tablice
Rekordy
Zbiory
Pliki.
Reprezentacja struktur danych.
Pojęcie algorytmu.
Cechy i rodzaje algorytmów.
Metody zapisu algorytmu: opis słowny, schematy blokowe.
Weryfikacja poprawności algorytmów.
Pojęcie niezmiennika, metoda Floyda.
Złożoność obliczeniowa algorytmów - pamięciowa i czasowa.
Złożoność czasowa średnia, pesymistyczna.
O-notacja dla złożoności algorytmów.
Przykład szacowania złożoności czasowej.
Podział algorytmów ze względu na złożoność.
Wyszukiwanie liniowe.
Wyszukiwanie binarne.
Rola wartownika w wyszukiwaniu.
Haszowanie.
Minimalna, doskonała funkcja haszująca.
Metody przezwyciężania kolizji.
Wyszukiwanie wzorca w tekście.
Sortowania przez proste wstawianie.
Sortowanie przez proste wybieranie.
Sortowanie bąbelkowe.
Metoda dziel i zwyciężaj - sortowanie szybkie.
Sortowanie drzewiaste.
Sortowanie stogowe.
Abstrakcyjne struktury danych - listy.
Abstrakcyjne struktury danych - stosy.
Abstrakcyjne struktury danych - kolejki.
Realizacja fizyczna list, stosów i kolejek.
Grafy - definicja, cechy, rodzaje.
Reprezentacje grafów skierowanych i nieskierowanych.
Pojęcie i definicje drzew.
Cechy drzew - wysokość, moment, rząd itd.
Drzewa binarne, reprezentacja tablicowa.
Operacje na drzewach - wstawianie, usuwanie węzłów, równoważenie drzewa.
Sposoby reprezentacji grafów.
Podstawowe operacje na grafach, przeszukiwanie grafu w głąb, wszerz.
Poszukiwanie najkrótszej ścieżki w grafie.
Programowanie dynamiczne.
Minimalne drzewo rozpinające.
Problem komiwojażera.
Algorytmy zachłanne.
Rekurencja - silnia, liczby Fibonacchiego.
Rekurencja w definicjach drzew i list.
Realizacja silni i liczb Fibonacchiego bez rekurencji.
Fraktale - trójkąt Sierpińskiego i krzywa Hilberta.