LogoULg

Premiers bacheliers en sciences mathématiques : Algèbre (compléments)

18/09 1h30 Quelques rappels de "notations" et de théorie naive des ensembles, produit cartésien d'ensembles, relation sur un ensemble + exemples, relation d'équivalence + exemples (billes de couleurs, sin x = sin y, entiers multiplicativement dépendants), classe d'équivalence + exemples .
25/09 1h30 Retour sur quelques exemples de relation d'équivalence, infinité de classes pour les entiers mult. indép., infinité de l'ensemble des nombres premiers, propriété fondamentale des classes d'équivalence (avec preuve) quotient, projection canonique, division euclidienne, congruence modulo m, x et y sont congrus mod m ssi même reste après division par m.
02/10 1h30 Congruence mod m est une relation d'équivalence, reste unique mod m, bijection avec {0,...,m-1}, structure de groupe, exemples, ensemble des parties de X muni de la différence symétrique, Z_m est un groupe, structures d'anneau, de corps, de champ, Z_m est un anneau commutatif, Z_4 est un anneau mais pas un champ, Z_5 est un champ.
09/10 1h30 Eléments inversibles dans un anneau, pgcd, algorithme d'Euclide, thm. de Bezout, exemples numériques, entiers premiers entre eux, caractérisation des éléments inversibles dans Z_m, Z_m champ ssi m premier.
16/10 1h30 Introduction aux espaces vectoriels sur un champ, définition, exemples, premières propriétés, dépendance/indépendance linére (premières propriétés).
23/10 1h30 Théorème de Steinitz, partie libre, génératrice, base, espace de dim. finie, toute partie libre/gén. incluse/contient une base, tout espace contient une base, deux bases ont le même nombre d'éléments.
30/10 1h30 partie libre/génératrice et base, propriété fondamentale des bases, passage aux composantes dans une base, isomorphisme entre E et K^n, exemples, changement de bases, formule de changement de bases, cas de 3 base, passage de "U à V" et de "V à U", sous-espace vectoriel, quelques exemples, dimension d'un s.e.v., si dim F=dim E, alors E=F.
6/11 1h30 Union de 2 sev, somme de 2 sev, partie génératrice de F+G, intersection de sev, enveloppe linéaire d'un sous-ensemble, enveloppe linéaire d'un ensemble fini, dim(F+G), somme directe de 2 sev, "décomposition unique ssi somme directe", supplémentaire.
13/11 1h30 Supplémentaire (existence et "non-unicité"), somme de p sous-espaces vectoriels, somme directe de p s.e.v., parallèle avec la définition quand p=2, intersection de plus de 2 s.e.v., caractérisiation (sous deux formes) de la somme directe de p s.e.v. (décomposition unique de tout élément et somme de F_1 avec F_2+...+F_p).
20/11 1h30 Applications linéaires, définitions, premières propriétés, T0=0, transformation linéaire, endomorphisme, L(E;F), L(E), forme ou fonctionnelle linéaire, dual de E, exemples d'applications linéaires, Ax, dérivation, intégration de fonctions continues sur [a,b], exemples "numériques", exemples d'applications qui ne sont pas linéaires, L(E;F) est un espace vectoriel (opérations), produit/composition d'applications, id, 0, une application linéaire est complètement déterminée par les images des éléments d'une base, notion d'isomorphisme, image d'une base par un isomorphisme.
27/11 1h30 Espaces de même dimension isomorphes, T(G), T^{-1}(H), image et noyau d'une application, T injectif SSI Ker T={0}, théorème de la dimension, T:E->F et dim E=dim F alors si T est injectif/surjectif, il est surjectif/injectif, rang d'une application, rg T <= inf(dim E,dim F), T injectif/surjectif SSI rg T=dim E/dim F.
04/12 Cours suspendu (St Nicolas)
11/12 1h30 Représentation matricielle des applications linéaires, exemples "numériques", représentaion de S+T, l T, ST, L(E;F) isomorphe a K^p_n d'ou dimension correspondante, image, noyau, rang et représentation, changement de bases et représentation.
18/12 1h30 Représentation d'endomorphisme, déterminant d'un endomorphisme, exemple "numérique", projection sur F parallèlement à G, projecteur, propriété sur Im P+ Ker P, système de projecteurs.
12/02 1h15 Lemme de D'Alembert et Gauss, polynômes à coefficients dans un champ (introduction).
19/02 1h00 Polynômes à coefficients dans un champ, premières propriétés, structure d'anneau, P.Q=0, division euclidienne, idéal d'un anneau, idéal engendré.
26/02 1h15 Idéaux principaux, anneaux principaux, K[X] est principal, Z est principal (exercice), idéaux et divisibilité, exemples, éléments associés, éléments inversibles dans K[X] ou Z, idéaux et pgcd.
04/03 1h15 Elements premiers entre eux dans un anneau (principal), éléments premiers, cas de Z et K[X], polynômes irréductibles, décomposition en éléments premiers (sans preuve), suite croissante d'idéaux, endomorphismes diagonalisables, premières définitions, valeur propre, vecteur propre, sous-espace propre, polynome caractéristique d'un endomorphisme, vecteurs propres associés à des valeurs propres distinctes, espaces propres en somme directe.
11/03 1h15 Endomorphisme diagonalisable ssi mult. alg. = mult. géom., cas des valeurs propres simples, polynômes d'endomorphismes, det(P(T)) (sans preuve), spectre de P(T) et propriétés, thm. de Cayley-Hamilton.
17/03 2h30 Idéal annulateur, polynôme minimum, polynômes minimum et caractéristique ont les mêmes zéros, thm. stabilisation des images et des noyaux (sans preuve), définition des sous-espaces caractéristiques, notion de sous-espaces stables, importance d'avoir des sous-espaces stables en somme directe dont la somme est E, E_lambda et F_lambda sont stables, E_lambda=F_lambda ssi m=1, projecteurs spectraux (définition et propriétés), E est somme directe des F_lambda et dim F_lambda=mult. algébrique correspondante, T est diagonalisable ssi son polynôme minimum n'a que des zéros simples, endomorphisme nilpotent (définition), lien avec notre probleme : T_j restreint à F_lambda_j est nilpotent d'indice de nilpotence m_j, Si N est nilpotent, son indice est inférieur ou égale à dim. E, N n'est pas inversible, spectre réduit à 0, N nilpotent et non nul n'est pas diagonalisable, chaînes engendrées par un endomorphisme nilpotent, définitions, longueur de chaînes, les éléments d'une chaîne sont lin. indépendants.
18/03 1h15 Base répartie en chaînes pour un endomorphisme nilpotent (sans preuve), forme du tableau, formule pour nombre d'éléments d'une colonne, stabilité pour T de l'enveloppe des éléments d'une chaîne engendrée par T_j, réduction à la forme de Jordan, exemple.
29h15

