17 Questions
Quel est l'objectif de la technique algorithmique DIVISER POUR RÉGNER?
Diviser un problème en parties plus petites, les résoudre puis les combiner pour obtenir la solution au problème initial
Qu'est-ce que la récursivité en informatique?
Une fonction qui s'appelle elle-même pour résoudre un problème de manière itérative
Quelle est la principale caractéristique de la récursivité terminale?
Elle s'appelle elle-même pour résoudre un problème sans utiliser une pile d'exécution
Comment peut-on définir une entité comme étant récursive?
Lorsqu'on l'utilise pour se définir elle-même
Quelle est la stratégie suivie par la technique algorithmique DIVISER POUR RÉGNER?
Diviser le problème initial en parties plus petites, les résoudre (récursivement ou directement) et ensuite les combiner pour obtenir la solution au problème initial
Quel est le principe de base de la technique algorithmique DIVISER POUR RÉGNER?
Diviser un problème en parties plus petites, résoudre ces parties puis les combiner pour obtenir la solution au problème initial
Qu'est-ce que la récursivité permet de faire ?
Résoudre un problème complexe en le décomposant en problèmes plus petits de même nature.
Que doit contenir un algorithme récursif?
Une expression évaluable sans appel récursif.
Combien de types de récursivité existe-t-il?
Quatre
Qu'est-ce que la récursivité simple ?
Une définition récursive contenant un seul appel récursif.
Quelle est la fonction du sous-algorithme Factorielle n ?
$n * Fact(n - 1)$
Dans quelle condition la fonction Fibonacci retourne-t-elle n ?
$n < 2$
Qu'est-ce que la récursivité mutuelle ?
Des définitions mutuellement dépendantes les unes des autres.
Quelle est la fonction du sous-algorithme Pair qui retourne Vrai si n = 0 ?
$Pair(n-1)$
Quelle est la fonction du sous-algorithme Impair qui retourne Faux si n = 0 ?
$Impair(n-1)$
'La récursivité est imbriquée si...'
'un sous-algorithme récursif contient un appel imbriqué.'
'Quelle valeur retourne la fonction Ackermann lorsqu'on a n = 0 ?'
'p+1'
Study Notes
Technique algorithmique DIVISER POUR RÉGNER
- L'objectif de la technique algorithmique DIVISER POUR RÉGNER est de résoudre un problème complexe en le divisant en sous-problèmes plus petits et plus simples.
- La stratégie suivie par cette technique consiste à diviser un problème en sous-problèmes, à résoudre chaque sous-problème, puis à combiner les solutions pour obtenir la solution finale.
- Le principe de base de la technique algorithmique DIVISER POUR RÉGNER est de réduire un problème complexe en sous-problèmes plus faciles à résoudre.
Récursivité
- La récursivité en informatique est une technique de programmation qui consiste à appeler une fonction dans elle-même pour résoudre un problème.
- La récursivité permet de décomposer un problème complexe en sous-problèmes plus simples et de résoudre chaque sous-problème de manière récursive.
- Une entité est dite récursive si elle est définie en termes d'elle-même.
- La récursivité terminale est une propriété de la récursivité où la fonction s'arrête de s'appeler elle-même lorsque certaines conditions sont remplies.
Types de récursivité
- Il existe deux types de récursivité : la récursivité simple et la récursivité mutuelle.
- La récursivité simple est une forme de récursivité où une fonction s'appelle elle-même de manière directe.
- La récursivité mutuelle est une forme de récursivité où deux ou plusieurs fonctions s'appellent mutuellement.
Exemples de récursivité
- La fonction Factorielle n est un exemple d'algorithme récursif qui calcule la factorielle d'un entier n.
- La fonction Fibonacci est un exemple d'algorithme récursif qui calcule le n-ième terme de la suite de Fibonacci.
- La fonction Ackermann est un exemple d'algorithme récursif qui prend deux entiers en entrée et retourne une valeur.
Conditions de récursivité
- Un algorithme récursif doit contenir au moins une condition d'arrêt pour éviter une boucle infinie.
- La fonction Pair retourne Vrai si n est pair, c'est-à-dire si n = 0 ou si n est divisible par 2.
- La fonction Impair retourne Faux si n = 0 ou si n est impair.
- La fonction Ackermann retourne une valeur lorsqu'on a n = 0.
Explore the course plan for Algorithm II taught by Pr. Ilyass OUAZZANI TAYBI at University Cadi Ayyad, covering topics such as arrays, functions, recursion, sorting algorithms, pointers, files, and algorithm complexity.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
