Discussion:INFO421 : Programmation fonctionnelle

2010-01-26T14:18:19Z

Rodlepigre : /* commentaire pour le tp0 */

== Comment commencer une discussion ==

Pour commencer une discussion, il suffit de cliquer sur le '''<tt>+</tt>''' en haut de la page. Vous pouvez alors rentrer un sujet de discussion et éditer le texte comme pour le wiki.

C'est mieux de signer vos intervention en utilisant l'avant dernier bouton d'édition, ou avec <tt><nowiki>--~~~~</nowiki></tt>.

:Pour répondre, il faut « modifier » la section correspondante...
:Par soucis de visibilité, il est parfois préférable de rajouter une marge à gauche (comme ici). Pour faire ça, il faut commencer votre ligne par un «<tt>:</tt>». (Ou un «<tt>::</tt>»...)

--[[Utilisateur:Hyvernat|Hyvernat]] 26 janvier 2010 à 10:15 (CET)

== Inscription sur le Wiki ==

Ben moi, je suis inscrit depuis longtemps...

--[[Utilisateur:Hyvernat|Hyvernat]] 26 janvier 2010 à 10:15 (CET)

Ben moi, je viens de m'inscrire

--[[Utilisateur:giunchi|Giunchi]] 26 janvier 2010 à 13:08

Salut!
--[[Utilisateur:Eosbo|Eosbo]] 26 janvier 2010

Hello!
--[[Utilisateur:Ciminera|Ciminera]] 26 janvier 2010

bonjour --[[Utilisateur:Scnig|Scnig]] 26 janvier 2010 à 13:16 (CET)

Salut la gente !! --[[Utilisateur:vkim|vkim]] 26 janvier 2010 à 13:19 (CET)

hello tous :p --[[Utilisateur:Manic|Maxime]]

Salut. --[[Utilisateur:Lemaire|Lemaire]] 26 janvier 2010 à 14:38

== commentaire pour le tp0 ==

salut !, on s est inscrit le 26/01/2010.
--[[Utilisateur:Gevet|Gevet]] 26 janvier 2010 à 13:13 (CET)

J'aime les carottes
--[[Utilisateur:Rmont|Raphael]] 26 janvier 2010 à 13:16 (CET)

coucou!,je suis inscrit.
--[[Utilisateur:Mathian|Mathian]] 26 janvier 2010 à 13:17 (CET)

voila j'suis inscris.
--[[Utilisateur:Jebes|Jeremy]] 26 janvier 2010 à 13:18 (CET)

Me voilà enfin !!!!! Bien dit ! Linux c'est bien mieux !
--[[Utilisateur:Rodlepigre|Rodlepigre]] 26 janvier 2010 à 15:18 (CET)

Windows, c'est mieux que Linux, et c'est plus cher !!! --[[Utilisateur:Fvite|Fvite]] 26 janvier 2010 à 13:36 (CET)

MATH203 : Introduction à l'algèbre

2009-02-10T22:11:19Z

Rodlepigre : /* Récurrence */

Feuilles de TD :
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD1-M2AL.pdf 1]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD2-M2AL.pdf 2]

== Que sont les mathématiques ==

En mathématique on étudie les propriétés d'objets tels que les nombres, les droites, ... Ces objets sont dénotés par des "expressions" comme
* x^2 - 1,
* Le milieu du segment [A,B],
* f est continue.

Chaque domaine des mathématiques possède son propre "vocabulaire" pour écrire des expressions et ce vocabulaire est introduit dans chacun de vos cours.

===L'égalité===
L'égalité joue un rôle particulier en mathématique car elle est "substitutive" : si deux expressions a et b sont égales, on peut remplacer a
par b dans toute expression sans en changer la valeur. Il faut tout de même faire attention aux variables liées. Considérons l'exemple suivant:

Soit y un réel et x = y + 2, on a donc x - y = 2.
Pour <math>x \in \mathbb{R}</math>, définissons la fonction f(x) = x^2 - y^2 = (x - y)(x + y).
On a donc pour tout <math>x \in \mathbb{R}</math> f(x) = 2(x + y).

On a commis une erreur car x est une variable liée dans la seconde phrase. On peut toujours changer le nom des variables liées et écrire

Soit y un réel et x = y + 2, on a donc x - y = 2.
Pour <math>z \in \mathbb{R}</math>, définissons la fonction f(z) = z^2 - y^2 = (z - y)(z + y).
On a donc f(x) = 2(x + y) seulement pour un x particulier.

