Algoritmi in podatkovne strukture 1
Section outline
-
Algoritmi in podatkovne strukture 1
Študijsko leto 2024 / 2025
Dobrodošli na straneh predmeta Algoritmi in podatkovne stukture 1 (APS1) za 2. letnik Visokošolskega strokovnega študija računalništvo in informatika Fakultete za računalništvo in informatiko, Univerza v Ljubljani.
Pomni: Prosojnice so samo pripomoček za predavanja. Primere, algoritme, izpeljave itd. bomo delali na tablo, zato poskrbite za ustrezne zapiske. Samostojno delanje zapiskov utrjuje človekov spomin.
-
Preden se lotimo svetovnih problemov, si oglejmo osnovne pojme kot sta problem in algoritem. Ogledali si bomo tudi, kako algoritme razvijamo in kako vemo, da algoritem res rešujem naš problem (da je pravilen).
-
Bodite pozorni na del, ki govori o pravilnosti algoritma.
-
-
Za vsak (pravilen) algoritem je ključno, da razumemo, katere in koliko virov porabi za svoje izvajanje. Na to vprašanje odgovarja analiza algoritmov, kjer se uporablja predvsem asimptotična notacija. Namig: asimptotična notacija močno poenostavi analizo algoritmov.
-
Dobrih algoritmov ni brez dobrih podatkovnih struktur. Ogledali si bomo strukture kot sta sklad in vrsta. Vse skupaj pa bomo izvedli (implementirali) s poljem in povezanim seznamom. Nato pa začnemo reševati svetovne probleme.
-
V tem sklopu si bomo ogledali osnovne vrste dreves in nekaj tehnik plezanja po njih. Za poslastico pa še najlepše drevo na svetu - kopica.
-
Ali obstajajo postopki za razvoj postopkov? Seveda! Gre za metode razvoja algoritmov, s katerimi se bomo ukvarjali v tem sklopu.
-
In končno je na vrsti sklop o algoritmih urejanja zaporedij. Gre za temeljne algoritme, ki jih mora poznati vsak študent računalništva, četudi jih ne bo nikoli kasneje v življenju sam programiral, jih bo pa gotovo veliko uporabljal. Začeli bomo z navadnimi algorimi, na koncu pa bomo znali celo hitro urejati.
-
Spet se malce vrnemo na podatkovne strukture. Ogledali si bomo grafe in omrežja ter tudi nekaj zanimivih algoritmov za sprehajanje po omrežjih.
-
Domačih nalog se loti zgodaj in pravočasno, da ti bo dobro na Fri in boš srečno živel(-a).
-
Oddaj nalogo 2 - Urejanje zaporedja števil Kviz