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

Théorie de la programmation - TDA et structures de données 2005 Génie Informatique Université de Technologie de Belfort Montbéliard

-

Cet ouvrage peut être téléchargé gratuitement
1 page
Français
Cet ouvrage peut être téléchargé gratuitement

Description

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.

Sujets

Informations

Publié par
Publié le 18 août 2008
Nombre de lectures 21
Langue Français

Extrait

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 d’algorithmes 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 d’un sousensemble: Soient un entier k et n entiers positifs a1, a2,, an. Y atil 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. L’entÍte de notre fonction sera "fonction boolÈen sommePartie(int k, taille, pos ; entier tab[] )" o˘tailleest le nombre d’entiers positifs du tableautabetposl’indice de l’entier ‡ traiter.  AprËsavoir dÈfini la (ou les) condition(s) d’arrÍ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 l’idÈe cidessous Le tableau des solutions est un tableau de boolÈens. IdÈe : quel est l’effet d’un nombre supplÈmentaire A sur le tableau des solutions ?  Pourchaque somme X qu’on peut atteindre, X reste atteignable, et (X+A) devient atteignable ! Exemple : peuton 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 d’afficher 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 ‡ l’adversitÈ, ensemble, la solution sera(8p) a) Etablissez la description syntaxique ou signature, puis la description axiomatique d’un 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 l’interface 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  b2 * a + 1 + b ;  aa + 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
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents