Course: Algorithms and Data Structures I

Home

Section outline

Select section General

General

Collapse all Expand all
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.
- Select activity Osnovne informacije
  
  Osnovne informacije
- Select activity O predmetu
  
  O predmetu Page
- Select activity Potek predmeta
  
  Potek predmeta Page
- Select activity Uvod v predmet
  
  Uvod v predmet File
- Select activity Obvestila in ostali viri
  
  Obvestila in ostali viri
- Select activity Splošna obvestila
  
  Splošna obvestila Forum
- Select activity Pomoč in vprašanja
  
  Pomoč in vprašanja Forum
- Select activity Viri in povezave
  
  Viri in povezave Page
- Select activity Kazalci po literaturi
  
  Kazalci po literaturi File
- Select activity Kazalo snovi
  
  Kazalo snovi File
- Select activity Erasmus and non-Slovene speaking students
  
  Erasmus and non-Slovene speaking students
- Select activity Basic information
  
  Basic information Page
- Select activity Literature pointers
  
  Literature pointers File
  
  Uploaded 5/10/20, 22:08
- Select activity Table of contents
  
  Table of contents File
  
  Uploaded 11/10/19, 22:25
Select section A - Algoritmi in problemi

A - Algoritmi in problemi
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).
- Select activity Snov
  
  Snov
- Select activity Algoritmi
  
  Algoritmi File
- Select activity Razvoj algoritmov
  
  Razvoj algoritmov File
- Select activity Sprotno delo
  
  Sprotno delo
- Select activity Kviz - Algoritmi
  
  Kviz - Algoritmi Quiz
- Select activity Dodatna zabava
  
  Dodatna zabava
- Select activity What is an algorithm? - David J. Malan (TedEd video)
  
  What is an algorithm? - David J. Malan (TedEd video) URL
  
  Bodite pozorni na del, ki govori o pravilnosti algoritma.
- Select activity How to solve it?, George Polya
  
  How to solve it?, George Polya URL
  
  Odlična in kratka knjiga o reševanju problemov.
- Select activity Hrošči v dvojiškem iskanju
  
  Hrošči v dvojiškem iskanju URL
Select section B - Zahtevnost algoritmov

B - Zahtevnost algoritmov
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.
- Select activity Snov (kopiraj) (kopiraj) (kopiraj)
  
  Snov
- Select activity Analiza algoritmov
  
  Analiza algoritmov File
- Select activity Asimptotična zahtevnost
  
  Asimptotična zahtevnost File
- Select activity Demo - moč asimptotike
  
  Demo - moč asimptotike Folder
- Select activity Demo - napovedovanje časa
  
  Demo - napovedovanje časa File
- Select activity Sprotno delo
  
  Sprotno delo
- Select activity Izziv 1 - Eksperimentalno določanje časovne zahtevnosti
  
  Izziv 1 - Eksperimentalno določanje časovne zahtevnosti Assignment
- Select activity Kviz - Zahtevnost algoritmov
  
  Kviz - Zahtevnost algoritmov Quiz
- Select activity Kviz - Asimptotična zahtevnost
  
  Kviz - Asimptotična zahtevnost Quiz
- Select activity Dodatna zabava (kopiraj) (kopiraj)
  
  Dodatna zabava
- Select activity Štetje zrn riža
  
  Štetje zrn riža URL
Select section C - Seznami

C - Seznami
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.
- Select activity Snov (kopiraj)
  
  Snov
- Select activity Podatkovni tipi
  
  Podatkovni tipi File
- Select activity Polja
  
  Polja File
- Select activity Povezani seznami
  
  Povezani seznami File
- Select activity Sprotno delo (kopiraj)
  
  Sprotno delo
- Select activity Kviz - ADT
  
  Kviz - ADT Quiz
- Select activity Izziv 2 - Sklad, vrsta z dvema koncema in zaporedje
  
  Izziv 2 - Sklad, vrsta z dvema koncema in zaporedje Assignment
- Select activity Kviz - Polja in seznami
  
  Kviz - Polja in seznami Quiz
