tc_info:2020_td_comp

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision		 Révision précédente
tc_info:2020_td_comp [2020/09/30 15:36] – ppreatc_info:2020_td_comp [2020/09/30 15:57] (Version actuelle) – pprea
Ligne 1: Ligne 1:
 +====== TD "Complexité & Preuves de Programmes" ======
 +
 +
 +===1. Addition ===
 +
 +Donnez deux algorithmes qui additionnent deux nombres entiers. 
 +
 +  * Un premier qui est celui utilisé quand on fait une addition "à la main" [[2020_CPP_1-1|Indications]]
 +  * Un deuxième qui utilise d'autres "fonctions de base" [[2020_CPP_1-2|Indications]]
 +
 +Comparez les complexités de ces algorithmes. [[2020_cpp_1-3|Solution (important)]]
 +
 +
 +===2. Puissance ===
 +
 +Donnez deux algorithmes, un itératif ([[2020_cpp_2-1-1|Solution]]) & un récursif ([[2020_cpp_2-1-2|Solution]]), rendant, à partir de deux entiers positifs $x$ & $y$, le nombre $x^y$. 
 +
 +Donnez leurs complexités. [[2020_cpp_2-2|Solution]]
 +
 +Prouvez les. [[2020_cpp_2-3|Solution]]
 +
 +
 +===3. Maximum d'un tableau ===
 +
 +Donnez deux algorithmes, un itératif ([[2020_cpp_3-1|Solution]]) & un récursif ([[2020_cpp_3-2|Solution]]), qui calculent la plus grande valeur d'un tableau de nombres. 
 +
 +Comparez leurs fonctionnements. [[2020_cpp_3-3|Solution]]
 +
 +
 +===4. Algorithme Mystère ===
 +
 +On considère l'algorithme suivant:
 +
 +def $misterioso(A, B)$:\\
 +$\;\;\;\;$ # $A$ & $B$ sont des entiers positifs\\
 +$\;\;\;\;$ $x \gets A ;\, y \gets B ;\, r \gets 1$ \\
 +$\;\;\;\;$ # Ligne 1 \\
 +$\;\;\;\;$ while $y \neq 0$: \\
 +$\;\;\;\;$ $\;\;\;\;$ # Ligne 2 \\
 +$\;\;\;\;$ $\;\;\;\;$ if $y$ impair: \\
 +$\;\;\;\;$ $\;\;\;\;$ $\;\;\;\;$ $r \gets r \times x$\\
 +$\;\;\;\;$ $\;\;\;\;$ $\;\;\;\;$ $y \gets y -1$ \\
 +$\;\;\;\;$ $\;\;\;\;$ else:\\
 +$\;\;\;\;$ $\;\;\;\;$ $\;\;\;\;$ $x \gets x\times x$\\
 +$\;\;\;\;$ $\;\;\;\;$ $\;\;\;\;$ $y \gets y /2$\\
 +$\;\;\;\;$ $\;\;\;\;$ # Ligne 3 \\
 +$\;\;\;\;$ # Ligne 4 \\
 +$\;\;\;\;$ return $r$\\ 
 +
 +
 +Que fait cet algorithme  ([[2020_cpp_4-1|indication]]) ?
 +Justifiez votre réponse. [[2020_cpp_4-2|Réponse]]
 +
 +
 +Quelle sa complexité dans le cas le meilleur ([[2020_cpp_4-2-1|indication]]), le pire ([[2020_cpp_4-2-2|indication]]), en moyenne ?
 +
 +
 +===5. Tris Naïfs ===
 +
 +Prouvez les algorithmes de tris simples vus en cours (tri par sélection & tri par insertion)
 +
 +[[2020_cpp_5-1|Indications]]
 +
 +
 +===6. Palindromes ===
 +
 +Implémentez un algorithme récursif permettant de savoir si un tableau de caractères est un palindrome (un palindrome se lit "à l'endroit" & "à l'envers" de la même façon, comme par exemple "À l'étape, épate-la !" (on considère ni la ponctuation, ni les  espaces, ni les accents)). Quelle est sa complexité?
 +
 +[[2020_cpp_6-1|Solution]]
 +
 +
 +===7. Tours de Hanoï ===
 +
 +Les //tours de Hanoï// sont un célèbre casse tête qui consiste à déplacer $n$ disques de diamètres différents d'une tour de "départ" à une tour d' "arrivée" en passant par une tour "intermédiaire", tout en respectant les règles suivantes :
 +
 +    * on ne peut déplacer qu'un disque à la fois,
 +    * on ne peut placer un disque sur un disque plus petit que lui.
 +   
 +On suppose que cette dernière règle est également respectée dans la configuration de départ.    
 +
 +
 +Donnez un algorithme récursif permettant de résoudre le problème. Quelle est sa complexité? Peut-on faire mieux?
 +
 +[[2020_cpp_7|Indication]]
 +
 +
 +
 +
 +
 +
 +