Big Data Infrastructure - gratis kurs från School of Data Analysis, 4 terminer, Datum: 5 december 2023.

Varje student måste framgångsrikt genomföra minst tre kurser under terminen. Till exempel, om det finns två av dem i huvudprogrammet, måste du välja en av specialkurserna.

Kunskaper prövas i första hand genom läxor - tentor och prov genomförs endast i vissa ämnen.

Första terminen

Obligatorisk
Algoritmer och datastrukturer, del 1

01 Komplexitet och beräkningsmodeller. Analys av redovisningsvärden (början)
02 Analys av redovisningsvärden (slut)
03 Algoritmer för sammanfogning-sortering och snabbsortering
04 Ordinalstatistik. Högar (början)
05 Heaps (slut)
06 Hashing
07 Sök i träd (början)
08 Sök i träd (fortsättning)
09 Sök i träd (slut). System av osammanhängande uppsättningar

10 Mål för RMQ och LCA
11 Datastrukturer för geometrisk sökning
12 Problem med dynamisk anslutning i en oriktad graf

Datorarkitektur och operativsystem

01 UNIX och programmering i C: kommandorad, processkontroll, kanaler, signaler. Implementering av ett kommandoradsskal.
02 x86 assembler: aritmetik, övergångar, villkor och funktionsanrop. Stapla, flytta uppför stapeln.
03 Länka program och ELF-formatet. Dynamisk länkning.
04 Begreppet sammanhang och exekveringsflöde. Implementering av lätta trådar.
05 Förebyggande multitasking: stöd från x86-processorn och implementering av processer i UNIX-kärnan.
06 Flerkärnig arkitektur: cachekoherens och minnesmodeller. Synkroniseringsprimitiver i flertrådade program.
07 Schemaläggning av processer på en kärna och på många kärnor.
08 Externt minne: hårddiskar och solid state-enheter. Principer för drift av filsystem.
09 Virtualisering: hårdvara och mjukvara. Binär sändning.

C++ språkträning, del 1

C++ är ett kraftfullt språk med ett rikt arv. För dem som precis har gett sig ut på vägen att bemästra detta språk är det mycket lätt att gå vilse i överflöd av tekniker och tekniker som skapats under de senaste 30 åren. Kursen lär ut "Modern C++" - en modern delmängd av språket (standard 11, 14 och 17). Mycket uppmärksamhet ägnas åt verktyg och bibliotek - sådant som inte är en del av språket, men utan vilka det inte kommer att vara möjligt att bygga ett stort och komplext projekt.
01 Introduktion till C++.
02 Konstanter. Pekare och länkar. Skicka argument till en funktion.
03 Klasser.
04 Dynamisk minneshantering.
05 Variabler, pekare och referenser.
06 Minneshantering, smarta pekare, RAII.
07 Standard mallbibliotek.
08 Arv och virtuella funktioner.
09 Felhantering.
10 Designmönster.
11 Namnområden Flytta semantik Perfekt vidarebefordran.
12 Representation av strukturer och klasser i minnet. Datajustering. Tips på klassmedlemmar/metoder. Variadiska mallar.

Andra terminen

Obligatorisk
Algoritmer och datastrukturer, del 2

01 Bypass i bredd. Depth First Traversal (start)
02 Depth Traversal (fortsättning)
03 Traversering i djupet (slut). 2-snitt
04 Hitta kortaste vägarna (början)
05 Hitta kortaste vägarna (fortsättning)
06 Minsta spännande träd
07 Minimala snitt. Sök efter delsträngar (start)
08 Sök efter delsträngar (fortsättning)
09 Sök efter delsträngar (slut)
10 suffixträd (början)
11 Suffixträd (slutar). Suffixmatriser (start)
12 suffixmatriser (slutar)
13 Längsta vanliga delsträngar. Ungefärlig delsträngsökning.

C++ språkträning, del 2

Den andra delen av C++-kursen, som täcker avancerade ämnen och språkkunskaper.

01 Flertrådsprogrammering. Synkronisera trådar med mutexes och villkorsvariabler.
02 Atomvariabler. C++ minnesmodell. Exempel på låsfria datastrukturer.
03 Avancerade metaprogrammeringstekniker i C++. Metafunktioner, SFINAE, koncept.
04 Konkurrenskraftig programmering, interaktion med nätverket.
05 llvm arkitektur. Arbeta med analysträdet C++. Utveckling av verktyg för att analysera C++-kod.