===Les énoncés===
Parmis les expressions certaines sont des "énoncés", c'est à dire des expressions dont la valeur est vraie ou fausse comme
* x^2 - 1 = (x - 1)(x + 1)
* Les trois droites sont concourantes
* Toute fonction continue est dérivable (cet énoncé est faux, mais on peut l'écrire !)
Les mathématiques ont pour objet de découvrir quels énoncés sont vrais en partant uniquement "d'axiomes" qui sont des énoncés que l'on adment comme
vrais dans un domaine donné des mathématiques.

Tous les énoncés mathématiques peuvent être ecrits en utilisant les "briques" de construction suivantes :
* Des énoncés atomiques propre à chaque domaine des mathématique comme <math>x\in E</math>, "f est continue", ... Attention: certains énoncés atomiques peuvent être transformés en énoncés plus complexe en faisant appel à une définition (c'est le cas de "f est continue").
* l'implication : notée <math>A \Rightarrow B</math>, <math>A \rightarrow B</math>, A implique B, A est une condition suffisante pour B, B est une condition nécessaire pour A, si A alors B, ...

Attention, l'implication mathématique est très différente de l'implication en langage courant qui contient souvent une relation de cause à effet voire qui exprime une équivalence : "si tu ne mange pas ta soupe tu n'aura pas de déssert" est une équivalence en langue naturelle.

<math>A \Rightarrow B</math> est faux uniquement si A est vrai et B est faux. Dans les trois autres cas, l'implication mathématique est vraie. Pour ce persuader que c'est cela qu'il faut faire, considérer l'énoncé suivant (qui est bien vrai ?) :

Si n est divisible par 4 alors n est pair

* Pour n = 2 on obtient "Faux implique Vrai"
* Pour n = 3 on obtient "Faux implique Faux"
* Pour n = 4 on obitent "Vrai implique Vrai"

* La conjonction : notée "A et B", "<math>A \land B</math>", ... Le sens devrait être clair
* La disjonction : notée "A ou B", "<math>A \lor B</math>", ... C'est le ou usuel. A ou B est vrai si l'un des deux enoncés au moins est vrai. Il ne faut pas le confondre avec le "ou exclusif", utilisé en informatique, et qui est faux lorsque les deux énoncés sont vrais en même temps.
* La négation : notée "non A", "A est faux", "il est faux que A", "<math>\lnot A</math>", ... On a non A est vrai si et seulement si A est faux et donc aussi non A est faux si et seulement si A est vrai.
* L'équivalence : notée "A équivalent à B", "A si et seulement si B", "A est une condition nécessaire et suffisante pour B", "<math>A \Leftrightarrow B</math>", "<math>A \leftrightarrow B</math>". "<math>A \Leftrightarrow B</math>" peut être défini comme "(A implique B) et (B implique A)".
* La quantification universelle : notée "pour tout x A", "on a A pour tout x", "quelque soit x A", <math>\forall x A</math>, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.
* La quantification existentielle : notée "il existe x tel que A", "on a A pour au moins un x", "on peut trouver un x tel que A", <math>\exists x A</math>, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.

==Qu'est-ce qu'une preuve==

===Définitions===
*Une preuve est un texte pour convaincre le lecteur de la vérité d'un énoncé. Une preuve est constituée d'une suite d'étapes telles qu'à chacune d'elles, on a :
# des connaissances : liste d'objets connus, de théorèmes, d'hypothèses locales au problème
# un but à démontrer
* Pour passer d'une étape à l'autre, on peut :
# chercher à simplifier le but/le diviser
# utiliser des connaissances pour progresser (montrer le but, obtenir de nouvelles connaissances, faire un lemme...)

===6X2+2+... briques de bases===
* Si le but est dans la liste des connaissances ou si A et ¬ A sont dans les connaissances, alors la preuve est finie.
* 6X2 briques de bases:
# ''' Montrer que <math>A\Rightarrow B</math> ''': Ajouter A aux hypothèses et montrer B. / ''' Utiliser que <math>A\Rightarrow B</math> ''': Démontrer A pour pouvoir ajouter B aux connaissances.
# ''' Montrer que A et B ''' : Deux preuves dont l'ordre n'a pas d'importance : on montre A puis B. Attentions, les connaissances ou objets introduits lors d'une des deux preuves ne sont plus valables lors de l'autre preuve. / ''' Utiliser que A et B ''' : Rajouter A et B aux connaissances, et utiliser l'une et/ou l'autre.
# ''' Montrer que A ou B ''' : On montre A ou B, au choix / ''' Utiliser que A ou B ''' : Raisonner par disjonction de cas, on a alors deux preuves; rajouter A aux connaissances et montrer le but '' et '' rajouter B dans les connaissances et montrer le but.
Attention, là encore, les connaissances ou objets introduits lors d'une des deux preuves ne sont plus valables lors de l'autre preuve.
# ''' Montrer que ¬ A ''' : Supposer A et chercher une contradiction / ''' Utiliser que ¬ A ''' : Montrer A et en déduire une contradiction
# ''' Montrer que ∀ x, A ''' : Montrer A pour un x '' quelconque ''. En fait un x quelconque est just eune nouvelle variable que l'on a pas utilisée avant et donc on ne sait rien, c'est à dire qu'elel n'apparaît pas dans la liste des connaissances à cet instant. / ''' Utiliser que ∀ x, A ''' : Prendre le x qui nous intéresse et ajouter A(x) aux connaissances courantes.
# ''' Montrer que ∃ x, A ''' : Montrer A pour un x bien choisi / ''' Utiliser que ∃ x, A ''': Prendre un '' queslconque (comme pour montrer ∀ x, A) '' x et supposer A(x)
* ''' Démonstration par l'absurde ''' : Si le but est A, alors on suppose ¬ A et on cherche une contradiction (particulièrement fréquent pour montrer un '' ou '', '' ∃ '', ou un '' énoncé atomique ''.
* Il existe d'autres briques propres au domaine dans lequel on se place ('' exemple '' : preuve par récurrence en arithmétique)

===Loi de Demorgan===

On les utilise souvent avec la négation pour simplifier les énoncés:
* ¬ ¬ A <math>\Leftrightarrow</math> A
* ¬ (A <math>\Rightarrow</math> B) <math>\Leftrightarrow</math> (A et ¬ B)
* ¬ (A et B) <math>\Leftrightarrow</math> (¬ A ou ¬ B) <math>\Leftrightarrow</math> (A <math>\Rightarrow</math> B)
<math>\Leftrightarrow</math> (B <math>\Rightarrow</math> A)
* ¬ (∀x, A) <math>\Leftrightarrow</math> ∃x, (¬ A)
* ¬ (∃x, A) <math>\Leftrightarrow</math> ∀x, (¬ A)

==Ensembles, Fonctions, Relations==

===Théorie des ensembles===
* ''' Schéma de compréhension ''' : {x ∈ A / P(x)} est l'ensemble des x de A qui ont la propriété P
* ''' Paradoxe de Russel ''' : Soit A={x / x <math> \notin </math> x}. Si A ∈ A alors A <math> \notin </math> A et si A <math> \notin </math> A alors A ∈ A. D'où une contradiction qui aboutit à la formulation de l'axiome de compréhension de Zermelo, modifiant le schéma de compréhension : {x '' ∈ A '' / ...} : on ne peut construire que des sous-ensembles d'ensemble déjà existant.
* ''' Construction des ensembles ''' :
# A ∪ B={x / x ∈ A ou x ∈ B} (Ici ce n'est pas le shéma de compréhension, mais une contruction nouvelle)
# A ∩ B={x / x ∈ A et x ∈ B} = {x ∈ A / x ∈ B}
# A-B=A ∩ Bc={x / x ∈ A et x <math> \notin </math> B}
# Ac complémentaire de A : cette notation signifie en général E-A où E est un ''grand'' ensemble sans ambiguïté.
# P(A) : ensemble des parties de A; B ∈ P(A) si et seulement si B ⊂ A ⇔ ∀ x (x ∈ B ⇒ x ∈ A)
# A × B est le produit cartésien : l'ensemble des couples; {(a,b) / a ∈ A b ∈ B}.
* On appelle relation entre A et B un sous ensemble de A × B (on dit aussi correspondance).
* ''' Inverse d'une relation R ''' : Soit R ⊂ P(A × B), on peut '' toujours '' définir R-1. R-1={(b,a) / b ∈ B, a ∈ A, et (a,b) ∈ R}

===Fonction de A dans B===
* notée A → B, F(A,B)
* F(A,B) est l'ensemble des relations de A dans B qui associe au plus un élément de B à chaque élément de A.
* F(A,B)=déf{R ⊂ (A × B) / ∀a ∈ A ∀b, b' ∈ B, ((aRb) et (aRb')) ⇒ (b=b')
* Si f ∈ F(A,B), on écrit b=f(a).

===Application de A dans B===
* Notée A(A,B) ou BA
* Il s'agit des fonctions de A dans B définie partout. C'est à dire qui associe exactement un élément de B à chaque élément de A.
* A(A,B)={f ∈ F(A,B) / ∀a ∈ A ∃!b ∈ B tel que b=f(a)} (∃! signifie ''il existe un unique'').

===Restriction===
Soient f ∈ F(A,B) et A' ⊂ A, fl`A' ∈ F(A',B)={(a,b) / a ∈ A' et b=f(a)}

===Image directe===
Soient f ∈ F(A,B) et A' ⊂ A, f(A')={b ∈ B / ∃a ∈ A', b=f(a)}

=== Image réciproque===
Soient f ∈ F(A,B) et B' ⊂ B f-1(B')={a ∈ A / f(a) ∈ B' }

=== Inclusion===
A ⊂ B ⇔ ∀x (x ∈ A ⇒ x ∈ B)

===Injection===
* notée parfois A <math>\hookrightarrow </math> B
* Une injection est une application telle que chaque élément de l'ensemble d'arrivée possède au plus un antécédent.
* Soit f une application de A dans B, ∀ a, a' ∈ A (f(a)=f(a') ⇒ a=a') ⇔ f est injective.

===Surjection===
* Une surjection est une application telle que chaque élément de l'ensemble d'arrivée possède au moins un antécédent.
* Soit f une application de A dans B. ∀ b ∈ B ∃ a ∈ A tel que b=f(a) ⇔ f est surjective.

===Bijection===
* Une bijection est une application qui est à la fois surjective et injective.
*(∀ a ∈ A ∃! b ∈ B tel que b=f(a) et ∀ b ∈ B ∃! a ∈ A tel que b=f(a)) ⇔ f est bijective.

===Composition ===
* Soient f ∈ F(A,B) et g ∈ F(B,C). (g ο f)(x) ∈ F(A,C) est définie par (g ο f)(x)=g(f(x)).
* f ο g injective, g surjective ⇒ f injective
: f ο g surjective, f injective ⇒ g surjective
: f ο g injective ⇒ g injective
: f ο g surjective ⇒ f surjective

===Relation d'ordre large ===
exemples: ≤ ≥ sur IR, ⊂ sur les ensembles, divise dans lN

R ⊂ (A × A) est d'ordre large si et seulement si elle est :
# '' réflexive '' : ∀a ∈ A aRa
# '' antisymétrique '' : ∀a, a' ∈ A (aRa' et a'Ra) ⇒ a=a'
# '' transitive '' : ∀a, b, c ∈ A (aRb et bRc) ⇒ aRc

===Relation d'équivalence===
=, ⇔, avoir même reste dans la division par n

R ⊂ (A × A) est d'équivalence si et seulement si elle est :
# '' réflexive '' : ∀a ∈ A a R a
# '' symétrique '' : ∀a, a' ∈ A a R a' ⇒ a' R a
# '' transitive '' : ∀a, b, c ∈ A (a R b et b R c) ⇒ a R c

===Quotients===
* ''' Définition ''' : On a un ensemble E et &equiv; une relation d'équivalence sur E. Le quotient de E par &equiv; noté E/&equiv; est l'ensemble des classes d'équivalence de &equiv;.
* ''' Classe d'équivalence ''' : La classe d'équivalence de x est x={y ∈ E / x &equiv; y} ⇔ ∀ a ∈ E (a ∈ x ⇔ a &equiv; x)
* ''' Propriétés ''' : Soient E un ensemble et &equiv; une relation d'équivalence sur E.
# ∀ x, y ∈ E (x &equiv; y ⇔ x=y)
# L'ensemble des classes d'équivalence est une partition de E
* ''' Construction de l'ensemble des rationnels par quotient ''' : Q={(n,d) l n∈Z, d∈lN*}, soit &equiv; / ((n,d) &equiv; (n',d') ⇔ nd'=n'd). &equiv; est une relation d'équivalence, et l'ensemble des rationnels est le quotient de Q par &equiv;.
* ''' Relever une opération sur le quotient '''
* ''' Loi interne ''' : f:EXE → E telle que si x &equiv; x' et y &equiv; y' alors f(x,y) &equiv; f(x',y').

==Arithmétique==

===Récurrence===
* ''' Proposition : ''' les trois propriétés suivantes sont équivalentes :
# Tous les sous-ensembles non vides de lN ont un plus petit élément.
# Si P est une propriété sur lN, si P(0) est vrai, si ∀n ∈ lN (P(n)⇒P(n+1)), alors ∀n∈lN P(n).
# Si P est une propriété sur lN, si ∀n∈lN, si ((∀k<n P(k))⇒P(n)), alors ∀n∈lN P(n).
* ''' Preuve '''
* ''' Principe '''
* ''' Récurrence généralisée '''

=== Division euclidienne===
* ''' Définition '''
* ''' Preuve de l'existence et de l'unicité par récurrence sur p ≥ 0 '''
===Divisibilité===

===PGCD===
* ''' Signification '''
* ''' Preuve de l'existence '''
* ''' Algorithme d'Euclide '''
# '' Propriétés ''
# '' Description ''
# '' Autre algorithme ''

===Théorème de Bezout===
* ''' Enoncé '''
* ''' Preuve '''
* ''' Corollaire '''
* ''' Réciproque '''

===Théorème de Gauss ===
* ''' Enoncé '''
* ''' Preuve '''

===Nombres premiers et décomposition===
* ''' Définition '''
* ''' Corollaire du théorème de Gauss '''
* ''' Théorème de décomposition '''

==Arithmétique modulaire==

===Définition de la congruence modulo n===
* ''' Congruence ''' : relation d'équivalence
* ''' Notation ''' : a&equiv;nb a&equiv;b(mod n) a=b(mod n)
* a&equiv;nb ⇔ b-a est un multiple de n
* a&equiv;nb ⇔ a%n=b%n
* Z/nZ est le quotient de Z par la relation d'équivalence modulo n.
# a&equiv;na%n
# Z/nZ={0,1,2,...,n-1} est un ensemble fini à n éléments.
# Z/nZ est un anneau commutatif non intègre. Tout élément non nul de Z/nZ est inversible si et seulement si n est premier. On note alors Z/nZ=Z/pZ.

===Petit théorème de Fermat===
* ''' Enoncé ''': '' <math>a^p = a \pmod p</math> si <math>p \in \mathbb N</math> est premier.'' Ceci peut aussi s'écrire
<math>a^{p-1} = 1 \pmod p</math> mais il faut alors que <math>p</math> ne divise pas <math>a</math>.
* ''' Preuve ''' : Dans (Z/pZ-{0},X) groupe à p-1 éléments, on veut montrer que ap-1=1(mod p).
: ∃ m tel que am=1. {an/n ∈ Z} est un sous groupe de Z/pZ fini, d'où ∃ n' tel que an=an' or p est premier donc an' a un inverse. D'où an-n'=1 ou an'-n=1.
: Montrons que le plus petit n tel que an=1 divise p-1 (théorème de Lagrange). On '' partitionne '' Z/pZ en une famille d'ensembles de '' même cardinal '' que {an}, tout élément de Z/pZ peut s'écrire sous la forme α a θ .
:: La donnée d'une telle partition revient à donner une relation d'équivalence sur Z/pZ : β R γ ⇔ ∃ e ∈ Z tel que β = γ α e.
::: R est réflexive : β=β α 0 d'où β R β
::: R est symétrique : ∃ e tel que β = γ α e donc γ=βα-e car α est inversible, d'où si β R γ alors γ R β
::: R est transitive : ∃ e,f tels que β = γ α e et γ=δ αf implique β = δ α e+f, donc si β R γ et γ R δ alors β R δ
:: 1={1,a,a2,...an-1}=A et b={b,ab,a2b,...an-1b}=B. Soit f:A→B telle que f(x)=xb, f-1(x)=xb-1. fof-1=id et f-1of=id donc f est bijective. Il en résulte que chaque classe est de taille n, d'où n l p-1.
: n l p-1 ⇒ ∃ q ∈ Z tel que p-1=qn et an=1 ⇒ ap-1=aqn=(an)q=1

==Compléments sur les polynômes==

===FTA ou théorème de d'Alembert===
* ''' Enoncé ''': '' Tout polynôme de degré supérieur ou égal à 1 à coefficients dans <math>\mathbb{C}</math> possède au moins un racine dans <math>\mathbb{C}</math>. ''
* ''' Preuve ''' :
: Soient <math> z=a_0+a_1z+ \dots +a_nz^n\,</math> un polynôme à coefficients dans <math>\mathbb{C}[z]</math>. Définissons <math>f:\mathbb{C} \rightarrow \mathbb{R}</math> par <math> f(z)=|P(z)|\,</math>. On va montrer que P admet une racine dans <math>\mathbb{C}</math>.
::* Montrons que <math> \lim_{\mid z \mid \longmapsto \infty} f(z)=\infty </math> :
::: On a <math> f(z)=\mid z^n (\frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} + a_n) \mid </math>, or <math>|ab|=|a| |b|\,</math>, d'où :
::: <math> f(z)= \mid z^n \mid \mid a_n + (\frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z}) \mid </math> or <math>|a+b| \geq ||a|-|b||\,</math>, d'où :
::: <math> f(z) \geq \mid z^n \mid \mid \mid a_n \mid - \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid \mid </math>
::: Cherchons R tel que si lzl>R alors <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid <\mid \frac{a_n}{2} \mid</math> :
:::: <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid \geq \mid \frac{a_0}{z^n} \mid + \mid \frac{a_1}{z^{n-1}} \mid +\dots + \mid \frac{a_{n-1}}{z} \mid </math>
:::: <math> \mid \frac{a_{n-1}}{z} \mid < \mid \frac{a_n}{2n} \mid</math>si <math> \mid z \mid > \mid 2n \frac{a_{n-1}}{a_n} \mid </math> ... <math> \mid \frac{a_0}{z^n} \mid < \mid \frac{a_0}{z} \mid < \mid \frac{a_n}{2n} \mid </math> si <math> \mid z \mid > max(1, \mid 2n \frac{a_0}{a_n}\mid) </math> c'est à dire <math> \mid \frac{a_p}{z^{n-p}} \mid < \mid \frac{a_p}{z} \mid < \mid \frac{a_n}{2n} \mid </math> si <math> \mid z \mid > max (1, \mid 2n \frac{a_p}{a_n} \mid)</math> ∀ p ∈ [lO;nl[. Donc si <math> \mid z \mid > max (1, \mid 2n \frac{a_0}{a_n} \mid, \dots, \mid 2n \frac{a_{n-1}}{a_n} \mid=R ) </math> alors <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid <\mid \frac{a_n}{2} \mid</math>.
::: D'où si lzl>R, alors <math> f(z) > \mid z^n \mid \mid \mid a_n \mid - \mid \mid \frac{a_n}{2} \mid \mid </math>, soit <math> f(z)> \mid z^n \mid \mid \frac{a_n}{2} \mid </math>
::: Cherchons z tel que ∀ M, f(z)>M. Il suffit que lzl>R et lzln>lzl> 2M/lanl. D'où si <math> \mid z \mid > max(1, \frac{2M}{\mid a_n \mid}, \frac{2na_0}{a_n}, \dots, \frac{2na_{n-1}}{a_n})=r</math> alors f(z)>M, c'est à dire <math> \lim_{\mid z \mid \longmapsto \infty} f(z)=\infty </math>.

