| Home / lib / M_Mathematics / | ||
Antonini et al. Les Mathematiques pour l'agregation (lectures, 2002)(fr)(680s).pdf |
|
Size 3.5Mb Date Jul 15, 2004 |
133 136 136 139 143 143 145 146 147 147 147 148 150 150 152 152 153 154 154 156 157 160 160 160 162 162 162 163 165 165 166 167 170 171 171 172 172 172 173 174 174 175...
214 214 215 215 218 219 220 220 225 226 228 228 228 229 229 230 230 230 231 232 233 233 234 235 238 239 239 240 242 246 252 253 253 253 253 254 255 256 256 256 256 257 259 261 261 261 262...
313 313 313 318 320 321 326 326 330 331 335 336 336 336 338 338 339 340 340 341 342 342 345 345 345 346 347 348 348 350 350 350 351 352 355 356 356 357 358 359 361 361 362 365 365 365...
445 446 449 450 450 451 452 453 454 454 456 461 467 469 469 469 470 471 471 472 472 472 473 473 475 477 480 481 483 486 487 487 488 492 496 496 496 497 499 500 500 504 504 505 505 507 507...
608 608 608 609 609 611 611 612 613 614 616 616 616 617 617 617 618 618 618 620 621 626 626 626 628 628 630 631 632 632 632 632 633 634 634 634 635 636 637 637 637 639 639 639 640 641...
Définition 3 Une chaîne C est dîte maximale si et seulement si quel que soit l’élément x, l’ensemble C ∪ {x} n’est pas une chaîne. Une antichaîne C est dîte maximale si et seulement si quel que soit l’élément x, l’ensemble C ∪ {x} n’est pas une antichaîne....
Ci-dessous un algorithme déterminant si oui ou non un graphe est sans circuit ou non. Le codage machine employé consiste en une liste de successeurs pour chaque sommet. Procédure sans-circuit(G) Début : Pour tout x ∈ X faire d− (x) = 0 Pour tout x ∈ X faire Pour tout y ∈ Γ+ (x) faire...
• Pour k variant de 1 à n faire • • Pour i variant de 1 à n faire • • • Pour j variant de 1 à n faire • • • • ai,j ← ai,j ∨ (ai,k ∧ ak,j ) On peut constater que l’on n’applique pas exactement le lemme, car les ai,j ne sont pas les bons, mais l’on peut aussi montrer que l’algorithme fonctionne tout de même. La complexité de l’algorithme de Roy-Warshall est O(n3 ). Soit G = (X, U ) un graphe orienté, Gr = (X, Ur ) est une réduction transitive de G si Ur ⊂ U , Gr n’a pas de transitivité et (Gr )f = Gf . La réduction transitive n’est pas toujours unique. Si G = (X, U ) est un graphe orienté sans circuit, il a une unique réduction transitive appelé graphe de Hasse. Algorithme général de calcul d’une fermeture transitive (pas seulement dans le cas d’un graphe sans circuit). • Pour x ∈ X faire • • marque(x) ← faux • • Γ+ (x) ← ∅ f • Pour tout x ∈ X faire • • file ← {x} • • tant que file = ∅ faire • • • y ← premier(file) • • • supprimer (y ,file) • • • Pour tout z ∈ Γ+ (y ) faire • • • • Si marque(y )=faux alors • • • • • marque(z ) ← vrai • • • • • marque(Γ+ (x) ← Γ+ (x) ∪ {z }) f f • • • • • file ← file ∪ { z } • • Pour tout z ∈ Gamma+ (x) faire f • • • marque(x) ← f aux Le coût de cet algorithme est O(n|U | + |Uf |). On cherche maintenant à déterminer à la fois la fermeture et la réduction transitive dans un graphe sans circuit. L’algorithme employé est l’algorithme de Goralcicova-Koubek. • Pour tout x ∈ X faire • • Γ+ (x) ← ∅ f • • Γ+ (x) ← ∅ r • • marque(x) ← faux • On classe les points dans l’ordre d’un tri topologique τ = (x1 , x2 , ..., xn ) • Pour i variant de n à 1 faire • • S ← Γ+ (xi ) • • Tant que S = ∅ • • • x ← minτ (S )...
Une classe est associée à une propriété d’une seul élément ; c’est à dire que l’on se donne une assertion comportant une et une seule variable libre ; un élément est dans la classe correspondante s’il vérifie l’assertion. Les formules comportant plusieurs variables libres sont appelées relations. Eventuellement on peut avoir une distinction entre des variables et des paramètres ; dans ce cas on a une classe pour chaque valeur possible des paramètres. La théorie des ensembles est basée sur un ensemble d’axiomes. Les objets de cette théorie sont appelés ensembles, et la classe des ensembles est appelée univers. Les axiomes de la théorie des ensembles de Zermelo-Fraenkel sont les suivants :...
On notera que toutes les opérations intuitives sur les ensembles sont possibles, enfin presque. On peut en tout cas utiliser les intersections, définir l’ensemble des éléments d’un ensemble donné qui vérifient une propriété donnée, on peut travailler sur l’ensemble des parties d’un ensemble, on peut travailler sur un produit cartésien d’ensembles, bref toutes ces choses sans lesquelles les maths prendraient vraiment la tête. On peut aussi montrer l’existence et l’unicité de l’ensemble vide....
Là aussi il convient de vérifier que le produit de deux couples d’ensembles de mêmes cardinaux respectifs est le même. On peut en outre vérifier que la multiplication de cardinaux est associative et commutative, et distributive par rapport à l’addition. On notera que le produit de deux cardinaux est le plus grand de ces deux cardinaux. Définition 44 (Exponentiation de cardinaux) Etant donnés des cardinaux A et B on note AB le cardinal de l’ensemble des applications de B dans A....
Propriété : Un ensemble infini est un ensemble contenant une partie dénombrable infinie. Un ensemble infini est un ensemble qui est en bijection avec l’une de ses parties 35...
Démonstration : La vérification est fastidieuse et ne présente pas de difficulté. 4...
Proposition 95 Un espace à base dénombrable d’ouverts contient un ensemble dénombrable dense Démonstration : Il suffit de considérer un point par ouvert non vide d’une base dénombrable. D éfinition 96 (Espace séparable) Un espace est séparable si il contient un ensemble dénombrable dense. Cela sera notamment utile pour définir une métrique sur la boule unité fermée du dual d’un espace séparable (pour la topologie faible). Ceux qui veulent en savoir plus peuvent aller voir la proposition 194. On note en particulier qu’un ensemble à base dénombrable d’ouverts est séparable (il suffit de prendre un point dans chaque ouvert) ; il s’agit de la proposition précédente. La réciproque est vraie dans le cas des espaces métriques :...
Démonstration : On considère les voisinages respectifs de deux limites, et on considère l’intersection de leurs images inverses respectives ; cette intersection est réduite T un singleton ; or c’est un voisinage de x0 . à héorème 119 Soient f1 et f2 deux applications continues ayant même ensemble de départ et même ensemble séparé d’arrivée. Alors {x|f1 (x) = f2 (x)} est fermé....
Définition 128 (Applications lipschitzienne) Une application h est dite lipschitzienne s’il existe K ∈ [0, +∞[ tel que d(h(x), h(x )) ≤ K.d(x, x ) On dit aussi qu’elle est K -lipschitzienne. On définit la constante de Lipschitz par Lip(h) = sup{ d(h(x), h(x )) |x, x d(x, x )
∈...
| © 2007 eKnigu | ||