Att välja ifrån
Teori och praktik av samtidighet

Kursen ägnas åt konkurrenskraftiga system och uppgifter i vid bemärkelse: från konkurrensnivån mellan processorkärnor för att skriva till en cell minne till distribuerade system som vill replikera sitt tillstånd över flera servrar på ett feltolerant och konsekvent sätt.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md

eller
Gå språk

01 Introduktion. Kursprogram. Redovisning av kursen, utvärderingskriterier. Designfilosofi. om, byta, för. Hej världen. Kommandoradsargument. Antal ord. Animerad gif. Hämtar URL. Hämtar URL samtidigt. Webbserver. Tour of go. Lokal IDE-inställning. gofmt. goimport. ludd.
02 Grundläggande språkstrukturer. namn, deklarationer, variabler, tilldelningar. typdeklarationer. paket och filer. omfattning. Noll värde. Minnesallokering. Stack vs heap. Grundläggande datatyper. Konstanter. Sammansatta datatyper. Matriser. Skivor. Kartor. Strukturer. JSON. text/mall. sträng och []byte. Arbetar med unicode. Unicode-ersättningstecken. Funktioner. Fungerar med ett variabelt antal argument. Anonyma funktioner. Fel.
03 Metoder. Värdemottagare vs pekmottagare. Inbäddning. Metodvärde. Inkapsling. Gränssnitt. Gränssnitt som kontrakt. io. Författare, io. Reader och deras implementeringar. sortera. Gränssnitt. fel. http. Hanterare. Gränssnitt som uppräkningar. Typ påstående. Typ omkopplare. Ju större gränssnitt, desto svagare abstraktion. Fel vid bearbetning. panik, skjuta upp, återhämta sig. fel.{Unwrap, Is, As}. fmt. Errorf. %w.
04 Goroutiner och kanaler. klockserver. ekoserver. Kanalstorlek. Blockerande och icke-blockerande läsning. välj uttalande. Kanalaxiom. tid. Efter. tid. NewTicker. Rörledningsmönster. Annullering. Parallell slinga. synkronisera. Väntegrupp. Felhantering i parallellkod. felgrupp. Grupp. Samtidig webbsökare. Samtidig kataloggenomgång.
05 Avancerad testning. Delprov. testning. B. (T). Loggf. (T). Skipf. (T). Misslyckas nu. testning. Short(), testar flaggor. Generation av hånar. vittna/{kräva, hävda}. vittna/svit. Testfixtur. Integrationstest. Goroutine läckagedetektor. TestingMain. Rapportering. Jämförelse av riktmärken.
06 Avancerad testning. Delprov. testning. B. (T). Loggf. (T). Skipf. (T). Misslyckas nu. testning. Short(), testar flaggor. Generation av hånar. vittna/{kräva, hävda}. vittna/svit. Testfixtur. Integrationstest. Goroutine läckagedetektor. TestingMain. Rapportering. Jämförelse av riktmärken.
07 Paketsammanhang. Skickar förfrågningsomfattningsdata. http mellanprogram. chi. Router. Efterfråga nedläggning. Avancerade samtidighetsmönster. Asynkron cache. Graciös serveravstängning. sammanhang. Med Timeout. Batchning och avbokning.
08 databas/sql, sqlx, arbetar med databaser, redis.
09 Reflektion. reflektera. Skriv och reflektera. Värde. struct-taggar. nät/rpc. kodning/gob. synkronisera. Karta. reflektera. DeepEqual.
10 Paket io, Reader och Writer implementeringar från standardbiblioteket. Programmering på låg nivå. osäker. Paket binärt. bytes. Buffert. cgo, syscall.
11 GC-arkitektur. Skrivbarriär. Stacktillväxt. GC paus. GOGC. synkronisera. Slå samman. Schemaläggare för Goroutine. GOMACPROCS. Läckta trådar.
12 Gå till verktyg. pprof. CPU och minnesprofilering. Korssammanställning. GOOS, GOARCH. CGO_ENABLED=0. Bygg taggar. gå moduler. godoc. x/analys. Kodgenerering.
13 Användbara bibliotek. CLI-applikationer med cobra. Protobuf och GRPC. zap-loggning.

Tredje terminen

Obligatorisk
Algoritmer i externt minne

Kursen introducerar studenterna till de grundläggande principerna för att konstruera algoritmer för att arbeta med data som inte passar in i datorns RAM.

