Strukture podataka i algoritmi

Flashkartice za obnavljanje pojmova i definicija iz predmeta Strukture podataka i algoritmi.

Pokazivač

Promjenljiva koja sadrži adresu druge varijable u radnoj memoriji.

Deklaracija malloc funkcije

\text{void *malloc(size_t size);}

Algoritam

Konačan skup naredbi koji, ukoliko se prati, završava određeni zadatak ili precizno opisan način rješenja nekog problema.

Kriteriji algoritma

Kriteriji koje svaki algoritam mora zadovoljiti su ulaz, izlaz, određenost, konačnost i učinkovitost.

Djelotvornost algoritma

Svojstvo algoritma koje podrazumijeva konačno vrijeme izvršavanja.

Učinkovitost algoritma

Sposobnost algoritma da proizvede izlaz brzo u odnosu na dodijeljene resurse.

Program

Algoritam koji je prilagođen i zapisan u obliku za izvršavanje na računaru (implementacija algoritma koja ne mora zadovoljavati uslov konačnosti).

Prostorna složenost algoritma

Količina memorije potrebna za izvršavanje algoritma.

Vremenska složenost algoritma

Količina procesorskog vremena potrebna za izvršavanje algoritma.

A priori analiza

Analiza trajanja izvođenja algoritma kao funkcija broja podataka koja se vrši prije implementacije u programskom jeziku.

A posteriori analiza

Mjerenje vremena izvršavanja algoritma na računaru na određenom skupu podataka nakon implementacije.

O-notacija

Asimptotska notacija složenosti kojom se predstavlja najgore vrijeme izvođenja algoritma.

\Omega-notacija

Asimptotska notacija složenosti kojom se predstavlja najbolje vrijeme izvođenja algoritma.

\Theta-notacija

Asimptotska notacija složenosti kojom se predstavlja prosječno vrijeme izvođenja algoritma.

Kompozitni ključ

Ključ sastavljen od više atributa.

Sekundarni ključ

Primarni ključ u drugoj tabeli (zapisu, entitetu).

Serijsko pretraživanje

Pretraživanje kod kojeg zapisi ne moraju biti sortirani, složenost je $O(n)$, a prosječno se čita $\frac{n}{2}$ zapisa.

Binarno pretraživanje

Efikasno pretraživanje sortiranih podataka koje se zasniva na principu polovljenja niza za pretragu.

Raspršeno adresiranje (hashing)

Postupak transformacije ključa zapisa u adresu ili neki drugi pseudo-slučajni broj.

Gustoća pakiranja (G)

Omjer za $N$ zapisa, kapacitet bloka $C$ i broj blokova $M$, izračunat kao $G = \frac{N}{M \times C}$.

Proces

Pokrenuta instanca programa učitana u radnu memoriju računara.

Segmenti virtuelne memorije u Windows OS-u

TEXT, DATA, BSS, HEAP i STACK.

DATA segment

Segment virtuelne memorije koji služi za inicijalizirane globalne i statičke lokalne varijable.

HEAP segment

Segment virtuelne memorije koji služi za dinamički dodijeljenu memoriju.

TEXT segment

Segment virtuelne memorije u kojem se nalaze instrukcije programa.

Stog (Stack)

Struktura podataka koja radi po LIFO (last in first out) principu i služi za smještanje privremenih varijabli i povratnih adresa.

Okvir stoga (Stack frame)

Struktura na stogu koja sadrži povratnu adresu, lokalne varijable, ulazne argumente i registre procesora.

Rekurzivna procedura

Procedura koja u proračunu rezultata poziva samu sebe i mora sadržavati osnovni slučaj prema kojem napreduje.

Selection sort

Algoritam sortiranja koji nađe najmanji član niza i zamijeni ga sa prvim članom niza.

Bubble sort

Algoritam sortiranja koji radi na principu zamjene susjednih članova ukoliko nisu u dobrom redoslijedu.

Insertion sort

Algoritam sortiranja kod kojeg se uzima prvi član nesortiranog dijela niza i postavlja na ispravno mjesto u sortiranom dijelu niza.

Indirektno sortiranje

Izdvajanje tabele sa pokazivačima na ključeve koji su sortirani, umjesto zamjene mjesta velikih struktura podataka u bazi.

Red (Queue)

Struktura podataka koja funkcionira po FIFO (first in first out) principu.

Jednostruko povezana lista

Struktura koja u svakom članu (atomu) sadrži polje sa vrijednosti člana i jednostruki pokazivač na sljedeći član liste.

Dvostruko povezana lista

Struktura koja sadrži pokazivače na sljedeći i prethodni član u svakom atomu, te glavu i rep.

Stepen čvora u stablu

Broj podstabala posmatranog čvora.

Stepen stabla

Najveći stepen svih čvorova stabla.

Puno binarno stablo

Stablo dubine $k$ sa $2^k - 1$ čvorova.

Sortirano binarno stablo

Binarno stablo u kojem su ključevi u lijevom podstablu manji, a u desnom veći od njihovog korijena.

Gomila (Heap)

Potpuno binarno stablo gdje se čvorovi mogu porediti nekom relacijom (npr. $\le$ ili $\ge$).

Potpuni usmjereni graf

Graf sa $n$ vrhova koji ima $n(n-1)$ ivica.

Potpuni neusmjereni graf

Graf sa $n$ vrhova koji ima $\frac{n(n-1)}{2}$ ivica.

Petlja u grafu

Jednostavna putanja u grafu sa istim početnim i krajnjim vrhom.

Stepen vrha u grafu

Broj susjednih ivica posmatranog vrha.