- Select activity Dodatna zabava (kopiraj)
  
  Dodatna zabava
- Select activity Vizualizacije podatkovnih struktur
  
  Vizualizacije podatkovnih struktur URL
Select section D - Drevesa

D - Drevesa
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.
- Select activity Snov (kopiraj) (kopiraj)
  
  Snov
- Select activity Drevesa
  
  Drevesa File
- Select activity Lastnosti dreves - izpeljave
  
  Lastnosti dreves - izpeljave File
- Select activity Kopica
  
  Kopica File
- Select activity Lastnosti kopice - izpeljave
  
  Lastnosti kopice - izpeljave File
- Select activity Sprotno delo (kopiraj) (kopiraj) (kopiraj)
  
  Sprotno delo
- Select activity Kviz - Drevesa
  
  Kviz - Drevesa Quiz
- Select activity Izziv 3 - Izris celovitega dvojiškega drevesa
  
  Izziv 3 - Izris celovitega dvojiškega drevesa Assignment
- Select activity Kviz - Kopica
  
  Kviz - Kopica Quiz
- Select activity Izziv 4 - Različne izvedbe prioritetne vrste
  
  Izziv 4 - Različne izvedbe prioritetne vrste Assignment
Select section E - Metode razvoja algoritmov

E - Metode razvoja algoritmov
Ali obstajajo postopki za razvoj postopkov? Seveda! Gre za metode razvoja algoritmov, s katerimi se bomo ukvarjali v tem sklopu.
- Select activity Snov (kopiraj) (kopiraj) (kopiraj) (kopiraj) (kopiraj)
  
  Snov
- Select activity Groba sila in izčrpno preiskovanje
  
  Groba sila in izčrpno preiskovanje File
- Select activity Sestopanje in razveji & omeji
  
  Sestopanje in razveji & omeji File
- Select activity Deli in vladaj
  
  Deli in vladaj File
- Select activity Požrešni algoritmi
  
  Požrešni algoritmi File
  
  Uploaded 18/12/24, 21:45
- Select activity Sprotno delo (kopiraj) (kopiraj) (kopiraj) (kopiraj) (kopiraj) (kopiraj)
  
  Sprotno delo
- Select activity Kviz - Deli in vladaj
  
  Kviz - Deli in vladaj Quiz
- Select activity Izziv 7 - Sudoku s sestopanjem
  
  Izziv 7 - Sudoku s sestopanjem Assignment
Select section F - Urejanja

F - Urejanja
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.
- Select activity Snov (kopiraj) (kopiraj) (kopiraj)
  
  Snov
- Select activity Navadna urejanja
  
  Navadna urejanja File
- Select activity Napredna urejanja
  
  Napredna urejanja File
- Select activity Zahtevnost Quicksorta
  
  Zahtevnost Quicksorta File
- Select activity Zahtevnost problema urejanja
  
  Zahtevnost problema urejanja File
- Select activity Urejanje brez primerjav
  
  Urejanje brez primerjav File
- Select activity Izbiranje
  
  Izbiranje File
- Select activity Sprotno delo (kopiraj) (kopiraj) (kopiraj) (kopiraj)
  
  Sprotno delo
- Select activity Kviz - Urejanje
  
  Kviz - Urejanje Quiz
- Select activity Izziv 5 - Urejanje polja objektov z navadno metodo
  
  Izziv 5 - Urejanje polja objektov z navadno metodo Assignment
- Select activity Dodatne aktivnosti
  
  Dodatne aktivnosti
- Select activity Bonus - Quicksorts
  
  Bonus - Quicksorts File
- Select activity Vizualizacija algoritmov urejanja
  
  Vizualizacija algoritmov urejanja URL
- Select activity Sonifikacija algoritmov urejanja
  
  Sonifikacija algoritmov urejanja URL
- Select activity Sonifikacija algoritmov urejanja 2.
  
  Sonifikacija algoritmov urejanja 2. URL
- Select activity Animacija urejanja s koši
  
  Animacija urejanja s koši URL
Select section G - Grafni algoritmi

