LDD3 Informatique, Mathématiques

Maîtriser les outils mathématiques permettant de traiter un grand nombre de problèmes du domaine des probabilités.

• axiomes des probabilités
• variables aléatoires réelles, caractérisations de leurs lois par la fonction de répartition, définition des variables aléatoires discrètes et à densité
• lois de probabilités usuelles : Bernoulli, binomiale, binomiale négative géométrique, Poisson, uniforme, gaussienne, exponentielle, gamma, Cauchy…
• transformations de variables aléatoires par la méthode de la fonction muette
• simulation par inversion de la fonction de répartitition
• espérance, variance, moments
• couples et vecteurs aléatoires, indépendance et corrélation
• suites de variables aléatoires et convergences
• loi des grands nombres, théorème central limite
• vecteurs gaussiens

Acquérir les outils mathématiques d’analyse numérique matricielle notamment les différents algorithmes de décompositions de matrices, les méthodes de résolution de systèmes linéaires et de problèmes aux valeurs propres.

Différentes méthodes de résolution de systèmes linéaires seront étudiées : les méthodes directes par décomposition LU et QR, les méthodes itératives de type Jacobi, Gauss-Seidel, relaxation. Différentes méthodes de recherche de valeurs propres et de vecteurs propres seront également étudiées, notamment dans le cas particulier des matrices symétriques. La notion de conditionnement sera évoquée afin de comprendre le comportement des erreurs numériques. Toutes ces notions seront appliquées en particulier à la matrice obtenue par discrétisation de l’opérateur Laplacien en dimension un par la méthode des différences finies.

Manipuler les fonctions de plusieurs variables, comprendre la notion de différentielle, connaître et comprendre les théorèmes fondamentaux (inversion locale, fonctions implicites), acquérir les outils de base pour l’étude de problèmes d’optimisation.

• Fonctions d’une variable : dérivabilité, égalité des accroissements finis, courbes paramétrées.
• Espace vectoriel normé : norme et produit scalaire ; distance, ouverts et fermés ; convergence des suites, continuité des fonctions ; compacité, équivalence des normes dans R^n.
• Différentiabilité des fonctions de R^n dans R^p ; dérivées partielles, jacobiennes ; différentielles des fonctions composées ; théorèmes des accroissements finis, fonctions C^1 ;
• Théorème d’inversion locale ; Théorème des fonctions implicites ; Hypersurface de R^n ;
• Différentielles et dérivées partielles d’ordre supérieur ; fonctions C^k ; matrice hessienne ; formule de Taylor ;
• Extremums des fonctions de R^n dans R ; condition nécessaire et suffisante d’extremum ; cas des fonctions convexes ; extremums liés et multiplicateurs de Lagrange.

Maîtriser la notion d’intégrabilité ainsi que les propriétés de l’intégrale de Lebesgue. Savoir appliquer les grands théorèmes de l’intégrale de Lebesgue (convergence monotone et dominée, intégrale à paramètre, Fubini, changement de variable).

Rappels sur l’intégrale de Riemann et les limites de suites de fonctions. Intégrale de Lebesgue sur R, théorèmes de convergence monotone et de convergence dominée, exemples de fonctions intégrables, intégrales dépendant d'un paramètre. Intégrale de Lebesgue sur R^d (généralisation de la construction précédente), théorème de Fubini, changement de variable. Espaces L¹ et L². Présentation de la convolution et de la transformée de Fourier sur L¹.

Comprendre ce qu’est une EDO et savoir représenter les champs de vecteurs, portraits de phase et les solutions pour différentes données et paramètres. Comprendre et savoir appliquer les principaux résultats d’analyse concernant l’existence, l’unicité et la régularité des solutions. Maîtriser les outils permettant de résoudre exactement les edo linéaires et à variables séparées. Maîtriser les outils d’analyse numérique et de calcul scientifique pour résoudre numériquement une edo et étudier les propriétés de convergence de la solution approchée vers la solution exacte.

Pré-requis : Topologie de R^N, compacité, application contractante, intégration numérique.

Théorie des Equations différentielles ordinaires (EDO). EDO du premier ordre linéaire et à variables séparées. EDO d’ordre supérieur et systèmes d’EDO. Théorème de Cauchy-Lipschitz, Théorème des bouts, Continuité de la solution vis-à-vis des paramètres. Exercices sur des résolutions d’EDO, calcul de temps d’existence, propriétés des solutions. Schémas numériques pour les EDOs : étude des méthodes à un pas, notion de convergence (consistance, stabilité et convergence, ordre des schémas). Travaux dirigés sur ordinateurs avec programmation en python.

