مسابقة دكتوراه 2014 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 01

مسابقة تخصص · Algèbre · المدة: 2سا

Concours Cycle D Maths Fondamentales et Cryptographie 2014-15, Épreuve de Complexité, Faculté de Mathématiques, USTHB, 13 octobre 2014, durée 2h.

التمرين 1

Exercice 1 — Ordres de croissance et sommes

#asymptotic-analysis#big-o-notation#summation#binomial-coefficients

Classer dans l'ordre croissant : $4^n;\ n+n!;\ \left(1+\tfrac1n\right)^n;\ n^{2n};\ (n!)^2;\ n^3$ . Justifier.
Évaluer les sommes $\displaystyle\sum_{i=0}^{n}\dfrac{1}{(i+2)(i+3)}$ ; $\displaystyle\sum_{i=0}^{n} i^2 3^i$ ; $1+C_n^4+C_n^8+\cdots$
Trouver $f:\mathbb{N}\to\mathbb{R}^+$ telle que $n^{\alpha}=O(f(n))$ et $f(n)=O(\beta^n)$ pour tous $\alpha\gt0,\ \beta\gt1$ . Conclure.
Montrer que $\forall(m,n)\in\mathbb{N}^2,\ \dfrac{(2m)!(2n)!}{m!\,n!\,(m+n)!}\in\mathbb{N}$ .

◀الحل

$\boxed{(1+\tfrac1n)^n\lt n^3\lt 4^n\lt n+n!\lt (n!)^2\lt n^{2n}}$ .
$\sum\frac{1}{(i+2)(i+3)}=\frac12-\frac{1}{n+3}$ (télescopage) ; $1+C_n^4+\cdots=2^{n-2}+2^{n/2-1}\cos\frac{n\pi}{4}$ .
$f(n)=\beta^n$ convient : le polynomial est dominé par l'exponentiel.
Entier par la valuation $p$ -adique (Kummer).

Exercice 2 — Récurrences et complexité d'algorithmes

#recurrence-relations#master-theorem#generating-functions#algorithm-complexity

Signification algorithmique puis résoudre $t(n)=7t(n/2)+2n^2$ , $t(1)=1$ .
i) Résoudre $t(n+3)-4t(n+2)+t(n+1)+6t(n)=0$ , $t(0)=1,t(1)=0,t(2)=6$ . ii) Par séries génératrices $t(n)=2t(n-1)+3t(n-2)$ , $t(0)=0,t(1)=1$ .
$u_0=u_1=1,\ u_{n+2}=2u_{n+1}+4u_n$ : algorithmes récursif puis itératif et leurs complexités.
Complexité de $f(n,m)$ : si $(m=n)$ ou $(m=0)$ alors $1$ sinon $f(n,m-1)+f(n-1,m-1)$ .

◀الحل

Exercice 3 — Recherche dichotomique et paires

#binary-search#divide-and-conquer#algorithm-design

Algorithme en $O(\log_2 n)$ testant si $val$ est dans un tableau trié de taille $n$ .
$S$ ensemble de $n\ge2$ entiers dans $V$ : a) $O(n)$ trouvant $x,y$ avec $|x-y|$ maximal ; b) $O(n\log_2 n)$ trouvant $x\ne y$ avec $|x-y|$ minimal ; c) $O(n\log_2 n)$ testant s'il existe $x,y$ avec $x+y=m$ .

◀الحل

Recherche dichotomique.
a) $x=\max,\ y=\min$ en $O(n)$ . b) Trier puis comparer voisins consécutifs. c) Trier puis deux pointeurs (début/fin) : $O(n\log n)$ .

Exercice 4 — Complexité binaire, SAT et NP

#computational-complexity#sat#np-completeness

Évaluer la complexité binaire du produit de deux entiers. 2. Décrire le problème de satisfiabilité SAT. 3. Donner la définition d'un problème NP.

◀الحل

$O(n^2)$ bits (Karatsuba $O(n^{\log_2 3})$ ). 2. SAT : existe-t-il une affectation rendant vraie une formule booléenne (FNC) ? 3. NP : solution vérifiable en temps polynomial par un certificat.