G - Grafni algoritmi
Spet se malce vrnemo na podatkovne strukture. Ogledali si bomo grafe in omrežja ter tudi nekaj zanimivih algoritmov za sprehajanje po omrežjih.
- Select activity Snov (kopiraj) (kopiraj) (kopiraj) (kopiraj)
  
  Snov
- Select activity Osnovne definicije
  
  Osnovne definicije File
- Select activity Algoritmi z matriko sosednosti
  
  Algoritmi z matriko sosednosti File
- Select activity Obhodi grafov
  
  Obhodi grafov File
- Select activity Povezanost in komponente grafov
  
  Povezanost in komponente grafov File
  
  Uploaded 7/01/25, 12:45
- Select activity Kviz - Grafi
  
  Kviz - Grafi Quiz
- Select activity Kviz - Algoritmi na grafih
  
  Kviz - Algoritmi na grafih Quiz
- Select activity Izziv 6 - Algoritmi nad grafi
  
  Izziv 6 - Algoritmi nad grafi Assignment
- Select activity Dodatne aktivnosti (kopiraj)
  
  Dodatne aktivnosti
- Select activity Vizualizacije algoritmov (na grafih in tudi drugih)
  
  Vizualizacije algoritmov (na grafih in tudi drugih) URL
- Select activity Štetje trikotnikov malo hitreje
  
  Štetje trikotnikov malo hitreje URL
- Select activity Članek (FRI študent) o Tarjanovem algoritmu
  
  Članek (FRI študent) o Tarjanovem algoritmu File
- Select activity Optimizacija BFS algoritma
  
  Optimizacija BFS algoritma URL
Select section Domače naloge

Domače naloge
Domačih nalog se loti zgodaj in pravočasno, da ti bo dobro na Fri in boš srečno živel(-a).
- Select activity Domača naloga 1
  
  Domača naloga 1
- Select activity Naloga 1: Programabilni kalkulator
  
  Naloga 1: Programabilni kalkulator Assignment
- Select activity Oddaj nalogo 1 - Programabilni kalkulator
  
  Oddaj nalogo 1 - Programabilni kalkulator Quiz
- Select activity Naloga 2: Urejanje zaporedja števil
  
  Naloga 2: Urejanje zaporedja števil Assignment
- Select activity Oddaj nalogo 2 - Urejanje zaporedja števil
  
  Oddaj nalogo 2 - Urejanje zaporedja števil Quiz
  
  Not available unless any of: Your Email address contains ml2541 ...
  
  Not available unless any of:
  
  Your Email address contains ml2541
  
  Your ID number is 63200175
Select section Naloge, nalogice, vaje, kolokviji in izpiti

Naloge, nalogice, vaje, kolokviji in izpiti
Naloge iz algoritmov in programiranja so zabavne - to ve že vsak FRIk.
- Select activity Programerski izzivi za vedoželjne
  
  Programerski izzivi za vedoželjne
- Select activity HackerRank (programiranje dela mojstra)
  
  HackerRank (programiranje dela mojstra) URL
- Select activity Project Euler (serija programerskih izzivov)
  
  Project Euler (serija programerskih izzivov) URL
- Select activity Vadnica APS1 - zbirka vaj
  
  Vadnica APS1 - zbirka vaj
- Select activity Vadnica APS1 - PDF dokument
  
  Vadnica APS1 - PDF dokument URL
- Select activity Vadnica APS1 - Latex source on GitHub
  
  Vadnica APS1 - Latex source on GitHub URL
- Select activity Primeri kolokvijev in pisnih izpitov
  
  Primeri kolokvijev in pisnih izpitov
- Select activity Kolokvij 2019/20
  
  Kolokvij 2019/20 File
  
  Uploaded 30/11/20, 09:43
- Select activity Pisni izpit 17/18 1. rok
  
  Pisni izpit 17/18 1. rok File
  
  Uploaded 30/11/20, 09:42
- Select activity Pisni izpit 18/19 1. rok
  
  Pisni izpit 18/19 1. rok File
  
  Uploaded 11/10/19, 22:31

Section outline

Algoritmi in podatkovne strukture 1

Študijsko leto 2024 / 2025