Big Data Infrastructure - gratis kurs fra School of Data Analysis, 4 semestre, Dato: 5. desember 2023.

Hver student må fullføre minst tre emner i løpet av semesteret. For eksempel, hvis det er to av dem i hovedprogrammet, må du velge ett av spesialkursene.

Kunnskap testes først og fremst gjennom lekser - eksamener og prøver gjennomføres kun i enkelte fag.

Første semester

Påbudt, bindende
Algoritmer og datastrukturer, del 1

01 Kompleksitet og beregningsmodeller. Analyse av regnskapsverdier (begynnelse)
02 Analyse av regnskapsverdier (slutt)
03 Slå sammen-sorterings- og hurtigsorteringsalgoritmer
04 Ordinalstatistikk. Heaps (begynnelse)
05 Heaps (slutt)
06 Hashing
07 Søk i trær (begynnelse)
08 Søk i trær (fortsettelse)
09 Søk i trær (slutt). System av usammenhengende sett

10 Mål for RMQ og LCA
11 Datastrukturer for geometrisk søk
12 Problem med dynamisk tilkobling i en urettet graf

Dataarkitektur og operativsystemer

01 UNIX og programmering i C: kommandolinje, prosesskontroll, kanaler, signaler. Implementering av et kommandolinjeskall.
02 x86 assembler: aritmetikk, overganger, betingelser og funksjonskall. Stabel, flytte opp stabelen.
03 Koble sammen programmer og ELF-formatet. Dynamisk kobling.
04 Konseptet kontekst og utførelsesflyt. Implementering av lette tråder.
05 Forebyggende multitasking: støtte fra x86-prosessoren og implementering av prosesser i UNIX-kjernen.
06 Flerkjernearkitektur: hurtigbufferkoherens og minnemodeller. Synkroniseringsprimitiver i flertrådede programmer.
07 Planlegging av prosesser på én kjerne og på mange kjerner.
08 Eksternt minne: harddisker og solid state-stasjoner. Prinsipper for drift av filsystemer.
09 Virtualisering: maskinvare og programvare. Binær kringkasting.

C++ språkopplæring, del 1

C++ er et kraftig språk med en rik arv. For de som nettopp har lagt ut på veien for å mestre dette språket, er det veldig lett å gå seg vill i overfloden av teknikker og teknikker som er laget de siste 30 årene. Kurset lærer "Modern C++" - en moderne delmengde av språket (standard 11, 14 og 17). Det rettes mye oppmerksomhet mot verktøy og biblioteker – ting som ikke er en del av språket, men uten hvilke det ikke vil være mulig å bygge et stort og komplekst prosjekt.
01 Introduksjon til C++.
02 Konstanter. Pekere og lenker. Sende argumenter til en funksjon.
03 Klasser.
04 Dynamisk minnehåndtering.
05 Variabler, pekepinner og referanser.
06 Minnehåndtering, smarte pekere, RAII.
07 Standard malbibliotek.
08 Arv og virtuelle funksjoner.
09 Feilhåndtering.
10 Designmønstre.
11 Navneområder Flytte semantikk Perfekt videresending.
12 Representasjon av strukturer og klasser i minnet. Datajustering. Tips til klassemedlemmer/metoder. Variadiske maler.

Andre termin

Påbudt, bindende
Algoritmer og datastrukturer, del 2

01 Bypass i bredden. Dybde First Traversal (start)
02 Dybdegjennomgang (fortsettelse)
03 Traversering i dybden (slutt). 2-kutt
04 Finne korteste veier (begynnelse)
05 Finne korteste veier (fortsettelse)
06 Minimumsspennende trær
07 Minimale kutt. Søk etter understrenger (start)
08 Søk etter understrenger (fortsettelse)
09 Søk etter understrenger (slutt)
10 suffiksetrær (begynnelse)
11 Suffiksetrær (avslutning). Suffiksmatriser (start)
12 suffiksmatriser (avslutning)
13 Lengste felles understrenger. Omtrentlig understrengsøk.

C++ språkopplæring, del 2

Den andre delen av C++-kurset, som dekker avanserte emner og språkkunnskaper.

01 Flertrådsprogrammering. Synkronisering av tråder ved hjelp av mutexes og tilstandsvariabler.
02 Atomvariabler. C++ minnemodell. Eksempler på låsfrie datastrukturer.
03 Avanserte metaprogrammeringsteknikker i C++. Metafunksjoner, SFINAE, konsepter.
04 Konkurransedyktig programmering, interaksjon med nettverket.
05 llvm arkitektur. Arbeide med C++-analysetreet. Utvikling av verktøy for å analysere C++ kode.

