Big Data Infrastructure - cours gratuit de la School of Data Analysis, 4 semestres, Date: 5 décembre 2023.

Chaque étudiant doit réussir au moins trois cours au cours du semestre. Par exemple, s'il y en a deux dans le programme principal, vous devez alors choisir l'un des cours spéciaux.

Les connaissances sont testées principalement par le biais de devoirs - les examens et les tests ne sont effectués que dans certaines matières.

Premier semestre

Obligatoire
Algorithmes et structures de données, partie 1

01 Complexité et modèles informatiques. Analyse des valeurs comptables (début)
02 Analyse des valeurs comptables (fin)
03 Algorithmes de tri par fusion et de tri rapide
04 Statistiques ordinales. Tas (début)

05 tas (fin)
06 Hachage
07 Rechercher des arbres (début)
08 Arbres de recherche (suite)
09 Rechercher des arbres (fin). Système d'ensembles disjoints
10 Objectifs du RMQ et de l'ACV
11 Structures de données pour la recherche géométrique
12 Problème de connectivité dynamique dans un graphe non orienté

Architecture informatique et systèmes d'exploitation

01 UNIX et programmation en C: ligne de commande, contrôle de processus, canaux, signaux. Implémentation d'un shell en ligne de commande.
02 Assembleur x86: arithmétique, transitions, conditions et appels de fonctions. Pile, en remontant la pile.
03 Liaison des programmes et format ELF. Liaison dynamique.
04 La notion de contexte et de flux d'exécution. Implémentation de threads légers.
05 Multitâche préemptif: support depuis le processeur x86 et implémentation de processus dans le noyau UNIX.
06 Architecture multicœur: cohérence du cache et modèles de mémoire. Primitives de synchronisation dans les programmes multithread.
07 Planification des processus sur un cœur et sur plusieurs cœurs.
08 Mémoire externe: disques durs et disques SSD. Principes de fonctionnement des systèmes de fichiers.
09 Virtualisation: matériel et logiciel. Diffusion binaire.

Formation linguistique C++, partie 1

C++ est un langage puissant avec un riche héritage. Pour ceux qui viennent de s'engager sur la voie de la maîtrise de cette langue, il est très facile de se perdre dans l'abondance de techniques et de techniques créées au cours des 30 dernières années. Le cours enseigne le "Modern C++" - un sous-ensemble moderne du langage (normes 11, 14 et 17). Une grande attention est accordée aux outils et aux bibliothèques - des éléments qui ne font pas partie du langage, mais sans lesquels il ne sera pas possible de construire un projet vaste et complexe.
01 Introduction au C++.
02 Constantes. Pointeurs et liens. Passer des arguments à une fonction.
03 cours.
04 Gestion dynamique de la mémoire.
05 Variables, pointeurs et références.
06 Gestion mémoire, pointeurs intelligents, RAII.
07 Bibliothèque de modèles standards.
08 Héritage et fonctions virtuelles.
09 Gestion des erreurs.
10 modèles de conception.
11 Espaces de noms Sémantique de déplacement Transmission parfaite.
12 Représentation des structures et des classes en mémoire. Alignement des données. Pointeurs vers les membres de la classe/méthodes. Modèles variés.

Deuxième mandat

Obligatoire
Algorithmes et structures de données, partie 2

01 Contournement en largeur. Profondeur première traversée (début)
02 Traversée en profondeur (suite)
03 Traversée en profondeur (fin). 2 coupes
04 Trouver les chemins les plus courts (début)
05 Trouver les chemins les plus courts (suite)
06 Arbres couvrant minimum
07 Coupes minimales. Rechercher des sous-chaînes (début)
08 Recherche de sous-chaînes (suite)
09 Recherche de sous-chaînes (fin)
10 arbres de suffixes (début)
11 Arbres de suffixes (fin). Tableaux de suffixes (début)
12 tableaux de suffixes (fin)
13 sous-chaînes communes les plus longues. Recherche approximative de sous-chaînes.

Formation linguistique C++, partie 2

La deuxième partie du cours C++, qui couvre des sujets avancés et des capacités linguistiques.

01 Programmation multithread. Synchronisation des threads à l'aide de mutex et de variables de condition.
02 Variables atomiques. Modèle de mémoire C++. Exemples de structures de données sans verrouillage.
03 Techniques avancées de méta-programmation en C++. Métafonctions, SFINAE, concepts.
04 Programmation compétitive, interaction avec le réseau.
05 architecture llvm. Travailler avec l'arbre d'analyse C++. Développement d'outils d'analyse de code C++.