'' Graphiquement '': Soit D={z/ lzl<r}, pour tout z n'appartenant pas à D f(z)>M. En particulier, il n'existe pas z n'appartenant pas à D tel que f(z)=0; z ≥ r n'est pas une racine.
::* Montrons qu'il existe z0 ∈ D tel que f atteint son minimum en z0.
::#f(D) ⊂ lR+ donc f(D) est une partie de lR minorée par 0. Par l'axiome de la borne inférieure, f(D) admet une borne inférieure.
::# Montrons que Inf(f(D)) est atteinte.
::## C est compact donc on peut trouver une suite z0, z1... ∈ D telle que f(zn) tend vers Inf(f(D)) quand n tend vers + ∞ .
::## f est une fonction continue car P(z) est continue, et z → lzl est continue?
::## <math> f(\lim_{n \rightarrow \infty}z_n)=\lim_{n \rightarrow \infty}(f(z_n))=Inf(f(D)) </math>. Soit m=Inf(f(D)) et soit <math>l= \lim_{n \rightarrow \infty}z_n</math>, f(l)=m et l ∈ D. f atteint son minimum en l ∈ D.
::# Montrons par l'absurde que m=Inf(f(D))=f(l)=0, c'est à dire trouvons z tel que lP(z)l<m alors que par hypothèse c'est impossible. Supposons que P n'a pas de racine. Posons Q(z)=P(z-l) et g(z)=f(z-l)=lQ(z)l.
::## g atteint son minimum en 0. Q(z)=b0+bpzp+...+bnzn où bp est le plus petit coefficient non nul autre que b0 ≠ 0, et lb0l=m.
::## On cherche z tel que bpzp=-b0C où C ∈ lR+ ⇔ <math> z^p=-C \frac{b_0}{b_p}=\lambda e^{i\theta} \Leftrightarrow z=\lambda ^{1/p}e^{i\theta /p} </math>
::## lbp+1zp+1+...+bnznl ≤ lzpl(lbp+1zl+lbp+2z2l+...+lbnzn-pl) or lbp+1zl ≤ lbp/(2n)l si lzl ≤ lbp/(2bp+qn)l ... lbp+qzql ≤ lbp/(2n)l si lzl ≤ min(1,lbp/(2nbp+ql), c'est à dire lbp/1zp+1+...+bnznl ≤ lbnzpl/2 si lzl ≤ min(1,lbp/(2nbp+1)l,...lb0/bql)=r.
::## Si on prend lzl=r, z=rei θ et bpzp=-b0C où C ∈ lR+. bp(rei θ )p=-b0C, ei θ =-cb0/(rpbp)=Kei ω . Pour que K=1, on prend lCl=lrpbp/b0l. D'où z=rei arg(-b0/bp)/p.
::## Q(z)=b0+bpzp+ ε avec ε ≤ lbpzp/2l. D'où bpzp=bprpei arg(-b0/bp)=-lbplrpei arg(b0). D'où Q(z)=(lb0l-lbprpl)ei arg(b0)+ε, soit Q(z) ≤ (lb0l-lbprpl)ei arg(b0)+lεl ≤ lb0l-lbprpl+lεl<lb0l<m