concepts fondamentaux de l'apprentissage automatique/statistique et application à des exemples simples.

Ce cours a pour but d'introduire les concepts de bases de l'apprentissage statistique en les illustrant sur des réseaux de neurones simples et en les appliquants à la reconnaissance de caractères, et ensuite en analysant les résultats obtenus. Dans un second temps, on s'intéressera à l'apprentissage par renforcement consistant à guider l'apprentissage d'un agent autonome en interaction avec un environnement à partir d'expérience. Le cours se abordera les points suivants

• La notion de gradient et d'optimisation de fonction de coût

• le perceptron multiclasse, et multicouche

• les ensembles pour valider l'apprentissage

• la notion d'agent en interaction avec un environnement

• les équations de Bellman permettan d'évaluer la politique de mouvement pour l'agent

• l'apprentissage Q-learning et SARSA

Responsable : Aurélien Decelle

introduction à l'informatique et python, introduction à la programmation impérative, Calculus 1-2, Algèbvre linéaire 1-2, Combi Proba

S6

L'UE s'organise en cours accompagnés de séances de (quelques) TD et de (nombreux) TP.

L’objectif du cours est de se familiariser avec le formalisme de la logique du premier ordre. La logique est utilisée pour modéliser des problèmes informatiques et comme outil de spécification de contraintes sur des objets informatiques comme des bases de données ou des programmes. Ce cours aborde les notions de démonstration, de validité, le lien entre les objets physiques (syntaxe) et le sens qu'on leur donne (sémantique). Il présente plusieurs techniques de démonstration automatique comme le calcul des séquents et la résolution. Il met en pratique un certain nombre d’outils mathématiques utilisés en informatique, comme les définitions récursives de fonctions, les preuves par récurrence structurelle ou les définitions par règle d'inférence.

Le programme du cours est le suivant :

• Langage logique (calul propositionnel et calcul des prédicats), modélisation à l'aide de la logique

• Systèmes de règles logiques pour construire des preuves

• Termes : signature, preuve par récurrence structurelle, définition récursive de fonctions

• Calcul des prédicats : syntaxe, variables libres et liées, sémantique, équivalence

• Modèle, modèle de Herbrand

• Exemples de théories

• Démonstration automatique, formes normales, résolution, séquents

Responsable : Christine Paulin

les bases du calcul propositionnel (tables de vérité des connecteurs logiques). Les bases du raisonnement mathématique (définitions, énoncé, preuves).

S5

UE est organisée de manière classique avec des séances de cours et exercices en classe entière suivies de séance de TD. Quelques activités d'apprentissage autonome en ligne sont proposées. L'évaluation repose sur un partiel et un examen final.

Savoir caractériser un langage par une syntaxe et une sémantique, connaître les techniques d’analyse syntaxique et savoir les mettre en œuvre manuellement ou à l’aide d’outils, représenter un programme à l’aide d’une syntaxe abstraite et l’interpréter.

Ce cours aborde les outils conceptuels permettant de définir un langage de programmation, et les outils algorithmiques permettant d’interpréter un programme fourni sous la forme d’un texte brut. Thèmes :

• Expressions régulières, automates finis, algorithmique et techniques de raisonnement associées

• Grammaires algébriques, automates à pile, algorithmique et techniques de raisonnement associées

• Techniques d’analyse lexicale : outils de type lex

• Techniques d’analyse syntaxique : récursive descendante, et ascendante avec outils de type yacc

• Syntaxe abstraite, environnements, interprétation

Le cours mêle raisonnement théorique et programmation. On utilisera le langage OCaml et les outils d’analyse associés.

algorithmique, programmation OCaml.

S5

l’UE s’organise en cours accompagnés de TD ou TP. L’évaluation se fait par des épreuves de contrôle continu (interrogations, TP notés) et deux épreuves écrites (partiel, examen terminal).

Connaissance de l'Internet des Objets (IoT) et des techniques d'optimisation associées.

