Infrastructură Big Data - curs gratuit de la Școala de Analiză a Datelor, 4 semestre, Data: 5 decembrie 2023.
Miscelaneu / / December 08, 2023
Pentru cei care iubesc algoritmii, lucrează cu date și se bucură de programare, dar nu ar dori să-și conecteze viața cu învățarea automată.
Algoritmi, programare, proiectare sisteme de fișiere, discuri, rețele și procesoare, precum și sisteme distribuite.
În crearea și sprijinirea sistemelor distribuite eficiente și fiabile pentru stocarea și procesarea datelor mari.
Fiecare student trebuie să parcurgă cu succes cel puțin trei cursuri pe parcursul semestrului. De exemplu, dacă există două dintre ele în programul principal, atunci trebuie să alegeți unul dintre cursurile speciale.
Cunoștințele sunt testate în primul rând prin teme - examenele și testele se desfășoară doar la unele materii.
Primul semestru
Obligatoriu
Algoritmi și structuri de date, partea 1
01 Complexitate și modele de calcul. Analiza valorilor contabile (început)
02 Analiza valorilor contabile (sfârșit)
03 Algoritmi Merge-Sort și Quick-Sort
04 Statistici ordinale. grămezi (început)
05 grămezi (sfârșit)
06 Hashing
07 Căutare arbori (început)
08 Căutare arbori (continuare)
09 Căutați arbori (sfârșit). Sistem de mulțimi disjunse
10 Obiectivele RMQ și LCA
11 Structuri de date pentru căutare geometrică
12 Problema conectivității dinamice într-un graf nedirecționat
Arhitectura calculatoarelor si sisteme de operare
01 UNIX și programare în C: linie de comandă, control proces, canale, semnale. Implementarea unui shell de linie de comandă.
Asamblator 02 x86: aritmetică, tranziții, condiții și apeluri de funcții. Stivă, deplasând în sus.
03 Conectarea programelor și a formatului ELF. Legătura dinamică.
04 Conceptul de context și flux de execuție. Implementarea firelor ușoare.
05 Multitasking preventiv: suport de la procesorul x86 și implementarea proceselor în nucleul UNIX.
06 Arhitectură multi-core: coerență cache și modele de memorie. Primitive de sincronizare în programe multithreaded.
07 Programarea proceselor pe un nucleu și pe mai multe nuclee.
08 Memorie externă: hard disk-uri și unități SSD. Principii de funcționare a sistemelor de fișiere.
09 Virtualizare: hardware și software. Difuzare binară.
Pregătirea limbajului C++, partea 1
C++ este un limbaj puternic, cu o moștenire bogată. Pentru cei care tocmai au pornit pe calea stăpânirii acestui limbaj, este foarte ușor să se piardă în abundența de tehnici și tehnici create în ultimii 30 de ani. Cursul predă „Modern C++” - un subset modern al limbajului (standardele 11, 14 și 17). Se acordă multă atenție instrumentelor și bibliotecilor - lucruri care nu fac parte din limbaj, dar fără de care nu se va putea construi un proiect amplu și complex.
01 Introducere în C++.
02 constante. Indicatori și link-uri. Transmiterea de argumente unei funcții.
03 Clasuri.
04 Gestionarea dinamică a memoriei.
05 Variabile, indicatoare și referințe.
06 Managementul memoriei, pointeri inteligente, RAII.
07 Bibliotecă de șabloane standard.
08 Moștenire și funcții virtuale.
09 Gestionarea erorilor.
10 modele de design.
11 Spații de nume Mutare semantică Redirecționare perfectă.
12 Reprezentarea structurilor și claselor în memorie. Alinierea datelor. Indicatori către membrii/metodele clasei. Șabloane variadice.
Al doilea mandat
Obligatoriu
Algoritmi și structuri de date, partea 2
01 Ocolire în lățime. Adâncime prima traversare (început)
02 Traversare adâncime (continuare)
03 Traversare în profunzime (capăt). 2-tăieri
04 Găsirea celor mai scurte căi (început)
05 Găsirea celor mai scurte căi (continuare)
06 Arbori de întindere minim
07 Tăieri minime. Căutați subșiruri (start)
08 Căutați subșiruri (continuare)
09 Căutați subșiruri (sfârșit)
10 arbori cu sufix (început)
11 Arbori de sufix (termină). Matrice de sufixe (start)
12 matrice de sufixe (termină)
13 Cele mai lungi subșiruri comune. Căutare aproximativă de subșiruri.
Pregătirea limbajului C++, partea 2
A doua parte a cursului C++, care acoperă subiecte avansate și capacități lingvistice.
01 Programare cu mai multe fire. Sincronizarea firelor de execuție folosind mutexuri și variabile de condiție.
02 Variabile atomice. Model de memorie C++. Exemple de structuri de date fără blocare.
03 Tehnici avansate de meta-programare în C++. Metafuncții, SFINAE, concepte.
04 Programare competitivă, interacțiune cu rețeaua.
05 llvm arhitectură. Lucrul cu arborele de analiză C++. Dezvoltarea de instrumente pentru analiza codului C++.
A alege din
Teoria și practica concurenței
Cursul este dedicat sistemelor și sarcinilor competitive în sensul cel mai larg: de la nivelul concurenței dintre nucleele procesorului pentru scriere la o singură celulă memorie către sistemele distribuite care doresc să-și reproducă starea pe mai multe servere într-un mod tolerant la erori și consecvent.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md
sau
Du-te limba
01 Introducere. Programul cursului. Raportarea cursului, criteriile de evaluare. Filosofia designului. dacă, comuta, pentru. Salut Lume. Argumente ale liniei de comandă. Număr de cuvinte. Gif animat. Se preia adresa URL. Se preia adresa URL simultan. server web. Tur de go. Configurare IDE locală. gofmt. goimports. scame.
02 Structuri de bază ale limbajului. nume, declarații, variabile, atribuiri. declarații de tip. pachete și fișiere. domeniul de aplicare. Valoare zero. Alocare de memorie. Stivă vs grămada. Tipuri de date de bază. constante. Tipuri de date compuse. Matrice. felii. Hărți. Structuri. JSON. text/șablon. șir și []octet. Lucrul cu unicode. caracter de înlocuire Unicode. Funcții. Funcții cu un număr variabil de argumente. Funcții anonime. Erori.
03 Metode. Receptor de valoare vs receptor pointer. Încorporarea. Valoarea metodei. Încapsulare. Interfețe. Interfețele ca contracte. io. Scriitor, io. Reader și implementările acestora. fel. Interfață. eroare. http. Handler. Interfețele ca enumerații. Tip afirmație. Comutator de tip. Cu cât interfața este mai mare, cu atât abstracția este mai slabă. Eroare la procesare. panica, amâna, recupera. erori.{Desfășurare, este, ca}. fmt. Errorf. %w.
04 Goroutine și canale. server de ceas. server echo. Dimensiunea canalului. Citire blocare și neblocare. selectează declarația. Axiomele canalului. timp. După. timp. NewTicker. Model de conducte. Anulare. Bucla paralelă. sincronizare. WaitGroup. Gestionarea erorilor în codul paralel. errgroup. Grup. Crawler web simultan. Parcurgere simultană a directoarelor.
05 Testare avansată. Subteste. testarea. B. (T).Logf. (T).Skipf. (T).FailNow. testarea. Short(), steaguri de testare. Generație de batjocuri. depune mărturie/{cere, afirmă}. mărturie/suită. Dispozitiv de testare. Teste de integrare. Detector de scurgeri Goroutine. TestingMain. Acoperire. Compararea benchmark-urilor.
06 Testare avansată. Subteste. testarea. B. (T).Logf. (T).Skipf. (T).FailNow. testarea. Short(), steaguri de testare. Generație de batjocuri. depune mărturie/{cere, afirmă}. mărturie/suită. Dispozitiv de testare. Teste de integrare. Detector de scurgeri Goroutine. TestingMain. Acoperire. Compararea benchmark-urilor.
07 Contextul pachetului. Transmiterea datelor din domeniul de aplicare al cererii. middleware http. chi. Router. Anularea cererii. Modele avansate de concurență. Cache asincron. Închidere grațioasă a serverului. context. WithTimeout. Loturi și anulare.
08 database/sql, sqlx, lucru cu baze de date, redis.
09 Reflecție. Reflectați. Tastați și reflectați. Valoare. etichete struct. net/rpc. codificare/gob. sincronizare. Hartă. Reflectați. DeepEqual.
10 Implementări pachet io, Reader și Writer din biblioteca standard. Programare la nivel scăzut. nesigure. Pachetul binar. octeți. Tampon. cgo, syscall.
11 Arhitectura GC. Bariera de scris. Creșterea stivei. GC pauză. GOGC. sincronizare. Bazin. Programator Goroutine. GOMACPROCS. Fire scurse.
12 Mergeți cu scule. pprof. Profilare CPU și memorie. Compilare încrucișată. GOOS, GOARCH. CGO_ENABLED=0. Construiți etichete. go module. godoc. x/analiza. Generarea codului.
13 biblioteci utile. Aplicații CLI cu cobra. Protobuf și GRPC. logging zap.
Al treilea semestru
Obligatoriu
Algoritmi în memoria externă
Cursul prezintă studenților principiile de bază ale construirii algoritmilor de lucru cu date care nu se potrivesc în memoria RAM a computerului.
01 Algoritmi în memoria externă.
02 Algoritmi ignorați în cache.
03 Algoritmi pentru procesarea datelor în flux.
Sisteme distribuite
Cursuri speciale recomandate
Puterea sistemelor criptografice
01 Abordări și principii de bază ale criptografiei moderne. Modelul adversarului, formalizarea conceptului de forță, problema evaluării puterii și problemele conexe, împărțirea în primitive și protocoale, etapele „vieții” unui sistem criptografic.
02 Confidențialitate. Definiții cotidiene ale confidențialității, abordări ale formalizării (modelul teoretic informațional al inamicului, modele KR, PR, LOR, ROR, IND, CPA, CCA), sistem de criptare simetrică, aplicarea informațiilor teoretice ale complexității pentru a determina relația dintre modele. Relații dintre modelele adverse de bază pentru evaluarea puterii sistemelor de criptare.
03 Abordări ale construirii sistemelor de criptare. Construire de la zero. Construcții bazate pe cifru bloc, definiția unui cifr bloc, principalele caracteristici, abordări ale construcției și proprietăți. Modelele PRP și PRF. Paradoxul problemei zilei de naștere. Lema privind relația dintre rezistență în modelele PRF și PRP.
04 Moduri de criptare. Moduri de criptare de bază: ECB, CBC, CFB, OFB, CTR. Proprietăți de bază de performanță. Durabilitatea CTR în LOR-CPA, instabilitatea BCE în LOR-CPA. Instabilitatea modurilor de bază în modelele CCA.
05 Integritate. Definiția conceptului de integritate. Abordări ale formalizării (modelul UF-CMA, modele bazate pe sarcina de discriminare, model PRF). Coduri de autentificare a mesajelor și funcții pentru generarea de inserții imitate. Proiecte bazate pe cifruri bloc: CBC-MAC, XCBC, TMAC, OMAC. Moduri vulnerabile.
06 Funcții hash. Definiție, proprietăți de bază, abordări ale construcției, formalizare și probleme conexe. Exemple de utilizare a funcțiilor hash: hashing parole, extrage entropie. Construirea de coliziuni și preimagini din seturi de cardinalitate scăzută.
07 Circuite HMAC, KDF, PRF, DRNG. Diagrama HMAC, pași de bază pentru obținerea ratingului de rezistență. Diversificarea cheilor și principiul separării cheilor, scheme KDF și PRF. Generator pseudorandom, circuite DRNG.
08 Încărcare cheie. Problemă la încărcarea cheii. Principalele metode de reducere a sarcinii unei chei sunt conversiile externe și interne ale cheilor. Scheme de reintroducere în paralel și în serie, proprietăți de bază. Arborele cheie. Schimbarea cheii interne și modul CTR-ACPKM.
09 Criptare cu protecție împotriva imitațiilor. Formularea problemei. Structuri generale (EtA, AtE, A&E) și proprietățile acestora. Exemple de moduri vulnerabile pentru asigurarea confidențialității și integrității folosind o singură cheie. Moduri de criptare AEAD: GCM, MGM.
10 Canal de comunicare securizat. Conceptul de canal de comunicare securizat: tipuri de canale, proprietăți de bază (integritatea și confidențialitatea fluxului de date). Exemple de protocoale vulnerabile. Înregistrați protocolul TLS 1.3.
Al patrulea semestru
A alege din
Teoria și practica concurenței
Cursul este dedicat sistemelor și sarcinilor competitive în sensul cel mai larg: de la nivelul concurenței dintre nucleele procesorului pentru scriere la o singură celulă memorie către sistemele distribuite care doresc să-și reproducă starea pe mai multe servere într-un mod tolerant la erori și consecvent.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md
sau
Du-te limba
01 Introducere. Programul cursului. Raportarea cursului, criteriile de evaluare. Filosofia designului. dacă, comuta, pentru. Salut Lume. Argumente ale liniei de comandă. Număr de cuvinte. Gif animat. Se preia adresa URL. Se preia adresa URL simultan. server web. Tur de go. Configurare IDE locală. gofmt. goimports. scame.
02 Structuri de bază ale limbajului. nume, declarații, variabile, atribuiri. declarații de tip. pachete și fișiere. domeniul de aplicare. Valoare zero. Alocare de memorie. Stivă vs grămada. Tipuri de date de bază. constante. Tipuri de date compuse. Matrice. felii. Hărți. Structuri. JSON. text/șablon. șir și []octet. Lucrul cu unicode. caracter de înlocuire Unicode. Funcții. Funcții cu un număr variabil de argumente. Funcții anonime. Erori.
03 Metode. Receptor de valoare vs receptor pointer. Încorporarea. Valoarea metodei. Încapsulare. Interfețe. Interfețele ca contracte. io. Scriitor, io. Reader și implementările acestora. fel. Interfață. eroare. http. Handler. Interfețele ca enumerații. Tip afirmație. Comutator de tip. Cu cât interfața este mai mare, cu atât abstracția este mai slabă. Eroare la procesare. panica, amâna, recupera. erori.{Desfășurare, este, ca}. fmt. Errorf. %w.
04 Goroutine și canale. server de ceas. server echo. Dimensiunea canalului. Citire blocare și neblocare. selectează declarația. Axiomele canalului. timp. După. timp. NewTicker. Model de conducte. Anulare. Bucla paralelă. sincronizare. WaitGroup. Gestionarea erorilor în codul paralel. errgroup. Grup. Crawler web simultan. Parcurgere simultană a directoarelor.
05 Testare avansată. Subteste. testarea. B. (T).Logf. (T).Skipf. (T).FailNow. testarea. Short(), steaguri de testare. Generație de batjocuri. depune mărturie/{cere, afirmă}. mărturie/suită. Dispozitiv de testare. Teste de integrare. Detector de scurgeri Goroutine. TestingMain. Acoperire. Compararea benchmark-urilor.
06 Concurență cu memoria partajată. sincronizare. Mutex. sincronizare. RWMutex. sincronizare. Cond. atomic sincronizare. O singura data. Detector de curse. Cache asincron. Lucrul cu baza de date. baza de date/sql. sqlx.
07 Contextul pachetului. Transmiterea datelor din domeniul de aplicare al cererii. middleware http. chi. Router. Anularea cererii. Modele avansate de concurență. Cache asincron. Închidere grațioasă a serverului. context. WithTimeout. Loturi și anulare.
08 database/sql, sqlx, lucru cu baze de date, redis.
09 Reflecție. Reflectați. Tastați și reflectați. Valoare. etichete struct. net/rpc. codificare/gob. sincronizare. Hartă. Reflectați. DeepEqual.
10 Implementări pachet io, Reader și Writer din biblioteca standard. Programare la nivel scăzut. nesigure. Pachetul binar. octeți. Tampon. cgo, syscall.
11 Arhitectura GC. Bariera de scris. Creșterea stivei. GC pauză. GOGC. sincronizare. Bazin. Programator Goroutine. GOMACPROCS. Fire scurse.
12 Mergeți cu scule. pprof. Profilare CPU și memorie. Compilare încrucișată. GOOS, GOARCH. CGO_ENABLED=0. Construiți etichete. go module. godoc. x/analiza. Generarea codului.
13 biblioteci utile. Aplicații CLI cu cobra. Protobuf și GRPC. logging zap.
sau
Bază de date
01 Interfețe ale bazelor de date moderne: relaționale, cheie-valoare, document, grafic. Algebră relațională și limbaj SQL.
02 Lucrul cu discul în SGBD relațional clasic: pagini, pool de pagini, evacuare din pool.
03 Executarea interogărilor SQL: analiza expresiei, planificare, execuție. Interpretare și generare de cod folosind LLVM.
04 Indici în SGBD relațional: tipuri de indici, metode de stocare, utilizare în interogări.
05 Tranzacții: acronim ACID, niveluri de izolare, implementarea tranzacțiilor prin încuietori și MVCC.
06 Recuperare în caz de dezastru: jurnal, puncte de control, algoritm ARIES.
07 Stocarea datelor folosind metoda Log-Structured Merge Tree.
08 SGBD pe coloane: avantaje, caracteristici, algoritmi de compresie a datelor.
09 SGBD distribuit: sharding, tranzacții, execuție interogări.
10 SGBD situate în memoria principală. Structuri de date pentru indici în memorie.
sau
Retele de calculatoare
01 Introducere în tehnologiile de rețea. Istoricul rețelelor, protocoalele de rețea, organizarea interacțiunii rețelei într-o rețea peer-to-peer și conexiunea rețelelor peer-to-peer între ele.
02 Transport. Model de rețea OSI/ISO. TCP, stabilirea conexiunii la rețea, compararea TCP și UDP. Analiza Tcpdump – octeți în zbor, retransmite grafice. Metode pentru controlul fluxului de date într-o sesiune TCP. Diferite tipuri de sesiuni TCP și gestionarea lățimii de bandă a datelor transmise în rețelele de pachete.
03 Dirijare. Conceptul de rutare în rețele. Rutare statică și dinamică. Bazele rutării dinamice. Protocol de rutare dinamică - OSPF. Protocoale de rutare vectorială la distanță. Prezentare generală a protocolului de rutare BGP - tipuri de mesaje, atribute BGP, alegerea rutei optime în BGP.
04 Cum funcționează Internetul: BGP și DNS. rutare pe internet. Prezentare generală a protocolului DNS.
05 Rețele în centre mari de date. Caracteristici ale arhitecturii rețelelor de centre de date. Cerințe pentru rețelele de centre de date. Arhitectura CLOS pentru rețelele de centre de date.
06 Întârzieri în rețele. Caracteristici de construire a rețelelor principale mari. Motive pentru întârzierile în transmiterea datelor prin rețelele principale.
07 Extinderea și disponibilitatea serviciilor de internet. Tehnologii de echilibrare a sarcinii și arhitectură de servicii.
08 MPLS și SR, programabilitate în rețea. Tehnologii MPLS și Segment Routing pentru construirea de rețele backbone. Scopul tehnologiei MPLS, protocoale utilizate pentru schimbul de etichete.
09 Principii de funcționare a dispozitivelor de rețea. Arhitectura routerului, caracteristici de procesare a traficului de rețea în interiorul dispozitivelor de rețea.
10 nori. Fundamentele rețelelor definite de software - Protocoale utilizate pentru a construi rețele definite de software. Integrarea platformelor de virtualizare și a infrastructurii de rețea.
sau
Protocoale criptografice
01 Idei de bază ale criptografiei asimetrice. Principala diferență dintre criptografia asimetrică și criptografia simetrică. Idei principale: protocol pentru generarea unei chei partajate, criptare cheie publică, semnătură electronică (probleme de rezolvat, înțelegere intuitivă a proprietăților de securitate). Scheme criptografice specifice: protocol Diffie-Hellman, scheme de criptare ElGamal și RSA, semnături ElGamal și RSA. Problema fundamentală a schemelor asimetrice este încrederea în cheia publică.
02 Puterea schemelor de criptografie asimetrică de bază. Definirea formală a rezistenței: modelele UF-CMA, IND-CPA, DLP, CDH, DDH. Relațiile dintre ei. Puterea schemei de criptare ElGamal. Instabilitatea schemei de semnătură RSA fără a utiliza o funcție hash.
03 Aflați mai multe despre criptografia asimetrică. Semnătura lui Lampart, diagrama lui Merkle. Atacul DSKS.
04 Fundamentele algebrice și teoretice de numere ale criptografiei asimetrice. Grupuri finite, grupuri ciclice, ordinea elementului de grup. Problemă cu logaritmul discret (DLP). Grupuri multiplicative de câmpuri finite. Informații de bază despre curbele eliptice.
05 Curbe eliptice. teorema lui Hasse. Adunarea punctelor pe o curbă eliptică. Grup de puncte pe o curbă eliptică. Schema de semnătură GOST R 34.10-2012.
06 Logaritm discret. Algoritmi logaritmi discreti (metoda Rho a lui Pollard, metoda de potrivire, metoda Polig-Hellman, metoda de calcul a indicilor).
07 Tehnologia PKI. Principii și concepte de bază ale infrastructurii cu chei publice (PKI). Certificat, CA, CRL, OCSP, spațiu de încredere.
08 Protocol TLS. Istoricul protocolului TLS. Structura protocolului, principii de bază de funcționare. Suite criptografice de protocol TLS bazate pe algoritmi criptografici ruși.
09 Elementele de bază ale construirii protocoalelor AKE. Conceptul protocolului AKE. Proprietăți țintă. Abordări de bază ale construcției.
10 Stocare securizată a cheilor. Problema utilizării în siguranță a cheilor private. Cheie media, chei nedetașabile. Problema prezenței unui adversar în canal, protocoale familiei PAKE.
11 Concepte de bază ale tehnologiei blockchain. Sarcina interacțiunii descentralizate coordonate. Concepte de bază ale conceptului de securitate. Abordări de securitate.
12 Principii de bază ale tehnologiilor cuantice și aplicațiile acestora în criptografie