Big Data Infrastructure - Data Analysis Schooli tasuta kursus, 4 semestrit, kuupäev: 5. detsember 2023.
Varia / / December 08, 2023
Neile, kes armastavad algoritme, töötamist andmetega ja naudivad programmeerimist, kuid ei tahaks oma elu masinõppega siduda.
Algoritmid, programmeerimine, failisüsteemide, ketaste, võrkude ja protsessorite, samuti hajutatud süsteemide projekteerimine.
Tõhusate ja töökindlate hajussüsteemide loomisel ja toetamisel suurandmete salvestamiseks ja töötlemiseks.
Iga üliõpilane peab semestri jooksul edukalt läbima vähemalt kolm kursust. Näiteks kui põhiprogrammis on neid kaks, siis tuleb valida üks erikursustest.
Teadmisi kontrollitakse eelkõige kodutööde kaudu – eksameid ja kontrolltöid tehakse vaid mõnes aines.
Esimene semester
Kohustuslik
Algoritmid ja andmestruktuurid, 1. osa
01 Keerukus ja arvutuslikud mudelid. Raamatupidamisväärtuste analüüs (algus)
02 Arvestusväärtuste analüüs (lõpp)
03 Ühenda-sortimise ja kiirsortimise algoritmid
04 Tavastatistika. Kuhjad (algus)
05 kuhjad (lõpp)
06 Räsimine
07 Otsingupuud (algus)
08 Otsingupuud (jätkub)
09 Otsi puud (lõpp). Disjunktsete komplektide süsteem
10 RMQ ja LCA eesmärki
11 Andmestruktuurid geomeetriliseks otsinguks
12 Dünaamilise ühenduvuse probleem suunamata graafis
Arvuti arhitektuur ja operatsioonisüsteemid
01 UNIX ja programmeerimine C-s: käsurida, protsessi juhtimine, kanalid, signaalid. Käsurea shelli juurutamine.
02 x86 assembler: aritmeetika, üleminekud, tingimused ja funktsioonikutsed. Virn, virnast ülespoole liikumine.
03 Programmide ja ELF-vormingu linkimine. Dünaamiline linkimine.
04 Konteksti ja täitmise voo mõiste. Kergekaaluliste niitide rakendamine.
05 Ennetav multitegumtöötlus: x86 protsessori tugi ja protsesside juurutamine UNIX-i tuumas.
06 Mitmetuumaline arhitektuur: vahemälu sidusus ja mälumudelid. Sünkroniseerimisprimitiivid mitme lõimega programmides.
07 Protsesside ajastamine ühel ja mitmel tuumal.
08 Välismälu: kõvakettad ja pooljuhtkettad. Failisüsteemide tööpõhimõtted.
09 Virtualiseerimine: riist- ja tarkvara. Binaarne saade.
C++ keeleõpe, 1. osa
C++ on rikkaliku pärandiga võimas keel. Neil, kes on just selle keele valdamise teele asunud, on väga lihtne eksida viimase 30 aasta jooksul loodud tehnikate ja tehnikate rohkusesse. Kursusel õpetatakse "Modern C++" - keele kaasaegset alamhulka (standardid 11, 14 ja 17). Palju tähelepanu pööratakse tööriistadele ja raamatukogudele – asjadele, mis ei kuulu keele alla, kuid ilma milleta pole võimalik ehitada suurt ja keerulist projekti.
01 Sissejuhatus C++.
02 Konstandid. Osutajad ja lingid. Argumentide edastamine funktsioonile.
03 Klassid.
04 Dünaamiline mäluhaldus.
05 Muutujad, viited ja viited.
06 Mäluhaldus, nutikad osutid, RAII.
07 Standardne malliteek.
08 Pärand ja virtuaalsed funktsioonid.
09 Vigade käsitlemine.
10 kujundusmustrit.
11 Nimeruumid Liigutamise semantika Täiuslik edastamine.
12 Struktuuride ja klasside kujutamine mälus. Andmete joondamine. Osutused klassi liikmetele/meetoditele. Variadic mallid.
Teine ametiaeg
Kohustuslik
Algoritmid ja andmestruktuurid, 2. osa
01 Laiuse ümbersõit. Sügavuse esimene läbimine (start)
02 Sügavuse läbimine (jätkub)
03 Läbisõit sügavuti (lõpp). 2-lõiget
04 Lühimate teede leidmine (algus)
05 Lühimate teede leidmine (jätkub)
06 Minimaalselt ulatuvad puud
07 Minimaalsed lõiked. Otsige alamstringe (algus)
08 Otsige alamstringe (jätkub)
09 Otsige alamstringe (lõpp)
10 järelliite puud (algus)
11 Sufiksipuud (lõpp). Sufiksimassiivid (algus)
12 järelliite massiivi (lõpp)
13 pikimat levinud alamstringi. Ligikaudne alamstringi otsing.
C++ keeleõpe, 2. osa
C++ kursuse teine osa, mis hõlmab edasijõudnuid teemasid ja keeleoskusi.
01 Mitme keermega programmeerimine. Lõimede sünkroonimine mutexide ja tingimusmuutujate abil.
02 Aatomi muutujad. C++ mälumudel. Lukuvabade andmestruktuuride näited.
03 Täiustatud metaprogrammeerimise tehnikad C++ keeles. Metafunktsioonid, SFINAE, mõisted.
04 Konkurentsivõimeline programmeerimine, suhtlus võrguga.
05 llvm arhitektuur. Töötamine C++ parsipuuga. Tööriistade väljatöötamine C++ koodi analüüsimiseks.
Et valida
Samaaegsuse teooria ja praktika
Kursus on pühendatud konkureerivatele süsteemidele ja ülesannetele kõige laiemas tähenduses: protsessorituumadevahelisest konkurentsist kirjutamise eest kuni ühe rakuni mälu hajutatud süsteemidele, mis soovivad kopeerida oma olekut mitme serveri vahel tõrketaluvusel ja järjepideval viisil.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md
või
Mine keelde
01 Sissejuhatus. Kursuse programm. Kursuse aruandlus, hindamiskriteeriumid. Disaini filosoofia. kui, lüliti, jaoks. Tere, Maailm. Käsurea argumendid. Sõnade arv. Animeeritud gif. URL-i toomine. URL-i toomine samaaegselt. Veebiserver. Ringkäik. Kohalik IDE seadistamine. gofmt. goimport. linting
02 Keele põhistruktuurid. nimed, deklaratsioonid, muutujad, ülesanded. tüüpi deklaratsioonid. paketid ja failid. ulatus. Null väärtus. Mälu eraldamine. Virn vs hunnik. Põhiandmetüübid. Konstandid. Komposiitandmete tüübid. Massiivid. Viilud. Kaardid. Struktuurid. JSON. tekst/mall. string ja []bait. Unicode'iga töötamine. Unicode asendusmärk. Funktsioonid. Funktsioonid muutuva arvu argumentidega. Anonüümsed funktsioonid. Vead.
03 Meetodid. Väärtuse vastuvõtja vs osuti vastuvõtja. Manustamine. Meetodi väärtus. Kapseldamine. Liidesed. Liidesed kui lepingud. io. Kirjanik, io. Lugeja ja nende teostused. sorteerida. Liides. viga. http. Käitleja. Liidesed loendustena. Tüüp väide. Tüübi lüliti. Mida suurem liides, seda nõrgem on abstraktsioon. Viga töötlemisel. paanika, edasi lükata, taastuda. vead.{Unwrap, Is, As}. fmt. Errorf. %w.
04 Gorutiinid ja kanalid. kella server. kajaserver. Kanali suurus. Blokeeriv ja mitteblokeeriv lugemine. vali avaldus. Kanali aksioomid. aega. Pärast. aega. UusTicker. Torujuhtme muster. Tühistamine. Paralleelne silmus. sünkroonimine. Ootegrupp. Viga paralleelkoodi töötlemisel. veagrupp. Grupp. Samaaegne veebiroomaja. Samaaegne kataloogi läbimine.
05 Täiustatud testimine. Alamtestid. testimine. B. (T).Logf. (T).Skipf. (T).FailNow. testimine. Short(), testimislipud. Piltide genereerimine. tunnistama/{nõudma, väitma}. tunnistama/sviit. Testimisseade. Integratsioonitestid. Goroutine lekkedetektor. TestingMain. Katvus. Võrdlusnäitajate võrdlus.
06 Täiustatud testimine. Alamtestid. testimine. B. (T).Logf. (T).Skipf. (T).FailNow. testimine. Short(), testimislipud. Piltide genereerimine. tunnistama/{nõudma, väitma}. tunnistama/sviit. Testimisseade. Integratsioonitestid. Goroutine lekkedetektor. TestingMain. Katvus. Võrdlusnäitajate võrdlus.
07 Paketi kontekst. Päringu ulatusega andmete edastamine. http vahevara. chi. Ruuter. Taotluse tühistamine. Täiustatud samaaegsusmustrid. Asünkrooni vahemälu. Graatsiline serveri sulgemine. Sisu. Timeoutiga. Pakkimine ja tühistamine.
08 andmebaas/sql, sqlx, andmebaasidega töötamine, redis.
09 Peegeldus. peegeldama. Sisestage ja peegeldage. Väärtus. struktuuri sildid. net/rpc. kodeering/gob. sünkroonimine. Kaart. peegeldama. DeepEqual.
10 Package io, Reader ja Writer rakendusi standardteegist. Madala taseme programmeerimine. ebaturvaline. Binaarne pakett. baiti. Puhver. cgo, syscall.
11 GC arhitektuur. Kirjuta barjäär. Virna kasv. GC paus. GOGC. sünkroonimine. Bassein. Gorutine'i ajakava. GOMACPROCS. Lekkinud niidid.
12. Mine tööriistadesse. pprof. Protsessori ja mälu profileerimine. Ristkoostis. GOOS, GOARCH. CGO_ENABLED=0. Ehitage silte. mine moodulid. goddoc. x/analüüs. Koodi genereerimine.
13 Kasulikud raamatukogud. CLI rakendused kobraga. Protobuf ja GRPC. zap logimine.
Kolmas semester
Kohustuslik
Algoritmid välismälus
Kursusel tutvustatakse õpilastele algoritmide koostamise põhiprintsiipe tööks andmetega, mis ei mahu arvuti RAM-i.
01 Algoritmid välismälus.
02 Vahemälu unustavad algoritmid.
03 Andmevoo töötlemise algoritmid.
Hajutatud süsteemid
Soovitatavad erikursused
Krüptosüsteemide tugevus
01 Kaasaegse krüptograafia põhilised lähenemisviisid ja põhimõtted. Vastase mudel, tugevuse mõiste formaliseerimine, tugevuse hindamise probleem ja sellega seotud probleemid, jaotus primitiivideks ja protokollideks, krüptograafilise süsteemi “elu” etapid.
02 Konfidentsiaalsus. Igapäevased konfidentsiaalsuse definitsioonid, lähenemised formaliseerimisele (vaenlase infoteoreetiline mudel, mudelid KR, PR, LOR, ROR, IND, CPA, CCA), sümmeetriline krüpteerimissüsteem, keerukusteoreetilise teabe rakendamine, et määrata seos mudelid. Seosed põhiliste vastase mudelite vahel krüpteerimissüsteemide tugevuse hindamiseks.
03 Lähenemisviisid krüpteerimissüsteemide ehitamisel. Ehitamine nullist. Plokkšifritel põhinevad konstruktsioonid, plokkšifri definitsioon, peamised omadused, konstruktsiooni käsitlused ja omadused. Mudelid PRP ja PRF. Sünnipäevaprobleemi paradoks. Lemma resistentsuse vahelise seose kohta PRF ja PRP mudelites.
04 Krüpteerimisrežiimid. Põhilised krüpteerimisrežiimid: ECB, CBC, CFB, OFB, CTR. Põhilised jõudlusomadused. CTR-i vastupidavus LOR-CPA-s, EKP ebastabiilsus LOR-CPA-s. Põhirežiimide ebastabiilsus CCA mudelites.
05 Ausus. Terviklikkuse mõiste definitsioon. Lähenemised formaliseerimisele (UF-CMA mudel, diskrimineerimisülesandel põhinevad mudelid, PRF mudel). Sõnumi autentimiskoodid ja funktsioonid imiteeritud lisade genereerimiseks. Plokkšifritel põhinevad kujundused: CBC-MAC, XCBC, TMAC, OMAC. Haavatavad režiimid.
06 Räsifunktsioonid. Definitsioon, põhiomadused, konstruktsiooni käsitlused, vormistamine ja sellega seotud probleemid. Näiteid räsifunktsioonide kasutamisest: parooli räsimine, entroopia eraldamine. Kokkupõrgete ja eelpiltide konstrueerimine madala kardinaalsusega komplektidest.
07 HMAC, KDF, PRF, DRNG vooluringid. HMAC diagramm, põhietapid takistuse reitingu saamiseks. Võtmete hajutamine ja võtmete eraldamise põhimõte, KDF ja PRF skeemid. Pseudojuhuslik generaator, DRNG ahelad.
08 Võtmekoormus. Klahvi laadimise probleem. Peamised meetodid võtme koormuse vähendamiseks on välised ja sisemised võtmete teisendused. Paralleel- ja jadavõtimise skeemid, põhiomadused. Võtmepuu. Sisemine võtmevahetus ja CTR-ACPKM režiim.
09 Krüpteerimine imitatsioonikaitsega. Probleemi sõnastus. Üldstruktuurid (EtA, AtE, A&E) ja nende omadused. Näited haavatavatest režiimidest konfidentsiaalsuse ja terviklikkuse tagamiseks ühe võtme abil. AEAD krüpteerimisrežiimid: GCM, MGM.
10 Turvaline sidekanal. Turvalise sidekanali kontseptsioon: kanalite tüübid, põhiomadused (andmevoo terviklikkus ja konfidentsiaalsus). Näited haavatavatest protokollidest. Salvestage TLS 1.3 protokoll.
Neljas semester
Et valida
Samaaegsuse teooria ja praktika
Kursus on pühendatud konkureerivatele süsteemidele ja ülesannetele kõige laiemas tähenduses: protsessorituumadevahelisest konkurentsist kirjutamise eest kuni ühe rakuni mälu hajutatud süsteemidele, mis soovivad kopeerida oma olekut mitme serveri vahel tõrketaluvusel ja järjepideval viisil.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md
või
Mine keelde
01 Sissejuhatus. Kursuse programm. Kursuse aruandlus, hindamiskriteeriumid. Disaini filosoofia. kui, lüliti, jaoks. Tere, Maailm. Käsurea argumendid. Sõnade arv. Animeeritud gif. URL-i toomine. URL-i toomine samaaegselt. Veebiserver. Ringkäik. Kohalik IDE seadistamine. gofmt. goimport. linting
02 Keele põhistruktuurid. nimed, deklaratsioonid, muutujad, ülesanded. tüüpi deklaratsioonid. paketid ja failid. ulatus. Null väärtus. Mälu eraldamine. Virn vs hunnik. Põhiandmetüübid. Konstandid. Komposiitandmete tüübid. Massiivid. Viilud. Kaardid. Struktuurid. JSON. tekst/mall. string ja []bait. Unicode'iga töötamine. Unicode asendusmärk. Funktsioonid. Funktsioonid muutuva arvu argumentidega. Anonüümsed funktsioonid. Vead.
03 Meetodid. Väärtuse vastuvõtja vs osuti vastuvõtja. Manustamine. Meetodi väärtus. Kapseldamine. Liidesed. Liidesed kui lepingud. io. Kirjanik, io. Lugeja ja nende teostused. sorteerida. Liides. viga. http. Käitleja. Liidesed loendustena. Tüüp väide. Tüübi lüliti. Mida suurem liides, seda nõrgem on abstraktsioon. Viga töötlemisel. paanika, edasi lükata, taastuda. vead.{Unwrap, Is, As}. fmt. Errorf. %w.
04 Gorutiinid ja kanalid. kella server. kajaserver. Kanali suurus. Blokeeriv ja mitteblokeeriv lugemine. vali avaldus. Kanali aksioomid. aega. Pärast. aega. UusTicker. Torujuhtme muster. Tühistamine. Paralleelne silmus. sünkroonimine. Ootegrupp. Viga paralleelkoodi töötlemisel. veagrupp. Grupp. Samaaegne veebiroomaja. Samaaegne kataloogi läbimine.
05 Täiustatud testimine. Alamtestid. testimine. B. (T).Logf. (T).Skipf. (T).FailNow. testimine. Short(), testimislipud. Piltide genereerimine. tunnistama/{nõudma, väitma}. tunnistama/sviit. Testimisseade. Integratsioonitestid. Goroutine lekkedetektor. TestingMain. Katvus. Võrdlusnäitajate võrdlus.
06 Samaaegsus ühismäluga. sünkroonimine. Mutex. sünkroonimine. RWMutex. sünkroonimine. Kond. aatomi sünkroonimine. Üks kord. Võistlusdetektor. Asünkrooni vahemälu. Töö andmebaasiga. andmebaas/sql. sqlx.
07 Paketi kontekst. Päringu ulatusega andmete edastamine. http vahevara. chi. Ruuter. Taotluse tühistamine. Täiustatud samaaegsusmustrid. Asünkrooni vahemälu. Graatsiline serveri sulgemine. Sisu. Timeoutiga. Pakkimine ja tühistamine.
08 andmebaas/sql, sqlx, andmebaasidega töötamine, redis.
09 Peegeldus. peegeldama. Sisestage ja peegeldage. Väärtus. struktuuri sildid. net/rpc. kodeering/gob. sünkroonimine. Kaart. peegeldama. DeepEqual.
10 Package io, Reader ja Writer rakendusi standardteegist. Madala taseme programmeerimine. ebaturvaline. Binaarne pakett. baiti. Puhver. cgo, syscall.
11 GC arhitektuur. Kirjuta barjäär. Virna kasv. GC paus. GOGC. sünkroonimine. Bassein. Gorutine'i ajakava. GOMACPROCS. Lekkinud niidid.
12. Mine tööriistadesse. pprof. Protsessori ja mälu profileerimine. Ristkoostis. GOOS, GOARCH. CGO_ENABLED=0. Ehitage silte. mine moodulid. goddoc. x/analüüs. Koodi genereerimine.
13 Kasulikud raamatukogud. CLI rakendused kobraga. Protobuf ja GRPC. zap logimine.
või
Andmebaas
01 Kaasaegsete andmebaaside liidesed: relatsioon, võtmeväärtus, dokument, graafik. Relatsioonialgebra ja SQL keel.
02 Kettaga töötamine klassikalises relatsioonilises DBMS-is: lehed, lehtede kogum, basseinist väljatõstmine.
03 SQL päringute täitmine: avaldise sõelumine, planeerimine, täitmine. Tõlgendus ja koodi genereerimine LLVM-i abil.
04 Indeksid relatsioonilises DBMS-is: indeksite tüübid, salvestusmeetodid, kasutamine päringutes.
05 Tehingud: ACID-akronüüm, isolatsioonitasemed, tehingute rakendamine lukkude ja MVCC kaudu.
06 Katastroofitaaste: logi, kontrollpunktid, ARIES-algoritm.
07 Andmete salvestamine logistruktureeritud liitmispuu meetodil.
08 Veerupõhine DBMS: eelised, funktsioonid, andmete tihendamise algoritmid.
09 Hajutatud DBMS: jagamine, tehingud, päringu täitmine.
10 DBMS-i, mis asuvad põhimälus. Andmestruktuurid mälusiseste indeksite jaoks.
või
Arvutivõrgud
01 Sissejuhatus võrgutehnoloogiatesse. Võrkude ajalugu, võrguprotokollid, võrgu suhtluse korraldamine peer-to-peer võrgus ja peer-to-peer võrkude ühendamine üksteisega.
02 Transport. OSI/ISO võrgumudel. TCP, võrguühenduse loomine, TCP ja UDP võrdlus. Tcpdump analüüs – baidid lendas, saadab uuesti graafikuid. Meetodid andmevoo juhtimiseks TCP-seansis. Erinevat tüüpi TCP-seansid ja edastatavate andmete ribalaiuse haldamine pakettvõrkudes.
03 Marsruutimine. Võrkudes marsruutimise kontseptsioon. Staatiline ja dünaamiline marsruutimine. Dünaamilise marsruutimise põhitõed. Dünaamiline marsruutimise protokoll - OSPF. Kaugusvektori marsruutimise protokollid. Ülevaade BGP marsruutimisprotokollist – sõnumitüübid, BGP atribuudid, optimaalse marsruudi valimine BGP-s.
04 Kuidas Internet töötab: BGP ja DNS. Interneti-marsruutimine. DNS-protokolli ülevaade.
05 Võrgud suurtes andmekeskustes. Andmekeskuste võrkude arhitektuuri tunnused. Nõuded andmekeskuste võrkudele. CLOS-arhitektuur andmekeskuste võrkude jaoks.
06 Viivitused võrkudes. Suurte magistraalvõrkude ehitamise omadused. Andmeedastuse hilinemise põhjused magistraalvõrkude kaudu.
07 Interneti-teenuste skaleerimine ja kättesaadavus. Koormuse tasakaalustamise tehnoloogiad ja teenuse arhitektuur.
08 MPLS ja SR, võrgu programmeeritavus. MPLS ja Segment Routing tehnoloogiad magistraalvõrkude ehitamiseks. MPLS-tehnoloogia eesmärk, etikettide vahetamiseks kasutatavad protokollid.
09 Võrguseadmete tööpõhimõtted. Ruuteri arhitektuur, võrguseadmetes võrguliikluse töötlemise funktsioonid.
10 pilved. Tarkvaraga määratletud võrgunduse põhialused – tarkvaraga määratletud võrkude loomiseks kasutatavad protokollid. Virtualiseerimisplatvormide ja võrgu infrastruktuuri integreerimine.
või
Krüptograafilised protokollid
01 Asümmeetrilise krüptograafia põhiideed. Peamine erinevus asümmeetrilise krüptograafia ja sümmeetrilise krüptograafia vahel. Peamised ideed: jagatud võtme genereerimise protokoll, avaliku võtme krüpteerimine, elektrooniline allkiri (lahendatavad probleemid, turvaomaduste intuitiivne mõistmine). Konkreetsed krüptograafilised skeemid: Diffie-Hellmani protokoll, ElGamali ja RSA krüpteerimisskeemid, ElGamali ja RSA signatuurid. Asümmeetriliste skeemide põhiprobleemiks on usaldus avaliku võtme vastu.
02 Põhiliste asümmeetriliste krüptograafiaskeemide tugevus. Resistentsuse formaalne määratlus: mudelid UF-CMA, IND-CPA, DLP, CDH, DDH. Nendevahelised suhted. ElGamali krüpteerimisskeemi tugevus. RSA allkirjaskeemi ebastabiilsus ilma räsifunktsiooni kasutamata.
03 Lisateave asümmeetrilise krüptograafia kohta. Lamparti allkiri, Merkle skeem. DSKS-i rünnak.
04 Asümmeetrilise krüptograafia algebralised ja arvuteoreetilised alused. Lõplikud rühmad, tsüklilised rühmad, rühmaelemendi järjekord. Diskreetse logaritmi probleem (DLP). Lõplike väljade korduvad rühmad. Põhiteave elliptiliste kõverate kohta.
05 Elliptilised kõverad. Hasse teoreem. Punktide liitmine elliptilisel kõveral. Punktide rühm elliptilisel kõveral. Allkirjaskeem GOST R 34.10-2012.
06 Diskreetne logaritm. Diskreetsed logaritmi algoritmid (Pollardi Rho meetod, sobitusmeetod, Polig-Hellmani meetod, indeksi arvutamise meetod).
07 PKI tehnoloogia. Avaliku võtme infrastruktuuri (PKI) põhiprintsiibid ja kontseptsioonid. Sertifikaat, CA, CRL, OCSP, usaldusruum.
08 TLS protokoll. TLS-protokolli ajalugu. Protokolli struktuur, põhilised tööpõhimõtted. TLS-protokolli krüptograafilised komplektid, mis põhinevad vene krüptoalgoritmidel.
09 AKE protokollide koostamise alused. AKE protokolli kontseptsioon. Sihtomadused. Põhilised lähenemised ehitusele.
10 Turvaline võtmehoidla. Privaatvõtmete turvalise kasutamise probleem. Võtmekandja, mitte-eemaldatavad võtmed. Kanalis vastase olemasolu probleem, PAKE perekonna protokollid.
11 Plokiahela tehnoloogia põhimõisted. Koordineeritud detsentraliseeritud suhtluse ülesanne. Turvalisuse mõiste põhimõisted. Turvalisuse lähenemisviisid.
12 Kvanttehnoloogiate põhiprintsiibid ja nende rakendused krüptograafias