01 Algoritmer i externt minne.
02 Cache-omedvetna algoritmer.
03 Algoritmer för bearbetning av strömdata.

Distribuerade system

Rekommenderade specialkurser
Styrkan hos kryptografiska system

01 Grundläggande tillvägagångssätt och principer för modern kryptografi. Motståndarmodellen, formalisering av begreppet styrka, problemet med att bedöma styrka och relaterade problem, uppdelning i primitiver och protokoll, stadier av "livet" för ett kryptografiskt system.
02 Sekretess. Vardagliga definitioner av konfidentialitet, förhållningssätt till formalisering (informationsteoretisk modell av fienden, modeller KR, PR, LOR, ROR, IND, CPA, CCA), symmetriskt krypteringssystem, tillämpning av komplexitetsteoretisk information för att bestämma förhållandet mellan modeller. Relationer mellan grundläggande motståndarmodeller för att bedöma styrkan hos krypteringssystem.
03 Tillvägagångssätt för att bygga krypteringssystem. Bygga från grunden. Konstruktioner baserade på blockchiffer, definition av ett blockchiffer, huvudegenskaper, förhållningssätt till konstruktion och egenskaper. Modeller PRP och PRF. Paradoxen med födelsedagsproblemet. Lemma om förhållandet mellan motstånd i PRF- och PRP-modellerna.
04 Krypteringslägen. Grundläggande krypteringslägen: ECB, CBC, CFB, OFB, CTR. Grundläggande prestandaegenskaper. Hållbarhet för CTR i LOR-CPA, instabilitet hos ECB i LOR-CPA. Instabilitet av grundläggande lägen i CCA-modeller.
05 Integritet. Definition av begreppet integritet. Ansatser till formalisering (UF-CMA-modell, modeller baserade på diskrimineringsuppgiften, PRF-modell). Meddelandeautentiseringskoder och funktioner för att generera imiterade inlägg. Design baserad på blockchiffer: CBC-MAC, XCBC, TMAC, OMAC. Sårbara lägen.
06 Hash-funktioner. Definition, grundläggande egenskaper, förhållningssätt till konstruktion, formalisering och relaterade problem. Exempel på användning av hashfunktioner: lösenordshasning, entropiextraktion. Konstruera kollisioner och förbilder från uppsättningar med låg kardinalitet.
07 HMAC, KDF, PRF, DRNG-kretsar. HMAC-diagram, grundläggande steg för att erhålla resistansklassificering. Nyckeldiversifiering och principen om nyckelseparering, KDF- och PRF-scheman. Pseudoslumpgenerator, DRNG-kretsar.
08 Nyckelladdning. Problem med nyckelladdning. De huvudsakliga metoderna för att minska belastningen på en nyckel är externa och interna nyckelkonverteringar. Parallella och seriella omnyckelscheman, grundläggande egenskaper. Nyckelträd. Intern nyckelbyte och CTR-ACPKM-läge.
09 Kryptering med imitationsskydd. Problemformulering. Allmänna strukturer (EtA, AtE, A&E) och deras egenskaper. Exempel på sårbara lägen för att säkerställa konfidentialitet och integritet med en enda nyckel. AEAD-krypteringslägen: GCM, MGM.
10 Säker kommunikationskanal. Konceptet med en säker kommunikationskanal: typer av kanaler, grundläggande egenskaper (integritet och konfidentialitet för dataflödet). Exempel på sårbara protokoll. Spela in TLS 1.3-protokoll.

Fjärde terminen

Att välja ifrån
Teori och praktik av samtidighet

Kursen ägnas åt konkurrenskraftiga system och uppgifter i vid bemärkelse: från konkurrensnivån mellan processorkärnor för att skriva till en cell minne till distribuerade system som vill replikera sitt tillstånd över flera servrar på ett feltolerant och konsekvent sätt.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md

