Algoritmi i strukture podataka: Osnovni pojmovi

Osnovni pojmovi

• Struktura podataka i algoritam zajedno organizuju podatke i rešavaju problem.
• Algoritam je niz koraka sa osobinama: determinisanost, diskretnost, rezultativnost, elementarnost, masovnost.
• Pseudo jezik je mešavina prirodnog i programskog jezika za pisanje algoritma.
• Postoje rekurzivni, paralelni i distribuirani algoritmi. Rekurzivni algoritam poziva sam sebe za manji problem. Paralelni koriste više procesora, a distribuirani više računara.
• Mašinski jezik je binarni, dok je izvorni jezik čitljiv ljudima.

Programske naredbe i operatori

• Strukturne naredbe obuhvataju sekvencu, selekciju i petlju.
• Operatori računaju ili porede vrednosti (npr. +, &&, ==).
• Elementarne naredbe su osnovne radnje, a strukturne upravljaju tokom izvršavanja.
• Identifikatori su imena koja dodeljuje korisnik, dok su ključne reči rezervisane.
• Aritmetički operatori izvode matematičke operacije (npr. +).
• Debugger se koristi za pronalaženje grešaka u kodu.
• Linker spaja kod, a loader ga učitava u memoriju.
• Logički operatori donose odluke (npr. &&).
• Operator dekrementiranja smanjuje vrednost za 1 (npr. x--).
• Operator dodele postavlja vrednost promenljive (npr. x = 5).
• Relacijski operatori služe za poređenje (npr. >, ==).

Kontrola toka

• Ciklus ponavlja deo koda (primeri: for, while).
• Sekvenca izvršava naredbe redom.
• Selekcija bira put izvršavanja (vrste: if, switch).

Algoritamske tehnike

• "Podeli pa vladaj" deli problem na manje potprobleme.
• Dinamičko programiranje pamti prethodna rešenja da bi izbeglo ponovno računanje.
• Linearno programiranje koristi se za optimizaciju uz zadate uslove.
• Postoje različiti algoritmi za pretraživanje podataka.
• Genetički algoritmi koriste principe evolucije.
• Heuristički algoritmi daju brza, ali približna rešenja.
• Pohlepni algoritmi biraju lokalno najbolje rešenje u svakom koraku.
• Slučajni algoritmi koriste slučajne vrednosti u svom radu.
• Numeracija u slučajnim algoritmima prati nasumične korake.

Testiranje i Složenost

• Strukturno testiranje proverava kod, a funkcionalno testiranje proverava funkcionalnost.
• Verifikacija proverava da li je sve urađeno, a validacija proverava da li radi ispravno.
• Storage complexity se odnosi na memoriju, a time complexity na vreme izvršavanja.
• Time complexity predstavlja vreme, a processing complexity broj koraka.

Programski jezici i faze razvoja

• Proceduralni jezik (npr. C) se razlikuje od objektno-orijentisanog jezika (npr. C++).
• "=" je operator dodele, a "==" je operator poređenja.
• Realne konstante imaju decimalni zapis, dok celobrojne nemaju.
• Faze sinteze koda su leksička, sintaksna i semantička analiza.
• Postoje izvorni, međujezik i mašinski jezici.
• Memoizacija pamti rešenja da bi ubrzala rad programa.
• Četvrta i peta faza rešavanja problema su kodiranje i testiranje.
• Prve tri faze rešavanja problema su definisanje problema, dizajn algoritma i izbor programskog jezika.
• Metod srednjeg vremena izračunava prosečno vreme izvršavanja.
• Analiza algoritma proučava njegovo ponašanje, a složenost algoritma meri vreme i memoriju.
• Aproksimacija je procena rešenja za teške probleme.
• Kubna složenost O(n³) podrazumeva tri ugnježdene petlje.
• Kvadratna složenost O(n²) podrazumeva dve ugnježdene petlje.
• Leksička analiza se bavi tokenima, a sintaksna analizira pravila jezika.
• Linearna složenost O(n) tipična je za sekvencijalnu pretragu.
• Implementacija algoritma podrazumeva pisanje koda.
• Prevođenje programa transformiše kod u mašinski jezik.
• Semantička analiza se bavi značenjem koda, a sintaksna strukturom.
• Vremenska složenost meri trajanje izvršavanja, a prostorna složenost potrebnu memoriju.

Elementi programiranja

