Épreuve : Examen Date : Jeudi 19 Écrire un algorithme sontInvOuOpp(a,b) o` u a et b sont deux nombres, qui retourne Vrai si a (c) (2 points) Écrire un algorithme existeInvOuOpp(T) o`u T est un tableau de nombres, qui retourne Vrai si T
| Previous PDF | Next PDF |
[PDF] Algorithmique I - École normale supérieure de Lyon
Algorithmique I - Cours et Travaux Dirigés L3, Ecole 1 7 Exercices 7 1 Recherche en table de l'humour, dans un fichier pdf `a télécharger absolument
[PDF] SUJET + CORRIGE
Épreuve : Examen Date : Jeudi 19 Écrire un algorithme sontInvOuOpp(a,b) o` u a et b sont deux nombres, qui retourne Vrai si a (c) (2 points) Écrire un algorithme existeInvOuOpp(T) o`u T est un tableau de nombres, qui retourne Vrai si T
[PDF] Introduction à lalgorithmique - Cours, examens et exercices gratuits
Table des matières 13 2 1 Tri par insertion 13 Exercices 18 2 2 Analyse des algorithmes 19 32 1 Algorithme naïf de recherche de chaîne de caractères
[PDF] Algorithmes et programmation en Pascal TD corrigés
Algorithmes et programmation en Pascal 9 Recherche dans un fichier 35 Faire un programme qui affiche la table des codes ASCII de 32 `a 127 sur une Dans ces exercices on suppose que l'on a en entrée un fichier texte, résultat du
[PDF] Les tableaux 1 Exercice 1 - LIPN
Ecrire les algorithmes permettant : 1 Le calcul du nombre d'occurences d'un élément donné dans un tableau Nb_occurences (T: Tableau d'entier, N: entier)
[PDF] Exercices corrigés - u-psudfr
Les exercices suivants sont fournis à titre d'exemples et de modèles Ils sont soit simples, Z/A 31 69 72 Affectez les données de ce tableau à un dictionnaire dico python de façon à pouvoir Écrire l'algorithme du calcul de : m3 = m1−m2
[PDF] Cours, Exercices et Travaux Pratiques - Enseeiht
3 1 7 Reconstruction du tableau des données au moyen des com- 6 3 Exercices Un algorithme d'apprentissage artificiel permet de mettre au point un Figure 3 1: La droite recherchée est telle que la moyenne des carrés des distances
[PDF] Langage C : énoncé et corrigé des exercices IUP GéniE - LAMSADE
à la fin du polycopié (voir table des matières) 1 1 EXERCICES FACILES Exercice 1 Ecrire un progra mm e q ui saisit deux entiers et a ffi che l eur produit
[PDF] Rechercher et trier
Algorithmique et arbres Année 2009-2010 L2 TD 3 Rechercher et trier Exercice 1 (Tri sélection) Soit un tableau indexé à partir de 0 contenant des éléments
[PDF] Exercices avec Solutions
Les Tableaux (Vecteurs – Matrices) et Chaines de caractères 23 Exercices Corrigés d'Algorithmique – 1ére Année MI 5 EXERCICE 1 2- Recherche du minimum et du maximum dans un ensemble de N nombres 3- Calcul du
[PDF] algorithme de recherche intelligence artificielle PDF Cours,Exercices ,Examens
[PDF] algorithme de recherche python PDF Cours,Exercices ,Examens
[PDF] algorithme de recherche séquentielle PDF Cours,Exercices ,Examens
[PDF] Algorithme de resolution d'equation de degré 1 ou 2 1ère Mathématiques
[PDF] Algorithme de seconde 2nde Mathématiques
[PDF] Algorithme de suite pour un devoir maison Terminale Mathématiques
[PDF] Algorithme de suites 1ère Mathématiques
[PDF] algorithme de tracé de cercle PDF Cours,Exercices ,Examens
[PDF] Algorithme de x en fonction de y 1ère Mathématiques
[PDF] algorithme débranché PDF Cours,Exercices ,Examens
[PDF] algorithme définition PDF Cours,Exercices ,Examens
[PDF] Algorithme dérivées 1ère Mathématiques
[PDF] Algorithme des probabilités 2nde Mathématiques
[PDF] algorithme des soustractions successives PDF Cours,Exercices ,Examens
Master BioInformatiqueAnn
ee :2013/2014Semestre de decembre 2013PARCOURS :Master 1
UE J1BS7202 :Algorithmique et Programmation
Epreuve :Examen
Date :Jeudi 19 decembre 2013
Heure :9 heures
Duree :2 heures
Documents : autorises
Epreuve de M. AlainGriffaultSUJET + CORRIGE
Avertissement
La plupart des questions son tind ependantes.
A chaque question, vous pouvez au choix
repondre par un algorithme ou bien par un programme python.Les inden tationsdes f onctions ecritesen Python
doivent ^etre respectees. L'espace laiss ep ourles r eponsesest susan t(sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement deconseille).QuestionPointsScoreMise en bouche7
Algorithmes de rang14
Liste doublement chainee9
Total:30
Exercice 1 : Mise en bouche (7 points)
(a) (1 p oint)Deux nom bresson topp osessi le ursom meest egale a0. Deux nombres sont inverses si leur produit est egal a1.Ecrire un algorithmesontInvOuOpp(a,b)ouaetbsont deux nombres, qui retourneVraisiaetbsont inverses ou opposes,Fauxsinon.Solution:Deux solutions parmi d'autres.
defsontInvOuOpp(a ,b): returna+b==0orab==1Algorithme 1:SontInvOuOpp(a,b)Donnees:Deux nom bresa et b retourner(a+b=0) OU (a*b=1);(b)(2 p oints) Ecrire un algorithmeexisteInvOuOppConsecutifs(T)ouTest un tableau de nombres, qui retourneVraisiTcontient deux nombresconsecutifsopposes ou inverses,Fauxsinon.Solution:Deux solutions parmi d'autres.
defexisteInvOuOppConsecutifs (T): foriinrange ( len (T)1): ifsontInvOuOpp(T[ i ] ,T[ i +1]): returnTrue returnFalseAlgorithme 2:ExisteInvOuOppConsecutifs(T)Donnees:Un tabl eauT de n ombres pouri=0alen(T)-2fairesisontInvOuOpp(T[i],T[i+1])alorsretournerTrue;retournerFalse;(c)(2 p oints) Ecrire un algorithmeexisteInvOuOpp(T)ouTest un tableau de nombres, qui retourne VraisiTcontient deux nombres,ayant des indices dierents, opposes ou inverses,Fauxsinon. UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013Solution:Deux solutions parmi d'autres.
defexisteInvOuOpp(T): foriinrange ( len (T)1): forjinrange ( i +1,len (T)): ifsontInvOuOpp(T[ i ] ,T[ j ] ) : returnTrue returnFalseAlgorithme 3:ExisteInvOuOpp(T)Donnees:Un tableau T de nom brespouri=0alen(T)-2fairepourj=i+1alen(T)-1fairesisontInvOuOpp(T[i],T[j])alorsretournerTrue;retournerFalse;(d)(2 p oints)
Ecrire un algorithmenbInvOuOpp(T)ouTest un tableau de nombres, qui retourne le nombre de paires d'indices(i,j)telles que : d'une partipouri=0alen(T)-2fairepourj=i+1alen(T)-1fairesisontInvOuOpp(T[i],T[j])alorsnb nb+1;retournernb;Exercice 2 : Algorithmes de rang (14 points)
Le probleme de la selection consiste a trouver dans un tableau de nombres l'element dit de rangi. Pour cet exercice, du fait que les indices d'un tableauTsont compris entre0etlongueur(T)-1, nous admettrons que l'element de rang0est le plus petit element du tableau, et que l'element de rang longueur(T)-1est le plus grand.Exemple :SoitT= [8;6;53;8;2;9;3;10], alors :
Les elementsde rang <0sont indenis.
L' elementde rang 0est 2.
L' elementde rang 1est 3.
L' elementde rang 2est 6.
L' elementde rang 3est 8.
L' elementde rang 4est 8.
L' elementde rang 5est 9.
L' elementde rang 6est 10.
L' elementde rang 7est 53.
Les elementsde rang >7sont indenis.
Page 2 sur 10
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 Remarque 1 :Une solution simple au probleme de la selection consiste a utiliser un algorithmequelconque de tri, puis de retourner l'element de rang souhaite.Algorithme 5:Rang(T,rang)Donnees:Un tabl eauT de n ombres,et rang un en tier
Resultat:Si rang est un indice, alors T[rang] apr esa voirtri eT sirang<0 OU ranglongueur(T)alorsretournernil;Trier(T);retournerT[rang];Remarque 2 :Il est facile de se persuader qu'il n'est pas utile de triertoutle tableau pour avoir une
solution au probleme de la selection. Dans cet exercice, nous allons adapter des algorithmes de tri vus
en cours an d'obtenir des algorithmes de rang plusecacesque le precedent.Dans toute la suite de l'exercice, vous pourrez utiliser la fonction classiqueEchange(T,i,j)qui echange
les valeurs du tableauTindicees parietj. defechange(T, i , j ):