Au choix
Théorie et pratique de la concurrence

Le cours est consacré aux systèmes et tâches compétitifs au sens le plus large: du niveau de compétition entre cœurs de processeur pour l'écriture sur une cellule mémoire aux systèmes distribués qui souhaitent répliquer leur état sur plusieurs serveurs de manière cohérente et tolérante aux pannes.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md

ou
Allez la langue

01 Présentation. Programme de cours. Rapport sur le cours, critères d'évaluation. Philosophie de conception. si, changer, pour. Bonjour le monde. Arguments de ligne de commande. Nombre de mots. GIF animé. Récupération de l'URL. Récupération de l'URL simultanément. Serveur Web. Tour de go. Configuration de l'IDE local. goofmt. goimports. peluchage
02 Structures linguistiques de base. noms, déclarations, variables, affectations. déclarations de type. paquets et fichiers. portée. Valeur nulle. Allocation de mémoire. Pile contre tas. Types de données de base. Constantes. Types de données composites. Tableaux. Tranches. Plans. Structures. JSON. texte/modèle. chaîne et []octet. Travailler avec Unicode. Caractère de remplacement Unicode. Les fonctions. Fonctions avec un nombre variable d'arguments. Fonctions anonymes. Les erreurs.
03 Méthodes. Récepteur de valeur vs récepteur de pointeur. Intégration. Valeur de la méthode. Encapsulation. Interfaces. Interfaces sous forme de contrats. io. Écrivain, io. Reader et leurs implémentations. trier. Interface. erreur. http. Gestionnaire. Interfaces sous forme d'énumérations. Tapez l’assertion. Tapez le commutateur. Plus l’interface est grande, plus l’abstraction est faible. Traitement des erreurs. paniquer, différer, récupérer. erreurs. {Déballer, Est, Comme}. enfin. Erreurf. %w.
04 Goroutines et chaînes. serveur d'horloge. serveur d'écho. Taille du canal. Lecture bloquante et non bloquante. instruction de sélection. Axiomes de canal. temps. Après. temps. NouveauTicker. Modèle de pipeline. Annulation. Boucle parallèle. synchroniser. Groupe d'attente. Gestion des erreurs dans le code parallèle. groupe d'erreurs. Groupe. Robot d'exploration Web simultané. Parcours simultané de répertoires.
05 Tests avancés. Sous-tests. essai. B. (T).Logf. (T).Skipf. (T).FailNow. essai. Short(), test des drapeaux. Génération de moqueries. témoigner/{exiger, affirmer}. témoigner/suite. Appareil d'essai. Tests d'intégration. Détecteur de fuite Goroutine. TestMain. Couverture. Comparaison des benchmarks.
06 Tests avancés. Sous-tests. essai. B. (T).Logf. (T).Skipf. (T).FailNow. essai. Short(), test des drapeaux. Génération de moqueries. témoigner/{exiger, affirmer}. témoigner/suite. Appareil d'essai. Tests d'intégration. Détecteur de fuite Goroutine. TestMain. Couverture. Comparaison des benchmarks.
07 Contexte du package. Transmission de données à l'échelle de la requête. Intergiciel http. chi. Routeur. Demande l'annulation. Modèles de concurrence avancés. Cache asynchrone. Arrêt progressif du serveur. contexte. AvecTimeout. Mise en lots et annulation.
08 base de données/sql, sqlx, utilisation de bases de données, redis.
09 Réflexion. refléter. Tapez et réfléchissez. Valeur. balises de structure. net/rpc. encodage/gob. synchroniser. Carte. refléter. DeepEqual.
10 Implémentations du package io, Reader et Writer de la bibliothèque standard. Programmation de bas niveau. peu sûr. Package binaire. octets. Tampon. cgo, appel système.
11 Architecture du GC. Écrivez la barrière. Croissance de la pile. Pause du CG. GOGC. synchroniser. Piscine. Planificateur Goroutine. GOMACPROCS. Fils qui ont fui.
12 Allez à l'outillage. pprof. Profilage du processeur et de la mémoire. Compilation croisée. GOOS, GOARCH. CGO_ENABLED=0. Créez des balises. aller aux modules. bondoc. x/analyse. Génération de codes.
13 Bibliothèques utiles. Applications CLI avec cobra. Protobuf et GRPC. journalisation zap.

Troisième semestre