'' Conclusion '': P a une racine z0 telle que lQ(0)l=lP(z0-l)l=m=0, c'est à dire que P a une racine z0=l ∈ D.

===Fonctions polynômes/Polynômes===
* Un ''' polynôme ''' de degré d est un élément de lRd+1 : P=(a0,a1,...,ad) est un '' vecteur ''.
Il est néanmoins possible de faire quelques opérations supplémentaires sur les polynômes :
:*+ sur des vecteurs de taille différente
:*division euclidienne
:*produit
:*dérivation
* ''' Fonction polynôme ''' :

Soit P un polynôme à coefficients dans lK=C, lR, Q, Z/pZ
P(x) est une foction de lK → lK qui a x associe a0+a1x+...adxd si P=(a0,a1,...,ad)
* ''' Egalité de deux polynômes ''' :

Dans lR, C et Q, deux polynômes sont égaux si et seulement si les fonctions associées sont égales.
Ce n'est pas le cas dans Z/pZ.

'' Exemple '': dans Z/2Z, P=1+X+X2 et Q=1, x ∈ {0;1}.
P(0)=Q(1)=1 et P(0)=P(1)=1 donc les fonctions sont égales bien que les polynômes soient différents.

'' Remarque '' : Il existe 4 polynômes de degré 2 dans Z/2Z.
* ''' Dérivation ''' :

