Topic outline
General
COVID Prisotnost na predavanjih
Vsebina predavanj 2021/2022
7. oktober 2021 (prosojnice)
- Organizacija predmeta
- Pojem algoritma
- Fibonaccijeva števila
- O-notacija in Omega-notacija
- Klasična aritmetika
14. oktober 2021 (prosojnice)
- Deli in vladaj
- Karatsubov algoritem
- Krovni izrek deli in vladaj
- Urejanje z zlivanjem
21. oktober 2021 (prosojnice)
- Spodnja meja za algoritme, ki urejajo na podlagi primerjav
- Mediana, hitra izbira
- Hitro urejanje
- Strassenovo množenje matrik
28. oktober, 4. november 2021 (prosojnice)
- Grafi, predstavitve grafov
- Pregled v globino - razišči, lastnosti algoritma (neusmerjen graf)
- DFS, povezane komponente, predogled in poogled (neusmerjen graf)
- DFS za neusmerjene grafe, vrste povezav
- DAG oz. usmerjeni grafi brez ciklov, topološka ureditev
- Krepko povezane komponente, določanje
11. november 2021 (prosojnice)
- Pregled v širino oz. BFS
- Najkrajše poti za utežene grafe in drevo najkrajših poti
- Dijkstrov algoritem
18. november 2021 (prosojnice - iste kot prejšnjič + nekaj dodatnih strani)
- Dijkstrov algoritem
- Binarna kopica
25. november 2021 (prosojnice od zadnjič + požrešne prosojnice)
- Negativne povezave, Bellman-Ford, DAG
- Požrešni algoritmi, Kruskal
2. december 2021 (dopolnjene požrešne prosojnice)
- Union-find
- Primov algoritem
- Huffmanovo kodiranje
9. december 2021 (prosojnice od zadnjič + prosojnice)
- Huffmanovo kodiranje
- Dinamično programiranje
- Najkrajše poti v DAG
- Najdaljše naraščajoče podzaporedje
- Urejevalna razdalja
16. december 2021 (dopolnjene prosojnice od zadnjič)
- Urejevalna razdalja
- Zvezni in 0/1-nahrbtnik (z in brez ponavaljanja)
24. december 2021 (dopolnjene prosojnice od zadnjič in predzadnjič)
- Problem Trgovskega potnika
- Optimalno množenje pravokotnih matrike
- Najkrajše poti med vsemi točkami v grafu
- Maksimalna neodvisna množica na drevesu
- Organizacija predmeta
Domače naloge
Navodila za reševanje domačih nalog
Naredite si uporabniški račun na https://putka-upm.acm.si s študentskim email naslovom. Uporabniško ime naj odraža vaše ime in priimek. Za ekipo vpišite "FMF PSA1 2021", za kraj pa "Ljubljana".
Naloge oddate na spletni učilnici, oddajte le eno datoteko z izvorno kodo programa, poimenovano
<ime>_<priimek>_<št. naloge>.<končnica>brez čšž, npr.neza_zagar_1.py. Na vrhu svoje rešitve v komentarje napišite glavo kot prikazano s primerom:# Naloga 1: Podkupnine
# Neža Žagar, 20140121
# matematika, 3. letnikNaloge rešujte samostojno. Oddane rešitve bodo po koncu roka za oddajo preverjene za podobnost in testirane na enak način kot ga imate na voljo uporabiti za vajo. Izbrani študeti (ne glede na sumljivost oddaje) bodo tudi poklicani na zagovor svoje rešitve.