Obligatoire
Algorithmes en mémoire externe

Le cours présente aux étudiants les principes de base de la construction d'algorithmes permettant de travailler avec des données qui ne rentrent pas dans la RAM de l'ordinateur.

01 Algorithmes en mémoire externe.
02 Algorithmes ignorant le cache.
03 Algorithmes pour le traitement des données de flux.

Systèmes distribués

Cours spéciaux recommandés
Force des systèmes cryptographiques

01 Approches et principes de base de la cryptographie moderne. Le modèle de l'adversaire, formalisation de la notion de force, problème de l'évaluation de la force et problèmes associés, découpage en primitives et protocoles, étapes de la « vie » d'un système cryptographique.
02 Confidentialité. Définitions quotidiennes de la confidentialité, approches de formalisation (modèle théorique de l'information de l'ennemi, modèles KR, PR, LOR, ROR, IND, CPA, CCA), système de chiffrement symétrique, application d'informations de la théorie de la complexité pour déterminer la relation entre des modèles. Relations entre les modèles d'adversaires de base pour évaluer la force des systèmes de chiffrement.
03 Approches de construction de systèmes de cryptage. Construire à partir de zéro. Constructions basées sur des chiffrements par blocs, définition d'un chiffrement par blocs, principales caractéristiques, approches de construction et propriétés. Modèles PRP et PRF. Le paradoxe du problème de l'anniversaire. Lemme sur la relation entre résistance dans les modèles PRF et PRP.
04 Modes de cryptage. Modes de cryptage de base: ECB, CBC, CFB, OFB, CTR. Propriétés de performances de base. Durabilité du CTR en LOR-CPA, instabilité de la BCE en LOR-CPA. Instabilité des modes de base dans les modèles CCA.
05 Intégrité. Définition de la notion d'intégrité. Approches de formalisation (modèle UF-CMA, modèles basés sur la tâche de discrimination, modèle PRF). Codes d'authentification des messages et fonctions de génération d'inserts imités. Conceptions basées sur des chiffrements par blocs: CBC-MAC, XCBC, TMAC, OMAC. Modes vulnérables.
06 Fonctions de hachage. Définition, propriétés de base, approches de construction, formalisation et problèmes associés. Exemples d'utilisation des fonctions de hachage: hachage de mot de passe, extraction d'entropie. Construction de collisions et de préimages à partir d'ensembles de faible cardinalité.
07 circuits HMAC, KDF, PRF, DRNG. Diagramme HMAC, étapes de base pour obtenir l'indice de résistance. Diversification des clés et principe de séparation des clés, schémas KDF et PRF. Générateur pseudo-aléatoire, circuits DRNG.
08 Chargement des clés. Problème de chargement des clés. Les principales méthodes permettant de réduire la charge sur une clé sont les conversions de clés externes et internes. Schémas de saisie parallèle et série, propriétés de base. Arbre clé. Changement de clé interne et mode CTR-ACPKM.
09 Cryptage avec protection contre les imitations. Formulation du problème. Structures générales (EtA, AtE, A&E) et leurs propriétés. Exemples de modes vulnérables pour garantir la confidentialité et l’intégrité à l’aide d’une clé unique. Modes de cryptage AEAD: GCM, MGM.
10 Canal de communication sécurisé. Le concept de canal de communication sécurisé: types de canaux, propriétés de base (intégrité et confidentialité du flux de données). Exemples de protocoles vulnérables. Enregistrez le protocole TLS 1.3.

Quatrième semestre

Au choix
Théorie et pratique de la concurrence

Le cours est consacré aux systèmes et tâches compétitifs au sens le plus large: du niveau de compétition entre cœurs de processeur pour l'écriture sur une cellule mémoire aux systèmes distribués qui souhaitent répliquer leur état sur plusieurs serveurs de manière cohérente et tolérante aux pannes.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md

