Informatyka studia – Algorytmy i struktury danych

Algorytm

Zespół kroków do rozwiązania problemu lub wykonania zadania.

Złożoność czasowa

Mierzy czas działania algorytmu w zależności od rozmiaru danych wejściowych.

Złożoność przestrzenna

Mierzy ilość pamięci potrzebnej przez algorytm w trakcie jego działania.

Algorytm sortowania bąbelkowego

Prosty algorytm sortujący, który porównuje pary elementów i zamienia je miejscami.

Rekurencja

Technika, w której funkcja wywołuje samą siebie w celu rozwiązania problemu.

Algorytm Dijkstry

Znajduje najkrótsze ścieżki w grafie z nieujemnymi wagami.

Pseudokod

Styl notacji, umożliwiający przedstawienie algorytmu w sposób zrozumiały dla ludzi.

Algorytm A*

Służy do znajdowania najkrótszej ścieżki w grafie, wykorzystując heurystyki.

Podział i zdobycie

Strategia algorytmiczna, która dzieli problem na mniejsze podproblemy.

Algorytm Kruskala

Znajduje minimalne drzewo rozpinające w grafie nieskierowanym.

Szukaj binarny

Algorytm wyszukiwania w posortowanej tablicy, działający w czasie $\displaystyle O(log n)$.

Algorytm QuickSort

Algorytm sortujący działający w czasie średnim $\displaystyle O(n imes log n)$.

Heurystyka

Metoda rozwiązywania problemów na podstawie przybliżeń i doświadczenia.

Algorytm Bellmana-Forda

Służy do znajdowania najkrótszej ścieżki w grafie z ujemnymi wagami.

Kolejka priorytetowa

Struktura danych, która przechowuje elementy w kolejności priorytetowej.

Stos

Struktura danych działająca w trybie LIFO (Last In, First Out).

Tablica asocjacyjna

Struktura danych przechowująca pary klucz-wartość.

Złożoność algorytmu

Klasyfikacja algorytmu na podstawie jego wydajności w czasie lub przestrzeni.

Lista

Struktura danych, która przechowuje kolekcję elementów w uporządkowanej formie.

Drzewo binarne

Struktura danych, w której każdy węzeł ma maksymalnie dwóch potomków.

Graf

Zbiór węzłów połączonych krawędziami, reprezentujący zależności.

Tablica dynamiczna

Tablica, której rozmiar może się zmieniać w trakcie działania programu.

Zbiór

Struktura danych przechowująca unikalne elementy bez określonej kolejności.

HashMap

Struktura danych wykorzystująca funkcję skrótu do przechowywania danych.

Drzewo AVL

Samobalansujące drzewo binarne, które zapewnia $\displaystyle O(log n)$ dostęp.

Kopiec

Struktura danych, która spełnia właściwości kopca max lub min.

Lista jednokierunkowa

Lista, w której każdy węzeł wskazuje tylko na następny.

Lista dwukierunkowa

Lista, w której każdy węzeł wskazuje zarówno na następny, jak i poprzedni.

Struktura danych FIFO

Przechowuje elementy w kolejności, w jakiej zostały dodane.

Struktura danych LIFO

Przechowuje elementy w odwrotnej kolejności do ich dodania.

Kolejka

Struktura danych, która działa na zasadzie FIFO.

Reprezentacja grafu

Można realizować za pomocą list sąsiedztwa lub macierzy sąsiedztwa.

Drzewo czerwono-czarne

Samobalansujące drzewo binarne, które zapewnia złożoność $\displaystyle O(log n)$.

Algorytm BFS

Algorytm przeszukiwania grafu w szerz.

Algorytm DFS

Algorytm przeszukiwania grafu w głąb.