Å velge fra
Teori og praksis for samtidighet

Kurset er viet konkurrerende systemer og oppgaver i vid forstand: fra nivået av konkurranse mellom prosessorkjerner for skriving til én celle minne til distribuerte systemer som ønsker å replikere tilstanden deres på tvers av flere servere på en feiltolerant og konsistent måte.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md

eller
Gå språk

01 Introduksjon. Kursprogram. Rapportering på kurset, evalueringskriterier. Designfilosofi. hvis, bytte, for. Hei Verden. Kommandolinjeargumenter. Ordtelling. Animert gif. Henter URL. Henter URL samtidig. Internett server. Tour of go. Lokalt IDE-oppsett. gofmt. goimporter. linting
02 Grunnleggende språkstrukturer. navn, erklæringer, variabler, oppdrag. typeerklæringer. pakker og filer. omfang. Null verdi. Minnetildeling. Stabel vs haug. Grunnleggende datatyper. Konstanter. Sammensatte datatyper. Matriser. Skiver. Kart. Strukturer. JSON. tekst/mal. streng og []byte. Jobber med unicode. Unicode-erstatningstegn. Funksjoner. Funksjoner med et variabelt antall argumenter. Anonyme funksjoner. Feil.
03 Metoder. Verdimottaker vs pekermottaker. Innebygging. Metodeverdi. Innkapsling. Grensesnitt. Grensesnitt som kontrakter. io. Forfatter, io. Reader og deres implementeringer. sortere. Grensesnitt. feil. http. Handler. Grensesnitt som oppregninger. Skriv påstand. Type bryter. Jo større grensesnitt, jo svakere abstraksjon. Feil under behandling. panikk, utsette, komme seg. feil.{Unwrap, Is, As}. fmt. Feilf. %w.
04 Goroutiner og kanaler. klokkeserver. ekkoserver. Kanalstørrelse. Blokkerende og ikke-blokkerende lesing. velg uttalelse. Kanalaksiomer. tid. Etter. tid. NewTicker. Rørledningsmønster. Kansellering. Parallell sløyfe. synkronisere. Ventegruppe. Feilhåndtering i parallell kode. feilgruppe. Gruppe. Samtidig webcrawler. Samtidig kataloggjennomgang.
05 Avansert testing. Delprøver. testing. B. (T). Loggf. (T). Skipf. (T).FailNow. testing. Short(), tester flagg. Generasjon av spotter. vitne/{require, assert}. vitne/suite. Testarmatur. Integrasjonstester. Goroutine lekkasjedetektor. TestingMain. Dekning. Sammenligning av benchmarks.
06 Avansert testing. Delprøver. testing. B. (T). Loggf. (T). Skipf. (T).FailNow. testing. Short(), tester flagg. Generasjon av spotter. vitne/{require, assert}. vitne/suite. Testarmatur. Integrasjonstester. Goroutine lekkasjedetektor. TestingMain. Dekning. Sammenligning av benchmarks.
07 Pakkekontekst. Sender data med forespørselsomfang. http mellomvare. chi. Ruter. Be om kansellering. Avanserte samtidighetsmønstre. Asynkron buffer. Grasiøs serveravslutning. kontekst. WithTimeout. Batching og kansellering.
08 database/sql, sqlx, arbeider med databaser, redis.
09 Refleksjon. reflektere. Skriv og reflekter. Verdi. struct-tagger. nett/rpc. koding/gob. synkronisere. Kart. reflektere. DeepEqual.
10 Pakke io, Reader og Writer-implementeringer fra standardbiblioteket. Programmering på lavt nivå. utrygt. Pakke binær. bytes. Buffer. cgo, syscall.
11 GC-arkitektur. Skrivesperre. Stabelvekst. GC pause. GOGC. synkronisere. Basseng. Goroutine-planlegger. GOMACPROCS. Lekkede tråder.
12 Gå til verktøy. pprof. CPU- og minneprofilering. Krysskompilering. GOOS, GOARCH. CGO_ENABLED=0. Bygg tagger. gå moduler. godoc. x/analyse. Kodegenerering.
13 Nyttige biblioteker. CLI-applikasjoner med cobra. Protobuf og GRPC. zap-logging.

Tredje semester

Påbudt, bindende
Algoritmer i eksternt minne

Emnet introduserer studentene til grunnleggende prinsipper for å konstruere algoritmer for arbeid med data som ikke passer inn i datamaskinens RAM.

01 Algoritmer i eksternt minne.
02 Buffer-uvitende algoritmer.
03 Algoritmer for behandling av strømdata.