eller
Gå språk
01 Introduktion. Kursprogram. Redovisning av kursen, utvärderingskriterier. Designfilosofi. om, byta, för. Hej världen. Kommandoradsargument. Antal ord. Animerad gif. Hämtar URL. Hämtar URL samtidigt. Webbserver. Tour of go. Lokal IDE-inställning. gofmt. goimport. ludd.
02 Grundläggande språkstrukturer. namn, deklarationer, variabler, tilldelningar. typdeklarationer. paket och filer. omfattning. Noll värde. Minnesallokering. Stack vs heap. Grundläggande datatyper. Konstanter. Sammansatta datatyper. Matriser. Skivor. Kartor. Strukturer. JSON. text/mall. sträng och []byte. Arbetar med unicode. Unicode-ersättningstecken. Funktioner. Fungerar med ett variabelt antal argument. Anonyma funktioner. Fel.
03 Metoder. Värdemottagare vs pekmottagare. Inbäddning. Metodvärde. Inkapsling. Gränssnitt. Gränssnitt som kontrakt. io. Författare, io. Reader och deras implementeringar. sortera. Gränssnitt. fel. http. Hanterare. Gränssnitt som uppräkningar. Typ påstående. Typ omkopplare. Ju större gränssnitt, desto svagare abstraktion. Fel vid bearbetning. panik, skjuta upp, återhämta sig. fel.{Unwrap, Is, As}. fmt. Errorf. %w.
04 Goroutiner och kanaler. klockserver. ekoserver. Kanalstorlek. Blockerande och icke-blockerande läsning. välj uttalande. Kanalaxiom. tid. Efter. tid. NewTicker. Rörledningsmönster. Annullering. Parallell slinga. synkronisera. Väntegrupp. Felhantering i parallellkod. felgrupp. Grupp. Samtidig webbsökare. Samtidig kataloggenomgång.
05 Avancerad testning. Delprov. testning. B. (T). Loggf. (T). Skipf. (T). Misslyckas nu. testning. Short(), testar flaggor. Generation av hånar. vittna/{kräva, hävda}. vittna/svit. Testfixtur. Integrationstest. Goroutine läckagedetektor. TestingMain. Rapportering. Jämförelse av riktmärken.
06 Samtidighet med delat minne. synkronisera. Mutex. synkronisera. RWMutex. synkronisera. Cond. atom- synkronisera. En gång. Rasdetektor. Asynkron cache. Arbeta med databasen. databas/sql. sqlx.
07 Paketsammanhang. Skickar förfrågningsomfattningsdata. http mellanprogram. chi. Router. Efterfråga nedläggning. Avancerade samtidighetsmönster. Asynkron cache. Graciös serveravstängning. sammanhang. Med Timeout. Batchning och avbokning.
08 databas/sql, sqlx, arbetar med databaser, redis.
09 Reflektion. reflektera. Skriv och reflektera. Värde. struct-taggar. nät/rpc. kodning/gob. synkronisera. Karta. reflektera. DeepEqual.
10 Paket io, Reader och Writer implementeringar från standardbiblioteket. Programmering på låg nivå. osäker. Paket binärt. bytes. Buffert. cgo, syscall.
11 GC-arkitektur. Skrivbarriär. Stacktillväxt. GC paus. GOGC. synkronisera. Slå samman. Schemaläggare för Goroutine. GOMACPROCS. Läckta trådar.
12 Gå till verktyg. pprof. CPU och minnesprofilering. Korssammanställning. GOOS, GOARCH. CGO_ENABLED=0. Bygg taggar. gå moduler. godoc. x/analys. Kodgenerering.
13 Användbara bibliotek. CLI-applikationer med cobra. Protobuf och GRPC. zap-loggning.

eller
Databas
01 Gränssnitt för moderna databaser: relationell, nyckel-värde, dokument, graf. Relationell algebra och SQL-språk.
02 Arbeta med disk i klassisk relations-DBMS: sidor, sidpool, vräkning från poolen.
03 Exekvera SQL-frågor: uttrycksanalys, planering, exekvering. Tolkning och kodgenerering med LLVM.
04 Index i relationell DBMS: typer av index, lagringsmetoder, användning i frågor.
05 Transaktioner: ACID akronym, isoleringsnivåer, implementering av transaktioner genom lås och MVCC.
06 Återställning efter katastrof: logg, kontrollpunkter, ARIES-algoritm.
07 Datalagring med metoden Log-Structured Merge Tree.
08 Kolumnbaserad DBMS: fördelar, funktioner, datakomprimeringsalgoritmer.
09 Distribuerat DBMS: skärning, transaktioner, exekvering av förfrågningar.
10 DBMS finns i huvudminnet. Datastrukturer för in-memory index.