P' est une opération formelle sur les coefficients car <math>\lim_{h \longmapsto 0} \frac{P(x+h)-P(x)}{h}</math> n'a pas de sens dans Z/pZ.

Si P=(a0,a1,...,ad) (d°=d), alors P'=(a1,2a2,...,dad) (d°=d-1)
* ''' PGCD et polynômes de Bezout ''' :
:* '' Plus grand '' diviseur commun : celui qui a le plus grand degré (donc plus grand à une constante multiplicative près)
:* ''Remarques '' :
:# Stathme : valeur absolue dans Z, degré d'un polynôme ∈ lN
:# Pour les polynômes, l'algorithme d'Euclide st la preuve de l'existence du PGCD
:* Algorithme d'Euclide : preuve par récurrence sur d°P+d°Q
:# 0 &and; Q=Q et P &and; 0=P
:# Si d°P+d°Q=0 : les deux polynômes sont constants, P &and; Q=1=P=Q et donc P &and; Q existe
:# Hypothèse de récurrence : On suppose que P' &and; Q' existe pour tout P' et pour tout Q' tels que d°P'+d°Q' ≤ d°P+d°Q. On a d°P+d°Q>0
:## Supposons d°Q ≥ d°P (sinon on échange P et Q). On effectue la division puissance croissante de Q par P : Q=SP+R où d°R<d°P. Soit D un polynôme : si D l P et D l Q alors D l SP-Q=R; si D l P et D l R alors D l SP+R=Q. Ainsi l'ensemble des diviseurs communs de P et Q est celui des diviseurs de P et R.
:## Par récurrence P &and; Q existe ( puisque d°P+d°Q<d°P+d°P ≤ d°P+d°Q)
:* Polynômes de Bezout
:# Si P &and; Q=D alors ∃ U, V deux polynômes tels que UP+VQ=D
:# '' Existence '' : On remonte l'algorithme (par récurrence sur d°P+d°Q)
:## Si P=0 et Q <math>\neq</math> 0 : 0.P+1.Q=Q=P &and;Q
:## Si P <math>\neq</math>0 et Q=0 : 1.P+0.Q=P=P &and; Q
:## Si d°P+d°Q=0 : <math>P=a\neq 0</math> et <math>Q=b\neq 0</math> : a-1.a+0.b=1=P &and; Q
:## Si d°P+d°Q>0 avec d°P ≤ d°Q : Q=SP+R. Par récurrence, on a trouvé U et V tels que UP+VR=P &and; Q= P &and; R soit (U-VS)P+VQ=P &and; Q

