C’est quoi un programme itératif ? Comment je vérifie qu’il se termine bien ?
Soit la fonction qui cherche un élément dans une liste, montrer la terminaison de ce programme
On prend un variant de boucle (un entier qui décroît a chaque itération de la boucle et qui atteindra 0, par exemple n-i). Et du coup, à chaque tour, l’entier décroît de 1. Si l’élément est trouvé, on quitte la boucle sinon on a n-n = 0
C’est quoi la correction d’un programme ?
On veut vérifier que l’algorithme vérifie la tache souhaitée avec un raisonnement proche de celui par récurrence.
On choisit un invariant de boucle qui dépend de i (par exemple Pᵢ : res=i!)
• avant la boucle i=1 : P₁ = 1! (C’est bon)
• si Pᵢ vraie, on passe dans la boucle, on a bien la prop …
• en fin de boucle, i = n, on a bien Pₙ : res=n!
Calcule la complexité pour le programme suivant
C’est combien la complexité de return True ? Dans une boucle, on calcule comment la complexité ?
0 !
On calcule la complexité de la taille parcourue par la boucle qu’on multiplie avec la complexité qu’on a dans la boucle
Explique pourquoi la complexité de ce programme est si grande et comment l’améliorer
Toute la complexité est concentrée sur la boucle for exécutée n fois. Or, à l’intérieur, on calcule à chaque fois moyenne(liste_hauteurs), la complexité est donc en O(n²) !
Décompose 21 en base 2
21 % 2 =1
10 % 2 =0 (quotients)
5 % 2 =1
2 % 2 =0
1 % 2 =1
21 s’écrit 10101 en base 2
Démontre la terminaison
Écris une fonction nombreZeros(L,i) qui prend une liste L, un indice i compris entre 0 et n-1 et retourne 0 si L[i] = 0 ou le nombre consequtifs de zéros dans L à partir de L[i] si L[i] = 0
Fais une fonction recherche_mot(texte,mot) qui renvoie si le mot est présent dans le texte et l’incide de la première lettre de mot dans le texte
Calcule le nombre de Fibonacci en récursif “Top Down”
Calcule le nombre de Fibonacci en itératif “Bottom up”
Quand on te demande en quoi un algorithme récursif utilise la méthode “diviser pour régner”
Diviser : on décompose le problème initial en un sous problème (un calcul antérieur).
Régner : on traite recursivement les problèmes antérieurs
Combiner : on combine les différents problèmes pour résoudre le problème de départ
Comment tu caractériserais un algorithme glouton ?
Dans la méthode gloutonne, on effectue une succession de choix, chacun d’eux semble être le meilleur sur le moment. On résout alors le sous problème mais on ne revient jamais sur le choix effectué
Cours
Cours
Écrire une fonction rec_double qui prend en argument une fonction f qui définie une récurrence double, u0, u1 et n) qui renvoie le nième terme de la récurrence
Cours
Écrire une fonction trouve qui prend en argument seq une liste et a qui renvoie True si l’élément a est présent sans seq et False sinon. Pour quels autres objets qu’une liste cette fonction peut elle continuer à fonctionner ?
Comment on écrit infini ?
Float(‘inf’)
