Big Data Infrastructure - brezplačen tečaj Šole za analizo podatkov, 4 semestri, datum: 5. december 2023.

Vsak študent mora uspešno opraviti vsaj tri predmete v semestru. Na primer, če sta v glavnem programu dva, potem morate izbrati enega od posebnih tečajev.

Znanje se preverja predvsem z domačimi nalogami – izpiti in preizkusi znanja se izvajajo le pri nekaterih predmetih.

Prvi semester

Obvezno
Algoritmi in podatkovne strukture, 1. del

01 Kompleksnost in računalniški modeli. Analiza računovodskih vrednosti (začetek)
02 Analiza knjigovodskih vrednosti (konec)
03 Algoritmi spajanja in hitrega razvrščanja
04 Redna statistika. Heaps (začetek)
05 Heaps (konec)
06 Zgoščevanje
07 Iskalna drevesa (začetek)
08 Iskalna drevesa (nadaljevanje)

09 Išči drevesa (konec). Sistem disjunktnih množic
10 Cilji RMQ in LCA
11 Podatkovne strukture za geometrijsko iskanje
12 Problem dinamične povezljivosti v neusmerjenem grafu

Računalniška arhitektura in operacijski sistemi

01 UNIX in programiranje v C: ukazna vrstica, nadzor procesa, kanali, signali. Implementacija lupine ukazne vrstice.
02 x86 sestavljalnik: aritmetika, prehodi, pogoji in klici funkcij. Sklad, premikanje po nizu navzgor.
03 Povezovanje programov in formata ELF. Dinamično povezovanje.
04 Koncept konteksta in tok izvajanja. Izvajanje lahkih niti.
05 Preventivna večopravilnost: podpora procesorja x86 in implementacija procesov v jedru UNIX.
06 Večjedrna arhitektura: koherenca predpomnilnika in pomnilniški modeli. Sinhronizacijski primitivi v večnitnih programih.
07 Razporejanje procesov na enem jedru in na več jedrih.
08 Zunanji pomnilnik: trdi diski in pogoni SSD. Načela delovanja datotečnih sistemov.
09 Virtualizacija: strojna in programska oprema. Binarno oddajanje.

Usposabljanje jezika C++, 1. del

C++ je močan jezik z bogato dediščino. Tisti, ki so šele stopili na pot osvajanja tega jezika, se zelo zlahka izgubijo v obilici tehnik in tehnik, ustvarjenih v zadnjih 30 letih. Predmet poučuje "Modern C++" - sodobno podmnožico jezika (standardi 11, 14 in 17). Veliko pozornosti je namenjeno orodjem in knjižnicam – stvarem, ki niso del jezika, a brez njih ne bo mogoče zgraditi velikega in kompleksnega projekta.
01 Uvod v C++.
02 Konstante. Kazalci in povezave. Posredovanje argumentov funkciji.
03 Razredi.
04 Dinamično upravljanje pomnilnika.
05 Spremenljivke, kazalci in reference.
06 Upravljanje pomnilnika, pametni kazalci, RAII.
07 Standardna knjižnica predlog.
08 Dedovanje in virtualne funkcije.
09 Odpravljanje napak.
10 oblikovalskih vzorcev.
11 Imenski prostori Semantika premika Popolno posredovanje.
12 Predstavitev struktur in razredov v spominu. Usklajevanje podatkov. Kazalci na člane/metode razreda. Različne predloge.

Drugi mandat

Obvezno
Algoritmi in podatkovne strukture, 2. del

01 Obhod po širini. Prvo prečenje globine (začetek)
02 Prehod globine (nadaljevanje)
03 Prehod v globino (konec). 2-kosi
04 Iskanje najkrajših poti (začetek)
05 Iskanje najkrajših poti (nadaljevanje)
06 Minimalna vpeta drevesa
07 Minimalni kosi. Iskanje podnizov (začetek)
08 Iskanje podnizov (nadaljevanje)
09 Iskanje podnizov (konec)
10 Priponska drevesa (začetek)
11 Priponska drevesa (končnica). Nizi pripon (začetek)
12 nizov pripon (konec)
13 Najdaljši skupni podnizi. Približno iskanje podniza.

