Exemples dalgorithmes récursifs 1 Des exercices sur les suites
Stage d'Algorithmique. Exemples d'algorithmes récursifs. Les programmes sont disponibles dans l'archive associée. Par exemple algo1Rtrous.sce désigne la
Examen dalgorithmique
30 Jan 2008 (2 points) Proposez un algorithme récursif retournant true si et seulement si l'arbre binaire passé en argument est un Arbre Binaire de ...
Algorithmique Récursivité
1 de 11. Algorithmique. Récursivité. Florent Hivert. Mél : Florent.Hivert@lri.fr. Adresse universelle : http://www.lri.fr/˜hivert
Algorithmes et programmation II : La récursivité
Algorithmes et programmation II : La récursivité Une fonction récursive est une fonction qui s'appelle elle-même. ... Test factorielle :.
Correction TD 09 : Algorithmes récursifs
Les algorithmes log et somme sont récursifs : chacun contient au moins un appel `a lui même par contre
Corrigé de la Fiche de TD Récursivité Exercice 1
Corrigé de la Fiche de TD Récursivité. Exercice 1 a) Déroulez les procédures récursives suivantes pour k=6 : Procédure test (?k : entier).
Examen dalgorithmique
30 Jan 2008 (2 points) Proposez un algorithme récursif retournant true si et seulement si l'arbre binaire passé en argument est un Arbre Binaire de ...
Examen dalgorithmique
2. Décrire ce que fait l'algorithme P appelé avec le param`etre 22. Exercice 2 : Dérouler un algorithme récursif (4 points).
Algorithmes récursifs - Licence 1 MASS - Introduction
3 May 2013 Algorithmes récursifs. Résolution de probl`emes par récursivité. Objectifs de la séance 11. Ecrire un algorithme récursif avec un seul test.
L3 Math-Info Algorithmique: examen terminal
L3 Math-Info Algorithmique: examen terminal. 17 décembre 2020 Un algorithme faisant 4 appels récursifs sur des instances de taille.
CHAPITRE 1 LA RECURSIVITE
2 LMD Classique Algorithmique et SDD Chapitre 1 : La récursivité CC : GOLEA N H Page 1 CHAPITRE 1 LA RECURSIVITE 1 Introduction : La récursivité est une notion importante de la programmation qui permet de régler des problèmes extrêmement complexes avec seulement quelques lignes
Algorithmes et programmation II : La récursivité
Principe de la récursivité I Décomposer le problème en un problème plus simple)réduire la taille du problème considéré I Pour la récursion sur des entiers : la taille du problème est dé nie par un entier on réduit la valeur de cet entier à chaque appel récursif I Pour la récursion sur les tableaux :
Searches related to examen algorithmique récursivité PDF
UE J1BS7202 : Algorithmique et Programmation Epreuve : Examen Date : Jeudi 19 d ecembre 2013 Heure : 9 heures Dur ee : 2 heures Documents : autoris es Epreuve de M Alain Griffault SUJET + CORRIGE Avertissement {La plupart des questions sont ind ependantes { A chaque question vous pouvez au choix r epondre par un algorithme ou bien par un
Comment définir un algorithme récursif?
Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même. Dans le cadre de ce cours, nous ne nous intéresserons qu’aux programmes et algorithmes récursifs. Mais la notion de définition récursive est beaucoup plus générale : en mathématiques : définition de l’exponentielle : ? x ? R, f 0 ( x) = f ( x) et f (0) = 1.
Quelle est la seconde règle de conception d’un algorithme récursif?
D’où la seconde règle de conception d’un algorithme récursif : Tout appel récursif doit se faire avec des données plus proches de données satisfaisant les conditions de terminaison. La remarque suivante est assez utile, lorsqu’on souhaite prouver qu’un algorithme récursif s’arrête.
Qu'est-ce que la récursivité ?
CHAPITRE 1 LA RECURSIVITE 1. Introduction : La récursivité est une notion importante de la programmation qui permet de régler des problèmes extrêmement complexes avec seulement quelques lignes. C’est cependant une méthode avec laquelle il est facile de se perdre et d’avoir des résultats imprévisibles ou erronés.
Comment prouver la terminaison d'un algorithme récursif ?
Dans le cas des algorithmes récursifs, ces méthodes sont spécifiques. Pour prouver la terminaison d'un algorithme récursif, la méthode la plus usuelle est la suivante: chacun des ensembles dans lesquels les paramètres prennent leurs valeurs sont équipés d'une relation d'ordre.
L3 Math-Info, Algorithmique: examen terminal
17 d´ecembre 2020Tout document manuscrit de cours autoris´e.
T´el´ephones portables et autres outils de t´el´ecommunication interdits.Le bar`eme sur 27 (24+3pt bonus) produira la note sur 20, il n"est donc pas n´ecessaire de traiter tout le+
sujet pour avoir la note maximale.La qualit´e de la r´edaction sera ´evalu´ee au mˆeme niveau que l"exactitude des r´eponses.
Dur´ee : 2h.Exercice 1. QCM (4 points)
R´eponse correcte : +0,5pt, r´eponse incorrecte : -0,25pt, NSP ou sans r´eponse : 0pt.Vrai Faux NSP
L"insertion d"un ´el´ement dans un tas de taillense fait toujours enO(logn) L"algorithmePour i=1`a n-1: Pour j=0`a i-1:
Si T[i] faitO(nL faitO(n2L ) d´efauts de cache sin > Z Calculer la somme d"un tableau de taillen > Zfait?nZ ?+ 1 d´efauts de cache Un algorithme faisant 4 appels r´ecursifs sur des instances de taille moiti´e et un nombre lin´eaire d"additions a un coˆutO(nlogn) Le tri par tas coˆuteO(nlogn) en pire cas En programmation dynamique, les variantes r´ecursives et it´eratives ont toujours
mˆeme coˆut en m´emoire La multiplication bas´ee sur la FFT r´epose sur un sch´ema d"´evaluation-interpolation Exercice 2. Parcours d"arbres (3 pts)
SoitAl"arbre binaire de recherche obtenu en ins´erant it´erativement aux feuilles les ´el´ements du tableau
<5,2,7,6,4,9,3,8>. a.(1pt) Repr´esenterA. b.(2pt) Indiquer ce que donne l"application de la m´ethodeaffichesur l"arbreAsuivant un parcours 1. en profondeur prefixe
2. en profondeur infixe
3. en profondeur postfixe
4. en largeur
Exercice 3. Transposition de matrices (8 points)On s"int´eresse au coˆut en d´efauts de cache des algorithmes calculant la transpos´ee d"une matrice :
B←ATo`uAest de dimensionsm×n. Le mod`ele de cache est celui vu en cours : on suppose un cache
`a 1 niveau, de tailleZavec des lignes de longueurL(etLdiviseZ). a.(1pt) Combien de lignes de caches sont occup´ees par les entr´ees-sorties? En d´eduire une borne
inf´erieure de la complexit´e cache pour cette op´eration. b.(1pt) Proposer un algorithme (na¨ıf) traitant la matriceAligne `a ligne.UGA - L3 Maths/Info - Algorithmique - Cl´ement Pernet Page 1/2
c.Donner sa complexit´e en d´efauts de cache selon que 1. (0.5pt) les deux matrices tiennent dans le cache : 2n2< Z.
2. (1pt) une ligne de A et une colonne deBtiennent dans le cache :nL+n < Z.
3. (1pt) une colonne de B ne tient pas dans le cache :nL > Z.
d.(2.5pt) Proposer un algorithme cache aware, bas´e sur une d´ecoupe en blocsK×K. On supposera
queKest suffisament petit pour que 2 blocksK×Ktiennent dans le cache. e.(1) Analyser son coˆut en d´efauts de cache. f.(Bonus) (3pt) Proposer une variante r´ecursive cache-oblivious. Analyser son coˆut cache. Exercice 4. Plus longue sous-s´equence commune (9 points)´ Etant donn´ees deux chaˆınes de caract`eres (repr´esent´ees par des tableaux de caract`eres)AetBde
longueursmetn, on souhaite trouver leur Plus Longue Sous-S´equence Commune (PLSSC), c"est `a dire la sous-chaˆıne de caract`eres la plus longue commune `aAetB. Noter que les lettres d"une sous-s´equence
doivent ˆetre dans le mˆeme ordre que dans la s´equence d"origine. Par exemple les chaˆınes"ELLE A AIM´E LES ALGORITHMES"et"IL A MANG´E HIER"ont pour PLSSC "L A MAGIE". Pour une chaˆıne de caract`ereS=< s0,s1,...,sn-1>de longueurn, on noteraSila sous-chaˆıne de
Scommen¸cant en positioni:Si=< si,si+1,...,sn-1>. AinsiS0=SetSn-1=< sn-1>. On d´efinit la fonctionc(i,j) comme ´etant la longueur de PLSSC aux chaˆınesAietBj. a.(1pt) Justifier les relations r´ecurrentes suivantes : ??c(m,j) = 0 c(i,n) = 0 c(i,j) = 1 +c[i+ 1,j+ 1] siai=bjeti < m,j < n c(i,j) = max(c[i+ 1,j],c[i,j+ 1]) siai?=bjeti < m,j < n b.(1pt) En d´eduire un algorithme r´ecursif calculant la longueur de la PLSSC de deux chaˆınes.
c.(1pt) Justifier bri`evement qu"il fait des appels redondants et que sa complexit´e est exponentielle.
d.(1pt) Modifier l"algorithme de la questionc.(par exemple en l"annotant) pour lui ajouter de la m´emo¨ısation. e.(1pt) Quel est son coˆut en temps et en m´emoire. f.(2pt) Proposer un algorithme it´eratif bas´e sur une m´ethode de programmation dynamique, calculant
la longueur de la PLSSC ainsi que les informations n´ecessaires `a la construction de cette PLSSC.
g.(1pt) Quel est son coˆut en temps et en m´emoire. h.(1pt) Proposer un algorithme calculant cette PLSSC `a partir de ces informations.UGA - L3 Maths/Info - Algorithmique - Cl´ement Pernet Page 2/2
quotesdbs_dbs41.pdfusesText_41
moiti´e et un nombre lin´eaire d"additions a un coˆutO(nlogn) Le tri par tas coˆuteO(nlogn) en pire cas En programmation dynamique, les variantes r´ecursives et it´eratives ont toujours
mˆeme coˆut en m´emoire La multiplication bas´ee sur la FFT r´epose sur un sch´ema d"´evaluation-interpolation Exercice 2. Parcours d"arbres (3 pts)
SoitAl"arbre binaire de recherche obtenu en ins´erant it´erativement aux feuilles les ´el´ements du tableau
<5,2,7,6,4,9,3,8>. a.(1pt) Repr´esenterA. b.(2pt) Indiquer ce que donne l"application de la m´ethodeaffichesur l"arbreAsuivant un parcours1. en profondeur prefixe
2. en profondeur infixe
3. en profondeur postfixe
4. en largeur
Exercice 3. Transposition de matrices (8 points)On s"int´eresse au coˆut en d´efauts de cache des algorithmes calculant la transpos´ee d"une matrice :
B←ATo`uAest de dimensionsm×n. Le mod`ele de cache est celui vu en cours : on suppose un cache
`a 1 niveau, de tailleZavec des lignes de longueurL(etLdiviseZ).a.(1pt) Combien de lignes de caches sont occup´ees par les entr´ees-sorties? En d´eduire une borne
inf´erieure de la complexit´e cache pour cette op´eration.b.(1pt) Proposer un algorithme (na¨ıf) traitant la matriceAligne `a ligne.UGA - L3 Maths/Info - Algorithmique - Cl´ement Pernet Page 1/2
c.Donner sa complexit´e en d´efauts de cache selon que1. (0.5pt) les deux matrices tiennent dans le cache : 2n2< Z.
2. (1pt) une ligne de A et une colonne deBtiennent dans le cache :nL+n < Z.
3. (1pt) une colonne de B ne tient pas dans le cache :nL > Z.
d.(2.5pt) Proposer un algorithme cache aware, bas´e sur une d´ecoupe en blocsK×K. On supposera
queKest suffisament petit pour que 2 blocksK×Ktiennent dans le cache. e.(1) Analyser son coˆut en d´efauts de cache. f.(Bonus) (3pt) Proposer une variante r´ecursive cache-oblivious. Analyser son coˆut cache. Exercice 4. Plus longue sous-s´equence commune (9 points)´Etant donn´ees deux chaˆınes de caract`eres (repr´esent´ees par des tableaux de caract`eres)AetBde
longueursmetn, on souhaite trouver leur Plus Longue Sous-S´equence Commune (PLSSC), c"est `a direla sous-chaˆıne de caract`eres la plus longue commune `aAetB. Noter que les lettres d"une sous-s´equence
doivent ˆetre dans le mˆeme ordre que dans la s´equence d"origine. Par exemple les chaˆınes"ELLE A AIM´E LES ALGORITHMES"et"IL A MANG´E HIER"ont pour PLSSC "L A MAGIE".Pour une chaˆıne de caract`ereS=< s0,s1,...,sn-1>de longueurn, on noteraSila sous-chaˆıne de
Scommen¸cant en positioni:Si=< si,si+1,...,sn-1>. AinsiS0=SetSn-1=< sn-1>. On d´efinit la fonctionc(i,j) comme ´etant la longueur de PLSSC aux chaˆınesAietBj. a.(1pt) Justifier les relations r´ecurrentes suivantes : ??c(m,j) = 0 c(i,n) = 0 c(i,j) = 1 +c[i+ 1,j+ 1] siai=bjeti < m,j < n c(i,j) = max(c[i+ 1,j],c[i,j+ 1]) siai?=bjeti < m,j < nb.(1pt) En d´eduire un algorithme r´ecursif calculant la longueur de la PLSSC de deux chaˆınes.
c.(1pt) Justifier bri`evement qu"il fait des appels redondants et que sa complexit´e est exponentielle.
d.(1pt) Modifier l"algorithme de la questionc.(par exemple en l"annotant) pour lui ajouter de la m´emo¨ısation. e.(1pt) Quel est son coˆut en temps et en m´emoire.f.(2pt) Proposer un algorithme it´eratif bas´e sur une m´ethode de programmation dynamique, calculant
la longueur de la PLSSC ainsi que les informations n´ecessaires `a la construction de cette PLSSC.
g.(1pt) Quel est son coˆut en temps et en m´emoire.h.(1pt) Proposer un algorithme calculant cette PLSSC `a partir de ces informations.UGA - L3 Maths/Info - Algorithmique - Cl´ement Pernet Page 2/2
quotesdbs_dbs41.pdfusesText_41[PDF] qcm biologie animale l1
[PDF] sujet dexamen de biologie animale
[PDF] qcm biologie animale s2
[PDF] examen biologie animale l1
[PDF] mécanique quantique solutions des examens corrigés
[PDF] examen corrige de mecanique quantique s5
[PDF] examen pharmacologie générale
[PDF] exercices corrigés de pharmacologie générale
[PDF] qcm pharmacologie generale corrigé
[PDF] exercice pharmacologie infirmier
[PDF] qcm pharmacologie speciale pdf
[PDF] exercices corrigés de pharmacologie générale pdf
[PDF] exercice+pharmacocinétique+correction
[PDF] exercice corrigé estimateur sans biais