Premiers bacheliers en sciences physiques : Géométrie

18/09 1h00 Rappels sur R (structure de champ), notion d'espace vectoriel, exemples : R^2, R^n, ensemble des fonctions continues.
25/09 1h00 Exemples : ensemble des solutions d'un système homogène d'équations linéaires, quelques conséquences élémentaires des axiomes d'espace vectoriel, notion de dépendance/d'indépendance linéaire et premières propriétés.
02/10 1h00 "y comb. lin. de x_1,...,x_p SSI x_1,...,x_p,y lin. dép.", enoncé du théorème de Steinitz, exemple, dans R^n on ne peut trouver plus de n vecteurs linéairement indépendants, vecteurs unitaires, partie libre, liée, partie génératrice, exemples "numériques", espace de dimension finie, base, toute partie libre (génératrice) est incluse dans (contient) une base (sans preuve, exemples), 2 bases ont le même nombre d'éléments, dimension.
09/10 1h00 Nombre d'éléments d'une partie libre, d'une partie génératrice, propriété fondamentale des bases (décomposition unique), passage aux composantes (bijection qui "respecte" les opérations), changement de bases : position du problème, exemple "numérique", règle générale, matrice de changement de bases, passage de U à V puis de V à W.
16/10 1h00 Sous-espace vectoriel, définition, exemples, enveloppe linéaire (définition + vérifier que c'est un s.e.v.), dimension d'un s.e.v., si dim F=dim E, alors F=E, équations paramétriques d'un s.e.v.
23/10 1h00 Mini-introduction aux systèmes linéaires et à la compatibilité (rang, sous-matrices bordées).
25/10 2h00 Equations cartésiennes d'un sous-espace vectoriel, "élimination" des paramètres, exemples de plan et droite vectoriels en dimension 3, cas de la dimension 2, cas de la dimension 3, faisceau de plans vectoriels, intersection de 3 plans vectoriels.
30/10 1h00 Espace affin construit sur un espace vectoriel, translation, définition, exemple, premières propriétés, relation de Chasles, différence de deux points, vecteurs liés, vecteurs équipollents, parallélogramme, règle du parallélogramme, combinaison affine de points.
6/11 1h00 Combinaisons affines de points, propriétés, isobarycentre, centre de gravité, associativité du barycentre, combinaisons avec somme des coefficients nulle, variété affine, sous-espace vectoriel directeur, "P+F=P'+F", si P+F=P+F' alors F=F'.
13/11 1h00 sous-vectoriel directeur associé à une variété affine, droite, segment, appartenance d'un point à une droite, "AB=PQ", combinaisons affines de points d'une variété affine, intersection de variétés affines.
15/11 2h00 Parallélisme de varitétés affines, propriétés, positions relatives de deux droites dans un espace de dimension 2 (en particulier, deux droites non parallèles sont sécantes), positions relatives de deux droites, deux plans, une droite et un plan en dimension 3, notion de repère et coordonnées de points d'un espace affin, points affinement indépendants, simplexe, propriété fondamentale des coordonnées/composantes d'une combinaison affine de points, équations paramétriques et cartésiennes d'une variété affine, exploitation des résultats sur les équations de s.e.v., équations cartésiennes du sous-vectoriel directeur d'une variété.
20/11 1h00 Equation (paramétrique, cartésienne) de droites en dimension 2, sous-vectoriel directeur, droites parallèles, faisceau de droites, droites en dimension 3, équation, sous-vectoriel directeur, positions relatives de deux droites "par calcul de rangs".
27/11 1h00 Retour sur les équations de droites en dimension 3, notations, exemples numériques, comment trouver un vecteur directeur, équation de plan, faisceau de plan, équation d'un plan contenant une droite donnée et un point donné (ou parallèle à une direction donnée) par la "technique du faisceau", droite s'appuyant sur deux droites gauches et passant par un point.
04/12 Cours suspendu (St Nicolas)
7/12 1h30 droite s'appuyant sur deux droites gauches et parallèle à une direction (sans preuve), long exercice "numérique" récapitulatif (équations de droites, faisceau, positions relatives, droite s'appuyant sur deux droites gauches, etc...), espace vectoriel euclidien, produit scalaire, norme, angle non orienté, vecteurs orthogonaux, premières propriétés (composantes, indépendance).
11/12 1h00 Procédé d'orthogonalisation de Gram-Schmidt (idée, sans preuve), base orthogonale, base orthonormée, produit scalaire et base orthonormée, changement de bases avec base orthonormée, matrices orthogonales, orientation, espace orienté, base orthonormée positive.
13/12 1h00 Angles orientés en dimension 2, cas de la dimension 3, produit mixte (définition et propriétés), produit vectoriel (définition, propriétés), formules du double produit vectoriel.
18/12 1h00 Equation vectorielle "a lambda x=b", complément orthogonal (notion et résultats sans preuve), projection orthogonale, projection sur une droite vectorielle, espace affin euclidien, repère orthonormé, coordonnées polaires, cylindriques, sphériques, normale à un hyperplan, angle de deux droites.
13/02 1h30 Angle de deux droites, de deux (hyper)plans, d'une droite et d'un (hyper)plan, distance de deux points, pythagore, variétés affines orthogonale, projection orthogonale d'un point sur un hyperplan, sur une droite, sur une variété affine, distance d'un point à un hyperplan, "formule", distance d'un point à une droite en dimension 3.
20/02 Séance de répétition (P. Mathonet)
27/02 1h30 Distance entre deux droites gauches, hyperplan médiateur d'un segment, formules de la trigonométrie sphérique, lemme des angles à côtés perpendiculaires (sans preuve).
05/03 1h30 Application affine, affinité, isométrie, point fixe, translation, homothétie, thm. de Thalès (sans preuve), thm. de représentation dans un repère (sans preuve, illustration), projections parallèles, symétries, rotations (cas de la dimension 2 en détails).
12/03 1h30 Courbes, premières définitions, arc régulier, paramétrage, exemples, paramétrages équivalents, orientation, tangente, longueur d'arc, abscisse curviligne, paramétrage naturel, obtention d'un paramétrage naturel (sans preuve).
19/03 Séance de répétition
7/042h30 Dérivation de fonctions vectorielles (produit scalaire, vectoriel, mixte), dérivation d'une fonction de norme constante, courbure, normale, définition et exemples, plan/cercle osculateur, approximation au premier/second ordre, binormale, formules de Frenet, torsion, courbe plane ssi torsion nulle, formules de courbure et normale pour paramétrage quelconque, courbes planes, courbure et normale signées, interprétation de la courbure signée comme vitesse angulaire.
9/042h00 Coniques, réduction à la forme "canonique", interprétation des vecteurs propres de la matrice associée, introduction aux surfaces, portion réulière de surface, plan tangent, normale, orientation, surfaces coniques, cylindriques, de révolution, réglées, quadriques.
31h00