Usposabljanje jezika C++, 2. del

Drugi del tečaja C++, ki pokriva napredne teme in jezikovne zmožnosti.

01 Večnitno programiranje. Sinhronizacija niti z uporabo muteksov in pogojnih spremenljivk.
02 Atomske spremenljivke. Pomnilniški model C++. Primeri podatkovnih struktur brez zaklepanja.
03 Napredne tehnike metaprogramiranja v C++. Metafunkcije, SFINAE, koncepti.
04 Konkurenčno programiranje, interakcija z omrežjem.
05 llvm arhitektura. Delo z drevesom razčlenjevanja C++. Razvoj orodij za analizo kode C++.

Na izbiro
Teorija in praksa sočasnosti

Predmet je namenjen tekmovalnim sistemom in nalogam v najširšem pomenu: od nivoja tekmovanja med procesorskimi jedri za pisanje v eno celico. pomnilnik za porazdeljene sisteme, ki želijo podvojiti svoje stanje na več strežnikih na dosleden in do napak način.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md

oz
Pojdi jezik

01 Uvod. Program tečaja. Poročanje o poteku, kriteriji ocenjevanja. Filozofija oblikovanja. če, zamenjati, za. Pozdravljen, svet. Argumenti ukazne vrstice. Število besed. Animirani gif. Pridobivanje URL-ja. Sočasno pridobivanje URL-ja. spletni strežnik. Tour of go. Lokalna nastavitev IDE. gofmt. goimports. linting.
02 Osnovne jezikovne strukture. imena, deklaracije, spremenljivke, dodelitve. tipske deklaracije. paketi in datoteke. Obseg. Ničelna vrednost. Dodelitev pomnilnika. Stack vs heap. Osnovni tipi podatkov. Konstante. Sestavljeni podatkovni tipi. Nizi. Rezine. Zemljevidi. Strukture. JSON. besedilo/predloga. niz in []bajt. Delo z unicode. Nadomestni znak Unicode. Funkcije. Funkcije s spremenljivim številom argumentov. Anonimne funkcije. Napake.
03 Metode. Sprejemnik vrednosti proti sprejemniku kazalca. Vdelava. Vrednost metode. Enkapsulacija. Vmesniki. Vmesniki kot pogodbe. io. Pisatelj, io. Reader in njihove izvedbe. vrsta. Vmesnik. napaka. http. Voditelj. Vmesniki kot naštevanja. Tipska trditev. Tipsko stikalo. Večji kot je vmesnik, šibkejša je abstrakcija. Obdelava napake. panic, defer, recover. napake.{Unwrap, Is, As}. fmt. Errorf. %w.
04 Goroutine in kanali. urni strežnik. echo strežnik. Velikost kanala. Blokiranje in neblokiranje branja. izberite izjavo. Aksiomi kanala. čas. Po. čas. NewTicker. Vzorec cevovoda. Odpoved. Vzporedna zanka. sinhronizacija WaitGroup. Obravnava napak v vzporedni kodi. errgroup. skupina. Sočasni spletni pajek. Sočasno prečkanje imenika.
05 Napredno testiranje. Podtesti. testiranje. B. (T).Logf. (T).Skipf. (T).FailNow. testiranje. Short(), testne zastavice. Generacija posmehov. pričati/{zahtevati, trditi}. pričevati/apartma. Testna naprava. Integracijski testi. Goroutine detektor puščanja. TestingMain. Pokritost. Primerjava meril uspešnosti.
06 Napredno testiranje. Podtesti. testiranje. B. (T).Logf. (T).Skipf. (T).FailNow. testiranje. Short(), testne zastavice. Generacija posmehov. pričati/{zahtevati, trditi}. pričevati/apartma. Testna naprava. Integracijski testi. Goroutine detektor puščanja. TestingMain. Pokritost. Primerjava meril uspešnosti.
07 Kontekst paketa. Posredovanje podatkov v obsegu zahteve. http vmesna programska oprema. chi. Usmerjevalnik. Zahtevaj preklic. Napredni vzorci sočasnosti. Asinhroni predpomnilnik. Elegantna zaustavitev strežnika. kontekstu. WithTimeout. Paketiranje in preklic.
08 baza podatkov/sql, sqlx, delo z bazami podatkov, redis.
09 Odsev. odražati. Tipkajte in razmislite. Vrednost. struct oznake. net/rpc. kodiranje/gob. sinhronizacija Zemljevid. odražati. DeepEqual.
10 Implementacije paketa io, Reader in Writer iz standardne knjižnice. Programiranje na nizki ravni. nevaren. Binarni paket. bajtov. Medpomnilnik. cgo, sistemski klic.
11 GC arhitektura. Ovira za pisanje. Rast sklada. GC premor. GOGC. sinhronizacija Bazen. Goroutine planer. GOMACPROCS. Uhajajoče niti.
12 Go tooling. pprof. Profiliranje procesorja in pomnilnika. Navzkrižna kompilacija. GOOS, GOARCH. CGO_ENABLED=0. Zgradite oznake. go moduli. godoc. x/analiza. Generiranje kode.
13 Uporabne knjižnice. Aplikacije CLI s cobro. Protobuf in GRPC. zap beleženje.