Distribuerte systemer

Anbefalte spesialkurs
Styrken til kryptografiske systemer

01 Grunnleggende tilnærminger og prinsipper for moderne kryptografi. Motstandsmodellen, formalisering av styrkebegrepet, problemet med å vurdere styrke og relaterte problemer, inndeling i primitiver og protokoller, stadier av "livet" til et kryptografisk system.
02 Konfidensialitet. Hverdagsdefinisjoner av konfidensialitet, tilnærminger til formalisering (informasjonsteoretisk modell av fienden, modeller KR, PR, LOR, ROR, IND, CPA, CCA), symmetrisk krypteringssystem, anvendelse av kompleksitetsteoretisk informasjon for å bestemme forholdet mellom modeller. Forhold mellom grunnleggende motstandermodeller for å vurdere styrken til krypteringssystemer.
03 Tilnærminger til å bygge krypteringssystemer. Bygge fra bunnen av. Konstruksjoner basert på blokkchiffer, definisjon av et blokkchiffer, hovedegenskaper, tilnærminger til konstruksjon og egenskaper. Modeller PRP og PRF. Det paradoksale med bursdagsproblemet. Lemma om forholdet mellom motstand i PRF- og PRP-modellene.
04 Krypteringsmoduser. Grunnleggende krypteringsmoduser: ECB, CBC, CFB, OFB, CTR. Grunnleggende ytelsesegenskaper. Holdbarhet av CTR i LOR-CPA, ustabilitet av ECB i LOR-CPA. Ustabilitet av grunnleggende moduser i CCA-modeller.
05 Integritet. Definisjon av begrepet integritet. Tilnærminger til formalisering (UF-CMA-modell, modeller basert på diskrimineringsoppgaven, PRF-modell). Meldingsautentiseringskoder og funksjoner for generering av imiterte innlegg. Design basert på blokkchiffer: CBC-MAC, XCBC, TMAC, OMAC. Sårbare moduser.
06 Hash-funksjoner. Definisjon, grunnleggende egenskaper, tilnærminger til konstruksjon, formalisering og relaterte problemer. Eksempler på bruk av hashfunksjoner: passordhashing, entropiekstraksjon. Konstruere kollisjoner og forhåndsbilder fra sett med lav kardinalitet.
07 HMAC, KDF, PRF, DRNG kretser. HMAC-diagram, grunnleggende trinn for å oppnå motstandsvurdering. Nøkkeldiversifisering og prinsippet om nøkkelseparasjon, KDF- og PRF-ordninger. Pseudorandomgenerator, DRNG-kretser.
08 Nøkkellast. Problem med nøkkelbelastning. Hovedmetodene for å redusere belastningen på en nøkkel er eksterne og interne nøkkelkonverteringer. Parallelle og serielle re-keying ordninger, grunnleggende egenskaper. Nøkkeltre. Intern nøkkelendring og CTR-ACPKM-modus.
09 Kryptering med imitasjonsbeskyttelse. Problemformulering. Generelle strukturer (EtA, AtE, A&E) og deres egenskaper. Eksempler på sårbare moduser for å sikre konfidensialitet og integritet ved bruk av én enkelt nøkkel. AEAD-krypteringsmoduser: GCM, MGM.
10 Sikker kommunikasjonskanal. Konseptet med en sikker kommunikasjonskanal: typer kanaler, grunnleggende egenskaper (integritet og konfidensialitet av dataflyten). Eksempler på sårbare protokoller. Ta opp TLS 1.3-protokoll.

Fjerde semester

Å velge fra
Teori og praksis for samtidighet

Kurset er viet konkurrerende systemer og oppgaver i vid forstand: fra nivået av konkurranse mellom prosessorkjerner for skriving til én celle minne til distribuerte systemer som ønsker å replikere tilstanden deres på tvers av flere servere på en feiltolerant og konsistent måte.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md