Premiers bacheliers en sciences mathématiques ou physiques : Algèbre

19/09 2h00 Structure de champ, nombres réels, nombres rationnels, racine de 2 n'est pas rationnel (démo. par l'absurde), définition des complexes comme couples de réels avec une addition et une multiplication particulières, structure de champ de C, R est identifié à une partie de C, imaginaires purs, forme "z=a+ib", nombres associés à un complexe (partie réelle, imaginaire, module, conjugué) et leurs propriétés.
20/09 1h30 Exponentielle de z, forme trigonométrique (module et argument), exemples (avec rappels sur les fonctions arcsin et arccos), produit de complexes sous forme trigonométrique, formule de De Moivre, interprétation géométrique de la somme et du produit de complexes.
26/09 2h00 Retour sur le produit de complexes, homothétie de centre C et de rapport r, racines carrées d'un complexe (sous 2 formes), équation du second degré, somme et produit des racines, binôme de Newton (énoncé), rappels sur symbole sommatoire, symbole produit et coefficients binomiaux, formule du triangle de Pascal.
03/10 2h00 Binôme de Newton (2 démonstrations), puissances divisées, théorème multinomial, racines n-ièmes d'un complexe, racines de l'unité, somme des racines, racines primitives de l'unité, matrices : premières définitions, somme, produit par scalaire, produit.
10/10 1h00 Matrices (suite) : matrices qui commutent ou non, matrices anticommutatives, binome de Newton, transposée, matrices (anti-)symétriques, opérations spécifiques aux matrices complexes, adjointe.
17/10 2h00 Matrices (fin) : matrices hermitiennes et anti-hermitiennes, sous-matrices, sous-matrices diagonales, matrices composées, opérations sur matrices composées, vecteurs de C^n, vecteurs unitaires, produit scalaire "canonique" et propriétés, norme, inégalité de Cauchy-Schwarz, inégalité de Minkowski (sans preuve), applications du calcul matriciel "dénombrement dans un réseau" et "évolution d'un système au cours du temps".
24/10 2h00 Permutations, produits, structure de groupe, permutations disjointes commutent, cycles, puissance/inverse d'un cycle, toute permutation est un produit de cycles disjoints (sans preuve), transpositions, tout cycle/toute permutation est un produit de transpositions, signature d'une permutation, signature d'un produit et corollaires (signature d'un cycle, d'une permutation), les nombres de permutations paires et impaires sont égaux.
31/10 2h00 Déterminant d'une matrice carrée, exemples en dimension 2 et 3, règle de Sarrus, privilégier lignes ou colonnes, déterminant transposée, adjointe, conjugué, propriétés fondamentales du dét., on peut ajouter à une colonne une combinaison d'autres colonnes, si D est une application multilinéaire et alternée..., dét. d'une matrice triangulaire, diagonale, mineur d'ordre p, mineur, cofacteur, lemme pour calculer un cofacteur.
7/11 2h00 Loi des mineurs (les 2 lois et forme matricielle), déterminant d'un produit de deux matrices n*n, det A=0 ssi lignes/colonnes lin. indépendantes, conditions sur mineurs d'ordre p pour que p vecteurs soient lin. dépendants/indépendants (sans preuve), rang d'une matrice, définitions, premières propriétés, méthode des matrices bordées.
14/11 2h00 Inversion de matrices, inverse à gauche, à droite, bilatère, premières propriétés, formules de Frobenius-Schur, corollaire (sans preuve), indépendance linéaire après multiplication par une matrice inversible, idem pour le rang d'une matrice, systèmes d'équations linéaires, premières définitions, cas où on ajoute des équations combinaisons linéaires des premières, Ax=b avec A inversible (système de Cramer), conditions nécessiare et suffisante pour unicité de la solution du système homogène Ax=0, structure de variété affine pour les solutions d'un système.
21/11 2h00 Compatibilité d'un système linéaire, considérer un nombre d'équations égal au rang, résolution et structure des solutions, exemples "numériques", système et formule de Cramer, exemples : applications aux lieux géométriques, étude de la compatibilité d'un système.
28/11 2h00 Polynomes à coefficients complexes, dérivabilité, fonction C_infini, D_z, opérateur de Cauchy-Riemann, degré d'un polynome, formule de Taylor, zéro d'un polynome, multiplicité, définition et caractérisation.
05/12 2h00 Théorème fondamental de l'algèbre, énoncé du thm. de d'Alembert, corollaires du thm. fondamental, localisation des zéros (règle de Descartes), un aperçu des formules de Viète, division de polynômes (existence, unicité, calcul pratique), D divise P, divisibilité et zéros, pgcd de polynômes, pgcd en fonction des zéros communs.
12/12 2h00 pgcd, si A divise BC et premier avec B, algorithme d'Euclide, thm. de Bezout, fractions rationnelles R=A/B, choisir A et B premiers entre eux, unicité de A et de B (à une constante multiplicative près), comportement au voisinage d'un pôle, pôles de D_z R.
19/12 2h00 Fractions rationnelles propres, décomposition d'une fraction rationnelle propres en somme de fractions propres, détermination des nuérateurs par identification des coefficients, décomposition en fractions simples sur C, conjugué d'un polynome, polynomes réels et zéros, factorisation d'un polynome réel en produit de polynomes irréductibles, fraction rationnelle réelle et décomposition, décomposition en fractions simples sur R (sans preuve, énoncé uniquement).
11/02 2h30 Diagonalisation, valeur propre, vecteur propre, lien entre matrice S qui diagonalise A et vecteurs propres de A, polynôme caractéristique et valeurs propres, multiplicité algébrique d'une valeur propre, propriétés du polynôme caractéristique, coefficients du pol. car. (deux résultats, en termes de déterminants de sous-matrices diagonales et en termes de valeurs propres), trace (définition et propriétés), sous-espaces propres, multiplicité géométrique inférieure ou égale à la mult. algébrique.
18/02 Cours reporté
25/02 Exemples numériques et rappels théoriques sur la diagonalisation (E. Charlier)
3/03 2h00 Condition nécessaire/suffisante pour qu'une matrice soit diagonalisable, vecteurs propres associés à des valeurs propres distinctes, expression des éléments de A^k en termes des valeurs propres de A (si A est diagonalisable), disques de Gerschgorin, rappels sur le produit scalaire de C^n, CNS pour que <Ax,y>=<x,By>, cas des matrices hermitiennes et unitaires.
10/03 2h30 Si A n'a que des valeurs propres simples,... matrices diagonalisables par une matrice unitaire, matrice normale, vecteur/valeur propres d'une matrice normale, vecteurs propres orthogonaux, toute matrice normale est diagonalisable par une unitaire, matrice normale hermitienne/unitaire SSI valeurs propres réelles/de module 1, diagonalisation simultanée de matrices normales (lemme sans preuve).
35h30