===Construction d'un nouveau corps===
* Soit P un polynôme d'un corps lK. On peut quotienter lK[X] par P, c'est à dire poser P=0. On quotiente par la relation d'équivalence avoir même reste dans la division par P (même preuves que dans Z/nZ).

On obtient un corps si et seulement si P est irréductible, c'est à dire que P ne peut pas s'écrire P=QR avec d°Q>0 et d°R>0.
::'' Remarques :''
::: En d°2 et 3 : P est irréductible si et seulement si P n'a pas de racine
::: a racine de P si et seulement si (X-a) l P
* ''' Construction de F4 ''' : lK=Z/2Z
:* Dans Z/pZ :
:::Tous les polynômes de degré 2 sont de la forme X2+aX+b, donc il y a p2 polynômes.
:::Tous les polynômes réductibles de degré 2 sont de la forme (X-a)(X-b), donc il y a p(p+1)/2 polynômes.
:::(a+b)p=ap+bp
:*X2, X2+X=X(X+1), et X2+1=(X+1)2 sont réductibles, contrairement à X2+X+1.
:*On pose X2+X+1=0, soit X2=X+1

F4={0,1,X,X+1}={0,1,α,β}, donc 0={P(X2+X+1) l P ∈ lK[X]}, 1={P(X2+X+1)+1 l P ∈ lK[X]}, α={P(X2+X+1)+X l P ∈ lK[X]}, et β={P(X2+X+1)+X+1 l P ∈ lK[X]}.
<center>
{| border="1"
| + || 0 || 1 || α || β
|-
| 0 || 0 || 1 || α || β
|-
| 1 || 1 || 0 || β || α
|-
| α || α || β || 0 || 1
|-
| β || β || α || 1 || 0
|}