eller
Dator nätverk
01 Introduktion till nätverksteknik. Nätverkens historia, nätverksprotokoll, organisation av nätverksinteraktion i ett peer-to-peer-nätverk och anslutningen av peer-to-peer-nätverk med varandra.
02 Transport. OSI/ISO nätverksmodell. TCP, upprättande av nätverksanslutning, jämförelse av TCP och UDP. Tcpdump-analys – byte i fly, återsänder grafer. Metoder för att styra dataflödet i en TCP-session. Olika typer av TCP-sessioner och bandbreddshantering av överförda data i paketnätverk.
03 Rutning. Konceptet med routing i nätverk. Statisk och dynamisk routing. Grunderna i dynamisk routing. Dynamiskt routingprotokoll - OSPF. Avståndsvektor routingprotokoll. Översikt över BGP-routingprotokollet - meddelandetyper, BGP-attribut, val av optimal rutt i BGP.
04 Hur Internet fungerar: BGP och DNS. Internet routing. Översikt över DNS-protokollet.
05 Nätverk i stora datacenter. Funktioner i arkitekturen för datacenternätverk. Krav för datacenternätverk. CLOS-arkitektur för datacenternätverk.
06 Förseningar i nätverk. Funktioner för att bygga stora stamnät. Orsaker till förseningar i dataöverföring över stamnät.
07 Skalning och tillgänglighet av Internettjänster. Lastbalanseringsteknik och tjänstearkitektur.
08 MPLS och SR, nätverksprogrammerbarhet. MPLS och Segment Routing-teknologier för att bygga stamnät. Syftet med MPLS-teknik, protokoll som används för etikettutbyte.
09 Principer för drift av nätverksenheter. Routerarkitektur, funktioner för bearbetning av nätverkstrafik inuti nätverksenheter.
10 moln. Software Defined Networking Fundamentals - Protokoll som används för att bygga mjukvarudefinierade nätverk. Integration av virtualiseringsplattformar och nätverksinfrastruktur.

eller
Kryptografiska protokoll
01 Grundidéer för asymmetrisk kryptografi. Den största skillnaden mellan asymmetrisk kryptografi och symmetrisk kryptografi. Huvudidéer: protokoll för att generera en delad nyckel, offentlig nyckelkryptering, elektronisk signatur (problem som ska lösas, intuitiv förståelse av säkerhetsegenskaper). Specifika kryptografiska system: Diffie-Hellman-protokollet, ElGamal- och RSA-krypteringsscheman, ElGamal- och RSA-signaturer. Det grundläggande problemet med asymmetriska system är förtroende för den offentliga nyckeln.
02 Styrkan hos grundläggande asymmetriska kryptografischeman. Formell definition av resistens: modellerna UF-CMA, IND-CPA, DLP, CDH, DDH. Relationer dem emellan. Styrkan hos ElGamal-krypteringsschemat. Instabiliteten hos RSA-signaturschemat utan att använda en hashfunktion.
03 Lär dig mer om asymmetrisk kryptografi. Lamparts signatur, Merkles diagram. DSKS attack.
04 Algebraiska och talteoretiska grunder för asymmetrisk kryptografi. Finita grupper, cykliska grupper, ordning på gruppelement. Diskret logaritmproblem (DLP). Multiplikativa grupper av ändliga fält. Grundläggande information om elliptiska kurvor.
05 Elliptiska kurvor. Hasses sats. Addering av punkter på en elliptisk kurva. Grupp av punkter på en elliptisk kurva. Signaturschema GOST R 34.10-2012.
06 Diskret logaritm. Diskreta logaritmalgoritmer (Pollards Rho-metod, matchningsmetod, Polig-Hellman-metoden, indexberäkningsmetod).
07 PKI-teknik. Grundläggande principer och koncept för offentlig nyckelinfrastruktur (PKI). Certifikat, CA, CRL, OCSP, förtroendeutrymme.
08 TLS-protokoll. Historik för TLS-protokollet. Protokollstruktur, grundläggande operativa principer. TLS-protokoll kryptografiska sviter baserade på ryska kryptografiska algoritmer.
09 Grunderna i att bygga AKE-protokoll. Konceptet med AKE-protokollet. Målfastigheter. Grundläggande tillvägagångssätt för konstruktion.
10 Säker nyckelförvaring. Problemet med säker användning av privata nycklar. Nyckelmedia, ej borttagbara nycklar. Problemet med närvaron av en motståndare i kanalen, PAKE-familjens protokoll.
11 grundläggande koncept för blockchain-teknik. Uppgiften att samordna decentraliserad interaktion. Grundläggande begrepp för säkerhetsbegreppet. Säkerhet närmar sig.
12 Grundläggande principer för kvantteknologier och deras tillämpningar inom kryptografi