Tretji semester

Obvezno
Algoritmi v zunanjem pomnilniku

Predmet seznani študente z osnovnimi principi konstruiranja algoritmov za delo s podatki, ki ne sodijo v RAM računalnika.

01 Algoritmi v zunanjem pomnilniku.
02 Algoritmi, ki ne upoštevajo predpomnilnika.
03 Algoritmi za obdelavo tokovnih podatkov.

Porazdeljeni sistemi

Priporočeni posebni tečaji
Trdnost kriptografskih sistemov

01 Osnovni pristopi in principi sodobne kriptografije. Nasprotniški model, formalizacija koncepta moči, problem ocenjevanja moči in s tem povezani problemi, delitev na primitive in protokole, faze "življenja" kriptografskega sistema.
02 Zaupnost. Vsakdanje definicije zaupnosti, pristopi k formalizaciji (informacijsko-teoretični model sovražnika, modeli KR, PR, LOR, ROR, IND, CPA, CCA), simetrični sistem šifriranja, uporaba teoretičnih informacij kompleksnosti za določitev razmerja med modeli. Razmerja med osnovnimi nasprotniškimi modeli za ocenjevanje moči šifrirnih sistemov.
03 Pristopi k izgradnji šifrirnih sistemov. Gradnja iz nič. Konstrukcije na osnovi bločnih šifer, definicija bločne šifre, glavne značilnosti, pristopi k konstrukciji in lastnosti. Modela PRP in PRF. Paradoks problema rojstnega dne. Lema o razmerju med odpornostjo v modelih PRF in PRP.
04 Načini šifriranja. Osnovni načini šifriranja: ECB, CBC, CFB, OFB, CTR. Osnovne lastnosti delovanja. Trajnost CTR v LOR-CPA, nestabilnost ECB v LOR-CPA. Nestabilnost osnovnih modusov v modelih CCA.
05 Integriteta. Opredelitev pojma integriteta. Pristopi k formalizaciji (model UF-CMA, modeli na podlagi diskriminacijske naloge, model PRF). Kode za preverjanje pristnosti sporočil in funkcije za generiranje posnemanih vstavkov. Zasnove, ki temeljijo na blokovnih šifrah: CBC-MAC, XCBC, TMAC, OMAC. Ranljivi načini.
06 Zgoščevalne funkcije. Definicija, osnovne lastnosti, pristopi k konstrukciji, formalizacija in sorodni problemi. Primeri uporabe zgoščevalnih funkcij: zgoščevanje gesel, ekstrakcija entropije. Konstruiranje trkov in praslik iz nizov nizke kardinalnosti.
07 HMAC, KDF, PRF, DRNG vezja. Diagram HMAC, osnovni koraki za pridobitev ocene odpornosti. Diverzifikacija ključev in princip ločevanja ključev, sheme KDF in PRF. Psevdonaključni generator, vezja DRNG.
08 Obremenitev ključa. Težava z obremenitvijo ključa. Glavne metode za zmanjšanje obremenitve ključa so zunanje in notranje pretvorbe ključev. Vzporedne in serijske sheme ponovnega ključa, osnovne lastnosti. Drevo ključev. Interna sprememba ključa in način CTR-ACPKM.
09 Šifriranje z zaščito pred imitacijo. Oblikovanje problema. Splošne strukture (EtA, AtE, A&E) in njihove lastnosti. Primeri ranljivih načinov za zagotavljanje zaupnosti in celovitosti z enim ključem. Načini šifriranja AEAD: GCM, MGM.
10 Varen komunikacijski kanal. Pojem varnega komunikacijskega kanala: vrste kanalov, osnovne lastnosti (celovitost in zaupnost pretoka podatkov). Primeri ranljivih protokolov. Snemanje protokola TLS 1.3.