ou
Allez la langue
01 Présentation. Programme de cours. Rapport sur le cours, critères d'évaluation. Philosophie de conception. si, changer, pour. Bonjour le monde. Arguments de ligne de commande. Nombre de mots. GIF animé. Récupération de l'URL. Récupération de l'URL simultanément. Serveur Web. Tour de go. Configuration de l'IDE local. goofmt. goimports. peluchage
02 Structures linguistiques de base. noms, déclarations, variables, affectations. déclarations de type. paquets et fichiers. portée. Valeur nulle. Allocation de mémoire. Pile contre tas. Types de données de base. Constantes. Types de données composites. Tableaux. Tranches. Plans. Structures. JSON. texte/modèle. chaîne et []octet. Travailler avec Unicode. Caractère de remplacement Unicode. Les fonctions. Fonctions avec un nombre variable d'arguments. Fonctions anonymes. Les erreurs.
03 Méthodes. Récepteur de valeur vs récepteur de pointeur. Intégration. Valeur de la méthode. Encapsulation. Interfaces. Interfaces sous forme de contrats. io. Écrivain, io. Reader et leurs implémentations. trier. Interface. erreur. http. Gestionnaire. Interfaces sous forme d'énumérations. Tapez l’assertion. Tapez le commutateur. Plus l’interface est grande, plus l’abstraction est faible. Traitement des erreurs. paniquer, différer, récupérer. erreurs. {Déballer, Est, Comme}. enfin. Erreurf. %w.
04 Goroutines et chaînes. serveur d'horloge. serveur d'écho. Taille du canal. Lecture bloquante et non bloquante. instruction de sélection. Axiomes de canal. temps. Après. temps. NouveauTicker. Modèle de pipeline. Annulation. Boucle parallèle. synchroniser. Groupe d'attente. Gestion des erreurs dans le code parallèle. groupe d'erreurs. Groupe. Robot d'exploration Web simultané. Parcours simultané de répertoires.
05 Tests avancés. Sous-tests. essai. B. (T).Logf. (T).Skipf. (T).FailNow. essai. Short(), test des drapeaux. Génération de moqueries. témoigner/{exiger, affirmer}. témoigner/suite. Appareil d'essai. Tests d'intégration. Détecteur de fuite Goroutine. TestMain. Couverture. Comparaison des benchmarks.
06 Concurrence avec mémoire partagée. synchroniser. Mutex. synchroniser. RW Mutex. synchroniser. Cond. atomique synchroniser. Une fois. Détecteur de course. Cache asynchrone. Travailler avec la base de données. base de données/sql. sqlx.
07 Contexte du package. Transmission de données à l'échelle de la requête. Intergiciel http. chi. Routeur. Demande l'annulation. Modèles de concurrence avancés. Cache asynchrone. Arrêt progressif du serveur. contexte. AvecTimeout. Mise en lots et annulation.
08 base de données/sql, sqlx, utilisation de bases de données, redis.
09 Réflexion. refléter. Tapez et réfléchissez. Valeur. balises de structure. net/rpc. encodage/gob. synchroniser. Carte. refléter. DeepEqual.
10 Implémentations du package io, Reader et Writer de la bibliothèque standard. Programmation de bas niveau. peu sûr. Package binaire. octets. Tampon. cgo, appel système.
11 Architecture du GC. Écrivez la barrière. Croissance de la pile. Pause du CG. GOGC. synchroniser. Piscine. Planificateur Goroutine. GOMACPROCS. Fils qui ont fui.
12 Allez à l'outillage. pprof. Profilage du processeur et de la mémoire. Compilation croisée. GOOS, GOARCH. CGO_ENABLED=0. Créez des balises. aller aux modules. bondoc. x/analyse. Génération de codes.
13 Bibliothèques utiles. Applications CLI avec cobra. Protobuf et GRPC. journalisation zap.

ou
Base de données
01 Interfaces des bases de données modernes: relationnelles, clé-valeur, document, graphique. Algèbre relationnelle et langage SQL.
02 Travailler avec le disque dans un SGBD relationnel classique: pages, pool de pages, expulsion du pool.
03 Exécution de requêtes SQL: analyse d'expressions, planification, exécution. Interprétation et génération de code à l'aide de LLVM.
04 Index dans les SGBD relationnels: types d'index, méthodes de stockage, utilisation dans les requêtes.
05 Transactions: acronyme ACID, niveaux d'isolement, mise en œuvre des transactions via des verrous et MVCC.
06 Reprise après sinistre: journal, points de contrôle, algorithme ARIES.
07 Stockage des données à l'aide de la méthode Log-Structured Merge Tree.
08 SGBD basé sur des colonnes: avantages, fonctionnalités, algorithmes de compression de données.
09 SGBD distribués: sharding, transactions, exécution de requêtes.
10 SGBD situés dans la mémoire principale. Structures de données pour les index en mémoire.

