Exercices et problèmes d'algorithmique - Poupa

1 Exercices ET PROBL MES D ALGORITHMIQUEXR appels de coursXExercices et probl mes avec corrig s d taill sXSolutions en pseudo code et en langage CNicolas Flasque Enseignant math matiques et informatique, EFREIH elen KasselEnseignant math matiques et informatique, EFREIF ranck LepoivreEnseignant-chercheurBoris VeliksonEnseignant math matiques et informatique, EFREI Dunod, Paris, 2010 Illustration de couverture : digitalvision ISBN 978-2-10-055072-2 TABLE DES MATI 1 CHAPITRE 1 LES BASES DE LA Les types de donn es .. Les Quelques l ments de syntaxe pour le langage algorithmique .. Op rations et op rateurs de base .. Op rateurs arithm tiques et Op rateurs d entr Structure de contr le.

2 Conditions et Ex cution conditionnelle d It rations et Tableaux .. D Repr Relation entre tableaux et Les tableaux plusieurs Notion d D finition et Les sous-programmes ou D finition d une 24 VExercices et probl mes d Appel des Les fonctions et les Les fonctions et les Cr ation de types par le programmeur : les types compos s ou Acc s aux Op rateur d affectation .. Structures contenant des tableaux et des Structures d finies l aide de Pointeurs vers les Types pointeurs et raccourcis de Structures et 34 CHAPITRE 2 STRUCTURES S QUENTIELLES 35 Rappels de Listes lin aires.

3 D Repr Variables Variantes d implantation des 43 nonc s des Exercices et des probl 45 Corrig s des Exercices et des probl mes .. 47 CHAPITRE 3 STRUCTURES S QUENTIELLES 87 Rappels de Piles .. Repr sentation contigu des Repr sentation cha n e des Manipulation d une Les files .. Repr sentation contigu des Repr sentation cha n e des Manipulation d une file (m thode avec deux pointeurs).. 91 nonc s des Exercices et des probl 98 Corrig s des Exercices et des probl mes .. 99 VITable des mati resCHAPITRE 4 STRUCTURES 127 Rappels de Arbres binaires .. D Repr Algorithmes de parcours d un arbre Arbres binaires de recherche (ABOH = Arbres Binaires Ordonn s Horizontalement).

4 132 nonc s des Exercices et des probl 142 Corrig s des Exercices et des probl mes .. 146 CHAPITRE 5 169 Rappels de Quelques d L interpr tation Automates d Automate 183 nonc s des 187 Corrig s des 217 VIIAVANT-PROPOSCet ouvrage s adresse aux l ves des coles d ing nieurs, aux l ves d IUT, de DUT, de BTS, auxauditeurs des organismes de formation continue et aux autodidactes qui souhaitent se doter de basespratiques et th oriques en algorithmique. Le niveau de ma trise attendu correspond la secondeann e de D EMPLOIUn contenu construit pour aller directement l essentielCet ouvrage de travaux dirig s d algorithmique est construit pour aller directement l essentielsans faire d impasse sur ce qui est important, ni se disperser dans ce qui viendra point nomm dans les tapes de votre d acc s, il contient les chapitres classiques d une introduction l algorithmique, avecnotamment les structures s quentielles, arborescentes, et les chapitre d bute avec un rappel de cours d une vingtaine de pages suivi des nonc s etcorrig s des Exercices et probl compl ter cette structure classique.

5 Un chapitre introductif r sume les bases minimales dela programmation corrig s sont donn s sous la forme suivante : une ventuelle tude des strat gies de r solution du probl me pos (si celui-ci est complexe),accompagn e de sch mas descriptifs de principe ; une sp cification en langage algorithmique (pseudo code) de la ou des solutions envisag es ; une ventuelle proposition de r alisation en C99 des solutions propos sch mas intuitifsLes sch mas descriptifs de principe facilitent la compr hension des principes de fonctionnementdes algorithmes propos liste suivante vous sera utile notamment pour interpr ter les sch mas du second place quelconqueUn pointeur sur uneplace non vide (et doncle d but d une liste deplaces)Une place pointantsur la suivante(placeinterm diaire)Une placeinterm diairecontenant l l ment 6 Dunod La photocopie non autoris e est un d litIXExercices et probl mes d algorithmiqueLa liste vide ( unpointeur ne pointantsur rien)Une place terminale(par composition)