Četrti semester

Na izbiro
Teorija in praksa sočasnosti

Predmet je namenjen tekmovalnim sistemom in nalogam v najširšem pomenu: od nivoja tekmovanja med procesorskimi jedri za pisanje v eno celico. pomnilnik za porazdeljene sisteme, ki želijo podvojiti svoje stanje na več strežnikih na dosleden in do napak način.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md

oz
Pojdi jezik
01 Uvod. Program tečaja. Poročanje o poteku, kriteriji ocenjevanja. Filozofija oblikovanja. če, zamenjati, za. Pozdravljen, svet. Argumenti ukazne vrstice. Število besed. Animirani gif. Pridobivanje URL-ja. Sočasno pridobivanje URL-ja. spletni strežnik. Tour of go. Lokalna nastavitev IDE. gofmt. goimports. linting.
02 Osnovne jezikovne strukture. imena, deklaracije, spremenljivke, dodelitve. tipske deklaracije. paketi in datoteke. Obseg. Ničelna vrednost. Dodelitev pomnilnika. Stack vs heap. Osnovni tipi podatkov. Konstante. Sestavljeni podatkovni tipi. Nizi. Rezine. Zemljevidi. Strukture. JSON. besedilo/predloga. niz in []bajt. Delo z unicode. Nadomestni znak Unicode. Funkcije. Funkcije s spremenljivim številom argumentov. Anonimne funkcije. Napake.
03 Metode. Sprejemnik vrednosti proti sprejemniku kazalca. Vdelava. Vrednost metode. Enkapsulacija. Vmesniki. Vmesniki kot pogodbe. io. Pisatelj, io. Reader in njihove izvedbe. vrsta. Vmesnik. napaka. http. Voditelj. Vmesniki kot naštevanja. Tipska trditev. Tipsko stikalo. Večji kot je vmesnik, šibkejša je abstrakcija. Obdelava napake. panic, defer, recover. napake.{Unwrap, Is, As}. fmt. Errorf. %w.
04 Goroutine in kanali. urni strežnik. echo strežnik. Velikost kanala. Blokiranje in neblokiranje branja. izberite izjavo. Aksiomi kanala. čas. Po. čas. NewTicker. Vzorec cevovoda. Odpoved. Vzporedna zanka. sinhronizacija WaitGroup. Obravnava napak v vzporedni kodi. errgroup. skupina. Sočasni spletni pajek. Sočasno prečkanje imenika.
05 Napredno testiranje. Podtesti. testiranje. B. (T).Logf. (T).Skipf. (T).FailNow. testiranje. Short(), testne zastavice. Generacija posmehov. pričati/{zahtevati, trditi}. pričevati/apartma. Testna naprava. Integracijski testi. Goroutine detektor puščanja. TestingMain. Pokritost. Primerjava meril uspešnosti.
06 Sočasnost s skupnim pomnilnikom. sinhronizacija Mutex. sinhronizacija RWMutex. sinhronizacija Cond. atomsko sinhronizacija Enkrat. Detektor dirke. Asinhroni predpomnilnik. Delo z bazo podatkov. baza podatkov/sql. sqlx.
07 Kontekst paketa. Posredovanje podatkov v obsegu zahteve. http vmesna programska oprema. chi. Usmerjevalnik. Zahtevaj preklic. Napredni vzorci sočasnosti. Asinhroni predpomnilnik. Elegantna zaustavitev strežnika. kontekstu. WithTimeout. Paketiranje in preklic.
08 baza podatkov/sql, sqlx, delo z bazami podatkov, redis.
09 Odsev. odražati. Tipkajte in razmislite. Vrednost. struct oznake. net/rpc. kodiranje/gob. sinhronizacija Zemljevid. odražati. DeepEqual.
10 Implementacije paketa io, Reader in Writer iz standardne knjižnice. Programiranje na nizki ravni. nevaren. Binarni paket. bajtov. Medpomnilnik. cgo, sistemski klic.
11 GC arhitektura. Ovira za pisanje. Rast sklada. GC premor. GOGC. sinhronizacija Bazen. Goroutine planer. GOMACPROCS. Uhajajoče niti.
12 Go tooling. pprof. Profiliranje procesorja in pomnilnika. Navzkrižna kompilacija. GOOS, GOARCH. CGO_ENABLED=0. Zgradite oznake. go moduli. godoc. x/analiza. Generiranje kode.
13 Uporabne knjižnice. Aplikacije CLI s cobro. Protobuf in GRPC. zap beleženje.