ou
Réseaux informatiques
01 Introduction aux technologies de réseaux. L'histoire des réseaux, les protocoles réseau, l'organisation de l'interaction réseau dans un réseau peer-to-peer et la connexion des réseaux peer-to-peer entre eux.
02 Transports. Modèle de réseau OSI/ISO. TCP, établissement de connexion réseau, comparaison de TCP et UDP. Analyse Tcpdump – octets à la volée, retransmet les graphiques. Méthodes de contrôle du flux de données dans une session TCP. Différents types de sessions TCP et gestion de la bande passante des données transmises dans les réseaux par paquets.
03 Routage. Le concept de routage dans les réseaux. Routage statique et dynamique. Bases du routage dynamique. Protocole de routage dynamique - OSPF. Protocoles de routage à vecteur de distance. Présentation du protocole de routage BGP - types de messages, attributs BGP, choix de la route optimale dans BGP.
04 Comment fonctionne Internet: BGP et DNS. Routage Internet. Présentation du protocole DNS.
05 Réseaux dans les grands centres de données. Caractéristiques de l'architecture des réseaux de centres de données. Exigences pour les réseaux de centres de données. Architecture CLOS pour les réseaux de centres de données.
06 Retards dans les réseaux. Caractéristiques de la construction de grands réseaux fédérateurs. Raisons des retards dans la transmission des données sur les réseaux fédérateurs.
07 Mise à l'échelle et disponibilité des services Internet. Technologies d’équilibrage de charge et architecture de services.
08 MPLS et SR, Programmabilité réseau. Technologies MPLS et de routage de segments pour la construction de réseaux fédérateurs. Objectif de la technologie MPLS, protocoles utilisés pour l'échange d'étiquettes.
09 Principes de fonctionnement des périphériques réseau. Architecture du routeur, fonctionnalités de traitement du trafic réseau à l'intérieur des périphériques réseau.
10 nuages. Principes fondamentaux des réseaux définis par logiciel - Protocoles utilisés pour créer des réseaux définis par logiciel. Intégration de plateformes de virtualisation et d'infrastructure réseau.

ou
Protocoles cryptographiques
01 Idées de base de la cryptographie asymétrique. La principale différence entre la cryptographie asymétrique et la cryptographie symétrique. Idées principales: protocole de génération de clé partagée, chiffrement à clé publique, signature électronique (problèmes à résoudre, compréhension intuitive des propriétés de sécurité). Schémas cryptographiques spécifiques: protocole Diffie-Hellman, schémas de cryptage ElGamal et RSA, signatures ElGamal et RSA. Le problème fondamental des systèmes asymétriques est la confiance dans la clé publique.
02 Force des schémas de cryptographie asymétrique de base. Définition formelle de la résistance: modèles UF-CMA, IND-CPA, DLP, CDH, DDH. Relations entre eux. Force du système de cryptage ElGamal. L'instabilité du schéma de signature RSA sans utiliser de fonction de hachage.
03 En savoir plus sur la cryptographie asymétrique. Signature de Lampart, diagramme de Merkle. Attaque DSKS.
04 Fondements algébriques et théoriques des nombres de la cryptographie asymétrique. Groupes finis, groupes cycliques, ordre des éléments du groupe. Problème de logarithme discret (DLP). Groupes multiplicatifs de champs finis. Informations de base sur les courbes elliptiques.
05 Courbes elliptiques. Théorème de Hasse. Ajout de points sur une courbe elliptique. Groupe de points sur une courbe elliptique. Schéma de signature GOST R 34.10-2012.
06 Logarithme discret. Algorithmes de logarithme discret (méthode Rho de Pollard, méthode d'appariement, méthode Polig-Hellman, méthode de calcul d'indice).
07 Technologie PKI. Principes et concepts de base de l'infrastructure à clé publique (PKI). Certificat, CA, CRL, OCSP, espace de confiance.
08 Protocole TLS. Histoire du protocole TLS. Structure du protocole, principes de fonctionnement de base. Suites cryptographiques du protocole TLS basées sur des algorithmes cryptographiques russes.
09 Bases de la construction de protocoles AKE. Le concept du protocole AKE. Propriétés cibles. Approches de base de la construction.
10 Stockage sécurisé des clés. Le problème de l'utilisation sécurisée des clés privées. Supports clés, clés non amovibles. Le problème de la présence d'un adversaire dans le canal, protocoles de la famille PAKE.
11 Concepts de base de la technologie blockchain. La tâche d'une interaction décentralisée coordonnée. Concepts de base du concept de sécurité. Approches de sécurité.
12 Principes de base des technologies quantiques et leurs applications en cryptographie