6 Un singleton (liste un seul l ment)Une liste l mentsmultiplesLe cas particulier ducouple (liste deux l ments)Repr sentation desmodifications effectu es(pointill s (apr s) pleins (avant))Un plan de travail qui peut tre adapt Si vous d butez et n avez jamais crit le moindre programme informatique de votre vie, la lecturedu premier chapitre vous sera n cessaire. Sinon, elle n est pas indispensable, sauf ventuellementcomme r f rence pour le langage algorithmique utilis dans les corrig vous d marrez avec quelques notions de programmation, les deux chapitres sur les structuress quentielles et arborescentes vous donneront les bases n cessaires pour raisonner en termesalgorithmiques et aborder par la suite des structures et algorithmes plus complexes, b tis sur ces l ments de , quel que soit votre niveau, le dernier chapitre sur les automates vous sensibilisera sur lesfondements math matiques de l algorithmique, notamment des logiques d ex les structures s quentielles et les approches it ratives.

7 Les structures arborescentes et lesapproches r cursives, et enfin, avec les automates et les logiques g n rales d ex cution, vousmunirez votre arc de trois cordes essentielles pour aborder la suite de votre apprentissage. PROPOS DES AUTEURS Nicolas FlasqueIng nieur IIE depuis 1992 et docteur en informatique depuis 2001. Apr s avoir travaill uneann e en tant que responsable logiciel sur les syst mes embarqu s automobiles, il reprend ses tudes et obtient un doctorat de l universit de Caen sur la reconnaissance de vaisseaux sanguinspour l imagerie m dicale. En poste l EFREI depuis septembre 2001, il enseigne l algorithmiqueainsi que la programmation dans des langages n cessitant des approches diff rentes (C, C++,C#, Java).

8 XAvant-propos Helen KasselDe double formation en math matiques (DEA obtenu en Russie) et en informatique (DEAobtenu en France), elle a enseign l informatique en Russie, aux tats-Unis et en France. Elleposs de galement une exp rience du travail en entreprise en tant qu ing nieur en en informatique et en math matiques l EFREI depuis plus de dix ans, elle estactuellement le chef du d partement math matiques/informatique. Franck LepoivreDipl m ing nieur de l ISEP en 1995, il volue dans les entreprises de nouvelles technologies entant que consultant IT (coauteur de XML & Java, Eyrolles 2000) puis directeur marketing produit(prix technologia ANVAR et 01 Informatique pour Kelua Kawana en 2002).

9 En 2004, il lancereciproCitypour porter l analyse sociologique dans le domaine de l intelligence 2007, il lancePepper Labspour porter les math matiques appliqu es et algorithmique versles entreprises et leur probl matiques m tier (mod lisation et prototypage d outils d analysecomplexe, notamment dans les domaines du marketing et des neurosciences appliqu es). Ilintervient l EFREI en algorithmique et structures de donn es, th orie des langages et techniquesde compilation, th orie des graphes, aide la d cision et algorithmique num rique. Boris VeliksonDipl m de en Physique th orique aux tats-Unis apr s un Bac+5 en Russie, il a travaill comme chercheur en th orie des champs quantiques et puis en biophysique, dans le domainede mod lisation de grosses mol cules biologiques sur ordinateur.

10 Depuis plusieurs ann es, iltravaille comme enseignant en math matiques, en statistique et en informatique, dans quelques tablissements de la r gion parisienne, des niveaux tr s diff rents, en fran ais et en remercions nos tudiants de l EFREI, sans qui l laboration de ce contenu n aurait pu trouverle juste diapason p dagogique. C est par la somme de nos interactions qu mergent et s am liorentnos contenus d apprentissage par la remercions notre diteur, Jean-Luc Blanc, qui nous a donn la chance de produire ce cahiersur la base de nos existants p dagogiques dans le cadre de la collectionExercices & Probl meso il trouve une place coh rente par rapport d autres ouvrages de math matiques appliqu remercions nos familles et nos amis, pour avoir tol r ce temps suppl mentaire que nousleur avons soustrait, et pour leur soutien pourtant ind EST-CE QUE L ALGORITHMIQUE?