oz
Baza podatkov
01 Vmesniki sodobnih baz podatkov: relacijski, ključ-vrednost, dokument, graf. Relacijska algebra in jezik SQL.
02 Delo z diskom v klasičnem relacijskem DBMS: strani, področje strani, izgon iz bazena.
03 Izvajanje poizvedb SQL: razčlenjevanje izrazov, načrtovanje, izvedba. Tolmačenje in generiranje kode z uporabo LLVM.
04 Indeksi v relacijskih DBMS: vrste indeksov, načini shranjevanja, uporaba v poizvedbah.
05 Transakcije: akronim ACID, ravni izolacije, izvajanje transakcij prek ključavnic in MVCC.
06 Obnovitev po katastrofi: dnevnik, kontrolne točke, algoritem ARIES.
07 Shranjevanje podatkov z metodo Log-Structured Merge Tree.
08 DBMS na podlagi stolpcev: prednosti, lastnosti, algoritmi za stiskanje podatkov.
09 Distribuirani DBMS: razčlenjevanje, transakcije, izvajanje poizvedb.
10 DBMS v glavnem pomnilniku. Podatkovne strukture za indekse v pomnilniku.

oz
Računalniška omrežja
01 Uvod v omrežne tehnologije. Zgodovina omrežij, omrežni protokoli, organizacija omrežne interakcije v omrežju enakovrednih in povezovanje omrežij enakovrednih med seboj.
02 Transport. Omrežni model OSI/ISO. TCP, vzpostavitev omrežne povezave, primerjava TCP in UDP. Analiza Tcpdump – bajti v letu, ponovno prenaša grafe. Metode za nadzor pretoka podatkov v seji TCP. Različne vrste TCP sej in upravljanje pasovne širine prenesenih podatkov v paketnih omrežjih.
03 Usmerjanje. Koncept usmerjanja v omrežjih. Statično in dinamično usmerjanje. Osnove dinamičnega usmerjanja. Protokol dinamičnega usmerjanja - OSPF. Protokoli za usmerjanje vektorjev razdalje. Pregled usmerjevalnega protokola BGP - tipi sporočil, atributi BGP, izbira optimalne poti v BGP.
04 Kako deluje internet: BGP in DNS. Internetno usmerjanje. Pregled protokola DNS.
05 Omrežja v velikih podatkovnih centrih. Značilnosti arhitekture omrežij podatkovnih centrov. Zahteve za omrežja podatkovnih centrov. Arhitektura CLOS za omrežja podatkovnih centrov.
06 Zamude v omrežjih. Značilnosti gradnje velikih hrbteničnih omrežij. Razlogi za zamude pri prenosu podatkov po hrbteničnih omrežjih.
07 Skaliranje in razpoložljivost internetnih storitev. Tehnologije za uravnoteženje obremenitve in storitvena arhitektura.
08 MPLS in SR, programiranje omrežja. Tehnologije MPLS in Segment Routing za gradnjo hrbteničnih omrežij. Namen tehnologije MPLS, protokoli za izmenjavo oznak.
09 Principi delovanja omrežnih naprav. Arhitektura usmerjevalnika, značilnosti obdelave omrežnega prometa znotraj omrežnih naprav.
10 Oblaki. Osnove programsko definiranega omrežja – Protokoli, ki se uporabljajo za gradnjo programsko definiranih omrežij. Integracija virtualizacijskih platform in omrežne infrastrukture.

oz
Kriptografski protokoli
01 Osnove asimetrične kriptografije. Glavna razlika med asimetrično kriptografijo in simetrično kriptografijo. Glavne ideje: protokol za generiranje skupnega ključa, šifriranje z javnim ključem, elektronski podpis (težave, ki jih je treba rešiti, intuitivno razumevanje varnostnih lastnosti). Specifične kriptografske sheme: Diffie-Hellmanov protokol, šifrirne sheme ElGamal in RSA, podpisi ElGamal in RSA. Temeljni problem asimetričnih shem je zaupanje v javni ključ.
02 Moč osnovnih asimetričnih kriptografskih shem. Formalna definicija odpornosti: modeli UF-CMA, IND-CPA, DLP, CDH, DDH. Odnosi med njimi. Moč sheme šifriranja ElGamal. Nestabilnost sheme podpisa RSA brez uporabe zgoščevalne funkcije.
03 Izvedite več o asimetrični kriptografiji. Lampartov podpis, Merklejev diagram. Napad DSKS.
04 Algebraične in številsko-teoretične osnove asimetrične kriptografije. Končne skupine, ciklične skupine, vrstni red elementa skupine. Problem diskretnega logaritma (DLP). Multiplikativne skupine končnih polj. Osnovni podatki o eliptičnih krivuljah.
05 Eliptične krivulje. Hassejev izrek. Seštevanje točk na eliptični krivulji. Skupina točk na eliptični krivulji. Shema podpisov GOST R 34.10-2012.
06 Diskretni logaritem. Algoritmi diskretnega logaritma (Pollardova Rho metoda, metoda ujemanja, Polig-Hellmanova metoda, metoda izračuna indeksa).
07 Tehnologija PKI. Osnovni principi in koncepti infrastrukture javnih ključev (PKI). Certifikat, CA, CRL, OCSP, prostor zaupanja.
08 Protokol TLS. Zgodovina protokola TLS. Struktura protokola, osnovni principi delovanja. Šifrirani paketi protokola TLS, ki temeljijo na ruskih kriptografskih algoritmih.
09 Osnove gradnje protokolov AKE. Koncept protokola AKE. Ciljne lastnosti. Osnovni pristopi k gradnji.
10 Varno shranjevanje ključev. Problem varne uporabe zasebnih ključev. Ključni mediji, neodstranljivi ključi. Problem prisotnosti nasprotnika v kanalu, protokoli družine PAKE.
11 Osnovni koncepti tehnologije blockchain. Naloga usklajene decentralizirane interakcije. Osnovni pojmi koncepta varnosti. Varnostni pristopi.
12 Osnovni principi kvantnih tehnologij in njihove uporabe v kriptografiji