Deuxièmes bacheliers en sciences mathématiques : Théorie des graphes

12/02 1h00 Graphes orientés, non oriéntés, applications diverses de la théorie des graphes.
13/02 1h30 Applications diverses de la théorie des graphes (suite), chemin, piste, chemin simple, circuit, connexité, composante connexe, distance (cas non orienté, connexe), chemins dans le cas orienté, forte connexité, simple connexité.
14/02 3h00 Recherche du plus court chemin, algorithme de Dijkstra, graphes eulériens, test de connexité, clôture réflexive et transitive de SUCC, graphe acyclique des composantes connexes, sous-graphe (propre, induit, couvrant), point/ensemble d'articulation, notion de k-connexité, arête d'articulation, algorithme de Fleury, ensemble de coupure, théorème de Menger (sans preuve + corollaire, avec preuve).
15/02 1h30 Graphes sans circuit et tri topologique, arbres, parcours d'arbres, homomorphismes/isomorphismes de graphes
26/02 1h00 Arbre lexicographique, arbre régulier, chemin/circuit/graphe hamiltonien, condition nécessaire pour qu'un graphe soit hamiltonien, énoncé des thm. de Dirac, Ore, Chvatal, Chvatal-Erdos.
27/02 1h30 Démonstration des thm. Dirac et Ore (I), fermeture d'un graphe, Ore (II), démo. thm. de Chvatal.
28/02 1h30 Introduction à la théorie algébrique des graphes, matrice d'adjacence, premières propriétés, spectre d'un graphe biparti, nombre de chemins de longueur n, matrices primitives et irréductibles, thm. de Perron-Frobenius (énoncé).
29/02 1h30 Tout graphe connexe à spectre symétrique est biparti, thm. de Perron (énoncé), période d'une matrice irréductible, lemmes menant à la structure générale des longueurs de chemins dans une matrice irréductible (dont lemme sur ensemble d'entiers naturels stable par addition).
04/03 1h00 Structure des longueurs de chemins dans une matrice irréductible (fin), matrice irréductible acyclique ssi primitive, exemples, conséquence du thm. de Perron sur la forme de A^k (sans preuve), application à l'estimation du nombre de chemin de longueur n dans un graphe primitif, digression sur le système de Fibonacci.
05/03 1h30 Estimation du nombre de chemins de longueur n dans un graphe à composantes primitives.
06/03 1h30 Google et PageRank.
12/03 1h00 Algèbre d'adjacence, dimension de l'algèbre et spectre du graphe, caractérisation des graphes réguliers connexe (SSI J appartient à l'algèbre, thm. de Hoffman).
14/03 1h30 Corollaire du thm. de Hoffman, sous-arbres couvrants, algorithme de recherche en profondeur, formule de Cayley pour compter le nombre de sous-arbres couvrants, thm. de Cayley pour compter les sous-arbres de K_n et codage de Prufer, thm de Berge pour compter le nombre d'arbre a degrés fixés (énoncé seul), introduction au comptage du nombre de sous-arbres pointés et orientés.
18/03 1h00 Nombre de sous-arbres pointés et orientés (Bott-Maybery), retour au cas non orienté.
21/03 1h30 Planarité, formule d'Euler, graphe simple planaire avec sommet de degré au plus 5, K_5, K_3,3 ne sont pas planaires, thm. de kuratowski (énoncé seul), à propos du thm. des 4 couleurs, thm. des 5 couleurs.
08/04 1h00 Polynome chromatique, définition, propriétés, nombres de coloriages avec au plus k couleurs, polynome chromatique d'arbres.
10/04 1h30 Nombres de Ramsey, thm. de Erdos-Szekeres.
24h00

Troisièmes bacheliers en sciences mathématiques : Calculabilité

18/09 1h30 Fonctions primitives récursives, fonctions de base, composition, récursion primitive, exemples (fonctions constantes, somme, produit, puissance, prédécesseur, monus, sign), prédicats et parties primitifs récursifs, > est PR.
19/09 2h00 Somme bornée, produit borné, prédicats primitifs récursifs (et, ou, non, >, quantification bornée, ...), schéma (généralisé) de définition par cas, exemples d'ensembles PR, schéma de minimisation bornée, DIV, MOD, ensemble des nombres premiers, énumération PR des n-uples d'entiers.
25/09 1h30 Fonction d'Ackermann, cf. "Beamer".
26/09 2h00 Fonction d'Ackermann, fin. schéma de récursion primitive généralisé, existence d'une fonction "calculable" qui n'est pas PR, F est non dénombrable, ]0,1[ est non dénombrable, fonctions récursives et minimisation, parties sures, les fonctions récursives sont "calculables", introduction des machines de Turing, un exemple de machine.
2/10 Séance de répétition
3/10 2h00 Arguments en faveur des machines de Turing, définitions : alphabet, mot, language, configuration mémoire, configuration machine, transitions, fonctions calculbales par M.T., composition de M.T, composition conditionnelle, organigramme.
9/10 1h30 Constructions de machines de Turing, machines élémentaires, "shift-left/right", copieur_k, effaceur_k, exemples, "R inclus dans C" : toute fonction récursive est calculable (4 lemmes).
10/10 2h00 C stable par minimisation, toute fonction calculable est récursive, R=C.
16/10 Séance de répétition.
17/10 2h00 codage de fonctions définies sur des alphabets quelconques, caractère calculable de ces fonctions, langages acceptables et décidables (récursivement énumérables et récursifs), L décidable => L acceptable, L décidable => complémentaire décidable, L et complémentaire acceptables => L décidable, le non déterminisme dans les machines de Turing, exemples, langage accepté par une machine non déterministe, les langages acceptés par les machines non déterministes sont les mêmes que par les machines déterministes, un exemple (existentiel) de fonction non calculable.
23/10 Séance de répétition.
24/10 2h00 La fonction "beta" n'est pas calculable, machines de Turing universelles, problèmes décidables (Primes,VC,TSP,SAT).
30/10 1h30 Quelques exemples de problèmes indécidables (PCP, problème de l'arrêt, 10ème problème de Hilbert), l'ensemble des langages récursifs est stable pour l'union, la concaténation, l'*, le passage au complémentaire, L décidable ssi L et complémentaire acceptables, énumération effective des mots d'un langage acceptable (d'où langage récursivement énumérable), "f calculable SSI son graphe est décidable", le problème de l'arrêt est indécidable.
31/10 2h00 Le langage associé au problème de l'arrêt est acceptable, R inclus strictement dans RE, théorème de Rice, un aperçu du problème de pavage (sans preuve), complexité, premières définitions ("grand O", ...), transformation polynomiale.
6/11 1h30 Transformation polynomiale, équivalence polynomiale, 2 exemples de classes d'équivalence, HC ≤ TSP, les classes de complexité P, NP, NPC, co-NP, co-NPC, P inclus dans NP, si "NPC inter P" non vide alors P=NP, certificat succint, discrédit succint.
7/11 2h00 Relations entre P, NP, NPC, co-NP et co-NPC, machine déterministe de complexité 2^Q(n), théorème de Cook (sans preuve), problème NP-dur, 3SAT est NPC, VC est NPC (SAT ≤ 3SAT ≤ VC).
13/11 Séance de répétition.
14/11 2h00 VC est NPC, quelques remarques sur la NP-complétude, pourquoi Primes n'est-il pas trivialement dans P, quelques autres classes de complexité (BP, RP, ZPP, P-Space, NP-Space).
20/11 Séance de répétition.
25h30

Troisièmes bacheliers en sciences mathématiques : Math. Discrètes

11/02 1h30 Structures algébriques (groupe, anneau, corps, champ, homomorphisme, K-vectoriel), extension de champ, extension de dimension finie, idéaux, anneau quotient, polynômes et division euclidienne, polynômes irréductibles.
13/02 3h00 Construction de champs finis, application Mathematica, <P> maximal ssi P irréductible, décomposition de polynômes en polynômes irréductibles, éléments algébriques, polynôme minimum, propriétés, a algébrique ssi [K(a):K] fini, l'ensemble des éléments algébriques est un champ, structure de K(a) si a algébrique, construction de champs finis comme extension, extension par un élément transcendant, racines d'un polynôme et propriétés, quelques résultat sur le corps de rupture d'un polynôme, exemples.
27/02 1h30 Groupe multiplicatif d'un anneau, caractéristique d'un anneau intègre, sous-champ premier, binome de Newton stupide, nombre d'éléments d'un champ fini, fonction indicatrice d'Euler, petit thm. d'Euler, thm. de Wilson, générateur d'un champ (énoncé du résultat, preuve du lemme).
29/02 1h30 Générateur d'un champ (preuve du résultat), unicité d'un champ fini à p^f éléments, structure des sous-champs de F_q, exemples, X^q-X est le produit des polynômes minimums des éléments de F_q.
03/03 1h30 X^q-X est le produit des polynômes moniques irréductibles sur F_p, formule pour N_p(f) "nombre de polynomes moniques irréductibles sur F_p de degré f", minoration de N_p(f) avec la notion de générateur de L sur K, exponentiation modulaire, complexité d'opérations (addition et multiplication d'entiers).
05/03 1h30 Algorithme d'Euclide étendu, complexité d'opérations dans F_q, quelques propriétés des nombres premiers, introduction à la cryptographie.
10/03 1h30 Cryptographie à clé privée, décalage, substitution, Hill, Vigenère, flot, DES, implémentation Mathematica.
12/03 Cours suspendu
14/03 1h30 Introduction à la cryptographie à clé publique, RSA, chiffrement, déchiffrement, signature, taille des blocs.
17/03 1h30 problème de la signature cachée, fonction de hachage, factorisation de n si d ou phi(n) connus, éléments à prendre en considération dans la construction d'un RSA, estimation de la probabilité de tirer un nombre premier.
21/03 1h30 Test de Fermat, au moins au tant de non-témoins de primalité que de témoins..., nombres de Carmichael (caractérisation de ceux-ci), test de Miller-Rabin (sans preuve).
07/04 1h30 Logarithme discret, isomorphisme avec (Z_{p-1},+), échange des clés de Diffie-Hellman, cryptosysème de ElGamal, introduction aux suites linéaires récurrentes, le problème de Josephus.
09/04 1h30 récurrences non homogènes, structure des solutions, polynome caractéristique, matrice compagnon, solutions d'une récurrence linéaire homogène, obtention de solutions, structure générale des solutions.
14/04 1h30 Séries formelles, fonctions génératrices.
15/04 1h30 Nombres de Catalan.
22h30

