LDD3 Informatique, Mathématiques cursus ENS

THEORIE DES GROUPES
Echantillonage irrégulier par homographie : stage de L3 promo 2015. (J.-T. De Laroche de Saint-André)

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.

Notions élémentaires de topologie (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

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.

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)

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

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

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

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 systèmes complexes en SHS
Théorie géométrique de la mesure
Approximation des EDP

Préparation au IELTS.

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

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.

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

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