eller
Gå språk
01 Introduksjon. Kursprogram. Rapportering på kurset, evalueringskriterier. Designfilosofi. hvis, bytte, for. Hei Verden. Kommandolinjeargumenter. Ordtelling. Animert gif. Henter URL. Henter URL samtidig. Internett server. Tour of go. Lokalt IDE-oppsett. gofmt. goimporter. linting
02 Grunnleggende språkstrukturer. navn, erklæringer, variabler, oppdrag. typeerklæringer. pakker og filer. omfang. Null verdi. Minnetildeling. Stabel vs haug. Grunnleggende datatyper. Konstanter. Sammensatte datatyper. Matriser. Skiver. Kart. Strukturer. JSON. tekst/mal. streng og []byte. Jobber med unicode. Unicode-erstatningstegn. Funksjoner. Funksjoner med et variabelt antall argumenter. Anonyme funksjoner. Feil.
03 Metoder. Verdimottaker vs pekermottaker. Innebygging. Metodeverdi. Innkapsling. Grensesnitt. Grensesnitt som kontrakter. io. Forfatter, io. Reader og deres implementeringer. sortere. Grensesnitt. feil. http. Handler. Grensesnitt som oppregninger. Skriv påstand. Type bryter. Jo større grensesnitt, jo svakere abstraksjon. Feil under behandling. panikk, utsette, komme seg. feil.{Unwrap, Is, As}. fmt. Feilf. %w.
04 Goroutiner og kanaler. klokkeserver. ekkoserver. Kanalstørrelse. Blokkerende og ikke-blokkerende lesing. velg uttalelse. Kanalaksiomer. tid. Etter. tid. NewTicker. Rørledningsmønster. Kansellering. Parallell sløyfe. synkronisere. Ventegruppe. Feilhåndtering i parallell kode. feilgruppe. Gruppe. Samtidig webcrawler. Samtidig kataloggjennomgang.
05 Avansert testing. Delprøver. testing. B. (T). Loggf. (T). Skipf. (T).FailNow. testing. Short(), tester flagg. Generasjon av spotter. vitne/{require, assert}. vitne/suite. Testarmatur. Integrasjonstester. Goroutine lekkasjedetektor. TestingMain. Dekning. Sammenligning av benchmarks.
06 Samtidig med delt minne. synkronisere. Mutex. synkronisere. RWMutex. synkronisere. Cond. atomisk synkronisere. En gang. Race detektor. Asynkron buffer. Arbeid med databasen. database/sql. sqlx.
07 Pakkekontekst. Sender data med forespørselsomfang. http mellomvare. chi. Ruter. Be om kansellering. Avanserte samtidighetsmønstre. Asynkron buffer. Grasiøs serveravslutning. kontekst. WithTimeout. Batching og kansellering.
08 database/sql, sqlx, arbeider med databaser, redis.
09 Refleksjon. reflektere. Skriv og reflekter. Verdi. struct-tagger. nett/rpc. koding/gob. synkronisere. Kart. reflektere. DeepEqual.
10 Pakke io, Reader og Writer-implementeringer fra standardbiblioteket. Programmering på lavt nivå. utrygt. Pakke binær. bytes. Buffer. cgo, syscall.
11 GC-arkitektur. Skrivesperre. Stabelvekst. GC pause. GOGC. synkronisere. Basseng. Goroutine-planlegger. GOMACPROCS. Lekkede tråder.
12 Gå til verktøy. pprof. CPU- og minneprofilering. Krysskompilering. GOOS, GOARCH. CGO_ENABLED=0. Bygg tagger. gå moduler. godoc. x/analyse. Kodegenerering.
13 Nyttige biblioteker. CLI-applikasjoner med cobra. Protobuf og GRPC. zap-logging.

eller
Database
01 Grensesnitt til moderne databaser: relasjonell, nøkkelverdi, dokument, graf. Relasjonsalgebra og SQL-språk.
02 Arbeide med disk i klassisk relasjons-DBMS: sider, sidepool, utkastelse fra bassenget.
03 Utføre SQL-spørringer: uttrykksanalyse, planlegging, utførelse. Tolkning og kodegenerering ved hjelp av LLVM.
04 Indekser i relasjonell DBMS: typer indekser, lagringsmetoder, bruk i spørringer.
05 Transaksjoner: ACID akronym, isolasjonsnivåer, implementering av transaksjoner gjennom låser og MVCC.
06 Katastrofegjenoppretting: logg, sjekkpunkter, ARIES-algoritme.
07 Datalagring ved hjelp av Log-Structured Merge Tree-metoden.
08 Kolonnebasert DBMS: fordeler, funksjoner, datakomprimeringsalgoritmer.
09 Distribuert DBMS: sharding, transaksjoner, utførelse av spørringer.
10 DBMS plassert i hovedminnet. Datastrukturer for indekser i minnet.