Master1 en sciences mathématiques : Théorie des automates et langages formels

18/09 2h00 Rappels sur les mots (préfixe, suffixe, facteur, longueur, concaténation, puissance, fonction de Parikh,...), mots suffisamment longs et carrés (alphabet binaire), mots infinis, mots engendrés par morphisme, uv=vu ssi u,v puissance d'un même mot, xy=yz ssi ..., mots périodiques, théorème de Fine-Wilf.
19/09 1h30 Retour sur le thm. de Fine-Wilf, langages, premières propriétés, opérations, étoile de Kleene, étoile d'un langage sur un alphabet unaire, expressions régulières, langages réguliers.
21/09 1h30 Quelques exemples de langages réguliers, expressions régulières équivalentes, caractérisation de l'ensemble des langages réguliers, langages réguliers sur un alphabet unaire (preuve post-posée), ensembles ultimement périodiques, "si L régulier, alors |L|...", applications de ce résultat.
25/09 2h00 Preuve du résultat des langages réguliers sur un alphabet unaire, automate fini déterministe, définitions, idem dans le cas non déterministe, automate élémentaire, thm. de Rabin et Scott.
26/09 Séance de répétition.
02/10 2h00 A propos de l'explosion exponentielle du nombre d'états (déterminisation), stabilité des langages acceptés par automate : union, concaténation, *, miroir, image par morphisme, ens. des préfixes, ens. des suffixes, intersection, shuffle (produit d'automates), tout langage régulier est accepté par AF.
03/10 1h30 Tout langage accepté par AF est généré par une expression régulière, automates finis étendus, élimination de sommets, théorème de Kleene, lemme de la pompe, application a {a^nb^n:n}, lemme de la pompe version forte.
05/10 1h30 Automate minimal : congruence de Nerode, définitions, premières propriétés, exemples, q^-1.F, w^-1.L=p^-1.F, relation d'équivalence sur les états, définition du minimal, deux exemples, le minimal de L accepte L.
9/10 Séance de répétition.
10/10 1h30 Propriétés fondamentales de l'automate minimal, détection des états équivalents pour minimiser un automate déterministe donné.
12/10 Séance de répétition.
16/10 2h00 Automate minimal : "prendre le miroir et rendre déterministe 2x" (avec d'abord un rappel sur la construction de déterminisation par sous-ensemble d'états), remarques sur la complexité pour rendre déterministe, utilisation du minimal : f^-1(M) régulier si M régulier et f morphisme, Pref(L) régulier, racine k-ième d'un langage (avec lemme sur "p et S(p)").
17/10 1h30 Transducteur (sans détails "techniques"), fonction de complexité d'un langage régulier, rappels sur les techniques de résolution d'équations linéaires récurrentes, polynôme minimum du minimal divise polynôme minimum de tout autre AFD acceptant le même langage.
19/10 Séance de répétition.
23/10 Séance de répétition.
24/10 1h30 Recherche d'un mot dans un texte, congruence syntaxique, monoide syntaxique, lien avec les actions de Sigma^* sur l'ensemble des états du minimal.
26/10 1h30 Monoide syntaxique (suite et fin), semi-groupe fini apériodique (2 propositions), test algorithmique pour déterminer si un langage est sans étoile (énoncé sans preuve du thm. de Schutzenberger).
30/10 2h00 Hiérarchie de Chomsky, langages algébriques, grammaire, mot et langage générés, dérivation, dérivation la plus à gauche, arbre d'analyse, ambiguité, exemple "expressions arithmétiques" ambigue et non-ambigue, tout langage régulier est algébrique, {a^nb^n} est algébrique.
31/10 1h30 Retour sur la hiérarchie de Chomsky (grammaire de type 0 et 1, langages "context-sensitive"), élimination des variables effaçables, des 1-productions, des symboles inutiles... mise sous forme normale de Chomsky (avec preuve), forme normale de Greibach (sans preuve).
7/11 1h30 Lemme sur hauteur d'arbre et mot produit, lemme de la pompe pour les grammaires, {a^nb^nc^n} n'est pas algébrique, langages algébriques et intersection, complémentaire, image par morphisme, fonction de Parikh, théorème de Parikh (sans preuve), ensemble semi-linéaire de N^t, automates à pile, introduction et définition.
14/11 1h30 Tout langage algébrique est accepté par un automate à pile, automate élémentaire, intersection d'un langage régulier et d'un algébrique (sans preuve détaillée), langage des mots préservant la pile vide (sans preuve détaillée), théorème de représentation de Chomsky-Schutzenberger.
21/11 Séance de répétition.
28/11 1h30 Intervention d'une chercheuse, M. LeGonidec.
05/12 Séance de répétition.
12/12 Séance de répétition.
28h00

Master2 en sciences mathématiques : Combinatoire des mots

20/09 2h30 Petite introduction à la combinatoire des mots (applications en bio-informatique, analyse du génome, théorie des nombres, transcendance, infographie, codage de droites, mots sturmiens, dynamique symbolique, codage de trajectoires), langages rationnels de mots infinis, automates de Buchi, définition de période d'un mot fini, thm. de Fine-Wilf, notion de mot infini, suite k-automatique, exemple de la suite de Thue-Morse, problème de Prouhet, notion de convergence, de topologie, de distance sur les mots infinis, énoncé du théorème de Cobham (1972), exemple d'application du thm. de Cobham, notion d'ensemble k-automatique, complexité d'un mot infini, mot de Champernowne, thm. de Morse-Hedlund caractérisant les mots ultimement périodiques, panorama sur les séries formelles rationnelles: généralisation "naturelle" de la notion de langage, semi-anneau, somme et produit de séries, rappel langages réguliers/reconnaissables par automate fini, parallèle avec la notion de série formelle rationnelle/reconnaissable (thm. de Schutzenberger), exemple de série reconnaissable (valuation de a^*b^*).
04/10 2h00 G. Amand, livre de J. Sakarovitch, Ch. II, section 1 : automates sur un monoide, parties, opérations, expressions rationnelles, image par morphisme, comportement des automates, parties rationnelles non ambigues.
11/10 1h30 A. Lacroix, livre de J. Sakarovitch, Ch. II, section 2 : actions sur un ensemble, représentation matricielle des actions, parties reconnues par une action, "reconnaissable-ci, reconnaissable-la", théorème de Kleene, représentation matricielle des automates sur A^*, automte d'une action.
22/10 1h30 A. Lacroix, livre de J. Sakarovitch, Ch. II, section 2 : opérations élémentaires sur les parties reconnaissables, minimisation, morphismes d'actions, action minimale, congruence et monoide syntaxique.
29/10 2h30 A. Lacroix, livre de J. Sakarovitch, Ch. II, section 2 : racine k-ième, image inverse par substitution, parties reconnaissables dans un produit
J. Leroy, livre de J. Sakarovitch, Ch. II, section 3: morphismes d'automates, morphismes conformes, propriétés locales, Out, In, morphisme localement injectif/surjectif/bijectif/co-injectif..., morphismes localement surjectifs/totalement surjectifs, quotient d'un automate, quotient minimum.
9/11 2h00 J. Leroy, livre de J. Sakarovitch, Ch. II, section 3: Algorithme de Moore, revêtements d'automates.
13/11 2h00 J. Leroy, livre de J. Sakarovitch, Ch. II, section 3: Immersion, produit d'un automate et d'une action, revêtement de Schutzenberger.
20/11 2h00 G. Amand, livre de J. Sakarovitch, Ch. II, section 4: factorisation, automate universel.
30/11 2h30 G. Amand, livre de J. Sakarovitch, Ch. II, section 4: automate universel (suite).
A. Lacroix construction de l'automate universel, expansion, automate de Cohen Brzozowski, quotient minimum de cet automate, extraction de l'automate universel.
7/12 2h00 A. Lacroix, meilleur approximation, approche duale. J. Leroy, livre de J. Sakarovitch, Ch. II, section 6: rationnels dans le groupe libre, action, prop. de Fatou, description du groupe libre, congruence/mots de Dyck, de Shamir, simplification, système de réécriture.
13/12 2h30 J. Leroy, livre de J. Sakarovitch, Ch. II, réduction associée à une simplification, factorisation non ambigue induite par une réduction.
G. Amand, théorème de Benois, l'automate "theta_pi A".
18/12 2h30 G. Amand, retour sur le groupe libre, thm. de Howson, de Sénizergues, systèmes de Buchi.
18/01 2h00 A. Lacroix, livre de J. Sakarovitch, Ch. III, section 1, séries formelles sur M à coeff. dans K, opérations, monoide gradué, matrice de séries et séries de matrices, topologie sur K[[M]], distance, convergence, famille sommable, famille localement finie, morphismes continus.
30/01 2h00 J. Leroy, livre de J. Sakarovitch, Ch. III, section 2, étoile dans un semi-anneau topologique, étoile d'une série propre/quelconque, opérations K-rationnelles, K-expressions rationnelles (valides).
14/02 -- E. Charlier, systèmes de numération abstraits sur un langage régulier, ensembles S-reconnaissables d'entiers, multiplication par une constante.
21/02 -- M. Legonidec, ensembles d'entiers reconnus par des automates dénombrables : ensemble "p-infini"-reconnaissables.
29/02 1h30 J. Leroy, étoile d'une matrice, K-automate avec multiplicité, chemin, calcul, comportement, définitions et exemples.
05/03 -- J. Cassaigne, Exposé "fonction de complexité".
21/03 1h G. Amand, thm. fondamental.
08/04 M. Rigo, Jeu de Wythoff et combinatoire des mots, morphismes bidimensionnels, etc....
17/04 W. Steiner, Exposé "Discrepancy of abstract van der Corput sequences".
E. Duchêne, Exposé "jeu de Tribonacci".
29/04 G. Amand, Jeu de Tribonacci et de Rayleigh.
06/05 F. Durand, Dynamique polynomiale dans Z_p, l'anneau des entiers p-adiques.
31h