• Konstante su vrednosti koje se ne menjaju i mogu biti numeričke, karakterne ili simboličke.
• Separatori razdvajaju elemente koda, na primer zarez.
• Analiza koda uključuje lekseme, sintaksu i semantiku.
• Prototip funkcije je njena deklaracija sa tipovima argumenata i povratnom vrednošću.

Strukture podataka

• Binarno stablo je struktura gde svaki čvor ima najviše dva potomka.
• Cirkularni niz ima poslednji element povezan sa prvim.
• Dvodimenzionalna polja predstavljaju tabele sa redovima i kolonama.
• Graf se sastoji od čvorova i veza između njih.
• String je niz karaktera koji se završava sa '\0'.
• Kompletno stablo ima svaki čvor sa istim brojem potomaka.
• Nizovi su kolekcije elemenata istog tipa, indeksirani i smešteni uzastopno u memoriji.
• Pokazivači čuvaju memorijske adrese; koriste se operatori * i &.
• Prioritetni red vraća element sa najvećim prioritetom kao prvi.
• Puno stablo ima sve puteve od korena do listova iste dužine.
• Rekurzivne funkcije pozivaju same sebe.
• List je čvor bez potomaka, a dubina stabla je dužina najdužeg puta do lista.
• Red se može implementirati pomoću niza ili liste.
• Element se dodaje u listu na početak ako je prazna, inače na kraj.
• Dek (dvostrani red) omogućava dodavanje i brisanje elemenata na oba kraja.
• Stek funkcioniše po principu LIFO (poslednji ulazi, prvi izlazi).

Razlike između struktura

• Dek omogućava operacije na oba kraja, dok red omogućava dodavanje na jednom i uklanjanje na drugom.
• Niz ima fiksnu veličinu, dok je lista dinamična.
• Stek funkcioniše po principu LIFO, a dek omogućava operacije na oba kraja.
• Stek je LIFO, dok je red FIFO (prvi ulazi, prvi izlazi).

Deklaracije i operacije

• Deklaracija niza karaktera: char ime[] = "Ana";
• Deklaracija strukture: struct Osoba { int godina; char ime[50]; };
• Deklaracija unije: union Broj { int i; float f; };
• Kopiranje nizova se vrši pomoću petlje (npr. for petlje).
• Kreiranje korisničkog tipa: typedef int INTEGER;
• Struktura alocira poseban prostor za svaki član, a unija deli isti prostor za sve članove.
• Rad sa datotekama uključuje otvaranje, čitanje, pisanje i zatvaranje.
• Enumeracije predstavljaju imenovane celobrojne konstante.
• Pretraga grafova se može vršiti pomoću DFS (Depth-First Search) i BFS (Breadth-First Search).
• Operacije nad dekom: push, pop, front, back.
• Operacije nad redom: dodavanje na kraj, uklanjanje sa početka.
• Operacije nad stekom: push i pop.
• Režimi rada sa datotekama: r (čitanje), w (pisanje), a (dodavanje) itd.
• #define se koristi za definisanje simboličkih konstanti.
• & operator vraća adresu promenljive.
• fopen() funkcija otvara datoteku.
• Funkcija (potprogram) je višekratni deo koda.
• main() funkcija je početna tačka programa.
• for-each petlja prolazi kroz sve elemente kolekcije.
• typedef kreira novo ime za postojeći tip.
• Indirekcija (operator *) pristupa vrednosti na adresi.
• r+ režim omogućava čitanje i pisanje, ali datoteka mora postojati.
• Simboličke konstante su imena koja zamenjuju brojeve.
• w+ režim omogućava čitanje i pisanje, ali briše sadržaj datoteke ako postoji.
• EOL označava kraj reda, a EOF kraj datoteke.
• Append dodaje sadržaj na kraj datoteke, dok Write prepisuje postojeći sadržaj.
• strcat() spaja dva stringa.
• strchr() pronalazi prvo pojavljivanje karaktera u stringu.
• strcmp() upoređuje dva stringa.
• strstr() traži podstring u stringu.
• puts() ispisuje string, a gets() učitava string.
• FIFO (First-In, First-Out) princip koristi red.
• LIFO (Last-In, First-Out) princip koristi stek.
• Pokazivač pokazuje poziciju u datoteci.
• Liste i pokazivači se koriste za povezivanje čvorova.
• Ime niza je pokazivač na prvi element niza.
• Obilazak binarnog stabla može biti levo-desno, vrh-dno ili dno-vrh.
• Definicija funkcije sadrži telo funkcije sa kodom.
• Deklaracija funkcije je njen prototip.