eller
Datanettverk
01 Introduksjon til nettverksteknologier. Historien om nettverk, nettverksprotokoller, organisering av nettverksinteraksjon i et peer-to-peer-nettverk og koblingen av peer-to-peer-nettverk med hverandre.
02 Transport. OSI/ISO nettverksmodell. TCP, etablering av nettverkstilkobling, sammenligning av TCP og UDP. Tcpdump-analyse – byte i fly, sender grafer på nytt. Metoder for å kontrollere dataflyt i en TCP-sesjon. Ulike typer TCP-sesjoner og båndbreddehåndtering av overførte data i pakkenettverk.
03 Ruting. Konseptet med ruting i nettverk. Statisk og dynamisk ruting. Grunnleggende om dynamisk ruting. Dynamisk rutingprotokoll - OSPF. Avstandsvektorrutingsprotokoller. Oversikt over BGP-rutingsprotokollen - meldingstyper, BGP-attributter, valg av optimal rute i BGP.
04 Slik fungerer Internett: BGP og DNS. Internett-ruting. Oversikt over DNS-protokollen.
05 Nettverk i store datasentre. Funksjoner av arkitekturen til datasenternettverk. Krav til datasenternettverk. CLOS-arkitektur for datasenternettverk.
06 Forsinkelser i nettverk. Funksjoner ved å bygge store ryggradsnettverk. Årsaker til forsinkelser i dataoverføring over ryggradsnettverk.
07 Skalering og tilgjengelighet av Internett-tjenester. Lastbalanseringsteknologier og tjenestearkitektur.
08 MPLS og SR, Nettverksprogrammerbarhet. MPLS og Segment Routing-teknologier for å bygge ryggradsnettverk. Formål med MPLS-teknologi, protokoller brukt for etikettutveksling.
09 Prinsipper for drift av nettverksenheter. Ruterarkitektur, funksjoner for behandling av nettverkstrafikk inne i nettverksenheter.
10 skyer. Software Defined Networking Fundamentals - Protokoller som brukes til å bygge programvaredefinerte nettverk. Integrasjon av virtualiseringsplattformer og nettverksinfrastruktur.

eller
Kryptografiske protokoller
01 Grunnleggende ideer om asymmetrisk kryptografi. Hovedforskjellen mellom asymmetrisk kryptografi og symmetrisk kryptografi. Hovedideer: protokoll for å generere en delt nøkkel, offentlig nøkkelkryptering, elektronisk signatur (problemer som skal løses, intuitiv forståelse av sikkerhetsegenskaper). Spesifikke kryptografiske skjemaer: Diffie-Hellman-protokollen, ElGamal- og RSA-krypteringsskjemaer, ElGamal- og RSA-signaturer. Det grunnleggende problemet med asymmetriske ordninger er tillit til den offentlige nøkkelen.
02 Styrken til grunnleggende asymmetriske kryptografiordninger. Formell definisjon av motstand: modellene UF-CMA, IND-CPA, DLP, CDH, DDH. Forholdet mellom dem. Styrken til ElGamal-krypteringsordningen. Ustabiliteten til RSA-signaturordningen uten å bruke en hash-funksjon.
03 Lær mer om asymmetrisk kryptografi. Lamparts signatur, Merkles diagram. DSKS angrep.
04 Algebraisk og tallteoretisk grunnlag for asymmetrisk kryptografi. Finite grupper, sykliske grupper, rekkefølge på gruppeelement. Diskret logaritmeproblem (DLP). Multiplikative grupper av endelige felt. Grunnleggende informasjon om elliptiske kurver.
05 Elliptiske kurver. Hasses teorem. Addisjon av punkter på en elliptisk kurve. Gruppe av punkter på en elliptisk kurve. Signaturordning GOST R 34.10-2012.
06 Diskret logaritme. Diskrete logaritmealgoritmer (Pollards Rho-metode, matchingsmetode, Polig-Hellman-metode, indeksberegningsmetode).
07 PKI-teknologi. Grunnleggende prinsipper og konsepter for offentlig nøkkelinfrastruktur (PKI). Sertifikat, CA, CRL, OCSP, trust space.
08 TLS-protokoll. Historien om TLS-protokollen. Protokollstruktur, grunnleggende driftsprinsipper. TLS-protokoll kryptografiske suiter basert på russiske kryptografiske algoritmer.
09 Grunnleggende om bygging av AKE-protokoller. Konseptet med AKE-protokollen. Målrett egenskaper. Grunnleggende tilnærminger til konstruksjon.
10 Sikker oppbevaring av nøkkel. Problemet med sikker bruk av private nøkler. Nøkkelmedier, ikke-flyttbare nøkler. Problemet med tilstedeværelsen av en motstander i kanalen, protokollene til PAKE-familien.
11 Grunnleggende konsepter for blokkjedeteknologi. Oppgaven med koordinert desentralisert samhandling. Grunnleggende begreper om sikkerhetsbegrepet. Sikkerhet nærmer seg.
12 Grunnleggende prinsipper for kvanteteknologier og deres anvendelser i kryptografi