T.2 · Mathématiques discrètes, probabilités et méthodes numériques

Préparation GRE niveau universitaire. Objectifs locaux dans le périmètre ETS examiné ; il s'agit d'un enseignement original, pas d'un test officiel ni d'un prédicteur de score.

Prérequis : Comptage fini, probabilités élémentaires, récurrences et dérivées.

• Utiliser le comptage, les récurrences, le raisonnement sur les graphes et la logique
• Calculer des probabilités et des propriétés de distribution
• Appliquer une approximation numérique et évaluer l'erreur

récurrence : Une règle reliant un terme d'une suite à ses termes précédents.

mutuellement exclusifs : Des événements qui ne peuvent pas se produire simultanément.

Choisir d'abord le modèle de dénombrement : les sélections ordonnées de r objets distincts parmi n utilisent n(n−1)⋯(n−r+1), tandis que les sous-ensembles non ordonnés utilisent C(n,r). Un graphe simple complet sur n sommets possède une arête par paire non ordonnée de sommets, soit n(n−1)/2 arêtes ; des boucles ou des arêtes multiples modifieraient ce modèle. Pour n droites en position générale dans un plan, la k-ième droite coupe les k−1 droites précédentes en points distincts et ajoute k régions. Le total est 1+n(n+1)/2 ; des parallèles ou une triple concourance invalident ce décompte.

Utilisez les compléments pour compter au moins une occurrence, et conditionnez sur la population restante réelle après un tirage sans remise. Pour r résultats i.i.d. choisis parmi n valeurs également probables, la probabilité que tous soient distincts est n(n−1)⋯(n−r+1)/n^r lorsque r≤n. Son complément compte les occurrences répétées. Pour un décompte binomial avec N essais indépendants et une probabilité de succès fixe p, la moyenne est Np et la variance Np(1−p). Des probabilités identiques seules n'établissent pas l'indépendance.

Une récurrence décrit les valeurs futures à partir des valeurs passées et nécessite assez de données initiales pour déterminer une suite. Séparer l'indice de la valeur : a_n=2a_(n−1) avec a_0=3 donne a_n=3·2^n. Les arguments graphiques et algorithmiques établissent souvent une récurrence en identifiant ce qu'un nouveau sommet ou étape ajoute. Une formule fermée doit satisfaire à la fois la récurrence et ses conditions initiales ; ajuster quelques termes observés ne prouve pas sa validité pour tout indice.

L'approximation numérique nécessite un argument d'erreur. La bissection conserve un intervalle de changement de signe pour une fonction continue et en divise la largeur à chaque étape ; une racine peut être absente si la continuité fait défaut. L'itération de Newton est x_new=x−f(x)/f′(x), nécessitant une dérivée non nulle au point courant ; la convergence n'est pas automatique depuis toute valeur initiale. Le résidu d'une approximation et son erreur en x sont différents. Énoncer les hypothèses de la méthode et un critère d'arrêt plutôt que considérer les décimales affichées supplémentaires comme une précision.

Pour f(x)=x²−2 et x₀=1, l'itération de Newton donne 1−(1−2)/2=1.5. La valeur suivante est 1.5−0.25/3=1.4167. Ces valeurs approchent sqrt(2), mais f′(0)=0 rend zéro un point de départ invalide.

Les événements à probabilités positives ne peuvent être à la fois indépendants et mutuellement exclusifs.

Quatre tirages étiquetés sont indépendants et uniformes parmi cinq symboles, avec remise. Trouver la probabilité qu'au moins deux tirages coïncident. Comparer le nombre de sélections ordonnées et non ordonnées de quatre symboles distincts.

Solution détaillée

Il y a $5^4$ chaînes de tirage ordonnées également probables. Le nombre de chaînes sans répétition est $5\cdot4\cdot3\cdot2=120$.

Les sélections ordonnées distinctes comptent 120 ; les sous-ensembles non ordonnés comptent $\binom54=5$. Chaque sous-ensemble apparaît dans $4!=24$ ordres. Diviser par $4!$ est approprié uniquement pour le décompte non ordonné, pas pour le dénominateur de probabilité du tirage.

Appliquer la bissection à $f(x)=x^3-2$ sur $[1,2]$. Donner les deux premiers intervalles conservés et une borne d'erreur du milieu après dix bissections. Un seul changement de signe justifierait-il la bissection pour $1/x$ sur $[-1,1]$ ?

Vérification après tentative

Le polynôme est continu ; $f(1)<0<f(2)$. Le premier milieu est $1.5$ avec valeur positive, conservant $[1,1.5]$. Le suivant est $1.25$ avec valeur négative, conservant $[1.25,1.5]$. Après dix divisions par deux, la largeur est $2^{-10}$ et le milieu de cet intervalle conservé diffère de la racine encadrée d'au plus $2^{-11}=1/2048$. La borne d'erreur utilise l'intervalle, pas seulement un résidu faible. Pour $1/x$, zéro est une singularité et il n'y a pas de racine. La continuité sur l'intervalle fait défaut ; des signes opposés aux extrémités ne justifient pas la méthode.