Les problèmes issus du monde de l'internet des Objets (IoT) posent intrinsèquement des problèmes d'optimisation. Cette UE vise donc à non seulement aborder les problématiques Réseaux issues du monde de l'IoT mais également à aborder les modèles et techniques d'optimisation (programmation mathématique en variables mixtes (non linéaire, fractionnaire, reformulations, méthodes de décomposition) s'y référant.

Notions de base de l'algèbre linéaire, bases de la programmation, réseaux

S5

Cours, TD, TP

- Faire comprendre les problèmes qui se posent lors de la conception et utilisation d'un système réparti et donner des solutions à ces problèmes. - Aborder les notions de preuve d'algorithme réparti et d'analyse de complexité.

Partie algorithmique distribuée : Les algorithmes distribués sont à la base de systèmes et applications reparties, comme par exemple : l’Internet, l’Internet des objets, le Cloud, Bitcoin (et d’autres systèmes à la base de la technologie Blockchain), les systèmes de calcul parallèle, etc. Dans des tels systèmes les processus sont distants et ne partagent pas de mémoire commune. Malgré ce fait, les processus doivent collaborer à une tâche commune, comme par exemple établir un consensus, effectuer le routage des messages, diffuser et collecter des données, détecter la terminaison, synchroniser des horloges, etc. Le but de cette partie du cours est de faire comprendre les problèmes qui se posent lors de la conception de tels systèmes et de donner des solutions à ces problèmes.   Partie parallélisation: Cette partie a pour but de sensibiliser les étudiants aux différentes problématiques des systèmes distribués et des machines parallèles. Elle propose une premier rencontre avec de différentes architectures parallèle (multi-cœurs, multi-nœud, accélérateurs, unités vectorielles) et de langages de programmation parallèle (OpenMP, MPI, SIMD, CUDA/OpenCL/OpenACC) dans le but de pouvoir développer des codes et de concevoir des algorithmes efficaces qui exploitent adéquatement la puissance de calcul offerte par ces architectures modernes.

Notions de base en : réseaux, systèmes, algorithmique classique et algorithmique de graphes

S6

La partie initiale et principale du cours est consacrée à l’algorithmique répartie. Elle est suivie par la partie consacrée à la parallélisation, qui présente en particulier l’exemple pratique d'un environnement basé systèmes répartis.   L’évaluation se fait par des épreuves de contrôle continu (interrogations écrites, TD notés, devoirs) et un examen terminal écrit.

Comprendre la protection des systèmes contre les défaillances et les attaques

Ce cours introduit la notion de sûreté de fonctionnement et sécurité. En premier lieu, il aborde la dimension temporelle pour des systèmes et des réseaux temps réel ayant des contraintes dures, c’est-à-dire pour lesquels le non-respect des échéances peut avoir de graves conséquences (avionique, centrale nucléaire, véhicules autonomes, ...). Seront étudiés les notions d’ordonnancement et de garanties déterministes/probabilistes, calculables mathématiquement, dans le cadre de certification. En second lieu, le cours explique les notions de sécurité informatique avec des exemples sur les attaques et les protections pour se prémunir contre ces attaques. Des exemples de la sécurité en réseau seront étudiés. Organisation générale de l’UE :

Aucun

S6

Cours + TD

Attendus de l'UE Langue-Anglais4 : Niveau B2+/C1 dans les 5 compétences linguistiques.

ANGLAIS DE SPÉCIALITÉ. Cette UE s'inscrit dans la continuité de l'UE Langue-Anglais3 et le travail sur la langue de spécialité (scientifique et/ou à visée professionnelle) : on prolongera l'approche actionnelle dans les 5 compétences et on s'attachera à la préparation de l'étudiant aux différentes tâches liées à son activité scientifique telles que la rédaction d'un compte rendu d'expérience, le commentaire d'un graphique, la desciption d'un processus mais aussi à son insertion dans le monde professionnel : rédaction d'un CV ou d'une lettre de motivation en vue d'un stage... On proposera une initiation au débat ainsi qu'un entraînement à la certification CLES 2. Le travail se fera par groupes de niveau.

• THEORIE DES GROUPES com.univ.collaboratif.utils.LectureFichiergw?CODE_FICHIER=1433332714187&ID_FICHE=34846

• Définitions (sous-groupe, sous-groupe distingué, quotient, factorisation d'un morphisme...) Ordre d'un groupe fini. Théorème de Lagrange. Exemples des groupes cycliques.
• Opération d'un groupe sur un ensemble : orbites, stabilisateurs. Exemples d'opérations usuelles. Classes de conjugaison dans un groupe, classes de conjugaison de sous-groupes... Applications : p-groupes, théorèmes de Sylow,...
• Parties génératrices de groupes .
• Décomposition d'un groupe : produits directs et semi-directs.
• Groupes classiques (linéaire, orthogonal...)
• Exemples de groupes simples.  

• THEORIE DES ANNEAUX

• Définitions (anneaux, idéaux, quotients, factorisation d' un morphisme)
• Anneaux principaux, anneaux euclidiens.
• k[X]. Polynômes irréductibles  

• THEORIE DES CORPS

• Corps de fractions d'un anneau intègre. Q. K(X).
• Caractéristique d'un corps. Sous-corps premier. Homomorphisme de Frobénius en caractéristique p.
• Corps finis.

• THEORIE DE LA MESURE  

  Tribus, mesures, théorème de Dynkin. Intégration abstraite : intégration des fonctions mesurables positives, théorème de convergence monotone et de Fatou ; fonctions intégrables, convergence dominée, de dérivation sous le signe somme. Construction de mesures : théorème d'extension de Carathéodory. Cas de la mesure de Lebesgue sur R^d. Formule de changement de variables. Intégrale de Stieljes, mesures de Radon, théorème de représentation de Riesz. Mesures produits, théorèmes de Fubini-Tonelli et Fubini-Lebesgue. Intégration par parties. Espaces Lp, inégalité de Jensen, Hölder et Minkowski, théorèmes de densité (pas de preuves ici, la théorie générale n'est pas faite dans ce cours). Dérivée de Radon Nykodyn.

• INTRODUCTION AUX PROBABILITES

  Introduction historique. Langage probabiliste et modélisation. Variables aléatoires, espérance mathématiques. Loi d'une variable aléatoire et lois classiques. Moments, fonctions caractéristiques, théorème d'injectivité. Fonctions génératrices. Indépendance: définitions et caractérisations. Théorème des coalitions. Tribu asymptotique, loi du tout ou rien, lemmes de Borel-Cantelli. Loi fortes des grands nombres. Applications. Convergence en loi : définitions et caractérisations, théorème de Levy. Comparaison des différents modes de convergences. Théorème central limite. Applications.

• Notions élémentaires de toologie (espaces de Banach)
• Théorème du point fixe; Théorème de Cauchy-Lipschitz
• Différentiabilité, inégalité de la moyenne et formules de Taylor
• Théorèmes d'inversion locale et théorèmes des fonctions implicites, submersion, immersion, théorème du rang constant
• Sous-variétés de Rn
• Optimisation

Les objectifs du cours sont d'acquérir les concepts des langages de programmation (impératifs, fonctionnels, à objets) sans se focaliser en cours sur un langage de programmation. Pour cela des exemples seront donnés dans plusieurs langages (Java, C++, Caml). Par ailleurs les élèves devront mettre en pratique leurs connaissances en programmant dans un ou deux langages.

• Architecture des machines:

  représentation des données CPU, registres, bus, cycles d'exécution, mémoire, cache niveaux d'abstraction: circuit, langage machine, langage d'assemblage,...

• Concepts fondamentaux de la programmation:

  déclarations, environnement, mémoire expressions, l'affectation, les différents modes d'évaluation structures de contrôle types de base, constructions simples (produits, sommes, tableaux) fonctions et procédures, variables locales, passage de paramètres récursion exceptions étiquetage pointeurs types de données récursifs définitions par motifs et filtrage polymorphisme inférence de type types abstraits objets, attributs, héritage modularité, interfaces, compilation séparée threads

• Eléments de preuve de programme

  terminaison assertions, pre et post-conditions, invariants preuves de fonctions récursives

• Compilation

  arbres abstraits, calculs d'attributs sémantiques analyse statique appels de procédures, passages de paramètres machines abstraites, exemple de la machine virtuelle Java génération de code et optimisations gestion mémoire

Le cours est structuré comme suit : Calculabilié :

• Machines de Turing
• Fonctions récursives

Complexité :

• Introduction aux classes de complexité
• La classe NP
• La classe PSPACE
• La classe PTIME
• La classe NLOGSPACE
• Inclusions strictes entre classes

Ce cours a pour objectif de donner les bases de l'algorithmique. Il recouvre en particulier le programme d'algorithmique de l'option informatique de l'agrégation de mathématiques. Il ne nécessite aucune connaissance préalable. Il est indépendant de tout langage de programmation mais l'étudiant devra réaliser des mini-projets dans un langage de son choix, par exemple, Java, Caml, C++, ... Les points suivants seront traités, pas forcément dans cet ordre.

• Preuves et complexité des algorithmes

  Preuves de Hoare : assertions, pré et post conditions, invariants de boucles, terminaison des boucles Complexité en temps et en espace. Coût au pire et coût en moyenne. coût amorti. Coût asymptotique. Récurrences de partition.

• Structures de données

  Types de données abstraits : listes, files, piles, dictionnaires, files de priorités, ... Implémentations des piles et des files par des tableaux ou des listes chaînées

• Algorithmes de tri

  Tris par comparaison : insertion, tri fusion, tri rapide, tri par tas, ... complexités au pire et en moyenne, borne inférieure des tris par comparaisons

• Algorithmes de recherche (implémentation des dictionnaires)

  recherche dichotomique Arbres binaires de recherche, arbres équilibrés Tables de hachage

• Implémentation des files de priorité

  Tas, tas binomiaux, tas de Fibonacci

• Recherche de motifs dans un texte

  Algorithme naïf Algorithme de Knuth Morris et Pratt Algorithme de Boyer et Moore Utilisation des automates finis : algorithme de Simon, Algorithme de Aho et Corasick

• Partitions : union et recherche
• Paradigmes

  Diviser pour régner Algorithmes gloutons Programmation dynamique

• Algorithmes pour les graphes

  Parcours de graphes, parcours en largeur, parcours en profondeur, applications au tri topologique et aux composantes fortement connexes Arbres couvrants de poids minimum (Kruskal, Prim) Plus courts chemins (Dijkstra, Floyd-Warshall) Graphes pondérés, algorithmes de flots (Ford-Fulkerson)

Préparation au Cambridge Advance.

Ce module est composé de trois mini-cours de chacun 3 semaines, où sont abordées les notions de base dans les domaines suivants:

• Introduction aux statistiques
• Topologie
• Algèbre Linéaire Numérique

• Recherche de chaînes de caractères
• Polynômes et transformée de Fourier rapide
• Compression de données
• Algorithmes d'approximation
• Algorithmes et probabilités
• Programmation linéaire

Stage de recherche de 6 à 8 semaines dans une instutition de recherche hors région Île-de-France

• RESUME :

  https://youtu.be/Yw2ST385T9w

  Les progrès en analyse mathématique des EDP et la formidable puissance des ordinateurs font de la modélisation numérique un outil très puissant tant en Sciences (Physique théorique, Chimie, Mécanique, Biologie, ...) que dans l'Industrie. L'objet de ce cours est à la fois de donner les bases de la théorie de l'approximation des équations aux dérivées partielles et de former à l'utilisation pratique de ces méthodes.  

• PROGRAMME :

• Équations hyperboliques en une dimension. Méthode des caractéristiques, Schémas classiques aux différences finies : def, consistance, stabilité, convergence.
• Méthode des différences finies pour les équations de Laplace, des ondes et de la chaleur.
• Méthodes des éléments finis pour les équations et les systèmes elliptiques. Application à l'équation de Laplace et au système de l'élasticité.
• Méthode des volumes finis pour les systèmes hyperboliques de lois de conservation. Application aux équations d'Euler des fluides parfaits.

I. Fonctions holomorphes: définitions; holomorphie des séries entières; les conditions de Cauchy-Riemann. Fonctions analytiques: analyticité des séries entières; zéros des fonctions analytiques.   II. La théorie de Cauchy: intégration le long d’un chemin dans le plan complexe; homotopie de chemins et formule de Cauchy; développement en séries entières et en séries de Laurent.   III. Constructions de fonctions analytiques: primitives; théorème de Morera; limites, sommes et intégrales; produits infinis.   IV. Fonctions méromorphes: définitions; fonctions méromorphes sur C; fonctions trigonométriques et fonctions elliptiques; la fonction Gamma.   V. Le théorème des résidus et ses applications: indice d’un lacet par rapport à un point; ouverts élémentaires; le théorème des résidus; applications aux zéros et aux pôles des fonctions méromorphes; calcul d’intégrales.   VI. Représentation conforme: topologie sur l’espace des fonctions analytiques; théorème de Montel; théorème de Riemann.   VII. Transformation de Fourier et fonctions holomorphes: transformation de Fourier et formule des résidus; la formule de Poisson; théorèmes de Paley-Wiener et espaces de Hardy.

• Langages reconnaissables
• Grammaires
• Langages algébriques
• Automates à pile
• Analyse syntaxique
• Reconnaissance par monoïde
• Logique monadique du second ordre

• Calcul propositionnel
• Calcul des prédicats
• Théorèmes d'incomplètude (Gödel)
• Théorie décidables