Théorie de la programmation - TDA et structures de données 2005 Génie Informatique Université de Technologie de Belfort Montbéliard
1
page
Français
Documents
2008
Cet ouvrage peut être téléchargé gratuitement
1
page
Français
Documents
2008
Cet ouvrage peut être téléchargé gratuitement
Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Théorie de la programmation - TDA et structures de données 2005. Retrouvez le corrigé Théorie de la programmation - TDA et structures de données 2005 sur Bankexam.fr.
Voir
UTBMle 14 novembre 2005 MÈdian LO42 Aucun document autorisÈ(la copie ou les idÈes du voisin pas plus). Le barËme est indicatif. Le soin donnÈ ‡ la rÈdaction sera ÈvaluÈ. Toute rÈponse devra Ítre claire et justifiÈe (toute ambiguÔtÈ sera mal interprÈtÈe). LÈlÈgance de la solution sera jugÈe. Sauf indication contraire, dans le cas dalgorithmes les rÈponses doivent Ítre rÈdigÈes en pseudo code. 1) La rÈcursivitÈ, dominer et contourner, vous pourrez ! La question c est en bonus ! (‡ ne faire que si le (8p) traitement des 3 exercices vous laisse du temps)ProblËme de la somme dun sousensemble: Soient un entier k et n entiers positifs a1, a2,…, an. Y atil un groupe de ces n entiers dont la somme vaut k ? a) On veut Ècrire une fonction rÈcursive permettant de rÈpondre ‡ la question. LentÍte de notre fonction sera "fonction boolÈen sommePartie(int k, taille, pos ; entier tab[] )" o˘tailleest le nombre dentiers positifs du tableautabetposlindice de lentier ‡ traiter. AprËsavoir dÈfini la (ou les) condition(s) darrÍt, prÈcisez votre dÈmarche pour rÈsoudre les autres cas. Enfin, Ècrivez la fonction rÈcursive. b) Ecrivez un programme utilisant la programmation dynamique selon lidÈe cidessous Le tableau des solutions est un tableau de boolÈens. IdÈe : quel est leffet dun nombre supplÈmentaire A sur le tableau des solutions ? Pourchaque somme X quon peut atteindre, X reste atteignable, et (X+A) devient atteignable ! Exemple : peuton faire la somme 17 avec {5, 8, 6, 2} ?Non Avec 00, 01, 02, 03, 04, 05,06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17{} 00, 01, 02, 03, 04,05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17{5} 00, 01, 02, 03, 04,05, 06, 07,08, 09, 10, 11, 12,13, 14, 15, 16, 17{5, 8} 00, 01, 02, 03, 04,05,06, 07,08, 09, 10,11, 12,13,14, 15, 16, 17{5, 8, 6} 00, 01,02, 03, 04,05,06,07,08, 09,10,11, 12,13,14,15,16{5, 8, 6, 2}, 17 c) Modifiez votre algorithme rÈcursif afin dafficher le groupe des entiers dont la somme vaut k. On pourra introduire un tableau permettant de marquer les entiers inclus dans la somme. 2) Face ‡ ladversitÈ, ensemble, la solution sera(8p) a) Etablissez la description syntaxique ou signature, puis la description axiomatique dun TDA ensemble qui fournit les opÈrations qui travaillent sur des ensembles et des ÈlÈments de typeElÈmentconnu: ensemblevide union cardinal intersection appartenance inclusion: le premier inclus dans le second ajout diffÈrence: ÈlÈments qui appartiennent au premier et pas au second suppression b) Ecrivez en Java linterface correspondant au TDA. Si des choix sont ‡ faire, vous expliquerezceux que vous avez faits. 3) La cerise, dÈception Èvitera(4p)Soit le programme utilisant des variables entiËres : Tantque a<c Faire b←2 * a + 1 + b ; a←a + 1 ; ftq ; 2 Trouvez la plus petite prÈcondition de la boucle assurant au programme un Ètat mÈmoire final vÈrifiant b = a . En dÈduire les initialisations.
LO42 mÈdian A2005 page1/1