{| border="1"
| × || 0 || 1 || α || β
|-
| 0 || 0 || 0 || 0 || 0
|-
| 1 || 0 || 1 || α || β
|-
| α || 0 || α || β || 1
|-
| β || 0 || β || 1 || α
|}
</center>
* ''' Construction de <math>\mathbb{C}</math> ''' : lK=lR
:*P=1+X2 est irréductible : X2=-1 et on pose X=i

Tous les restes de la division par 1+X2 sont de la forme a+bX=a+ib

D'où <math>\mathbb{C}</math>=P[lR]/1+X2={a+ib l a,b ∈ lR}
:*<math>\mathbb{C}</math>=P[lR]/1+X+X2={a+jb l a,b ∈ lR}

==Permutations==
===Définition===
Une permutation est une bijection sur un ensemble fini. On note Sn l'ensemble des permutations de {1,2,...,n}
===Notation===
<math> \sigma=\begin{pmatrix}1 & 3 & 4 & 5 & 2 \\ 2 & 4 & 1 & 3 & 5\end{pmatrix} </math>. Sur chaque ligne figurent une fois tous les éléments de 1 à n. σ(1)=2 et σ-1(2)=1.
===Composition===
*Si σ, σ' ∈ Sn alors σ•σ' est aussi une permutation.

idn ∈ Sn : <math> id_n=\begin{pmatrix}1 & 2 & 3 & \dots & n \\ 1 & 2 & 3 & \dots & n\end{pmatrix} </math>

σ•id=σ (id est neutre pour •), σ•σ-1=id
*{Sn,•} est un groupe non commutatif.
:*<math> S_2=\{\begin{pmatrix}1 & 2 \\ 1 & 2 \end{pmatrix},\begin{pmatrix}1 & 2 \\ 2 & 1 \end{pmatrix} \}=\{ id_2, \sigma \} </math>, où σ•σ=id
:*<math> S_3=\{ (132),(213), (321), (123), (231), (312) \} </math>
===Support de σ===

===Transposition===

===Signature===

==Corrections de quelques exercices==

===Feuille 4 - Exercice 5===

<math>P(X) = X^5 + 3X^4 + X^3 + X^2 + 3X + 1</math> et
<math>Q(X) = X^4 + 2X^3 + X + 2</math>

Après une division, on trouve : <math>P(X) = Q(X)(X + 1) + R(X)</math> avec
<math>R(X) = -X^3 - 1</math>

On effectue une seconde division : <math>Q(X) = R(X)(-X-2) + 0</math>

Donc un pgcd de <math>P(X)</math> et <math>Q(X)</math> est <math>X^3 + 1</math>.

On a donc <math>-P(X) + (X+1)Q(X) = X^3 + 1</math>

===Feuille 4 - Exercice 6===

<math>P(X) = X^3 + X^2 - X - 1</math> a pour racine évidente 1 et -1 et on trouve par identification
<math>P(X) = (X^2 - 1)(X + 1) = (X - 1)(X + 1)^2</math>

<math>Q(X) = X^4 + X^3 - 3X^2 - 4X - 1</math> n'a pas 1 pour racine, mais il admet -1 comme racine et
on trouve <math>Q(X) = (X + 1)(X^3 - 3X - 1)</math>. <math>X^3 - 3X - 1</math> lui n'admet ni 1 ni -1 comme
racine.

Donc le seul facteur commun entre <math>P(X)</math> et <math>Q(X)</math> est <math>X + 1</math> qui
est donc un pgcd de <math>P(X)</math> et <math>Q(X)</math>.

Décomposer les polynômes ne permet pas de trouver des "polynômes de Bezout".

On utilise alors l'algorithme d'Euclide:

<math>Q(X) = P(X)X -2X^2 -3X - 1</math> puis

<math>{P(X) = (2X^2 + 3X + 1)((1/2)X - 1/4) - (3/4)X - 3/4}</math>

On retrouve le même pgcd à un facteur multiplicatif près, mais on peut écrire:

<math>3X + 3 = (2X^2 + 3X + 1)(2X - 1) - 4P(X)</math>

<math>3X + 3 = (XP(X) - Q(X))(2X - 1) - 4P(X)</math>

<math>3X + 3 = (-2X + 1)Q(X) + (2X^2 - X - 4)P(X)</math>

et donc au final

<math>X + 1 = (1/3)(-2X + 1)Q(X) + (1/3)(2X^2 - X - 4)P(X)</math>

Wiki du LAMA (UMR 5127) - Contributions [fr]

Discussion:INFO421 : Programmation fonctionnelle

MATH203 : Introduction à l'algèbre