Home

Livre: EXERCICES ET PROBLÈMES D`ALGORITHMIQUE (228 pages)

Contents

1. Tableau 5 56 Etat a B 0 1 1 2 01 2 3 02 3 4 03 n 1 0 0 n 1 01 12 01 02 13 02 0 n 1 01 0 n 1 12 23 012 13 24 013 1 n 1 02 0 1 n 1 Ici figurent toutes les combinaisons possibles de m tats parmi n c est dire 1 lt m lt n n Ilya ae C 2 1 de tels tats Si l on y ajoute l tat poubelle o m ne la fl che tiquet e b m 0 partant de l tat 0 pour que l automate soit complet on obtient 2 tats 214 BIBLIOGRAPHIE BAYNAT B CHRETIENNE P HANEN C KEDAD SIDHOUM S MUNIER KORDON A et PICOU LEAU C Exercices et probl mes d algorithmique 2 dition Dunod Paris 2007 CARREZ C Des structures aux bases de donn es Dunod Paris 1994 CORMEN T LEISERSON C RIVEST R et STEIN C Introduction l algorithmique 3 dition Dunod Paris 2010 FROIDEVAUX C GAUDEL M C et SORIA M Types de donn es et algorithmes Ediscience International Paris 1994 GUYOT J et VIAL C Arbres tables et algorithmes Eyrolles Paris 1992 Luc BOUGE L KENYON C MULLER J M et ROBERT Y Algorithmique Exercices corrig s Ellipses Paris 1993 215 Dunod La photocopie non autoris e est un d lit accepteurs 169 adresse 18 affectation 7 afficher 8 45 algorithme 1 allocation dynamique 23 alphabet 170 171 174 176 177 182 arbre 127 129 131 137 139 143 binaire 127 129
2. 24 lt Exercices et probl mes d algorithmique 1 8 2 Appel des fonctions 1 8 3 Les fonctions et les tableaux 1 8 4 Les fonctions et les pointeurs 1 9 Cr ation de types par le programmeur les types compos s ou structures 1 9 1 Acc s aux champs 1 9 2 Op rateur d affectation 1 9 3 Structures contenant des tableaux e t des POMUCUIS ss bebe heed dd dieser 1 9 4 Structures d finies l aide de structures 1 9 5 Pointeurs vers les structures 1 9 6 Types pointeurs et raccourcis de no 1 9 7 Structures et fonctions CHAPITRE 2 e STRUCTURES SEQUENTIELLE Rappels de cours 2 1 Listes lin aires 2 1 1 D finition 2 1 2 Repr sentation 2 1 3 Variables dynamiques 2 1 4 Variantes d implantation des listes nonc s des exercices et des probl mes Corrig s des exercices et des probl mes CHAPITRE 3 e STRUCTURES SEQUENTIELLE Rappels de COUrS 2 suisses 3 1 Piles cco 2 2h 2o2 ce Seen sets 3 1 1 Repr sentation contigu des piles 3 1 2 Repr sentation chain e des piles 3 1 3 Manipulation d une pile 3 2 LES TES esta es 3 2 1 Repr sentation contigu des files 3 2 2 Repr sentation chain e des files LEE TO RS we ao a a Boe eh ars aod gwen deacon nancies ae S SIMPLES 2 25 fee tees Sea b
3. Le groupe II se s pare en deux 1 11 111 1V V avec I 025 H 0 01 IM 014 IV 013 V 02 Tableau 5 34 tat a b a b 0 01 0 Il Il 01 01 02 Il Vv O tout les tats se sont s par s l automate tait minimal Exercice 5 10 Solution A Reprenons l automate d terministe complet A 203 Chapitre 5 Automates Tableau 5 35 Etat a b 0 0 01 01 0 012 012 0 0123 0123 0 0123 SOD Figure 5 58 e Minimisation Qo I H avec I 0 01 012 H 0123 Tableau 5 36 tat a B A b 0 0 01 l 01 0 012 l 012 0 0123 l Il Le groupe I se s pare en deux Modifiant la notation on a Q I H M avec I 0 01 H 012 M 0123 Tableau 5 37 Etat a B a b 0 0 01 l 01 0 012 l Il minimal d s le d but 204 Les deux tats du groupe se sont s par s donc tous les tats se sont s par s l automate tait Dunod La photocopie non autoris e est un d lit Corrig s des exercices Solution A2 Reprenons l automate d terministe complet A mais modifions la notation des tats pour plus de clart Tableau 5 38 En renommant les tats tat a b tat a b Initial 0 0 01 A A B 01 02 012 B D C 012 023 0123 C F E 02 03 013 D G H Terminal 0123 023 0123 E F E Terminal 023 03 013 F G H Terminal
4. o est la racine de B B1 est le sous arbre gauche sag de la racine de B ou plus simplement le sous arbre gauche de B et B2 est son sous arbre droit sad On dit que C est un sous arbre de B si et seulement si C B ou C B1 ou C B2 ou C est un sous arbre de B1 ou de B2 On appelle fils gauche respectivement fils droit d un n ud la racine de son sous arbre gauche respectivement sous arbre droit et l on dit qu il y a un lien gauche respectivement droit entre la racine et son fils gauche respectivement fils droit Si un n ud n a pour fils gauche respectivement droit un n ud nj on dit que n est le p re de nj chaque n ud n a qu un seul p re Deux n uds qui ont le m me p re sont dits fr res Le n ud n est un ascendant ou un anc tre du n ud n si et seulement si n est le p re de nj ou un ascendant du p re de nj n est un descendant de n si et seulement si n est fils de nj ou ni est un descendant d un fils de nj Tous les n uds d un arbre binaire ont au plus deux fils un n ud qui a deux fils est appel n ud interne ou point double un n ud sans fils est appel n ud externe ou feuille Donc un arbre binaire est soit vide soit constitu d un l ment de type T et d au plus deux arbres binaires 4 1 2 Repr sentation La repr sentation la plus naturelle reproduit la d finition r cursive des arbres binaires Elle peut tre r alis e en allouant
5. quilibre parfait pour tout n ud de l arbre la valeur absolue de la diff rence entre le nombre des n uds du sad et le nombre des n uds du sag est inf rieure ou gale 1 ng nal lt 1 138 4 1 Arbres binaires Exemples Figure 4 18 Arbres parfaitement quilibr s Figure 4 19 Arbre imparfaitement quilibr quilibre partiel pour tout n ud de l arbre la valeur absolue de la diff rence entre la hauteur du sad et la hauteur du sag est inf rieure ou gale 1 he hal lt 1 Les trois arbres de l exemple pr c dent sont partiellement quilibr s Il existe des proc d s pour viter le d s quilibre d arbres par exemple les arbres AVL Principe SI l arbre est vide gt retourner 0 SINON compter le nombre de n uds du sag compter le nombre de n uds du sad retourner 1 nsag nsad 139 Chapitre 4 Structures arborescentes Figure 4 20 Balance 1 hsag hsad 1 0 hsad hsag 1 hasd hsag 1 Algorithme Donn e ptr_arbre a R sultat de type entier FONCTION compter a ptr_arbre entier VAR n entier DEBUT SI a NULL ALORS n 0 SINON n lt 1 compter a sag compter a sad FINSI RETOURNER n FIN Hauteur SI l arbre est vide gt retourner 0 SINON calculer la hauteur du sag calculer la hauteur du sad SI hg gt hd alors retourner 1 hg SINON retourner 1 hd Algorithme Donn e ptr_arbre a R sultat de type entier FONCTION hau
6. 173 5 3 2 Automate asynchrone 183 nonc s des exerciCes 187 Corrig s des CX CFCS ae te cee crus cosa ns ae ok dete eee eels cow ae ae 191 BIBLIOGRAPHIE 22s2c2tcase10ttsccesca coe ayerssers tidied detdecdes teankiriensaaesecs 215 INDEX a eddie da dde ene Din ent E EE in 217 VII Dunod La photocopie non autoris e est un d lit AVANT PROPOS Cet ouvrage s adresse aux l ves des coles d ing nieurs aux l ves d IUT de DUT de BTS aux auditeurs des organismes de formation continue et aux autodidactes qui souhaitent se doter de bases pratiques et th oriques en algorithmique Le niveau de ma trise attendu correspond la seconde ann e de licence MODE D EMPLOI Un contenu construit pour aller directement l essentiel Cet ouvrage de travaux dirig s d algorithmique est construit pour aller directement l essentiel sans faire d impasse sur ce qui est important ni se disperser dans ce qui viendra point nomm dans les tapes de votre apprentissage Simple d acc s il contient les chapitres classiques d une introduction l algorithmique avec notamment les structures s quentielles arborescentes et les automates Chaque chapitre d bute avec un rappel de cours d une vingtaine de pages suivi des nonc s et corrig s des exercices et probl mes Pour compl ter cette str
7. L automate prend un mot constitu de symboles de son alphabet en entr e et d marre dans son ou ses tat s initial aux Il parcourt ensuite le mot de gauche droite si l automate se trouve dans un tat p et le symbole lire est a alors s il existe nt un ou des tat s q tels que la transition p a qi existe il passe aux tats g et de suite S il y a plus d un tat g on consid re chacun d eux s par ment La lecture se termine soit si la lettre suivante ne peut pas tre lue il n y a pas de transition y correspondant soit si on a atteint la fin du mot Si la fin de la lecture automate est dans un tat final accepteur on dit qu il accepte l entr e ou qu il la reconna t Autrement on dit qu il la rejette Notation Pour un mot w A on note p q s il existe un chemin de l tat p l tat q obtenu en lisant w D finitions formelles Va A on a p q ssi il existe une fl che p a q E Ensuite pour u A eta A on a pq ssi Ir Q tq p retr q Quand on a p q on va dire qu il existe un chemin de p q d tiquette w 171 Chapitre 5 Automates On peut facilement voir par r currence que pour u v A ona p ssi Ir Q tq p r etr 4 Un mot w A est donc reconnu par l automate fini s il existe un chemin i t o i I et t T c a d qu en partant d un tat initia
8. t te lo FINSI TANTQUE dernier po FAIRE 54 Dunod La photocopie non autoris e est un d lit Po lt SUCC Po SI contenu po 2 0 ALORS SI estvide 1 ALORS pi t te 1 Po SINON p succ pi Po FINSI SINON SI estvide l ALORS p2 t te ls po SINON P2 succ p2 Po FINSI FINSI FAIT FINSI FIN R alisation en C void separate list pl0 list pll list pl2 liste 10 p10 11 NULL 12 NULL if 10 NULL return si 10 vide ne rien faire if 10 gt content gt 0 11 pll pl0 t te de 71 else 12 pl2 pl0 t te de 12 while 10 gt succ NULL it ration de 10 10 10 gt succ it ration de 10 if 10 gt content gt 0 transfert vers 11 if 11 NULL pll 11 10 t te de 11 else au del de la t te 11 gt succ 10 compl te 11 11 11 gt succ it ration de 71 else transfert vers 12 if 12 NULL pl2 12 10 t te de 12 else au del de la t te 12 gt succ 10 compl te 12 Corrig s des exercices 55 Chapitre 2 Structures s quentielles simples 12 12 gt succ it ration de 11 important pour la cl ture des listes 11 et 12 11 gt succ NULL finalisation de 11 12 gt succ NULL finalisation de 12 p10 NULL lib ration de 10 opt Exercice 2 4 Permuter deux places d une liste tude Il convient de pr voir un c
9. un enchainement d termin On conna t depuis antiquit des algorithmes sur les nombres comme par exemple l algorithme d Euclide qui permet de calculer le p g c d de deux nombres entiers Pour le traitement de l information on a d velopp des algorithmes op rant sur des donn es non num riques les algorithmes de tri qui permettent par exemple de ranger par ordre alphab tique une suite de noms les algorithmes de recherche d une cha ne de caract res dans un texte ou les algorithmes d ordonnancement qui permettent de d crire la coordination entre diff rentes t ches n cessaire pour mener bien un projet 1 TAOCP The Art of Computer Programming la Bible de l algorithmique en quatre volumes par Donald E Knuth professeur m rite de Stanford et inventeur de TEX TAOCP est une encyclop die algorithmique plus proche des math matiques pures que de la programmation informatique Dunod La photocopie non autoris e est un d lit Introduction Un programme destin tre ex cut par un ordinateur est la plupart du temps la description d un algorithme dans un langage accept par cette machine D finissons plus formellement le concept e Un algorithme d crit un traitement sur un certain nombre fini de donn es e Un algorithme est la composition d un ensemble fini d tapes chaque tape tant form e d un nombre fini d op rations dont chacune est d finie
10. 5 3 L interpr tation intuitive Proc dure applicable la partition courante commencer par POUR chaque groupe G de FAIRE d but partitionner G en sous groupes de mani re que deux tats e et t de G soient dans le m me sous groupe ssi pour tout symbole a A les tats e et t ont des transitions sur a vers des tats du m me groupe de au pire un tat formera un sous groupe par lui m me remplacer G dans par tous les sous groupes ainsi form s on obtient la partition de 1 tape suivant O fin Si O41 O alors Ofing O et continuer l tape 4 Sinon r p ter 1 tape 2 avec j 4 comme partition courante Choisir un tat dans chaque groupe de la partition 4 en tant que repr sentant de ce groupe Les repr sentants seront les tats de l automate fini d terministe r duit D Soit e un tat repr sentatif et supposons que dans D il y a une transition e Soit r le repr sentant du groupe de f r peut tre gal f Alors D a une transition de e vers r sur a er L tat initial de D est le repr sentant du groupe qui contient l tat initial i de D les tats terminaux de D sont des repr sentants des tats de T Pour tout groupe G de 4 soit G est enti rement compos d tats de T soit G n en contient aucun Remarque En r alit il est parfois plus facile au lieu de choisir un repr sentant marquer les groupes finaux comme t
11. bool en casC DEBUT RETOURNER crit re_estPair n 77 Chapitre 2 Structures s quentielles simples FIN FONCTION crit re_estSup n entier seuil entier bool en casD VAR estSup bool en DEBUT SI n gt seuil ALORS estSup lt vrai SINON estSup faux FINSI RETOURNER estSup FIN FONCTION crit re estInf n entier seuil entier bool en casE VAR estInf bool en DEBUT estinf lt faux SI n lt seuil ALORS estinf lt vrai FINSI RETOURNER estInf FIN Implantation C int removeATIB plist pl param lt B gt tosuppr lt B gt element element 2 int removeATIC plist pl param lt C gt tosuppr lt C gt element element 2 int removeAl1ID plist pl int threshold param lt D gt int threshold tosuppr lt D gt element threshold element gt threshold int removeAllE plist pl int threshold param lt E gt int threshold tosuppr lt E gt element threshold element lt threshold e Adaptations pour le cas A Le cas de figure A du fait de la r gularit des intervalles de suppression conduit 4 une version simplifi e du sch ma g n ral pr c dent On limine notamment un niveau d imbrication de boucles tantque traduction du fait qu il n existe pas de cha ne de plusieurs l ments directement successifs supprimer 78 Dunod La photocopie non autoris e est un d lit Corrig s des exercices
12. c k c n k 4 2 2n 1 La complexit est donc lin aire 4 comparer avec une complexit en temps constant deux op rations une somme et une affectation pour un calcul par la formule de r currence de Pascal Si l on passe a chelle de la ligne de profondeur n il y a n 1 termes calculer et donc le co t en op rations pour une ligne du triangle de Pascal est 2 2n 1 n 1 avec la mauvaise m thode et 2 n 1 avec la bonne l chelle d un triangle de profondeur n nous obtenons donc un co t de 5 2Qi 1 i 1 i l avec la mauvaise m thode et un co t de gt 2 i 1 n 1 n 2 avec la bonne i l Probleme 4 2 interlude Syracusien Fonction de retour du pr d cesseur e Le principe Il s agit de v rifier dans un premier temps que n est divisible par 3 Cela se v rifie facilement l aide du test n 1 3 0 soitm 3 Oavecm n 1 Mais ce n est pas suffisant puisqu il faut par ailleurs que m 3 soit impair car sinon le terme trouv aurait pour successeur sa moiti et non pas n c est a dire que son successeur serait m 6 et non pas n L imparit de m 3 peut se v rifier l aide de m 3 2 1 ou 0 mais si le r sultat invalide cette imparit une division aura t effectu e pour rien Il suffit de constater que si m est la fois multiple de 3 et multiple de 2 alors il est multiple de 6 etdoncm 6 0 La condition d imparit de
13. cas gt t gt gt v vs autres cas if prec_t NULL prec_v NULL if prec_t NULL printf case gt t gt gt v gt gt v gt gt t gt n pl v prec_v gt succ t if prec_v NULL printf case gt Ev gt 0 gt t gt gt ft gt L gt v gt n pl t prec_t gt suce V3 else printf case J gt t v gt L gt v t gt gt L J gt Lv t gt 0 gt 0t vJ gt n prec yv t prec_t v et dans tous les cas t gt succ SUCC_V v gt succ succ_t return 0 that s all folks Fonction d l gu e de r cup ration du pr d cesseur et du successeur d un n ud fonction s curis e par l appelant param tres suppos s coh rents entre eux int getPrecAndSucc list 1 list t list prec list succ if 1 t cas de t en t te 60 Dunod La photocopie non autoris e est un d lit Corrig s des exercices prec NULL succ 1 gt succ return else cas de t en milieu ou en queue while 1 gt succ NULL if 1 gt succ t prec 1 succ 1 gt succ gt succ return else 1 gt succ Exercice 2 5 Supprimer des l ments Etude Nous proposons de r aliser le second algorithme en premier lieu puis de construire le premier par un appel r cursif du second avec pour condition d arr t un dernier appel qui laisse l
14. nb_elt 0 ALORS si la file contenait un seul l ment elle devient vide et ff fin devient NULL ainsi que ff tete ff fin amp NULL FINSI SINON ok lt faux FINSI RETOURNER ok FIN Remarque Une file se repr sente beaucoup mieux en dynamique repr sentation chain e Utilisation des files tous les cas o l on dispose d une ressource destin e tre utilis e par plusieurs programmes les cas o plusieurs donn es sont manipul es par cette ressource Exemple le buffer d imprimante est g r en file d attente Exemple de gestion d un buffer clavier en liste circulaire le dernier poste d une liste circulaire est rattach au premier On a un ensemble des donn es homog nes g r es sur un principe de lecture criture concurrente lecture et criture peuvent se produire de mani re simultan e mais sont conditionn es par l autre op ration Une lecture ne peut tre faite que si une criture a d j t faite mais une criture ne peut tre faite que si la lecture a t effectu e sous peine de perdre l information Plus g n ralement il s agit d une file d attente particuli re o l on n a pas besoin de produire toutes les donn es pour commencer les consommer Le nombre de postes est fix au d part et ne varie plus au cours du programme Il faut crire deux algorithmes qui utilisent respectivement un pointeur de lecture et un pointeur d criture
15. term_t dernierElt t term_v lt dernierElt v SI term t term_1 ET term_v term_1 ALORS RETOURNER 1 FINSI FINSI SI t v ALORS RETOURNER 0 FINSI 1 pl trouverPrecEtSucc l t amp prec_t amp succ_t trouverPrecEtSucc l v amp prec_v amp succ_v SI prec_v t OU prec_t v ALORS SI prec_v t ALORS SI prec_t NULL ALORS Xl v SINON prec_t succ v FINSI v succ t t succ SUCC_V SINON SI prec_v NULL ALORS Ap t SINON prec_v succ t FINSI 57 Chapitre 2 Structures s quentielles simples t succ v v succ succ_t FINSI SINON SI prec_t NULL OU prec_v NULL ALORS SI prec_t NULL ALORS Xpl v prec_v succ t FINSI SI prec_v NULL ALORS xpl t prec_t succ v FINSI SINON precy t prec_t v FINSI t succ SUCC_V v succ succ_t FINSI FIN R alisation en C de la fonction principale Permutation de deux l ments int swap list pl place t place v if pl NULL if t NULL amp amp v NULL return 0 tout va bien else return 1 else if t NULL v NULL return 1 non consistant Maintenant test d appartenance on utilise un truc m me terminal list term_ lastElement pl list term_t lastElement t list term_v lastElement v if term_t term_1 amp amp term_v term_1 return 1 pr conditions v rifi es on
16. tre modifi es par une autre fonction lorsque l on applique ce m canisme pour des param tres de type simple entier caractere ou reel En effet il ne faut pas confondre les arguments d une fonction appel e et les variables du programme qui appelle cette fonction Un argument n est pas n cessairement une variable et m me si c est le cas c est la valeur de l argument qui est transmis la fonction et non la variable elle m me On peut donc en conclure qu une variable utilis e comme argument d un appel de fonction ne sera pas modifi e par l appel car c est simplement sa valeur qui est recopi e 1 8 3 Les fonctions et les tableaux Syntaxe utilis e pour les entr es de type tableau Un tableau est une adresse et c est donc une adresse qui sera transmise par le biais d une entr e d un tel type Il n est pas possible de transmettre avec un seul param tre d autres informations que adresse c est dire la taille utile ou m me la taille maximum du tableau Pour transmettre l une de ces informations il faudra utiliser un param tre suppl mentaire Ainsi un param tre de type tableau sera d fini comme un tableau contenant un certain type de valeurs mais sans fournir ni la taille maximum ni la taille utile Exemple Une entr e de type tableau sera fournie de la mani re suivante nom_entree type_des_valeurs_stock es Les crochets ne contiennent aucune valeur ils sont juste pr
17. 131 142 145 de Syracuse 145 automate fini 169 170 172 173 176 178 B boucle 12 C calcul 1 champ 29 complexit algorithmique 1 concat nation 37 45 51 52 condition 9 constante 7 d cidabilit 1 algorithmique 1 logique 1 pratique 1 th orique 1 d terminisation 173 177 195 198 200 201 208 210 214 INDEX E mond 176 188 195 196 198 quifinalit 1 ET 11 tat 169 172 174 178 182 204 accepteur 171 initial 170 174 terminal 170 174 177 178 182 valuation 13 expression 8 FIFO 90 file 90 fonction 23 appel 25 appelante 25 appel e 25 argument 26 corps 24 en t te 24 Heqat 99 I insertion 35 37 43 99 112 point d 112 it ratif 12 45 49 50 54 63 142 178 217 Exercices et probl mes d algorithmique LIFO 87 liste doublement chain e 44 99 112 lin aire 35 simplement chain e 38 46 112 M machine de Turing 169 minimisation 178 182 201 mot vide 170 N NON 11 NULL 21 O OU 11 P pile 87 89 pile 89 pointeur 18 19 pr d cesseur 60 61 112 145 166 probl me 1 probl me de Joseph 99 pseudo code IX 218 racine 127 raisonnement 1 r cursif 45 50 52 61 65 136 142 r cursivit 127 136 saisir 9 40 solution 1 sommet de pile 87 sous programme 23 structures de contr le 9 successeur 56 112 suppression 37 41 43 46 61 99 112 138 T tableaux 14 tables de v rit 11 transition 33 169 17
18. Cette structure fonctionne de la mani re suivante e sila condition est vraie alors les instructions crites entre les accolades sont ex cut es e si la condition est fausse alors les instructions ne sont pas ex cut es Structure SI ALORS SINON Il arrive assez souvent qu en fonction de la valeur d une condition le programme doive ex cuter des instructions si elle est vraie et d autres instructions si elle est fausse Plut t que de tester une condition puis son contraire il est possible d utiliser la structure SI ALORS SINON dont la syntaxe est la suivante Langage algorithmique SI condition ALORS instructions 1 SINON instructions 2 FINSI 10 Dunod La photocopie non autoris e est un d lit 1 5 Structure de contr le Implantation C if condition instructions 1 else instructions 2 La partie SI ALORS est identique la structure de contr le simple si la condition est vraie alors les instructions 1 sont ex cut es et pas les instructions 2 Les instructions 2 concern es par le SINON sont ex cut es si et seulement si la condition est fausse Dans un programme l utilisation de tests est tr s fr quente Quelle forme aurait un programme dans lequel il serait n cessaire de v rifier deux quatre voire dix conditions avant de pouvoir ex cuter une instruction En vertu des r gles d indentation et de pr sentation il deviendrait rapidement illisib
19. FINSI cas de la liste vide SI isempty pl ALORS autre moyen de tester la liste vide RETOURNER vrai FINSI cas de la place en t te de liste SI place pl ALORS xp lt pl succ SI place succ NULL ALORS pl succ prev NULL FINSI LIBERER place RETOURNER vrai FINSI prec place prev prec succ place succ SI place succ NULL ALORS place succ prev prec FINSI LIBERER place RETOURNER vrai FIN Implantation C Suppression dans une liste doublement chain e Type abstrait list supprimer list 1 int k status code 0 ok 1 ko int removeElement list pl list place v rifier que la place est bien dans la liste concern e m me m thode que pour 1 exercice 2 5 if areConvergent place pl return 1 cas de la liste vide 115 Chapitre 3 Structures s quentielles complexes if pl NULL return 0 cas t te de liste if place pl pl pl gt succ if place gt succ NULL pl gt succ gt prev NULL free place return 0 list prec place gt prev prec gt succ place gt succ if place gt succ NULL place gt succ gt prev prec free place return 0 CORRIG S DES PROBL MES Probl me 3 1 Probl me de Joseph tude e Phase de construction Avec n 12etk 3 e cr ation de la liste circulaire e cr ation d une liste chain e avec les 12 l ments en croissante arithm tique de ra
20. L ensemble des mots sur l alphabet 0 1 2 3 4 5 6 7 8 9 qui repr sentent en langage C des constantes num riques e d L ensemble des mots sur l alphabet 0 1 qui comportent au moins une fois le motif 10 et au moins une fois le motif 01 ces deux motifs ne sont pas oblig s d tre s par s l un de l autre par exemple la s quence 010 comporte les deux motifs e e a b n m pair Exercice 5 3 Construire un automate fini reconnaissant les entiers crits en base deux divisibles par cinq Exercice 5 4 Construire un automate fini reconnaissant les lignes contenant des commentaires d un programme crit en langage C La sortie de l automate correspond la fin du commentaire On prendra comme alphabet x a o a repr sentera tous les caract res autres que et Tout commentaire commence par et finit par Le commentaire peut contenir des et des mais il ne peut pas contenir le motif sauf l int rieur d une cha ne qui commence par et finit par sans contenir d autres En fait toute cha ne de caract res plac e entre les guillemets doubles est d sp cialis e donc le nombre de guillemets doubles doit tre pair et avant le commentaire et l int rieur du commentaire La s quence n est pas consid r e comme comportant et le motif et le motif Exemple d un commentaire reconnu par automate commentaire toto
21. La photocopie non autoris e est un d lit e Affichage du polyn me Sp cification de FONCTION prin DEBUT l algorithme tPolynomial p polynome SI p NULL ALORS RETOURNER FINSI printTerm p TANTQUE p suivant NULL FAIRE p p gt printTerm FAIT FIN Implantation C void printPol if p NU printf L printTerm p while p gt n p p gt ne printler printf 1 suivant p ynomial polynomial p LL return extTerm NULL xtTerm p e Affichage d un terme du polyn me Sp cification de l algorithme FONCTION prin DEBUT SI p NUL RETOURNER FINSI SI p coef RETOURNER FINSI SI p coeff SI p ex AFFICHE SINON tTerm p polynome L ALORS f 0 ALORS 1 ALORS posant 0 ALORS R 1 Corrig du probl me 83 Chapitre 2 Structures s quentielles simples SI p exposant 1 ALORS AFFICHER x SINON AFFICHER x p exposant FINSI FINSI RETOURNER FINSI SI p coeff 1 ALORS SI p exposant 0 ALORS AFFICHER 1 SINON SI p exposant 1 ALORS AFFICHER x SINON AFFICHER x1 p exposant FINSI RETOURNER FINSI SI p coeff lt 0 ALORS SI p exposant 0 ALORS AFFICHER p coeff SINON SI p exposant 1 ALORS AFFICHER p coeff SINON AFFICHER p coeff x p exposant FINSI FINSI SINON SI p exposant 0 ALORS AFFICHER p c
22. NULL return list head 1 while 1 gt succ NULL amp amp 1 gt succ head if 1 gt succ gt prev NULL 1 gt succ gt prev l 1 gt succ if 1 gt succ NULL head gt prev 1 Exercice 3 4 Inverser pile et file e Inversion de pile Sp cification de l algorithme FONCTION reverseQueue p_q Queue 1Queue VAR valeur longueur entier invers e lQueue temp 1Stack DEBUT SI p_q NULL ALORS RETOURNER NULL FINSI longueur p_q length invers e newEmptyQueue r sultat de l inversion temp newEmptyStack pile pour stockage des valeurs principe empiler tous les l ments de la file puis les d piler dans la file inverse TANTQUE longueur gt 0 FAIRE qPop amp valeur p_q sPush valeur temp qPush valeur p_q longueur longueur 1 FAIT construction de la file inverse longueur lt p_q length TANTQUE longueur gt 0 FAIRE sPop amp val temp qPush val invers e longueur longueur 1 108 Dunod La photocopie non autoris e est un d lit Corrig s des exercices FAIT RETOURNER invers e FIN Implantation C Entr e la file source dont il s agit de construire l inverse Sortie la file inverse Cr e la file inverse de la file p_q 1Queue reverseQueue const 1Queue p_q if p_q NULL fprintf stderr reverseQueue error null queue return NULL int val int length p_q
23. VAR rep caractere pour la saisie des valeurs tape num ro 1 initialisation des variables t_ut 0 ce stade pas de variable dans le tableau FAIRE AFFICHER entrez une valeur dans le tableau valeur rang e dans la case d indice t_ut SAISIR tabloval t_ut incr mentation de t_ut car ajout d un l ment t_ut lt t_ut l AFFICHER une autre saisie o n SAISIR rep la boucle reprend s il reste de la place dans le tableau ET si l utilisateur souhaite continuer TANTQUE t_ut lt 50 ET rep o pour l instant le plus grand est dans la case 0 maxi tabloval 0 cherchons case par case de l indice 1 t_ut 1 POUR cpt DE 1 A t_ut 1 FAIRE si l on trouve plus grand SI tablovallcpt gt maxi ALORS la valeur est m moris e dans maxi maxi tabloval cpt FINSI FAIT 1 6 4 Les tableaux plusieurs dimensions Il est possible de d finir des tableaux plusieurs dimensions en les indiquant dans des crochets successifs lors de la d finition du tableau Pour des propos d illustration l exemple se limitera deux dimensions la g n ralisation N dimensions est imm diate Certains probl mes notamment les jeux de plateau ont une repr sentation naturelle en deux dimensions avec un rep rage en lignes colonnes ou abscisse ordonn e Exemple Un damier se repr sente comme un plateau de 100 cases constitu de 10 lignes et 10 colonnes U
24. a construire un automate non d terministe d abord tg dg fg dg Figure 5 50 Tableau 5 28 Etat a b 02 12 01 01 12 1 12 2 01 1 2 P 2 P 01 P P P EA D Un automate d terministe complet qui reconna t l ensemble des mots sur l alphabet 0 1 qui contiennent exactement trois fois le symbole 1 se construit directement sans qu on ait besoin de 0 1 199 Chapitre 5 Automates D o l automate reconnaissant le compl ment de ce langage 554 Figure 5 51 i L tat P n est plus un tat poubelle car il est un tat terminal Solution b 0 1 0 1 Figure 5 52 Cet automate n est pas d terministe il faut le d terminiser e D terminisation Tableau 5 29 Etat 0 1 0 0 01 01 01 01 0 1 1 Figure 5 53 200 Dunod La photocopie non autoris e est un d lit Corrig s des exercices En fait on aurait pu dessiner cet automate d s le d but Cet automate d terministe est complet donc pour construire l automate reconnaissant le compl ment du langage il suffit de modifier la position de la sortie 9 4 Figure 5 54 Ilest facile de voir qu ici l tat 01 est la poubelle Exercice 5 9 Nous construisons d abord un automate qui lit tous les mots qui se terminent par abaab Puis nous le d terminiserons et compl terons et puis nous ferons de tous les tats finaux tats non finaux et vice versa La minimisa
25. avec l alphabet A 0 1 Figure 5 14 La proc dure de minimisation donne T 1 T 12 182 Dunod La photocopie non autoris e est un d lit 5 3 L interpr tation intuitive Oo 1 2 3 4 5 6 I II 1 2 3 6 4 5 7 II III en recyclant les chiffres romains 0 Voici l automate minimis 1 1 Figure 5 15 5 3 2 Automate asynchrone Souvenons nous que jusqu ce point nous avons vit le mot vide Un automate fini dans lequel certaines fl ches sont tiquet es par le mot vide transitions s appelle automate asynchrone L ensemble des fl ches v rifie donc E C Q x AU e x Q Proposition pour tout automate asynchrone il existe un automate fini ordinaire c d sans e transitions qui reconna t le m me langage Comme tout automate non d terministe est quivalent un automate d terministe il en suit que tout automate asynchrone est quivalent 4 un automate d terministe Il existe un algorithme de suppressions de e transitions Pour un automate asynchrone C Q 1 T E avec E C Q x A U e x Q nous allons construire un automate B Q T F qui ne diff re de C que par l ensemble de ses fl ches et ce suivant une r gle bien d termin e e par d finition on a p a q F s il existe un chemin e e e a e c Po gt P1 kaea gt Pn gt do gt q1 gt dm et Po P 4m 4 eo sa SEP EO T Po p P
26. avec une longueur qui se r duit chaque tape tree prevLine root ligne de sad gt sad gt pr c dente tree prev prevLine unsigned i n while i gt 0 passage a la ligne suivante d abord cr er sa t te currLine prevLine gt sag newSingletonTree 1 curr currLine unsigned j i on co it re la ligne pr c dente avec la ligne en cours de cr ation pour profiter de la formule de Pascal while j gt 0 prev prev gt sad curr gt sad newSingletonTree curr gt content prev gt content gt cl de performance de algo curr curr gt sad prevLine currLine prev prevLine Complexit algorithmique compar e Pour que le gain entre le calcul de toutes factorielles et l exploitation de la formule de r currence de Pascal ne soit pas seulement abstrait valuons la complexit algorithmique compar e entre les deux approches en fonction d un param tre n qui repr sente le niveau de profondeur de l arbre avec premier niveau pour n 0 Pour calculer une factorielle d un entier n il faut r aliser n 1 produits avec affectation de chaque r sultat interm diaire dans une variable temporaire Notons c f n le co t du calcul d une fonction f n c n 2 n 1 Pour calculer une combinaison nous avons trois factorielles un produit et une division trois affectations 165 Chapitre 4 Structures arborescentes c amp c am c n
27. cesseurs en sus des successeurs Les probl mes d insertion suppression en d but ou fin de listes vs en milieu de liste restent peu pr s les m mes qu avec une liste simplement cha n e e Insertion Sp cification de l algorithme Insertion dans une liste doublement chain e pl liste o s effectue l insertion place place dans la liste on ins re juste devant 112 Dunod La photocopie non autoris e est un d lit Corrig s des exercices k l ment ins rer status code 0 ok 1 non ok Type abstrait list inserer list 1 int k element e FONCTION insert pl list place list k entier bool en VAR noeudk last prec list DEBUT la place concern e est elle bien dans la liste SI appartient place pl ALORS RETOURNER faux FINSI noeudk newSingletionList k cr ation d un neud cf p 87 cas de la liste vide SI pl NULL ALORS pl noeudk RETOURNER vrai FINSI cas de la place en t te de liste SI place pl ALORS noeudk mis en t te de liste noeudk succ pl noeudk prec NULL pl lt noeudk RETOURNER vrai FINSI cas de la place en fin de liste SI place NULL ALORS last lastElement pl on trouve le dernier l ment de la liste last succ noeudk noeudk prev last RETOURNER vrai FINSI autre cas place en milieu de liste prec place prev prec succ noeudk noeudk succ place neud kprev lt prec plac
28. es LIFO pour Last In First Out c est dire dernier entr premier sorti une bonne image pour repr senter une pile est une pile d assiettes c est en haut de la pile qu il faut prendre ou mettre une assiette Les op rations sur les piles sont tester si une pile est vide acc der au sommet d une pile empiler un l ment retirer l l ment qui se trouve au sommet d piler On peut utiliser pour impl menter les piles toutes les repr sentations possibles pour les listes On va parler en d tail d une repr sentation chain e mais il faut comprendre que la repr sentation contigu est tout fait possible 3 1 1 Repr sentation contigu des piles Les l ments de la pile sont rang s dans un tableau et l on conserve aussi l indice du sommet de pile D finition d une structure de pile r alis e avec un tableau Pseudo code formel STRUCTURE tStack content T n top entier Implantation C typedef struct tStack lt type gt content n int top tStack 87 Chapitre 3 Structures s quentielles complexes La pile vide est repr sent e par tout enregistrement dont le champ top contient 1 car ce champ repr sente l indice de la derni re case du tableau content de stockage des donn es 5 1 8 3 1 2 Repr sentation cha n e des piles Les l ments de la pile sont cha n s entre eux et le sommet d une pile non vide est le pointeur vers le premier
29. gt length lQueue p_rev_q newEmptyQueue la file inverse retourn e 1Stack p_tmp_s newEmptyStack la pile pour l inversion while length gt 0 qPop amp val p_q d filement depuis la file d entr e p_q sPush val p_tmp_s empilement dans la pile d inversion qPush val p_q r enfile val rotation de p_q construction de la file inverse length p_q gt length while length gt 0 sPop amp val p_tmp_s qPush val p_rev_q free p_tmp_s Soyons diligents avec la m moire return p_rev_q Exemple d inversion de file void testQueueReversing printf n ninversion d une file n n int val 10 1Queue p_q newEmptyQueue do qPush val p_q while val gt 0 printListGraph p_q gt head input queue 109 Chapitre 3 Structures s quentielles complexes TlQueue p_rev_q reverseQueue p_q printListGraph p_rev_q gt head reversed queue printListGraph p_q gt head unchanged input queue e Inversion de pile Sp cification de l algorithme FONCTION reverseStack p_s IStack 1Stack VAR valeur entier invers e temp 1Stack DEBUT SI p_s NULL ALORS RETOURNER NULL FINSI invers e newEmptyStack temp newEmptyStack FAIRE sPop amp valeur p_s sPush valeur invers e sPush valeur temp TANTQUE isEmptyStack p_s FAIRE sPop amp valeur t
30. joseph removeKkst amp joseph k AFFICHER i i itl printListGraph joseph FAIT FIN Implantation C Ex cution du proc d d limination de Joseph void playJoseph int n int k printf nPlay Joseph for n d and k d n n k list joseph newJosephCList n printListGraph joseph 1 118 Dunod La photocopie non autoris e est un d lit Corrig s des probl mes int i 2 while joseph NULL joseph removeKst amp joseph k printf d i printListGraph joseph e Construction de la liste circulaire Sp cification de l algorithme FONCTION newJosephCList longueur entier list VAR joseph list DEBUT SI longueur lt 1 ALORS RETOURNER NULL FINSI joseph newJosephList longueur 1 appel de la fonction qui suit concat amp joseph amp joseph RETOURNER joseph FIN FONCTION newJosephList longueur entier premier entier list VAR t te list DEBUT SI longueur lt 1 ALORS RETOURNER NULL FINSI RESERVER t te t te contenu premier t te succ newJdosephList longueur 1 premier 1 RETOURNER t te FIN Implantation C Cr ation d une liste circulaire de 1 n version r cursive list newJosephCList int longueur if longueur lt 1 return NULL list joseph newJosephList longueur 1 concat amp joseph amp joseph voir exercice 2 2 return joseph 119 Chapitre 3 Structures s quentielles complexes list newJos
31. pas d l ment x dans la liste while 11 gt succ NULL amp amp 11 gt succ gt content x 11 11 gt succ si nous avons atteint la fin de liste c est une op ration blanche if 11 gt succ NULL return 0 CODE GENERIQUE COMMUN DE FINALISATION Cas du s lecteur position Donn e k la distance de la t te de liste au point de coupe int cutC plist pll plist pl2 unsigned k CODE GENERIQUE COMMUN D INITIALISATION cas de la coupure en t te de liste if k 0 pl1 NULL ol2 11 return status Sinon on parcourt la liste jusqu au pr d cesseur du point de coupe ou jusqu la queue de liste cutPoint pointe sur une autre liste while 11 gt succ NULL amp amp k gt 0 11 11 gt succ si nous avons atteint la fin de liste c est une erreur if 11 gt succ NULL return ERR CODE GENERIQUE COMMUN DE FINALISATION Cas du s lecteur l ment minimal int cutD plist pll plist pl2 CODE GENERIQUE COMMUN D INITIALISATION on r utilise la fonction minOf de mesure de longueur de liste int min minOf 11 sur vos copies il faut la r crire cas de la coupure en t te de liste 73 Chapitre 2 Structures s quentielles simples if min 11 gt content p11 NULL pl2 11 return status Sinon on parcourt la liste jusqu au pr d cesseur du point de coupe whil
32. pos_prod content pos_prod_ok 1 if content lt 0 neg_prod content neg_prod_ok 1 while 1 gt succ NULL gt succ content 1 gt content if contenu gt 0 pos_prod content pos_ prod_ok 1 if contenu lt 0 Dunod La photocopie non autoris e est un d lit Corrig s des exercices neg_prod content neg_prod_ok 1 if pos_prod_ok pos pos_prod if neg_prod_ok neg neg_prod if pos_prod_ok amp amp neg_prod_ok return 4 if pos_prod_ok amp amp neg_prod_ok return 2 if pos_prod_ok amp amp neg_prod_ok return 1 return 0 Exercice 2 10 Couper une liste en deux tude Dans les cinq cas de figure il s agit de v rifier l existence d une position de coupe dans la cha ne et le cas ch ant d effectuer celle ci puis de savoir retourner les deux cha nes Le cas vacuer en d but de fonction est celui de la liste vide Ensuite nous devons respectivement pour les cinq cas e A v rifier que le pointeur d signe bien un maillon de la liste e B v rifier que la liste contient bien la donn e x e C v rifier que la liste contient au moins k l ments e D identifier la valeur minimale de la liste e E mesurer la longueur de la liste Les cas A B et C sont tr s similaires et doivent int grer les cas de t te et de queue de liste Les cas D E n cessitent u
33. puis range dans un second temps cette valeur calcul e dans la variable qui se trouve gauche de l op rateur d affectation 1 4 4 Op rateurs d entr e sortie Les op rations que nous venons d aborder permettent juste de faire des calculs mais ne permettent pas encore de visualiser les r sultats ou d afficher du texte ou encore de faire des saisies au clavier Pour cela nous utiliserons les commandes AFFICHER et SAISIR e AFFICHER sert comme son nom l indique afficher du texte ou les valeurs des variables On utilise afficher suivi entre parenth ses des diff rents l ments faire appara tre l cran Ces l ments sont soit du texte brut crit entre doubles guillemets soit une expression Dans le cas de texte brut ce dernier appara t tel quel l cran Dans le cas d une expression c est la valeur num rique du calcul de cette expression qui est affich e Les l ments successifs afficher sont s par s par une virgule Exemple VAR t r el d finition de la variable enti re t t 2 421 AFFICHER t vaut t cette instruction fera apparaitre l cran le message suivant t vaut 2 421 1 5 Structure de contr le e SAISIR permet d initialiser une variable partir d une saisie faite au clavier On utilise saisir suivi entre parenth ses du nom de la variable que l on veut saisir L instruction saisir a pour seul effet d attendre que l utilisateur e
34. seul le crit re de choix des l ments supprimer change Pour illustrer ce fait dans la partie Sp cification de l algorithme le second param tre de la fonction removeAll est en r alit une fonction nomm e crit re Cette fonction crit re a pour param tre un entier la valeur extraite de la liste et pour sortie un bool en indiquant si la valeur O 75 Chapitre 2 Structures s quentielles simples 76 r pond au crit re de suppression Cette fonction crit re peut avoir d autres param tres notamment un entier indiquant le seuil partir duquel effectuer la suppression pour les cas D et E Sp cification de l algorithme FONCTION removeAll pl list crit re entier bool en entier VAR 1 suppr list DEBUT SI pl NULL ALORS RETOURNER 1 1 signale une erreur FINSI 1 pl SI 1 NULL ALORS RETOURNER O O indique qu aucune suppression n est faite FINSI suppression partir de la t te de liste TANTQUE 1 NULL ET crit re 1l content vrai FAIRE suppr suppr succ LIBERER suppr FAIT xp suite de la liste TANTQUE 1 NULL FAIRE TANTQUE 1 succ NULL ET crit re 1 succ content vrai FAIRE suppr lt 1l succ l succ suppr succ LIBERER suppr FAIT 1 1 succ FAIRE RETOURNER 1 indique que tout s est bien pass FIN Implantation C Donn es modifi es la liste dont on supprime des l ments R sultat
35. 03 0 01 G A B Terminal 013 02 012 H D C Le dessin n est pas trop utile pour cet automate e Minimisation Oo I II avec I A B C D I E F G H Tableau 5 39 Etat a b a A A B l g F E B C l Ot c F E Il e en D G H Il E E F E Il z F G H Il a 2 G A B I 5 H D C I IL IIL IV avec I A B II C D IN E F IV G H 205 Chapitre 5 Automates Tableau 5 40 Etat a b A b A A B l B D c Il Il c F E Ill Ill D G H IV IV E F E Ill ill F G H IV IV G A B I H D C Il Il Tous les tats se sont s par s l automate tait minimal d s le d but Solution A3 Reprenons l automate d terministe complet A Figure 5 59 e Minimisation Tableau 5 41 tat a b 0 01 01 01 01 012 012 0123 012 0123 0123 0123 a Oo L II avec I 0 01 012 II 0123 a b Tableau 5 42 Etat a b a b 0 01 01 l 01 01 012 l 012 0123 012 Il l L tat 012 est sorti du groupe I Nouveaux groupes I IL II avec I 0 01 I 012 I 0123 206 Dunod La photocopie non autoris e est un d lit Corrig s des exercices Tableau 5 43 tat a b a B 0 01 01 l 01 01 012 l Il Tous les tats se sont s par s l automate tait minimal d s le d
36. 4 4 eee eee eee 7 1 4 2 Constantes e eee eee 7 1 4 3 Op rateurs arithm tiques et expressions 8 1 4 4 Op rateurs d entr e sortie 0 cake res spamemamenepepieepanuaua x 8 1 5 Structure d contr l icc suede esse iadusasees coer aceeeddaueaedsaeebeea R 9 1 5 1 Conditions et tests 9 1 5 2 Ex cution conditionnelle d instructions 9 1 5 3 It rations et boucles 12 116 TADIEAUX 2 a ne errant te a benoit certes 14 1 61 D N eseni wl Glob Re Dalida ete tite tease tin 14 1 6 2 Repr sentation 15 1 6 3 Relation entre tableaux et boucles 16 1 6 4 Les tableaux plusieurs dimensions 17 1 7 Pointeurs 4444 44444 18 1 7 1 Notion d adresse 18 1 7 2 D finition et contenu 19 1 7 3 Initialisation 2 212 248482 atome eue oo eke ae ware me memes ob aaa ad due a cons de eee 20 1 8 Les sous programmes ou fonctions 23 1 8 1 D finition d une fonction
37. On consid re deux listes cha n es L et Lz dont les l ments sont des entiers crire un algorithme qui rattache la liste L3 la suite de la liste L4 Tous les cas particuliers doivent tre pris en compte NONC S DES EXERCICES ET DES PROBL MES Exercice 2 1 Rechercher l l ment maximal d une liste crire deux algorithmes l un it ratif l autre r cursif qui permettent de d terminer la valeur maximale d une liste cha n e d entiers positifs 45 Chapitre 2 Structures s quentielles simples x Exercice 2 3 Extraire deux listes partir d une liste Soit une liste de nombres relatifs crire un algorithme permettant de s parer cette liste en deux listes la premi re ne comportant que des entiers positifs ou nuls et la seconde ne comportant que des nombres n gatifs Exercice 2 4 Permuter deux places d une liste crire un algorithme sur une liste simplement cha n e qui change les positions des n uds donn es par deux pointeurs t et v Exercice 2 5 Supprimer des l ments Soit L une liste cha n e crire trois algorithmes tels que e dans le premier on supprime toutes les occurrences d un l ment donn x e dans le deuxi me on ne laisse que les k premi res occurrences de cet l ment et on supprime les suivantes e dans le troisi me pour chaque l ment de la liste on ne laisse que sa premi re occurrence Concevez le second algorithme en adaptant le pr
38. affecter d o son nom une valeur une variable Sa syntaxe est la suivante CaA nom_de_variable valeur_ _affecter Le symbole lt indiquant le sens de I affectation La valeur d une variable qui n a pas subi d affectation est al atoire Elle est repr sent e par un point d interrogation 1 4 2 Constantes Il est possible d affecter des valeurs num riques appel es constantes dans une variable Comme toute valeur une constante est typ e et ce type a une influence sur la syntaxe e Constantes de type entier il suffit juste d crire la valeur en base dix cette valeur peut tre positive ou n gative La variable recevra alors la valeur choisie Constantes de type r el elles sont crites sous la forme mantisse exposant c est dire la notation scientifique avec les puissances de dix utilis e par les calculatrices La virgule est repr sent e par un point notation anglo saxonne et l exposant qui est un nombre positif ou n gatif est pr c d du symbole E Il est possible de ne pas indiquer l exposant lorsque celui ci est nul le signe devant l exposant si celui ci est positif la partie d cimale d un nombre si celle ci est nulle par contre on fera toujours figurer le point d cimal Constantes de type caract re est possible d affecter un entier un caract re en utilisant une constante enti re ou en indiquant le caract re souhait entour de
39. b A B D Il Il D B E Il Il B c A Il Il E B E Il Il c P A l Il e Minimisation Qo I II avec I P If A B C D E Nouveaux groupes d tats I P H C IN A B D E Tableau 5 51 tat a b a b A B D Il ill D B E ull ill B c A Il ul E B E ul ul Nouveaux groupes d tats I P H C IN B IV A D E Tableau 5 52 tat a b a b A B D Ill IV D B E Il IV E B E Il IV Le groupe IV ne se s pare pas Le r sultat a b TA to Figure 5 65 211 Chapitre 5 Automates Exercice 5 12 e tats 0 1 2 fl ches 0 a 1 mod 3 0 a 1 1 a 2 mod 3 1 2 2 2 a 3 mod 3 2 a 0 1 b 0 1 b 1 2 b 0 2 b 2 Tableau 5 53 Etat a b 0 1 1 2 0 1 2 0 0 2 b a a b Figure 5 66 J Ag tats 0 1 2 3 fl ches 0 a 1 mod 4 0 a 1 1 a 2 mod 4 1 a 2 2 a 3 mod 4 2 a 3 2 a 4 mod 4 2 a 0 1 b 0 1 b 1 2 6 0 2 b 2 3 b 0 3 b 3 Tableau 5 54 Etat a B 0 1 1 2 0 1 2 3 0 2 3 0 0 3 212 Dunod La photocopie non autoris e est un d lit Corrig s des exercices b a P a b a b a b Figure 5 67 e An Tableau 5 55 Etat a B 0 1 1 2 0 1 2 3 0 2 3 4 0 3 n 1 0 0 n 1 af b LA o a Figure 5 68 213 Chapitre 5 Automates e D terminisation
40. but Solution A4 Reprenons l automate d terministe complet A4 Figure 5 60 e Minimisation Tableau 5 44 Etat 0 1 A AB B AB ABC BC ABC ABC BC B c c c BC c c l AB 0 1 0 1 4 0 1 0 1 0 1 Oo L II avec I A C H AB ABC BC B 207 Chapitre 5 Automates Tableau 5 45 Etat 0 1 0 1 E 2 A AB B Il Il oe E 5 C C l AB ABC BC Il Il T ABC ABC BC Il Il g v S 3 BC C C l o B Cc C l On peut voir imm diatement que les tats A et C se s parent et que le groupe II se divise en deux groupes qui ne pourront plus se s parer On obtient donc les tats de l automate minimis A B BC AB ABC et C Graphiquement cet automate minimal se pr sente comme Figure 5 61 o l tat C sert comme l tat poubelle L automate d terministe correspondant A4 n tait donc pas minimal On voit qu en le minimisant on est arriv au m me automate qu on a obtenu en d terminisant l automate A4 initial non d terministe duquel on a coup sa poubelle Remarque On rappelle encore une fois que la poubelle d un automate non d terministe l tat ou le groupe d tats dont on ne peut pas allez vers la ou les sortie s n est pas la m me chose que la poubelle de automate d terministe qui en r sulte apr s la d terminisation La seule utilit de la poubell
41. c t droit de l arbre Figure 4 25 162 Dunod La photocopie non autoris e est un d lit Corrig s des probl mes Strat gie de r solution e Utilisation de la formule de r currence de Pascal Le proc d de construction d un arbre est naturellement r cursif et en particulier celui ci La formule de Pascal est une r currence qu il convient d exploiter pour viter de recalculer pour chaque n ud de l arbre une expression qui comprend trois factorielles dont on sait le co t prohibi tif Ne pas exploiter cette r currence est une v ritable erreur professionnelle pour un informaticien C est ce qui a justifi un bonus suppl mentaire pour les quelques unes et quelques uns qui y ont pens e Approche r cursive ou it rative Comme on supprime les filiations gauches il faut qu un parent gauche puisse passer la valeur du parent droit non reli tout nouveau fils droit qu il cr e Si on reste sur une vision arbre a peut devenir compliqu en particulier en cherchant une m thode r cursive Or si l on constate que l arbre n est rien d autre qu une liste de listes la premi re liste tant la branche de droite 1 1 1 puis la branche 1 2 3 puis 1 3 6 alors le probl me appara t plus simple et se pr te naturellement une proc dure it rative deux boucles La figure 4 26 la m me sous une perspective peine diff rente
42. ce cas la taille utile est diminu e de 1 ou d cr ment e Avant d enlever un l ment du tableau il faut v rifier que la taille utile est strictement positive c est dire qu il y a au moins un l ment dans le tableau Enfin cette variable stockant la taille utile d un tableau n a pas de nom qui lui est sp cifiquement d di Pour des raisons de lisibilit cette variable sera nomm e util ou tai_ut par exemple 1 6 3 Relation entre tableaux et boucles Les boucles sont extr mement utiles pour les algorithmes associ s aux tableaux En effet de nombreux algorithmes relatifs au tableau n cessitent de parcourir les l ments du tableau dans un certain ordre le plus souvent dans le sens des indices croissant Le traitement de chacun des l ments tant souvent le m me seule la valeur de l indice est amen e changer Une boucle est donc parfaitement adapt e ce genre de traitements Illustration par un algorithme de recherche de la plus grande valeur stock e dans un tableau d en tiers Cet algorithme est abondamment comment car il est une synth se des notions rencontr es pour les tableaux 16 Dunod La photocopie non autoris e est un d lit 1 6 Tableaux PROGRAMME recherche max VAR maxi entier stocke la valeur du maximum VAR tabloval entier 50 un tableau stockant des valeurs VAR t_ut entier la taille utile du tableau VAR cpt entier index des l ments du tableau
43. champs est de type pointeur vers une structure cha n e du m me type Exemple de d finition d une structure cha n e Pseudo code formel STRUCTURE n ud nom caract re 20 prenom caract re 20 suiv n ud TYPE ptr_neud n ud Implantation C typedef struct n ud char nom 20 36 2 1 Listes lin aires char prenom 20 struct neud suiv neud typedef neud ptr_neud La liste vide est repr sent e par le pointeur NULL Figure 2 1 Liste simplement chain e Cette repr sentation n impose pas une longueur maximum sur les listes elle permet de traiter facilement la plupart des op rations sur les listes le parcours s quentiel l insertion et la suppres sion d un l ment a une place quelconque la concat nation de deux listes se font par une simple manipulation des pointeurs Cependant le calcul de la longueur n cessite le parcours de toute la liste de m me l acc s au k l ment n est plus direct on doit parcourir k 1 pointeurs partir de la t te pour trouver le k l ment Avant de passer aux exemples de fonctions qui traitent les listes chain es il faut faire un petit rappel sur les variables dynamiques 2 1 3 Variables dynamiques e C est une variable dont la place m moire est allou e en cours d ex cution e On ne prend de la place m moire que lorsqu on en a besoin e Cette place m moire est allou e explicitement c est a dire par une inst
44. dans ce cas Continuons le programme pour illustrer les relations entre les variables ptr_c et lettre lettre Y AFFICHER ptr_c 1 cette instruction affiche 2Z Explication avec des valeurs num riques Lors de la d finition de la variable lettre une adresse lui est automatiquement attribu e par l ordinateur La valeur choisie est par exemple 102628 ce nombre n a aucune importance mais aide illustrer l explication L adresse de lettre amp lettre vaut donc 102628 et lettre vaut Y suite son initialisation par l instruction lettre Y Suite l ex cution de l instruction ptr_c lt amp lettre le pointeur ptr_c re oit 102628 la valeur de ptr_c est donc 102628 Que vaut le contenu de ptr_c ptr_c Le contenu du pointeur ptr_c est la Valeur stock e en m moire l adresse 102628 car ptr_c vaut 102628 Il se trouve que cette adresse est celle de la variable lettre Ainsi ptr_c vaut Y Il n est donc pas tonnant que ptr_c 1 soit gal 7 Allocation dynamique de m moire et commande RESERVER Le dernier type et le plus int ressant d initialisation de pointeur consiste effectuer cette initiali sation l aide d une nouvelle adresse autoris e C est rendu possible par l emploi d une nouvelle commande dont le but est d obtenir une zone de stockage m moire dynamiquement c est dire lors de l ex cution du programme Cette commande se nomme
45. de donner la taille maximale d un tableau sous la forme d une constante est une contrainte lourde puisque cette valeur est fix e lors de I criture du programme Or un tableau ne stockera pas en pratique toujours autant d l ments que sa taille maximale Il est donc n cessaire de savoir combien de variables sont r ellement int ressantes traiter Ce nombre de variables doit tre stock dans une variable de type entier nomm taille utile du tableau par opposition la taille maximale fournie la d finition du tableau Dans un tableau dont la taille utile est P et dont la taille maximale est N les variables int ressantes seront rang es aux indices compris entre 0 et P 1 Les cases dont les indices vont de P N 1 stockent des valeurs car une variable n est jamais vide mais elles ne seront pas concern es par les traitements ou instructions effectu es A chaque d finition d un tableau est associ e la d finition de sa taille utile Ceci doit tre syst matique Cette taille utile peut voluer lorsque e Un l ment est ajout au tableau dans ce cas la taille utile est augment e de 1 ou encore incr ment e Avant d ajouter un l ment il faut v rifier qu il reste au moins une case disponible la taille utile doit tre inf rieure strictement a la taille maximale du tableau Cette v rification est r alis e par l emploi d un test instruction si e Un l ment est retir du tableau dans
46. de z ros Sp cification abstraite Entr e la liste d entiers Entr e modifi e le produit des positifs et le produit des n gatifs Sortie code de statut qui peut prendre l un des 4 tats TOUT 4 UNIQUEMENT _POSITIFS 2 UNIQUEMENT NEGATIFS 1 RIEN 0 Algorithme FONCTION produits l liste lt entier gt pos neg entier statut VAR pos_ok neg_ok bool en p place DEBUT pos 1 pos_ok faux neg 1 neg_ok faux SI estvide 1 ALORS p t te 1 SI contenu p gt 0 ALORS pos contenu p pos_ok vrai FINSI SI contenu p lt 0 ALORS neg lt contenu p neg_ok vrai FINSI TANTQUE dernier p FAIRE p succ p SI contenu p gt 0 ALORS pos pos contenu p pos_ok lt vrai FINSI SI contenu p lt 0 ALORS neg neg contenu p neg_ok lt vrai FINSI FAIT 69 Chapitre 2 Structures s quentielles simples 70 FIN SI SI pos_ok ALORS SI neg_ok ALORS RETOURNER TOUT SINON RETOURNER UNIQUEMENT _POSITIFS F SIN INSI ON SI neg_ok ALORS RETOURNER UNIQUEMENT NEGATIFS SINON RETOURNER RIEN F FIN FIN INSI SI Implantation C status code 4 tout 2 positifs 1 n gatifs 0 rien int p if int int int int int rodui 1 pos_ pos_ neg_ neg_ ts list 1 int pos int neg NULL return 0 prod 1 prod_ok 0 prod 1 prod_ok 0 content 1 gt content pas indispensable mais conomique if content gt 0
47. donn dont la racine contient la valeur Co le fils gauche de la racine C i le fils droit de la racine C E puis d s la profondeur n 2 dont les fils gauche et droit du fils le plus gauche de profondeur n 1 contenant C 9 _1 contiennent respectivement les valeursC et C et dont tous les n uds situ s droite de ces deux fils contenant ce gt l soient les fils droits de leur p re de niveau n 1 contenant C ss 129 143 Chapitre 4 Structures arborescentes Figure 4 22 Triangle de Yang Hui Source http en wikipedia org wiki File Yanghui_triangle gif Le h vous est donn et l algorithme peut tre r alis en pseudo code ou directement en C typedef struct treeNode int contenu struct treeNode sag sad treeNode typedef treeNode tree void buildPascalTriangle tree t unsigned n RE Probl me 4 2 Interlude Syracusien Une suite de Syracuse de terme initial un entier N est d finie par a N N Se n pair st sm 3 impair s3 Snap 35 1 Wn EN 144 Dunod La photocopie non autoris e est un d lit Probl mes Il semblerait que quel que soit N la suite s converge vers 1 i e VNEN 4EeN s 1 Dans cet interlude il vous est demand de r aliser une fonction r cursive qui construit un arbre de Syracuse de racine un entier donn e de profondeur donn e g dont les branches sont toutes les suites de Syracuse qui convergent vers e en q
48. e Lire c est prendre l information r f renc e par lecteur condition que cela soit possible et d placer le pointeur de lecture sur le poste suivant 93 Chapitre 3 Structures s quentielles complexes e Ecrire c est mettre une information r f renc e par le pointeur Ecriture si cela est possible et d placer le pointeur d criture sur le poste suivant Ecriture Lecture Figure 3 1 tat initial du buffer clavier On ne peut pas lire si rien n a t crit ou si l information a t d j lue On ne peut pas crire si le poste contient une information encore non lue Exemple Ecriture Lecture Figure 3 2 criture C gt copy a le fait de taper RC entame la lecture On tape dir tr s rapidement 94 Dunod La photocopie non autoris e est un d lit Ecriture Figure 3 3 Lecture et criture simultan es Mod le statique Pseudo code formel STRUCTURE elt info T alire bool en Implantation C typedef struct elt T info bool en alire elt alire est un flag drapeau alire vrai on peut lire mais pas crire alire faux on peut crire mais pas lire Pseudo code formel SRUCTURE liste_circ donn e elt n lecteur entier crivain entier Lecture 3 2 Les files 95 Chapitre 3 Structures s quentielles complexes Implantation C typedef struct liste_circ elt donn e n int lecteur int crivain liste _c
49. en Physique th orique aux Etats 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 domaine de mod lisation de grosses mol cules biologiques sur ordinateur Depuis plusieurs ann es il travaille comme enseignant en math matiques en statistique et en informatique dans quelques tablissements de la r gion parisienne a des niveaux tr s diff rents en frangais et en anglais REMERCIEMENTS Nous remercions nos tudiants de l EFREI sans qui l laboration de ce contenu n aurait pu trouver le juste diapason p dagogique C est par la somme de nos interactions qu mergent et s am liorent nos contenus d apprentissage par la pratique Nous remercions notre diteur Jean Luc Blanc qui nous a donn la chance de produire ce cahier sur la base de nos existants p dagogiques dans le cadre de la collection Exercices amp Probl mes ou il trouve une place coh rente par rapport d autres ouvrages de math matiques appliqu es Nous remercions nos familles et nos amis pour avoir tol r ce temps suppl mentaire que nous leur avons soustrait et pour leur soutien pourtant ind fectible XI Dunod La photocopie non autoris e est un d lit INTRODUCTION QU EST CE QUE L ALGORITHMIQUE Un probl me est un questionnement qui appelle une solution Mais existe t il seulement une solution Tout probl me en induit deux autres deux q
50. est son contenu Une adresse est le num ro d une cellule m moire et dans cette cellule se trouve une valeur Cette valeur est appel e le contenu du pointeur et ne doit pas tre confondue avec sa valeur Le contenu d un pointeur est la valeur de la cellule m moire dont ce pointeur stocke l adresse Puisque ces deux notions sont diff rentes il existe une nouvelle notation pour indiquer l acc s un contenu cette notion est l op rateur lire toile Cet op rateur est le m me que l op rateur de multiplication mais le contexte d criture permet l ordinateur de reconna tre quelle est la signification exacte de cet op rateur Voici une r gle tr s simple et tr s utile pour l utilisation de cet op rateur il se lit toujours comme contenu de et non pas pointeur Cette r gle vitera de nombreuses confusions par la suite Exemple Soit ptr un pointeur Supposons que la valeur de ce pointeur soit 25040 rappelons que cette valeur est tout a fait arbitraire Supposons galement que dans la m moire l emplacement 25040 se trouve la valeur 17 Dans ce cas la Valeur de ptr not e ptr est 25040 Le contenu de ptr not ptr est la valeur de la cellule m moire num ro 25040 c est dire 17 ptr vaut donc 17 Type point Quelle est la syntaxe permettant de d finir un pointeur Cette syntaxe n est h las pas imm diate sinon elle aurait d j t pr sent e car le ty
51. getPrimeChildren t sag SI gcd t content t sag content 1 ALORS primechild newSingletonList t sag content SI primechild 3 NULL ALORS primechild succ sagprimechildren Sagprimechildren lt primechild FINSI FINSI FINSI SI t sad NULL ALORS sadprimechildren getPrimeChildren t sad SI gcd t content t sad content 1 ALORS primechild newSingletonList t sad content SI primechild NULL ALORS primechild succ sadprimechildren sadprimechildren primechild FINSI 158 Dunod La photocopie non autoris e est un d lit Corrig s des exercices FINSI FINSI RETOURNER concat amp sagprimechildren amp sadprimechildren FIN Algorithme d Euclide accessible dans les Elemens FONCTION gcd numerator entier denominator entier entier DEBUT SI denominator 0 ALORS RETOURNER numerator SINON RETOURNER gcd denominator numerator denominator FINSI FIN R alisation en C list getPrimeChildren tree t if t NULL return NULL list sagprimechildren NULL list sadprimechildren NULL list primechild if t gt sag NULL sagprimechildren getPrimeChildren t gt sag if gcd t gt content t gt sag gt content 1 primechild newSingletonList t gt sag gt content if primechild NULL primechild gt succ sagprimechildren sagprimechildren primechild if t gt sad NULL sadprimechildren getPri
52. instruction ou du bloc d instruction concern e e Test de la condition on dit aussi valuation e Si la condition est vraie l instruction ou les instructions du bloc sont ex cut es et on recom mence l tape 1 soit ex cution de l instruction ou des instructions du bloc e Sila condition est fausse le programme passe aux instructions suivantes La boucle POUR Lorsque le nombre de fois o un bloc d instructions doit tre ex cut est connu l avance la boucle POUR est pr f rable aux boucles pr c dentes L usage principal de la boucle POUR est de faire la gestion d un compteur de type entier qui volue d une valeur une autre Langage algorithmique POUR variable DE valeurl A valeur2 FAIRE instruction 1 instruction n FAIT instructions suivantes Implantation C for variable valeurl variable lt valeur2 variable bloc d instructions instructions suivantes 13 Chapitre 1 Les bases de la programmation Lorsque ordinateur rencontre cette structure il proc de syst matiquement de la mani re sui vante e La variable jouant le r le de compteur est initialis e la valeur1 e L ordinateur teste si la variable est inf rieure ou gale la valeur2 si c est le cas l instruction ou le bloc d instruction est effectu la variable jouant le r le de compteur est augment e de 1 et retour l tape 2 et non l tape 1 qui initialise la vari
53. it ratif comme par exemple pour en afficher le contenu Le r sultat produit sur l exemple donn est 1 2 8 12 10 5 Sp cification de l algorithme FONCTION getPostorderRouteList t tree list VAR thisNode sagldpl sadldpl list DEBUT pr conditions et pr traitements standards des cas aux limites SI isEmptyTree t ALORS RETOURNER emptyList FINSI thisNode newSingletonList t content SI isSingletonTree t ALORS RETOURNER thisNode FINSI sagldpl getPostorderRouteList t sag sadldpl getPostorderRouteList t sad RETOURNER concat amp sagldpl concat amp sadldpl amp thisNode FIN Exercice 4 2 afficher le contenu des feuilles d un arbre tude d faut de prescription contraire nous laborons un algorithme r cursif Le crit re caract ristique d un n ud feuille est qu il n a ni fils droit ni fils gauche 147 Chapitre 4 Structures arborescentes Pour donner une port e plus g n rale la fonction demand e et pour r utiliser des fonctionnalirt s d velopp es dans des exercices pr c dents nous nous proposons d extraire les feuilles d un arbre sous forme de liste cha n e laquelle pourra tre affich e l aide d une fonction d impression de liste Sp cification de l algorithme FONCTION getleaves t tree list VAR sagldpl sadldpl list DEBUT pr conditions et pr traitements standards des cas aux limites SI isEmptyTree t ALORS RETOURN
54. ki n uds de la liste en effectuant un parcours circulaire dans celle ci et jusqu ce que tous les n uds aient t supprim s D s qu un n ud est supprim le suivant dans la boucle est consid r comme la nouvelle t te de liste et ainsi de suite Si n 8 et k 3 par exemple la suppression des n uds contenant les huit entiers se fait dans cet ordre 3 6 1 5 2 8 4 7 Ce proc d peut tre illustr par un groupe compos l origine de n personnes formant un cercle que l on limine successivement en d signant le k de ceux restant dans le cercle que l on continue de parcourir RARER Probl me 3 2 Mesurer la longueur d une liste de type Heqat Soit une liste simplement cha n e de type Heqat c est dire obtenue par l op ration concat amp l sublist amp l n concevoir un algorithme pour en mesurer la longueur en nombre de n uds qui retourne d une part la longueur de la partie amont lin aire et d autre part la longueur p rim tre de la partie circulaire en aval Vous devrez respecter les contraintes suivantes e pas de modification de la liste pendant le traitement lecture seule e pas de copie de information des n uds travers s Corrig s des exercices et des probl mes PREAMBULE Repr sentation d une structure de file l aide d une liste Pseudo code formel STRUCTURE 1Queue head list queue list length entier 99 Chapitre 3 Str
55. la structure Le doit syst matiquement tre pr c d d un nom de variable 1 9 2 Op rateur d affectation L op rateur d affectation est le seul op rateur que ordinateur peut appliquer aux structures car il s agit dans ce cas de recopier les champs d une variable de type compos dans les m mes champs d une autre variable du m me type C est d ailleurs tout ce que fait cette op ration Une instruction d affectation entre deux variables d un type compos copie donc les champs d une variable dans une autre 1 9 3 Structures contenant des tableaux et des pointeurs Tableaux statiques Puisqu un champ peut tre de n importe quel type il peut s agir entre autres d un tableau par exemple statique Il est n cessaire dans ce cas de stocker sa taille utile dans un champ de la structure Lorsque plusieurs variables d un tel type sont d finies un tableau statique diff rent d adresse diff rente est cr pour chacune de ces variables En cas d affectation ce sont les contenus des cases du tableau qui sont recopi s 1 9 4 Structures d finies l aide de structures Un champ d une structure peut tre de n importe quel type donc il peut tre d un type compos c est dire une structure Cela aide bien hi rarchiser les diff rents niveaux pour viter que les structures ne comportent trop de champs Il est possible dans ce cas d avoir un acc s un ch
56. la m moire soit de fa on chain e soit de fa on contigu 128 4 1 Arbres binaires La repr sentation classique d un arbre est dynamique A chaque n ud on associe deux pointeurs l un vers le sous arbre gauche l autre vers le sous arbre droit et l arbre est d termin par l adresse de sa racine Lorsque l arbre est tiquet on repr sente dans un champ suppl mentaire l information contenue dans le n ud Implantation en C typedef struct arbre T info struct arbre sag sad arbre typedef arbre ptr_arbre Si a est un pointeur sur la racine de l arbre alors a NULL correspond un arbre vide a gt sag pointe sur le fils gauche de a a gt sad pointe sur le fils droit de a a gt 7nfo permet d acc der au contenu du n ud On ne parle d arbres binaires que par l interm diaire des algorithmes qui utilisent le type arbre 4 1 3 Algorithmes de parcours d un arbre binaire Il y a deux types de parcours e Parcours en profondeur d abord Examiner compl tement un chemin et passer au chemin suivant tant qu il en reste Figu re 4 4 Parcours en profondeur l aide d une pile e Parcours en largeur d abord Examiner tout un niveau profondeur hi rarchique passant au niveau du dessous tant qu il en reste 0 Probl me pas de lien entre fils Cela doit tre trait it rativement 129 Chapitre 4 Structures arborescentes Figure 4 5 Parcours en lar
57. les actions sont li es aux tats 169 Chapitre 5 Automates 5 2 QUELQUES DEFINITIONS Pour d finir un automate fini on a besoin des l ments suivants Un alphabet A qui est un ensemble fini d objets qu on appelle lettres ou caract res mais qui peuvent selon le cas tre de n importe quel genre instructions machine tat civil d une personne type d objet g om trique etc Des mots sont des s quences ordonn es de caract res de l alphabet Dans nos applications on aura affaire qu a des mots de longueur finie mais il n est pas interdit d utiliser des mots de longueur infinie automates de Rabin automates de Biichi La longueur d un mot est le nombre de lettres le constituant Exemple w abacda mot de longueur six sur l alphabet latin ou bien sur alphabet a b c d Un mot vide est not par ou par 1 C est le seul mot de longueur nulle On note A l ensemble de tous les mots sur l alphabet A y compris le mot vide Un automate fini sur l alphabet A est donn par un quadruplet Q I T E ot Q est un ensemble fini d tats de l automate I C Q est un ensemble d tats initiaux T C Qest un ensemble d tats terminaux ECOQOX A U e x Q est un ensemble de triplets p a q appel s les fl ches ou les transitions de l automate o Remarque Nous allons temporairement oublier la notion du mot vide jusqu l introduction ex
58. liste lin aire standard puis de finaliser en la refermant sur elle m me avec un concat amp l amp 1 Il s agit de r aliser un tri e Soit en triant avant ou apr s l appel au constructeur m thode en deux temps soit tri du tableau avant d appeler ce constructeur soit tri de la liste apr s l avoir construite e Soit en triant au fur et mesure de la construction de la liste m thode en flux tendu soit au moment de choisir le prochain l ment ins rer en t te de liste it ration non lin aire sur le tableau soit au moment de choisir l emplacement d insertion dans la liste de l l ment suivant du tableau it ration lin aire du tableau e Avec une difficult mais quelle l gance suppl mentaire si on choisit d ins rer dans une liste circulaire d s son initialisation Le mode de tri n tait pas impos vous pouvez laisser libre cours votre savoir faire et vos connaissances en ce domaine R alisation Ci apr s deux solutions m thode en flux tendu l une it rative qui parcourt le tableau et qui pour chaque tape cr e puis ins re un nouveau maillon dans la liste puis se termine en refermant la cha ne sur elle m me l autre plus compacte r cursive qui travaille sur une liste circulaire initi e avec le premier l ment du tableau 102 Dunod La photocopie non autoris e est un d lit Corrig s des exercices e M thode it rative classique Sp
59. m 3 peut donc tre v rifi e parm 6 0 Si les deux conditions sont valid es alors et seulement alors on calcule et on retourne m 3 Cette optimisation est importante car cette fonction utilitaire est appel e chaque tape de la r cursion ci apr s et que son co t d ex cution repr sente un co t l mentaire facteur direct du co t global de l ex cution de l algorithme principal e R alisation Retourne le pr d cesseur impair de n tel que n prec 3 1 s il existe 0 sinon FONCTION precInf n entier entier VAR m entier DEBUT mn 1 166 Dunod La photocopie non autoris e est un d lit Corrig s des probl mes SI m 3 0 ALORS RETOURNER 0 FINSI SI m 6 0 ALORS RETOURNER 0 FINSI RETOURNER m 3 FIN e Optimisation Une solution plus efficace peut tre trouv e moyennant un petit raisonnement d arithm tique modulaire Yn E N 3p E N n 3p 1 A impair p e JlkeEN n 3 2k 1 1 6k 4 amp n 4 6 Et donc la fonction se r duit FONCTION precInf n entier entier DEBUT SI n 6 4 ALORS RETOURNER n 1 3 SINON RETOURNER 0 FINSI FIN Cette r alisation quivalente conomise de nombreuses op rations l mentaires soustractions inutiles modulos interm diaires n gations logiques rapporter au fait que l appel de cette fonction utilitaire est syst matique au fur et mesure de la r cursion Fonction r cursive de cons
60. nouveau curr c est le 3 si par exemple le 3 me n a pas de successeur c est la queue pas d autre passage dans la boucle curr gt succ prev pointage du 3 me sur le 2d pl curr le 3 dernier devient t te Algorithme r cursif FONCTION esreverse pl list list VAR head list DEBUT SI pI NULL ALORS cas de la liste vide RETOURNER FINSI SI pl succ NULL ALORS cas de la liste un seul l ment RETOURNER FINSI head pl esreverse amp head succ succ head pl head succ head succ NULL RETOURNER amp head FIN reverse2 en m thode r cursive list esreverse list pl if pl NULL return cas liste vide if pl gt succ NULL return pl cas singleton autres cas list head pl esreverse amp head gt succ gt succ head pl head gt succ head gt succ NULL return amp head 65 Chapitre 2 Structures s quentielles simples Exercice 2 7 Construire une liste partir d une source de donn es e Cr ation depuis un tableau d entiers Sp cification de l algorithme FONCTION newListFromArray content entier longueur entier list VAR listenouv courant list i entier DEBUT SI longueur lt 1 ALORS la liste sera vide RETOURNER NULL FINSI listenouv newSingletonList content 0 construction de la t te courant listenouv ajout des autres places la suite POU
61. s l exercice 6 sont tous minimaux sauf un Lequel Exercice 5 11 D terminiser et minimiser les automates suivants e a a a b Q Figure 5 31 e b Figure 5 32 190 Dunod La photocopie non autoris e est un d lit Corrig s des exercices Exercice 5 12 On d finit la famille d automates suivants A Qn L T E nol avec e A a b e Q 0 1 n 1 ef T 0 e Comme fl ches tiquet es par a l ensemble de q a q 1 mod n pour Vg 0 lt q lt n 1 e Comme fl ches tiquet es par b l ensemble de g b 0 et g b q pour Yq 1 lt q lt n 1 attention la premi re in galit commence par 0 et la seconde par 1 Dessiner As et A4 Puis montrer que le d terminis complet de An a toujours 2 tats Corrig s des exercices Exercice 5 1 Figure 5 33 Cet automate est d terministe Exercice 5 2 Solution a L automate le plus simple qui reconna t l ensemble des mots sur l alphabet 0 1 dont l avant dernier symbole est 0 est le suivant 191 Chapitre 5 Automates XX 20 Figure 5 34 Cet automate n est pas d terministe 1 Solution b L automate le plus simple qui reconna t l ensemble des mots sur l alphabet 0 1 qui commencent et qui finissent par 0 est le suivant Figure 5 35 Cet automate n est pas d terministe Solution c Un des nombreux automates quivalents qui reconnaissent l ensemble des mots
62. sources des plantages des programmes et m me la source la plus fr quente de ce ph nom ne Afin d viter un trop grand nombre d erreurs de ce type l ordinateur le compilateur en r alit refusera d initialiser un pointeur avec des valeurs arbitraires toute autre variable il stocke alors une valeur al atoire La r gle d or d utilisation de l op rateur acc s au contenu ou encore prise de contenu est la suivante l acc s au contenu d un pointeur ne se fait en toute s curit que si ce dernier a t correctement initialis 0 Le seul cas o un pointeur stocke une valeur arbitraire est lorsqu il vient d tre d fini comme O La valeur NULL Il est possible d initialiser un pointeur avec une adresse qui est forc ment inaccessible quel que soit le programme crit L utilit d une telle initialisation est qu elle permet de savoir par un simple test si le pointeur a t initialis avec une adresse valide et ainsi viter les acc s malencontreux a des adresses invalides L adresse qui est forc ment inaccessible est adresse 0 Selon le type de machines cette adresse stocke des informations plus ou moins vitales pour le compte du syst me d exploitation En informatique adresse 0 porte un nom particulier NULL qui n est qu un autre nom qui est donn a la valeur 0 mais NULL ne s utilise que dans des contextes particuliers De nombreuses instructions utilisent d ailleurs c
63. suivent la position d insertion pour d gager de la place Le co t d une telle op ration est lev et peut devenir prohibitif dans certains cas Pour viter ce type de probl me il faudrait que le passage d une case d un tableau la suivante ne se fasse plus partir d un indice absolu qu on incr mente mais en notant localement dans une case du tableau l indice de la case suivante On va pr senter ici les listes lin aires qui sont la forme la plus commune d organisation des donn es On organise en liste lin aire des donn es qui doivent tre trait es s quentiellement De plus une liste est volutive c est dire qu on veut pouvoir ajouter et supprimer des donn es 2 1 1 D finition Une liste lin aire est une structure de donn es correspondant une suite d l ments Les l ments ne sont pas index s dans la liste mais pour chaque l ment sauf le dernier on sait o se trouve l l ment suivant Par cons quent on ne peut acc der un l ment qu en passant par le premier l ment de la liste et en parcourant tous les l ments jusqu ce qu on atteigne l ment recherch 2 1 2 Repr sentation Repr sentation tabulaire On peut repr senter une liste par deux tableaux e le tableau 2 1 contient les l ments de la liste dans un ordre quelconque e le tableau 2 2 est organis de fa on suivante si la case d indice i du premier tableau contient l l ment dont le s
64. sur l alphabet 0 1 2 3 4 5 6 7 8 9 repr sentant en C les constantes num riques est le sui vant Figure 5 36 Cet automate est d terministe Solution d Un des nombreux automates quivalents qui reconna t l ensemble des mots sur l alphabet 0 1 comportant au moins une fois le motif 10 et au moins une fois le motif 01 est le suivant 192 Dunod La photocopie non autoris e est un d lit Corrig s des exercices ee ee Figure 5 37 Cet automate est d terministe Solution e Un des nombreux automates quivalents qui reconna t le langage a b n m pair est le suivant Figure 5 38 Cet automate est d terministe Exercice 5 3 Ajout d un 0 la fin d un nombre binaire le multiplie par 2 Ajout d un 0 la fin d un nombre binaire le multiplie par 2 et lui ajoute 1 Tableau 5 20 N N mod 5 Ajout d un 0 N mod 5 Ajout d un 1 N mod 5 la fin de la fin de l criture binaire l criture binaire donne N donne N 5n 0 10n 0 10n 1 1 5n 1 1 10n 2 2 10n 3 3 5n 2 2 10n 4 4 10n 5 0 5n 3 3 10n 6 1 10n 7 2 5n 4 4 10n 8 3 10n 9 4 Cela se traduit par l automate suivant 193 Chapitre 5 Automates Tableau 5 21 tat En lisant 0 En lisant 1 0 0 1 1 2 3 2 4 0 3 1 2 4 3 4 1 1 1 1 Figure 5 39 Exercice 5 4 Figure 5 40 Exercice 5 5 tats 2 et 3 n
65. tapes Pour cela il suffit de proc der une inversion de la suite Partons de e le terme de convergence vis et racine de l arbre e peut tre le successeur direct de 2e et ventuellement de e 1 3 si cet entier existe et s il est impair Disons que e a n cessairement un fils droit 2e et ventuellement un fils gauche e 1 3 En appliquant r cursivement ce proc d on peut donc construire un arbre binaire de profondeur quelconque dont chaque branche est l une des suites de Syracuse qui converge vers e Figure 4 23 Arbre de Syracuse crire une fonction qui retourne le pr d cesseur entier impair d un entier donn s il existe et 0 sinon 145 Chapitre 4 Structures arborescentes crire une fonction r cursive qui construit l arbre de Syracuse partir d une feuille donn e conte nant la valeur e et d velopp jusqu la profondeur p Si un fils gauche e 1 3 vaut 0 ou 1 une tape quelconque de la r cursion i e e vaut 1 ou 4 ce fils gauche n est pas cr Corrig s des exercices et des problemes EN PREAMBULE Quelques remarques utiles Les structures arborescentes bien que plus complexes que les structures s quentielles conduisent pardoxalement a des algorithmes naturellement r cursifs et donc plus compacts Implantation en C d une structure d arbre binaire Pour la r alisation en C de tous les algorithmes sp cifi s ci dessous on d finit la structu
66. un algorithme permettant d afficher tous les entiers enregistr s dans les feuilles d un arbre binaire en ignorant les entiers contenus dans tous les autres n uds Exercice 4 3 Rechercher it rativement un l ment dans un ABOH crire un algorithme it ratif de recherche d un l ment dans un ABOH CET Exercice 4 4 valuer le caract re ABOH d un AB crire un algorithme permettant de d terminer si un arbre binaire donn est ou n est pas un arbre ABOH Exercice 4 5 Mesurer la hauteur d un ABOH crire un algorithme de calcul de la hauteur d un ABOH Wek Exercice 4 6 valuer l quilibre d un AB crire un algorithme permettant de savoir si un arbre binaire est partiellement quilibr ex Exercice 4 7 Parcourir un AB en largeur et en profondeur crire deux algorithmes respectivement de parcours en largeur d abord et en profondeur d abord pour afficher le contenu d un arbre binaire CET ET Exercice 4 8 Effectuer un calcul complexe sur un arbre crire un algorithme qui retourne la moyenne des l ments positifs et celle des l ments n gatifs d un arbre 0 est consid r ici comme un positif 142 Dunod La photocopie non autoris e est un d lit Probl mes Exercice 4 9 Extraire une liste d l ments d un arbre crire un algorithme qui retourne la liste cha n e des l ments d un arbre d entiers qui ne sont pas divisibles par leur parent et que leu
67. un seul sens du premier l ment vers le dernier l ment Cependant de nombreuses applications n cessitent de parcourir les listes la fois vers l avant et vers l arri re et dans ce cas on peut faciliter le traitement en rajoutant des pointeurs arri re ce qui augmente videmment la place m moire utilis e On obtient alors une liste doublement chain e chaque place comporte un pointeur vers la place suivante et un pointeur vers la place pr c dente Figure 2 4 Liste lin aire doublement cha n e D finition d une structure de liste doublement chain e Pseudo code formel STRUCTURE node content T succ prev node TYPE list node Implantation C typedef struct node lt type gt content struct node succ prev node typedef node list 44 Dunod La photocopie non autoris e est un d lit Afficher le contenu d une liste l envers Sp cification abstraite FONCTION afficher l liste DEBUT t te 1 TANTQUE dernier 1 FAIRE q succ 1 FAIT TANTQUE premier 1 FAIRE AFFICHER contenu 1 1 lt prev 1 FAIT FIN R alisation en C Donn e list 1 la liste afficher void reversePrintList list 1 int k 1 while 1 gt succ NULL 1 1 gt succ k while 1 NULL Enonc s des exercices et des probl mes printf tListl d d n k 1 gt content 1 1 gt prev EXERCICES Exercice 2 2 Concat ner deux listes
68. un type qui ne peuvent tre modifi s au cours du programme car fix s au moment de la d finition de la variable et une valeur qui au contraire volue au cours du programme En r alit toute variable poss de galement une autre caract ristique fondamentale utilis e en interne par la machine une adresse En effet afin de m moriser la valeur d une variable l ordinateur doit la stocker au sein de sa m moire m moire dont les l ments ou cellules sont rep r s par des num ros de mani re analogue ce qui se passe dans un tableau en r alit Le nom de la variable n est en fait pas utile la machine qui se contente de son adresse c est pour le confort du programmeur que le choix du nom est rendu possible Ainsi il existe une dualit entre le nom de la variable c t programmeur et son adresse c t machine L adresse d une variable n est autre que le num ro de la case ou cellule m moire que celle ci occupe au sein de la machine Au m me titre que son nom l adresse d une variable ne peut pas varier au cours d un programme Il n est m me pas possible de choisir l adresse d une variable cette adresse est attribu e automatiquement par l ordinateur Chose curieuse ces adresses de variables seront manipul es sans m me conna tre leur valeur exacte Il suffira de savoir les nommer pour les utiliser Pour ce faire un nouvel op rateur est n cessaire l op rateur amp Il se lit tou
69. 0 1 2 3 4 Tableau 5 10 Etat Groupes r sultant en lisant a en lisant b Donc le groupe J se s pare en deux et ona 2 0 2 1 3 4 Notons les groupes en recyclant la notation I 0 2 17 Dj I IV 9 Essayons de s parer le groupe J en regardant o tombent les transitions a partir de ses tats dans les termes de la s paration 0 2 1 3 4 180 Dunod La photocopie non autoris e est un d lit 5 3 L interpr tation intuitive Tableau 5 11 2 Groupes r sultant tat z en lisant a en lisant b 0 Il l Le groupe I ne se s pare pas 3reste identique la s paration de l tape pr c dent 0O 0 0 2 1 3 4 Fin de la proc dure it rative de s paration Voici les it rations qu on a effectu es Etape 1 Ocourant 0 1 2 3 4 Onew 0 1 2 3 4 tape 2 Ocourant 0 1 2 3 4 Onew 0 2 1 3 4 tape 3 Ocourant 0 2 1 3 4 Onew 0 2 1 3 4 final Passons aux repr sentants Tableau 5 12 Groupe Repr sentant 0 ou 2 Il 1 IlI 3 IV 4 Il devient clair maintenant qu on peut marquer les tats de l automate minimis soit par un repr sentant soit par les chiffres Il Ill IV suivant le groupe du dernier tape soit par le contenu du groupe dans ce cas l tat initial sera marqu 0
70. 1 174 175 214 table de 171 tri 2 type 5 point 20 variable 6 locale 24
71. 1max du tableau Le seul point d licat est la d tection des d bordements D finition d une structure de file r alis e avec un tableau Pseudo code formel STRUCTURE file donn e Tfn t te entier fin entier Implantation en C typedef struct file T donn e n int t te int fin file 90 Dunod La photocopie non autoris e est un d lit 3 2 Les files 3 2 2 Repr sentation chain e des files Dans le cas d une repr sentation chain e soit on a deux pointeurs t te et dernier vers le premier et le dernier l ment de la file soit on utilise le pointeur qui suit le dernier l ment pour rep rer le premier l ment On a donc une repr sentation circulaire 3 2 3 Manipulation d une file m thode avec deux pointeurs D finition d une structure de file cha n e Pseudo code formel STRUCTURE poste info T suivant poste TYPE ptr_poste poste STRUCTURE file t te ptr_poste fin ptr_poste nb_elt entier Implantation en C typedef struct poste T info struct poste suivant poste typedef poste ptr_poste typedef struct file ptr_poste t te ptr_poste fin int nb_elt file Initialiser une file juste d clar e D clarations R sultat de type file En t te en C file init Algorithme initialiser FONCTION init VAR f file DEBUT f tete NULL f fin NULL f nb elt 0 RETOURNER f FIN 91 Chapitre 3 Structures s quentielles
72. 2 cette derni re solution est pratique tant que le groupe consiste en peu d tats L automate minimis Figure 5 12 181 Chapitre 5 Automates On peut maintenant poser la question suivante pourquoi les tats 0 et 2 sont rest ensemble apr s la minimisation Qu y a t il de sp cial concernant ces deux tats par rapport aux autres Regardons nouveau l automate initial a Figure 5 13 et introduisons la terminologie suivante on dit que la cha ne w distingue l tat s de l tat t si quand on commence dans l tat s et litw on arrive dans un tat terminal et sion commence dans t et lit w on arrive dans un tat non terminal ou vice versa Ici tous les tats peuvent tre distingu s par une cha ne ou une autre sauf les tats 0 et 2 C est facile voir et partir de O et partir de 2 on arrive en 1 en lisant un nombre quelconque y compris z ro de b et un a puis comme on est dans le m me tat 1 il ne nous reste que les m mes cha nes pour arriver l tat final ici il y en a un seul Donc les tats non distinguables se fondent dans un m me tat en l occurrence 0 2 de automate minimis En fait on peut montrer que l algorithme de minimisation qu on a expliqu est bas sur la recherche des tous les groupes qui peuvent tre distingu s par une cha ne ou J 1 T 1 2 une autre Exemple 2 Voici un automate d terministe complet avec deux tats terminaux
73. 2 est NULL ou non int status pl2 NULL 1 2 CODE SPECIFIQUE lt Version gt on coupe pl2 11 gt succ 11 gt succ NULL return status Cas du s lecteur pointeur Donn e cutPoint le pointeur sur la cellule suivant le point de coupe int cutA plist pll plist pl2 list cutPoint CODE GENERIQUE COMMUN D INITIALISATION si cutPoint est NULL autant arr ter ici if cutPoint NULL return 0 cas de la coupure en t te de liste if cutPoint 11 pl1 NULL ol2 11 return status Sinon on parcourt la liste jusqu au pr d cesseur du point de coupe ou jusqu la queue de liste cutPoint pointe sur une autre liste while 11 gt succ NULL amp amp 11 gt succ cutPoint 11 11 gt succ si nous avons atteint la fin de liste c est un cas d erreur if 11 gt succ NULL return ERR CODE GENERIQUE COMMUN DE FINALISATION Cas du s lecteur l ment Donn e x l l ment de la cellule suivant le point de coupe int cutB plist pll plist pl2 int x 72 Dunod La photocopie non autoris e est un d lit Corrig s des exercices CODE GENERIQUE COMMUN D INITIALISATION cas de la coupure en t te de liste if x 11 gt content pl1 NULL pl2 11 return status Sinon on parcourt la liste jusqu au pr d cesseur du point de coupe ou jusqu la queue de liste
74. 8 bits la valeur enti re peut donc aller de 0 255 Dans le tableau ne sont pr sentes que les valeurs de 32 127 en de de 32 il s agit de caract res non imprimables au del de 127 ce sont des caract res optionnels qui sont adapt s un type de clavier ou de langue particulier notamment les caract res accentu s etc Chapitre 1 Les bases de la programmation 1 2 LES VARIABLES Une variable est une donn e qu un programme peut manipuler Tout variable poss de e Un type entier r el caract re ou bool en e Un nom ou identificateur que l utilisateur choisit il permet au programme de reconna tre quelle donn e il doit manipuler e Une valeur qui peut voluer au cours du programme mais qui doit respecter le type Une variable dont le type est entier ne pourra donc jamais contenir de valeur a virgule Videntificateur ou nom de la variable peut tre quelconque mais doit respecter les crit res suivants e un identificateur commence toujours par une lettre minuscule e l exception du premier caract re il peut contenir des lettres des chiffres et le symbole soulign ou underscore e les majuscules et les minuscules sont des lettres diff rentes les identificateurs toto et Toto sont diff rents e le nom de variable doit avoir une relation avec le r le de cette variable et tre compr hensible 1 3 QUELQUES ELEMENTS DE SYNTAXE POUR LE LANGAGE ALGORITHM
75. Dunod La photocopie non autoris e est un d lit nonc s des exercices Tableau 5 18 Groupes r sultant en lisant b en lisant a en lisant c 2 se s pare 1 1 2 2 P G 7 2 P 3 Tableau 5 19 Groupes r sultant Etat en lisant a en lisant b en lisant c 1 2 3 1 2 2 3 Le groupe 1 1 2 na aucun chance se scinder en deux car d s le d but 1 et 1 2 ont les m mes transitions Donc on a termin et on obtient a Figure 5 23 ce qui est le m me automate que le r sultat de compl ter l automate A5 en minimisant automate AS la seule chose qu il reste faire cest de le compl ter autrement il est d j minimal NONC S DES EXERCICES Exercice 5 1 Construire un automate fini dont les tats correspondent aux situations de famille possibles d une personne c libataire mari divorc veuf et dont les fl ches correspondent aux changements de situation possible Etiqueter ces fl ches par M mariage D divorce et V veuvage Exercice 5 2 Construire des automates finis qui reconnaissent les langages suivants e a L ensemble des mots sur l alphabet 0 1 dont l avant dernier symbole est 0 187 Chapitre 5 Automates e b L ensemble des mots sur l alphabet 0 1 qui commencent et qui finissent par 0 On consid re que le mot consistant en un seul 0 v rifie cette condition e c
76. ER t sag content lt t content ET isPseudoBinarySearchTree t sag FINSI SI isEmptyTree t sag ALORS RETOURNER t sad content gt t content ET isPseudoBinarySearchTree t sad FINSI RETOURNER t sag content lt t content ET isPseudoBinarySearchTree t sag ET t sad content gt t content ET isPseudoBinarySearchTree t sad FONCTION isBinarySearchTree t tree bool en DEBUT SI isEmptyTree RETOURNER vrai FINSI SI isSingleton RETOURNER vrai FINSI SI isEmptyTree RETOURNER vrai FINSI SI isEmptyTree t ALORS ree t ALORS t sag ET isEmptyTree t sad ALORS t sad ALORS RETOURNER max0OfTree t sag lt t content ET 149 Chapitre 4 Structures arborescentes isBinarySearchTree t sag FINSI SI isEmptyTree t sag ALORS RETOURNER minOfTree t sad gt t content ET isBinarySearchTree t sad FINSI RETOURNER max0fTree t sag lt t content ET isBinarySearchTree t sag ET minOfTree t sad gt t content ET isBinarySearchTree t sad FIN Attention cette fonction n est pas d finie pour un arbre vide FONCTION minOfTree t tree entier VAR min sagMin sadMin entier DEBUT min lt t gt content SI isEmptyTree t sag ALORS sagMin minOfTree t sag SI sagMin lt min ALORS min sagMin FINSI FINSI SI isEmptyTree t sad ALORS sadMin minOfTr
77. ER emptyList FINSI SI isSingletonTree t ALORS RETOURNER newSingletonList t content FINSI Sinon sagldpl getLeaves t sag sadldpl getLeaves t sad RETOURNER concat amp sagldpl amp sadldpl FIN Exercice 4 3 rechercher it rativement un l ment dans un ABOH Sp cification de l algorithme FONCTION containsElement t tree k entier bool en DEBUT TANTQUE t NULL FAIRE SI t content k ALORS RETOURNER vrai FINSI SI t content gt k ALORS t t sad SINON t t sag FINSI FAIT RETOURNER faux FIN Exercice 4 4 valuer le caract re ABOH d un AB tude En terminologie courante on appelle un ABOH un ABR Arbre binaire de recherche en anglais un BST Binary Search Tree 148 Dunod La photocopie non autoris e est un d lit Corrig s des exercices L erreur fr quente consiste ne v rifier que la condition fils gauche lt parent lt fils droit sur tous les n uds et non pas descendants gauches lt parent lt descendants droits Donnons donc la mauvaise et la bonne solution toutes fins utiles Sp cification de l algorithme FONCTION isPseudoBinarySearchTree t tree bool en SI isEmptyTree RETOURNER vrai FINSI SI isSingleton RETOURNER vrai FINSI SI isEmptyTree RETOURNER vrai FINSI SI isEmptyTree t ALORS ree t ALORS t sag ET isEmptyTree t sad ALORS t sad ALORS RETOURN
78. EXERCICES ET PROBLEMES D ALGORITHMIQUE gt Rappels de cours gt Exercices et probl mes avec corrig s d taill s gt Solutions en pseudo code et en langage C Nicolas Flasque Enseignant math matiques et informatique EFREI Helen Kassel Enseignant math matiques et informatique EFREI Franck Lepoivre Enseignant chercheur Boris Velikson Enseignant math matiques et informatique EFREI DUNOD Illustration de couverture digitalvision Le pictogramme qui figure ci contre m rite une explication Son objet est d alerter le lecteur sur la menace que repr sente pour l avenir de l crit particuli rement dans le domaine de l dition technique et universi taire le d veloppement massif du photocopillage Le Code de la propri t intellec tuelle du 1 juillet 1992 interdit en effet express ment la photoco pie usage collectif sans autori sation des ayants droit Or cette pratique s est g n ralis e dans les tablissements DANGER LE PHOTOCOPILLAGE TUE LE LIVRE d enseignement sup rieur provoquant une baisse brutale des achats de livres et de revues au point que la possibilit m me pour les auteurs de cr er des uvres nouvelles et de les faire diter cor rectement est aujourd hui menac e Nous rappelons donc que toute reproduction partielle ou totale de la pr sente publication est interdite sans autorisation de l auteur de son diteur ou du Centre fran ais d exploita
79. Exemple Q Q a Figure 5 6 e D terminisation g Tableau 5 5 5 z 5 tats r sultant Etat amp en lisant a en lisant b en lisant c a entr e 0 0 1 0 e 8 0 1 0 1 0 2 sortie 2 4 2 Nous rempla ons les traits pas de transition dans ce tableau par un nouvel tat appel E poubelle P qui a la propri t que toutes les transitions partir de cet tat reviennent sur lui m me 175 Chapitre 5 Automates Tableau 5 6 Etats r sultant Etat z en lisant a en lisant b en lisant c entr e 0 0 1 0 P 0 1 0 1 0 2 sortie 2 P P P P P P P Voici donc l automate d terminis complet dans lequel 0 est rest l tat initial et le seul tat terminal reste 2 a b c Figure 5 7 Remarque Il ny a pas trop de sens de parler d un automate non d terministe complet ou pas complet De m me m me si introduire un tat poubelle dans un automate non d terministe est possible et ne nuit pas a son fonctionnement ceci n est pas utile pour la d terminisation de cet automate Normalement on n introduit un tat poubelle si besoin est qu une fois l automate est devenu d terministe Un automate est accessible si nimporte quel tat est accessible partir d un tat initial c d s il existe un chemin y menant partir d un tat initial Cd Un automate est coaccessible si part
80. Exercice 5 5 Quel est le langage reconnu par l automate suivant Quels tats de cet automate sont inutiles b a D a b Figure 5 24 Exercice 5 6 Voici cinq automates not s ils n ont rien voir les uns avec les autres ce n est pas une s quence L alphabet A a b sauf pour A4 o il est 0 1 Pour chacun de ces automates e D crire L A en langage ordinaire sauf pour As e Caract riser A dire s il est accessible coaccessible mond e Calculer l automate d terministe quivalent A 188 Enonc s des exercices yO OO Figure 5 25 al Figure 5 26 a2 Figure 5 27 A3 Figure 5 28 a4 Figure 5 29 As Ici ne pas d crire L As avant que l automate ne soit d terminis 189 Chapitre 5 Automates Exercice 5 7 D terminiser l automate suivant Figure 5 30 Exercice 5 8 Construire des automates d terministes qui reconnaissent les langages suivants En d duire des automates d terministes qui reconnaissent les compl mentaires de ces langages e a L ensemble des mots sur l alphabet 0 1 qui contiennent exactement trois fois le symbole 1 e b Lensemble des mots sur l alphabet 0 1 qui contiennent au moins un 1 Exercice 5 9 Construire un automate fini reconnaissant l ensemble des mots sur l alphabet A a b qui ne se terminent pas par abaab Le d terminiser et minimiser Exercice 5 10 Montrer que les automates d terministes calcul
81. I pI NULL ALORS cas de la liste vide RETOURNER FINSI Corrig s des exercices SI pl succ NULL ALORS cas de la liste un seul l ment 63 Chapitre 2 Structures s quentielles simples RETOURNER FINSI prev pl curr prev succ SI curr succ NULL ALORS curr succ prev prev succ NULL pl lt curr RETOURNER SINON prev succ NULL FINSI TANTQUE curr succ NULL FAIRE succ Curr succ CUrr SUCC prev prev lt curr curr lt succ FAIT curr succ lt prev pl lt curr FIN Inversion d une liste utilis e pour 1 exo 1 4 normalisation void reverse list pl if pl NULL return liste vide if pl gt succ NULL return singleton list prev pl t te list curr prev gt succ 2d l ment if curr gt succ NULL si cas 2 l ments curr gt succ prev pointage du 2d lt sur le 1 prev gt succ NULL et du ler sur NULL queue pl curr le 2d devient t te return termin else sinon au moins 3 elts prev gt succ NULL pointage du 1 XNULL queue list succ while curr gt succ NULL Expl sur l re it ration succ Curr gt succ sauv du succ le 3 me lt 64 Dunod La photocopie non autoris e est un d lit Corrig s des exercices curr gt succ prev pointage du 2d elt sur le 1 prev curr le nouveau prev c est le 2d curr succ le
82. IQUE Pour crire correctement un programme en langage algorithmique il faut fournir certaines informa tions l ordinateur le mot programme suivi du nom du programme indique le nom du programme ainsi que son point de d part Avant d utiliser une variable dans un programme il faut la d finir c est dire indiquer le mot VAR puis le nom de la variable et enfin son type pr c d de Une variable s appelant taux et dont le type est r el doit tre d finie de la mani re suivante VAR taux r el Cette d finition cr e une variable nomm e taux dans laquelle peuvent tre stock s des nombres virgule Quelques exemples de d finition de variables VAR solution_equation r el d finit une variable nomm e solution_equation dont le type est r el VAR val_1 entier d finit une variable nomm e val_1 dont le type est entier VAR lettre caract re d finit une variable nomm e lettre dont le type est caract re CA 1 4 Op rations et op rateurs de base Il est possible de d finir plusieurs variables dun m me type en sp cifiant le nom du type puis la liste des noms de variables s par s par des virgules Ainsi les d finitions suivantes sont strictement quivalentes VAR val_a entier VAR val_b entier VAR val_c entier amp VAR val_a val _b val_c entier 1 4 OP RATIONS ET OP RATEURS DE BASE 1 4 1 Affectation L op ration d affectation permet de donner ou d
83. L 1 1 gt succ it ration de la liste if 1 gt content gt max max 1 gt contenu return max Et r crite avec les m thodes utilitaires donn es en introduction int maxOf list lt unsigned gt 1 if isempty 1 return ERR int max content 1 valeur en premi re place while islast 1 1 succ l it ration de la liste if content 1 gt max max content 1 return max Sp cification de l algorithme r cursif Entr e liste de positifs non vide Sortie un positif FONCTION maxOf 1 liste lt positif gt positif VAR max contenu positif DEBUT RETOURNER maxOfRec t te 1 FIN FONCTION maxOfRec p place positif VAR max contenu positif DEBUT contenu contenu p SI dernier p ALORS RETOURNER contenu 50 Dunod La photocopie non autoris e est un d lit Corrig s des exercices FINSI max maxOfRec succ p SI contenu gt max ALORS RETOURNER contenu FINSI RETOURNER max FIN R alisation en C de l algorithme r cursif int maxOfRec list lt unsigned gt 1 if 1 NULL return ERR int content 1 gt content if 1 gt succ NULL return content int max maxOfRec 1 gt succ if content gt max return content return max Et r crite avec les m thodes utilitaires donn es en introduction int maxOfRec list lt unsigned gt 1 if isempty 1 return ERR int content content 1 if islast 1 return content
84. List nextElement 1 nextElement 1 1 gt succ int countElementOccurrences list 1 int k int count 0 if isEmptyList 1 return count 39 Chapitre 2 Structures s quentielles simples if getHeadContent 1 k count while hasMoreElements 1 1 nextElement 1 if getHeadContent 1 k count return count Cr er une liste cha n e par ajouts successifs d l ments saisis jusqu fin Sp cification de l algorithme cr ation de liste en ligne de commande FONCTION cr er_par_saisie liste VAR 1 liste e l ment DEBUT listevide SAISIR e SI e fin ALORS cons e 1 FINSI FIN Alternative DEBUT 1 listevide FAIRE SAISIR e SI e fin ALORS cons e 1 FINSI TANTQUE e fin FIN R alisation en C Donn e modifi e list pl XX Construction d une liste par saisie depuis l entr e standard La saisie s ach ve quand l utilisateur crit fin La saisie d un terme qui n est pas un entier ni fin est interpr t e comme la saisie de 0 2J int newListFromStandardInput list pl pl NULL int size 1 char input 10 printf Saisissez des entiers puis tapez fin n printf d gt size 40 Dunod La photocopie non autoris e est un d lit 2 1 Listes lin aires scanf s input if stremp fin input 0 return 0 allocation m moire et rattachement de la t te p
85. R i DE 1 A longueur 1 FAIRE courant succ newSingletonList content il courant courant succ passage au suivant FAIT RETOURNER listenouv retour de la t te qui repr sente la liste FIN Implantation C list newListFromArray int content int length if length lt 1 return emptyList cas de la liste vide sinon initialisation de la cha ne avec la cr ation de la t te list 1 newSingletonList content 0 d claration et initialisation d un variable d it ration de liste list pp 1 it ration de la 1 place la derni re longueur 1 intervalles int i for i 1 i lt length i pp gt succ newSingletonList content il pp gt succ gt prev pp chafnage arri re opt pp pp gt succ it ration de la liste return 1 retour du pointeur sur la t te lequel repr sente la liste Il est possible mais risqu par l astuce suivante d viter le passage du param tre qui indique la longueur du tableau source size_t longueur sizeof contenu sizeof int 66 Dunod La photocopie non autoris e est un d lit e Duplication d une liste existante Sp cification de l algorithme FONCTION duplicate l list list VAR t te copie copie_t te list DEBUT SI 1 NULL ALORS RETOURNER NULL FINSI t te copie newSingletonList l content copie_t te copie TANTQUE 1 succ NULL ET 1 succ t te FAIRE l gt succ p
86. RESERVER et sa syntaxe d utilisation est la suivante RESERVER pointeur 22 1 8 Les sous programmes ou fonctions Le r le de cette commande est d allouer un espace m moire pour stocker le contenu qui sera point par le pointeur qui est fourni la commande Exemple Soit le pointeur ptr d fini de la mani re suivante VAR ptr r el A priori ptr n est pas initialis et il est donc hasardeux d acc der a son contenu Afin d initialiser ptr correctement il est possible de reserver de l espace m moire pour son contenu RESERVER ptr aura cet effet Une r servation de m moire se nomme galement une allocation dynamique de m moire Lorsque la place en m moire n est plus utile il suffit de la lib rer en utilisant la commande suivante LIBERER pointeur 1 8 LES SOUS PROGRAMMES OU FONCTIONS Le r le d une fonction est de regrouper des instructions ou traitements qui doivent tre faits de mani re r p titive au sein d un programme Par exemple dans un programme traitant des tableaux on voudrait afficher plusieurs fois des tableaux dont les variables stockent des valeurs diff rentes Cependant m me si les valeurs sont diff rentes l affichage d un tableau se r sume toujours un parcours de toutes les variables utilis es avec une boucle POUR de l indice 0 jusqu l indice taille _utile 1 avec un affichage de chaque valeur gr ce l instruction AFFICHER Il serait utile de re
87. RETOURNER trouve FIN R alisation en C Donn es list 1 la liste de recherche int k l l ment recherch R sultat type bool en int en C int containsElement list 1 int k int found 0 if 1 NULL return found while 1 gt succ NULL amp found Dunod La photocopie non autoris e est un d lit 2 1 Listes lin aires if 1 gt content k found 1 else 1 1 gt succ if 1 gt content k found 1 return found Remarque On ne peut pas remplacer la condition found dans la boucle while par 1 gt succ gt content k parce que si 1 gt succ pointe sur NULL 1 gt succ gt content n existe pas Une alternative sans variable bool enne Sp cification de l algorithme recherche b FONCTION recherche l liste lt l ment gt x l ment bool en VAR p place DEBUT SI estvide 1 ALORS p t te 1 TANTQUE dernier p FAIRE SI contenu p x ALORS RETOURNER vrai SINON p succ p it ration vers la cellule suivante FINSI FAIT SI contenu p x ALORS RETOURNER vrai FINSI FINSI RETOURNER faux FIN R alisation en C et par extension fonction de d compte d occurrences Donn es list 1 la liste de recherche int k l l ment recherch R sultat type bool en int en C Notez l utilisation de petites fonctions utilitaires isEmptyList 1 1 NULL getHeadContent l1 1 gt content hasMoreElements 1 isEmpty
88. Sp cification de l algorithme FONCTION removeAllA pl list entier VAR 1 suppr list DEBUT SI pl NULL ALORS RETOURNER 1 FINSI q pl SI 1 NULL ALORS RETOURNER 0 FINSI pl lt l succ LIBERER 1 1 pl TANTQUE 1 NULL ET 1 succ NULL FAIRE suppr 1l succ l succ suppr gt succ LIBERER suppr 1 succ FAIT RETOURNER 1 FIN Implantation C int removeAllA plist pl if pl NULL return ERR cas d erreur list 1 pl if 1 NULL return ID cas d op ration blanche suppression de la t te pl 1 gt succ free 1 1 pl supression raison d un n ud sur deux list killed while 1 NULL amp amp 1 gt succ NULL killed 1 gt succ 1 gt succ killed gt succ free killed 1 gt suecs 79 Chapitre 2 Structures s quentielles simples return OK CORRIG DU PROBL ME Probl me 2 1 Saisir enregistrer puis valuer un polyn me tude Pour le module de saisie on s inspirera de la fonctionnalit de construction de liste partir de la saisie sur l entr e standard dont on fera une adaptation Pour l valuation il s agit d un calcul it ratif Deux fonctionnalit s utilitaires pourront constituer une am lioration de la version de base e Une fonction d affichage de la formule polyn me e Une fonction laiss e en exercice non corrig de normalisation du polyn me apr
89. ULL ALORS prev succ NULL LIBERER courant RETOURNER NULL SINON prev succ courant succ LIBERER courant RETOURNER prev succ FINSI FINSI FINSI FIN Implantation C Supprime le ki et retourne le suivant Si le 1 l ment est supprim retour du suivant sinon pl inchang note la fonction fonctionne pour les listes circulaires et lin aires simplement cha n es list removeKst list pl int k list head pl list curr pl if curr NULL return NULL pour moduler Tes traitements liste circulaire ou lin aire int circular isCircular curr int perimeter getCLength curr if circular amp perimeter 1 finalisation pl NULL return NULL m morisation du prev soit le prev de curr soit NULL lin aire 121 Chapitre 3 Structures s quentielles complexes 122 list prev circular getKstElement pl perimeter 1 NULL on commence par it rer jusqu la bonne position note amp amp amp le k est d cr ment ssi curr gt succ NULL while curr gt succ NULL amp k gt 0 prev curr curr Curr gt Succ si la liste n est pas circulaire et qu on a atteint la queue alors que k gt 0 on arr te if curr gt succ NULL amp amp k gt 0 return pl sinon on supprime en tenant compte de tous les cas possibles cas de la liste circulaire if circular prev gt succ Curr gt succ da
90. a liste inchang e Pour supprimer un l ment il s agit de rep rer l l ment et de court circuiter celui ci en reliant le pointeur succ de son pr d cesseur directement sur son successeur Algorithme r cursif e Retrait de toutes les occurrences d un l ment Entr e x l entier dont on supprime toutes les occurrences dans la liste Entr e modifi la liste dont on supprime des occurrences de x Sortie un code de statut d ex cution e SUPPRESSION 1 il y a eu au moins un retrait effectif e IDENTITE 0 il n y a eu aucun retrait car la liste ne comporte aucun x Cette fonction utilise un type num r num ration qui est un type d fini par les valeurs que peuvent prendre les variables de ce type Ainsi dans la fonction suivante les variables statut et st2 ne peuvent prendre que les valeurs SUPPRESSION ou IDENTITE FONCTION supprimerOccurrences l liste lt entier gt x entier VAR statut st2 num ration SUPPRESSION IDENTITE e entier DEBUT 61 Chapitre 2 Structures s quentielles simples statut IDENTITE SI estvide 1 ALORS SI premier 1 x ALORS l fin 1 statut SUPPRESSION SI estvide 1 ALORS supprimerOccurrences 1 x FINSI SINON e lt premier 1 1e fin 1 SI estvide 1 ALORS st2 lt supprimerOccurrences SI statut IDENTITE ALORS statut st2 FINSI FINSI 1 cons e 1 FINSI FINSI RETOURNER statut FIN X e Retrait de toutes les oc
91. able si ce n est pas le cas l instruction ou le bloc d instruction n est pas effectu e et l ordinateur passe aux instructions suivantes En r alit la boucle POUR est quivalente la boucle TANTQUE mais les deux sont utilisables dans des cas distincts Dans le cas o le nombre d it rations n est pas connu l avance la boucle TANTQUE sera utilis e 1 6 TABLEAUX Un programme peut tre amen manipuler de nombreuses variables repr sentant des valeurs distinctes mais de m me nature Par exemple un relev de plusieurs temp ratures en plusieurs endroits et plusieurs dates n cessitera autant de valeurs enti res que de temp ratures stocker Il est difficilement envisageable de d finir manuellement autant de variables que de valeurs stocker Les tableaux en informatique permettent de r soudre ce probl me en proposant la cr ation de plusieurs variables de m me type d une mani re tr s compacte 1 6 1 D finition Un tableau se d finit en indiquant son nom le type des l ments stock s dans le tableau ainsi que leur nombre crit entre crochets Ce nombre se nomme galement la taille maximale du tableau Syntaxe VAR nom_du_tableau type _des_ l ments taille maximale Exemple VAR tab entier 100 est la d finition d un tableau nomm tab qui peut stocker 100 valeurs de type entier au maximum La taille maximale d un tableau doit tre une constante num riqu
92. affiche umtcoyba 4 1 4 Arbres binaires de recherche ABOH Arbres Binaires Ordonn s Horizontalement D finitions et algorithmes de manipulation ABOH Arbre Binaire Ordonn Horizontalement Il est tel que pour tout n ud de l arbre les l ments de son sag lui sont inf rieurs de son sad lui sont sup rieurs ou gaux Exemple On a bien l arbre ordonn horizontalement Pour un parcours en ordre on obtient 1 5 6 10 15 30 35 50 60 La relation d ordre est donc totale Mais cela d pend de la d finition on peut mettre les plus grands dans le sad ou sag 132 Dunod La photocopie non autoris e est un d lit Ordre croissant sag lt racine lt 4 1 Arbres binaires sad d croissant sad gt racine gt sag Figure 4 9 Arbre Binaire Ordonn Horizontalement ABOH Algorithmes de manipulation de l ABOH Ordre Donne les l ments en ordre total croissant ou d croissant selon la d finition choisie pour ABOH et la priorit de traitement du sag par rapport au sad e Recherche d un l ment dans un ABOH Pas de notion de retour arri re on ne parcourt qu une branche de l arbre car on sait s il est plus grand ou plus petit Donc le parcours est naturellement dichotomique Principe SI l arbre est vide ALORS fin et chec SINON SI l l ment cherch fin et r ussite SINON SI l l ment cherch rechercher l l SINON rechercher l l l ment po
93. amp en utilisant plusieurs fois de suite la notation Pour qu un champ d une structure s1 soit lui m me une structure s2 il faut cependant que cette structure s2 soit d finie avant s1 Exemple STRUCTURE t_date jj mm aa entier pour jour mois ann e STRUCTURE t_evenement ladate t_date r utilisation du type t_date d fini pr c demment description caract re ou encore description caract re 50 le type t_evenement est d fini l aide du type t_date 31 Chapitre 1 Les bases de la programmation 1 9 5 Pointeurs vers les structures Est il possible d utiliser des pointeurs pour stocker l adresse d une variable de type compos La r ponse cette question a des cons quences assez importantes dans la mesure o comme pour les exemples d j trait s dans les chapitres pr c dents des applications programmes professionnels utilis s dans l entreprise auront utiliser beaucoup de structures Or la possibilit de stocker en m moire un certain nombre de structures implique que l on puisse utiliser des tableaux et le plus souvent des tableaux dynamiques En r alit les tableaux statiques ne sont quasiment pas utilis s seule la notation est vraiment confortable d un point de vue de la programmation Un petit retour en arri re vers les pointeurs est ici n cessaire Afin de pouvoir manipuler un contenu l ordinateur a besoin de deux informations e une adresse lui per
94. ans des langages n cessitant des approches diff rentes C C C Java Avant propos e Helen Kassel De double formation en math matiques DEA obtenu en Russie et en informatique DEA obtenu en France elle a enseign l informatique en Russie aux Etats Unis et en France Elle poss de galement une exp rience du travail en entreprise en tant qu ing nieur en informatique Enseignant en informatique et en math matiques l EFREI depuis plus de dix ans elle est actuellement le chef du d partement math matiques informatique e Franck Lepoivre Dipl m ing nieur de l ISEP en 1995 il volue dans les entreprises de nouvelles technologies en tant que consultant IT coauteur de XML amp Java Eyrolles 2000 puis directeur marketing produit prix technologia ANVAR et 01 Informatique pour Kelua Kawana en 2002 En 2004 il lance reciproCity pour porter l analyse sociologique dans le domaine de intelligence conomique En 2007 il lance Pepper Labs pour porter les math matiques appliqu es et algorithmique vers les entreprises et leur probl matiques m tier mod lisation et prototypage d outils d analyse complexe notamment dans les domaines du marketing et des neurosciences appliqu es Il intervient l EFREI en algorithmique et structures de donn es th orie des langages et techniques de compilation th orie des graphes aide a la d cision et algorithmique num rique e Boris Velikson Dipl m de Ph D
95. arcours de la liste d origine cr ation d une place partir de la place d origine copie succ newSingletonList l content insertion de la nouvelle place dans la copie SI 1 prev NULL ALORS copie succ prev copie FINSI copie copie succ FAIT SI 1 succ NULL ALORS copie succ copie_t te FINSI RETOURNER copie_t te FIN Implantation C list duplicate list 1 if 1 NULL return NULL list head 1 list dupl newSingletonList 1 gt content list dupl_head dupl while 1 gt succ NULL amp amp 1 gt succ head T 1 gt succ it ration de la liste de r f rence dupl gt succ newSingletonList 1 gt content if 1 gt prev NULL dupl gt succ gt prev dupl dupl dupl gt succ it ration de la liste copi e Corrig s des exercices 67 Chapitre 2 Structures s quentielles simples if 1 gt succ NULL dupl gt succ dupl_head return dupl_head Exercice 2 8 Refermer une liste sur elle m me Sp cification Donn e modifi e la liste transform e FONCTION refermer _sur_ elle meme l liste VAR p place DEBUT SI estvide 1 ALORS RETOURNER FINSI p lt t te 1 TANTQUE dernier p FAIRE p succ p FAIT succ p t te 1 FIN R alisation en C Donn e modifi e la liste transform e void lin2circ plist pl if pl NULL return list 1 pl if 1 NULL return while l gt succ NULL 1 1 gt succ i
96. aux ne sont pas n cessairement faciles d acc s On commence g n ralement l apprentissage par la pratique de la programmation l aide d un langage simple puis dans un second temps on prend du recul par rapport cette premi re approche pour d couvrir les aspects les plus g n raux des structures de donn es et des algorithmes standards Enfin on aborde les l ments plus math matiques de la complexit apr s en avoir ressenti la r alit par l exp rience programmatique Une tape majeure qui fera la diff rence entre programmeur et algorithmicien consistera prendre de la distance avec la programmation et se repr senter dans toute leur g n ralit les sch mas algorithmiques ind pendamment de tout langage d implantation L influence du paradigme de programmation sp cifique du premier langage appris est souvent le frein qui emp che d aborder l algorithmique selon la bonne perspective l autre extr mit du spectre de progression destin l ing nieur en informatique accompli un ouvrage tel que le TAOCP de Donald E Knuth qui repr sente la quintessence de l art algorithmique est un ouvrage radicalement indigeste pour qui fait ses premiers pas en informatique QU EST CE QU UN ALGORITHME Selon l Encyclopedia Universalis un algorithme est la sp cification d un sch ma de calcul sous forme d une suite finie d op rations l mentaires ob issant
97. cc cour LIBERER cour SINON m morisation de la place d l ment pr c dent l l ment tester prec cour cour succ cour FINSI FAIT FINSI RETOURNER ok FIN R alisation en C avec extensions pour les listes circulaires et doublement cha n es Donn e int x l l ment supprimer Donn e modifi e list pl la liste d o supprimer l l ment R sultat type bool en int en C int removeFirst list pl int x list prec cour int ok 0 if pl NULL return ok int circular isCircular pl A vous de jouer int perimeter getCLength p1 Idem if pl gt content x si le x est le premier l ment prec pl la t te est not e prec pl pl gt succ on d place le d but de liste au suivant if pl NULL pl gt prev NULL pour la doublement cha n e en pour la circulaire qui pendant un instant ne l est plus if circular if pl gt succ prec pl gt succ pl else list last pl while last gt succ prec last last gt succ last gt succ pl ok 1 free prec on lib re la m moire de l ex t te else prec pl la t te est not e prec Dunod La photocopie non autoris e est un d lit 2 1 Listes lin aires cour pl gt succ while CC ok amp amp cour NULL amp circular circular amp perimeter gt 0 if cour gt
98. cification de l algorithme construit une liste circulaire ordonn e d entiers partir d un tableau non ordonn d entiers FONCTION newOrdoredCircList donn es entier size entier list VAR i valeur entier trouv bool en tete sl_val 1 list DEBUT SI size 0 ALORS pas de donn es gt liste vide RETOURNER NULL FINSI construction de la t te a partir du tableau de donn es tete lt newSingletonList donn es 0 tete POUR i DE 1 A size 1 FAIRE valeur lt donn es i trouve faux sl_val lt newSingletonList valeur insertion en t te de liste SI valeur lt l content ALORS sl_val succ lt sl_val tete SINON insertion faire en milieu de liste TANTQUE 1 succ NULL ET trouv faux FAIRE SI val lt l succ content ALORS il faut ins rer ici sl_val succ 1 succ 1l succ sl_val trouv vrai SINON parcours de la liste passage au suivant TT 1 succ FINSI FAIT SI 1 succ NULL ALORS cas o on a atteint la fin de liste 1l succ sl_val FINSI FINSI FAIT concat amp tete amp tete pour rendre la liste circulaire RETOURNER tete FIN 103 Chapitre 3 Structures s quentielles complexes Implantation C construit une liste circulaire ordonn e d entiers partir d un tableau non ordonn d entiers list newOrdoredCircList int data unsigned size if data NULL return NULL int i int val
99. cle TANT QUE Sa syntaxe est la suivante Langage algorithmique TANTQUE condition FAIRE instruction 1 instruction n FAIT instructions suivantes Implantation C while condition instruction 1 instruction n instructions suivantes Lorsque ordinateur rencontre cette structure il proc de syst matiquement de la mani re sui vante e Lacondition est test e on dit aussi valu e e Si la condition est fausse l instruction ou les instructions du bloc ne sont pas ex cut es et on passe aux instructions suivantes apr s la structure de contr le e Si la condition est vraie l instruction ou les instructions du bloc sont ex cut es et on recom mence l tape 1 test de la condition La boucle FAIRE TANT QUE Cette structure de contr le est tr s proche syntaxiquement de la boucle ou r p tition TANTQUE La seule diff rence r side dans l ordre dans lequel sont faits les tests et les instructions Cette structure s utilise de la mani re suivante Langage algorithmique FAIRE instruction 1 12 Dunod La photocopie non autoris e est un d lit 1 5 Structure de contr le instruction n TANTQUE condition instructions suivantes Implantation C do instruction 1 instruction n while condition instructions suivantes Lorsque ordinateur rencontre cette structure il proc de syst matiquement de la mani re sui vante e Ex cution de l
100. complexes Tester si la file est vide D clarations Donn e file f R sultat de type bool en En t te enC int file vide file f Algorithme file vide FONCTION file_vide f file bool en VAR vide bool en DEBUT SI f nb_elt 0 ALORS vide lt vrai SINON vide faux FINSI RETOURNER vide FIN Placer un l ment la fin de la file enfiler D clarations Donn e T elt_a_enf Donn e modifi e file ff En t te C void enfiler T elt_a_enf file ff Algorithme enfiler FONCTION enfiler x T ff file VAR courant ptr_poste DEBUT RESERVER courant courant info x courant suivant NULL SI ff tete NULL ALORS ff tete courant ff fin courant SINON ff fin suivant lt courant ff fin courant FINSI ff nb_elt ff nb elt 1 FIN Retirer un l ment de la t te de la file d filer D clarations Donn e modifi e file ff T elt_def R sultat de type bool en En t te int defiler file ff T elt_dep 92 Dunod La photocopie non autoris e est un d lit 3 2 Les files Algorithme d filer FONCTION defiler ff file elt_ def T bool en VAR courant ptr_ poste ok bool en DEBUT SI non file _vide ff ALORS ok vrai elt def ff tete info ff nb elt ff nb elt 1 op ration pour lib rer l espace m moire courant ff tete ff tete ff tete suivant LIBERER courant SI ff
101. content x removeFirst et terminaison OKs Ss prec gt succ cour gt SUCC en pour la liste doublement chafn e if cour gt succ NULL cour gt succ gt prev prec free cour else it ration prec cour cour cour gt succ return ok 2 1 4 Variantes d implantation des listes Il existe d ailleurs de nombreuses variantes de la repr sentation des listes l aide de pointeurs Cellule racine Il est parfois commode de d finir une liste non pas comme un pointeur sur une cellule mais par un bloc de cellules du m me type que les autres cellules de la liste Ce bloc ne contient que l adresse du premier l ment de la liste L utilisation d un tel bloc permet d viter un traitement sp cial pour P insertion et la suppression en d but de liste ER ER GRR GE Figure 2 2 Liste lin aire simplement cha n e avec cellule racine Liste circulaire On peut aussi cr er des listes circulaires on remplace dans la derni re place de la liste le pointeur NULL par un pointeur vers la t te de la liste de plus si l on choisit la derni re place comme point d entr e dans la liste on retrouve la t te de liste en parcourant un seul lien 43 Chapitre 2 Structures s quentielles simples Figure 2 3 Liste simplement chain e circulaire Liste doublement chain e ou chain e bidirectionnelle Dans la repr sentation classique le parcours des listes est orient dans
102. currences d un l ment apr s la ki me Tr s semblable au pr c dent Entr es x l entier dont on supprime toutes les occurrences sauf les k premi res dans la liste k le nombre d occurrences qu on laisse sauves Entr es modifi es la liste dont on supprime certaines occurrences de x Sortie un code de statut d ex cution e SUPPRESSION 1 il y a eu au moins un retrait effectif e IDENTITE 0 il n y a eu aucun retrait car la liste ne comporte aucun x FONCTION suppr OccurApr sKi me l liste lt entier gt x SUPPRESSION VAR statut DEBUT statut IDENTITE SI estvide 1 ALORS SI premier 1 x ALORS SI k lt 1 ALORS Te fin 1 statut SUPPRESSION SINON e lt premier 1 Te fin 1 st2 num ration 62 entier k IDENTITE e entier entier Dunod La photocopie non autoris e est un d lit ke k 1 FINSI SI estvide 1 ALORS supprOccurApr ski me 1 x k FINSI SI k gt 0 ALORS 1 lt cons e 1 FINSI SINON e lt premier 1 1 fin 1 SI estvide 1 ALORS st2 lt suppr ccurApr sKi me l x k SI statut IDENTITE ALORS statut st2 FINSI FINSI 1 lt cons e 1 FINSI FINSI RETOURNER statut FIN Exercice 2 6 Inverser une liste Etude Figure 2 10 Inversion d une liste Deux approches l une it rative l autre r cursive Algorithme it ratif FONCTION reverse pl list VAR prev curr succ list DEBUT S
103. cursif n ayant pas grand int r t pour une simple jonction Nous travaillons par r f rence c est dire qu il n y a pas de copie des deux listes on rattache les deux listes Sp cification de l algorithme Entr es modifi es deux listes d entiers FONCTION concat l lo liste lt entier gt VAR pi p2 place DEBUT SI estvide l ALORS SI estvide l2 ALORS 1 lt lo SINON 52 Dunod La photocopie non autoris e est un d lit Corrig s des exercices DT lt t te l TANTQUE dernier p FAIRE p succ p FAIT succ p1 t te lo FINSI FINSI FIN R alisation en C void concat list pll list pl2 if pl2 NULL return ras 11 soit nulle ou non if pll NULL affectation directe de 12 11 oll pl2 return sinon list 1 pll while l1 gt succ NULL 1 1 gt succ it ration 11 1 gt succ pl2 rattachement de 12 Et r crite avec les m thodes utilitaires donn es en introduction void concat list pll list pl2 if isempty pl2 return ras 11 soit nulle ou non if Cisempty p11 affectation directe de 12 11 pll pl2 return sinon list 1 pll while islast 1 1 succ 1 it ration 11 1 gt succ pl2 rattachement de 12 53 Chapitre 2 Structures s quentielles simples Exercice 2 3 Extraire deux listes partir d une liste tude Plusieurs app
104. de dans le fait que si plusieurs entr es ont le m me type on ne peut pas les crire comme on le ferait pour une d finition multiple de plusieurs variables du m me type Il faut rappeler le type de l entr e pour chacune des entr es La sortie ne n cessite pas d tre nomm e car c est la fonction ou au programme appelant la fonction de r cup rer cette valeur Le r le de la fonction se limite uniquement dans le cas de la sortie pouvoir fournir une valeur num rique seul son type est donc important e Corps Le corps de la fonction est constitu des instructions de la fonction et est plac directement la suite de l en t te de la fonction entre les mots DEBUT et FIN Dans le corps de la fonction outre les instructions on peut galement trouver des d finitions de variables qui peuvent tre utiles pour faire des calculs interm diaires lorsque l on utilise la fonction Les d finitions des variables se trouvent avant le mot DEBUT e Les variables locales Ces variables d finies l int rieur de la fonction sont des variables dites locales car elles ne sont connues que par la fonction C est logique car c est la fonction qui les d finit en quelque 24 Dunod La photocopie non autoris e est un d lit 1 8 Les sous programmes ou fonctions sorte pour son usage propre Une autre fonction ou un programme ext rieur ne connaissent pas l existence de ces variables et donc plus forte
105. de fa on rigoureuse et non ambigu effective c est dire pouvant tre effectivement r alis e par une machine cela correspond a une action qui peut tre r alis e avec un papier et un crayon en un temps fini par exemple la division enti re est une op ration effective mais pas la division avec un nombre infini de d cimales Quelle que soit la donn e sur laquelle on travaille un algorithme doit toujours se terminer apr s un nombre fini d op rations et fournir un r sultat CONCEPTION D UN ALGORITHME La conception d un algorithme un peu compliqu se fait toujours en plusieurs tapes qui corres pondent des raffinements successifs La premi re version de l algorithme est autant que possible ind pendante d une impl mentation particuli re En particulier la repr sentation des donn es n est pas fix e ce premier niveau les donn es sont consid r es de mani re abstraite on se donne une notation pour les d crire ainsi que l ensemble des op rations qu on peut leur appliquer et les propri t s de ces op rations On parle alors de type abstrait de donn es La conception de l algorithme se fait en utilisant les op rations du type abstrait Pour r soudre des probl mes nous allons appliquer une d marche descendante on se donne la d finition des types de donn es on dit encore leur sp cification et on con oit l algorithme ce niveau On donne ensuite une repr sentation co
106. de toutes les mesures est qu elles sont calcul es selon un proc d r cursif Sp cification de l algorithme k k Retourne l cart en valeur absolue entre Ja mesure de la partie droite et celle de la partie gauche Le second param tre utilis indique la mesure utilis e 1 masse 2 profondeur 3 surface zy FONCTION getBalance t tree selectedMeasure entier entier VAR balance entier 151 Chapitre 4 Structures arborescentes DEBUT SI isEmptyTree t OU isSingletonTree t ALORS RETOURNER 1 FINSI balance lt 0 SI selectedMeasure 1 ALORS balance getMass t sag getMass t sad SINON SI selectedMeasure 2 ALORS balance getDepth t sag getDepth t sad SINON SI selectedMeasure 3 ALORS balance getSurface t sag getSurface t sad FINSI FINSI FINSI SI balance lt 0 ALORS RETOURNER balance SINON RETOURNER balance FINSI FIN FONCTION getSurface t tree entier DEBUT SI isEmptyTree t ALORS RETOURNER 0 FINSI SI isSingletonTree t ALORS RETOURNER 1 SINON RETOURNER getSurface t sag getSurface t sad FINSI FIN FONCTION getMass t tree entier DEBUT SI isEmptyTree t ALORS RETOURNER 0 SINON RETOURNER 1 getMass t sag getMass t sad FINSI FIN 152 Dunod La photocopie non autoris e est un d lit Corrig s des exercices Exercice 4 7 parcourir un AB en largeur et en profondeur tude Deux utilisations classiq
107. devrait vous aider vous le repr senter Figure 4 26 163 Chapitre 4 Structures arborescentes Sp cification de l algorithme FONCTION buildPascalTriangle pt tree n entier VAR i j entier root curr currline prev prevline tree DEBUT pt lt newSingletonTree 1 root pt SI n 0 ALORS RETOURNER FINSI j n i currline root curr currline TANTQUE j gt 0 FAIRE curr sad newSingletonTree 1 curr lt curr sad sel FAIT prevLine root prev prevLine in TANTQUE i gt 0 FAIRE prevLine sag newSingletonTree 1 currLine prevLine sag curr currLine 11 TANTQUE j gt 0 FAIRE prev lt prev sad curr sad newSingletonTree curr content prev content curr curr sad J j l FAIT prevLine lt currLine prev lt prevLine 1 1 1 FAIT FIN R alisation en C void buildPascalTriangle tree pt unsigned n tree root pt newSingletonTree 1 if n 0 return unsigned j n 1 it rateur de colonnes indices de 0 n 164 Dunod La photocopie non autoris e est un d lit Corrig s des probl mes tree currLine root ligne de sad gt sad gt courante tree curr currLine fils sad en cr ation courant on commence par cr er toute la branche droite de l arbre while j gt 0 curr gt sad newSingletonTree 1 curr curr gt sad le travail s effectue ensuite ligne apr s ligne
108. e d un automate non d terministe consiste en la possibilit de la couper pour simplifier la d terminisation 208 Dunod La photocopie non autoris e est un d lit Solution A Figure 5 62 A e Minimisation Oo L II avec I 0 P H 12 Corrig s des exercices a b a b Tableau 5 46 Etat a b a b 0 12 P Il l P P P l l Les deux tats du groupe I se sont s par s donc tous les tats se sont s par s l automate tait minimal d s le d but Exercice 5 11 Solution a e D terminisation Tableau 5 47 tat a b 0 0 01 01 0 012 012 02 012 02 02 012 209 Chapitre 5 Automates Figure 5 63 e Minimisation gt O Oo L II avec I 0 01 II 012 02 Tableau 5 48 tat a b a b 0 0 01 l I 01 0 012 l Il 012 02 012 Il Il 02 02 012 Il Il Le groupe II ne peut pas se s parer Le groupe I se s pare en 0 et 01 Le r sultat Figure 5 64 Solution b e D terminisation Tableau 5 49 En modifiant les tiquettes des tats tat a b tat a b 02 12 01 A B D 01 12 012 D B E 12 1 02 B C A 012 12 012 E B E 1 02 C P A P P P P P Tous les tats sont des tats finaux sauf l tat poubelle 210 Dunod La photocopie non autoris e est un d lit Corrig s des exercices Tableau 5 50 tat a b a
109. e O Ce que n est pas un tableau Un tableau est en r alit une variable comme les autres mais son type est d une nature radicalement diff rent des types pr sent s plus haut En particulier ce n est pas le type des l ments stock s Ainsi e un tableau stockant des entier n est pas un entier e un tableau stockant des reel n est pas un reel e un tableau stockant des caractere n est pas un caractere 14 1 6 Tableaux Il n est pas possible de manipuler un tableau en utilisant les op rateurs arithm tiques et logiques que nous avons rencontr s jusqu pr sent ceux ci tant limit s aux types de base Il est tr s important de se rappeler cela c est un bon moyen d viter les erreurs lors de l criture d un programme A 1 6 2 Repr sentation Un tableau peut tre vu comme un ensemble de cases o chaque case stocke une valeur Soit la d finition suivante VAR vals r el 15 Cette d finition cr e un tableau nomm vals qui stocke au maximum quinze r el dans quinze cases diff rentes Aucune de ces cases n est initialis e ce qui est indiqu par un Tableau 1 3 vals Chacune de ces cases est rep r e par son num ro ou indice l int rieur du tableau Un tableau de taille maximale N verra ses cases num rot es de 0 N 1 En effet pour un ordinateur la valeur 0 est une valeur comme une autre Soit i un indice i est do
110. e prev noeudk RETOURNER vrai FIN Implantation C Insertion dans une liste doublement cha7n e pl liste o s effectue l insertion place place dans la liste on ins re juste devant 113 Chapitre 3 Structures s quentielles complexes k l ment ins rer status code 0 ok 1 ko Type abstrait list inserer list 1 int k element e int insert list pl list place int k v rifier que la place est bien dans la liste concern e m me m thode que pour 1 exercice 2 5 if areConvergent place pl return 1 list K newSingleton k cas de la liste vide if pl NULL pl K return 0 cas t te de liste if place pl K gt succ pl K gt prev NULL pl K return 0 cas fin de liste if place NULL list last lastElement pl last gt succ K K gt prev last return 0 sinon milieu de liste list prec place gt prev prec gt succ K K gt succ place K gt prev prec place gt prev K return 0 114 Dunod La photocopie non autoris e est un d lit Corrig s des exercices e Suppression Sp cification de l algorithme Suppression dans une liste doublement cha n e Type abstrait list supprimer list 1 int k status code 0 ok 1 ko FONCTION removeElement pl list place list bool en VAR prec list DEBUT SI appartient place pl ALORS RETOURNER faux
111. e 11 gt succ NULL amp amp 11 gt succ gt content min 11 11 gt succ avoir atteint la queue de liste ne peut logiquement pas arriver CODE GENERIQUE COMMUN DE FINALISATION Cas du s lecteur milieu de liste int cutE plist pll plist pl2 CODE GENERIQUE COMMUN D INITIALISATION on r utilise la fonction Ten de mesure de longueur de liste int n len 11 sur vos copies il faut la r crire on calcule la distance au point de coupe note distance gt 1 int cutPoint n 2 0 n 2 n 2 1 int status 1 on modifie le statut si p12 n est pas NULL if pl2 NULL status 2 on effectue le parcours jusqu au pr d cesseur du point de coupe while cutPoint gt 0 11 11 gt succ avoir atteint la queue de liste ne peut logiquement pas arriver CODE GENERIQUE COMMUN DE FINALISATION Sp cification abstraite Une fois n est pas coutume petit mensonge d ing nieur nous proc dons une r tro conception du principe algorithmique g n ral partir des cinq cas tudi s et r alis s pr c demment 74 Donn es modifi es 1 la liste d entr e coup e en deux qui devient la liste amont et l la liste aval ventuellement produite en sortie Donn e c un param tre du crit re pour rep rer la place qui suit directement le point de coupe et qui devient donc la t te de 1l R sultat un statut d ex cution 1 ERR ERREUR 0 ID op rat
112. e arri re d une liste doublement cha n e Concevoir un algorithme qui r alise le cha nage arri re d une liste doublement cha n e dont seul le chainage avant a t effectu He Exercice 3 4 Inverser pile et file Concevoir deux algorithmes qui cr ent respectivement e la file inverse d une file e la pile inverse d une pile Ces deux algorithmes doivent restituer leur entr e inchang e Exercice 3 5 Simuler la r cursivit l aide d une pile crire un algorithme pour calculer la somme de 1 n n N en simulant la r cursivit l aide d une pile Les en t tes des op rations utiliser pour cet exercice sont fournis FONCTION nouvellePile pile FONCTION estPileVide p pile bool en Ps FONCTION empiler val T pp pile FONCTION depiler pval T pp pile entier 98 Dunod La photocopie non autoris e est un d lit Probl mes Exercice 3 6 Ins rer et supprimer dans une liste doublement cha n e crire un algorithme d insertion dans une liste doublement cha n e crire un algorithme de suppression dans une liste doublement cha n e PROBL MES Probl me 3 1 Probl me de Joseph crire un algorithme permettant de lire deux entiers positifs n et k Construire une liste circulaire dans laquelle seront enregistr s les nombres 2 3 n dans cet ordre En commen ant partir du n ud contenant supprimer successivement tous les
113. e fonction lors de son appel est une expression et non une variable cela signifie entre autres que lors de l appel une fonction dont un param tre est un pointeur l argument associ ne devra pas obligatoirement tre un pointeur mais tout simplement une adresse Il pourra donc s agir de l adresse d une variable existante ou d une adresse stock e dans un poin teur 28 Dunod La photocopie non autoris e est un d lit 1 9 Cr ation de types par le programmeur les types compos s ou structures Les donn es modifi es Les param tres d une fonction sont une copie des arguments Ainsi la modification de la valeur d un param tre n aura aucune influence sur la valeur de l argument Une fonction ne peut pas modifier la valeur des arguments qui lui sont transmis Cependant il est parfois int ressant qu une fonction puisse modifier une variable de la fonction qui l appelle Pour ce faire la technique consiste transmettre la fonction l adresse de la variable modifier Ainsi la fonction r cup re l adresse de la variable et acc de sa valeur gr ce l op rateur contenu de La notation donn es modifi es rencontr e dans la suite de cet ouvrage indique que c est une adresse qui est transmise Retour d une adresse Une fonction peut retourner une adresse car n importe quel type peut tre fourni en sortie de fonction Les pr cautions prendre lorsqu une adresse est
114. e m nent pas la sortie Ils sont donc inutiles Le langage reconnu par cet automate est le m me que le langage reconnu par o o Figure 5 41 Il consiste en mots a aba ababa abababa qu on peut crire comme a ba ou ab a 194 Dunod La photocopie non autoris e est un d lit Exercice 5 6 Solution A e Cet automate lit tous les mots se terminant par bbb e Il est mond e D terminisation Tableau 5 22 Etat a b 0 0 01 01 0 012 012 0 0123 0123 0 0123 Figure 5 42 a Solution A2 e Cet automate lit tous les mots avec un b en 3 position de la fin e Il est mond e D terminisation Initial Terminal Terminal Terminal Terminal Tableau 5 23 Etat b 0 0 01 01 02 012 012 023 0123 02 03 013 0123 023 0123 023 03 013 03 0 01 013 02 012 Corrig s des exercices 195 Chapitre 5 Automates a Solution A3 e Cet automate lit tous les mots contenant au moins trois caract res d b a o peut tre vide e Il est mond e o D terminisation Tableau 5 24 tat a b 0 01 01 01 01 012 012 0123 012 0123 0123 0123 a b Figure 5 44 Solution A4 e Cet automate lit tous les mots consistant en des 0 ou en des 0 suivis d un seul 1 ou le mot 1 196 Dunod La photocopie non autoris e est un d lit e Il est accessible mais no
115. e mani re typedef struct listNode lt element gt content struct place succ listes simplement cha n es struct place prev listes doublement chain es listNode typedef listNode list typedef list plist define ERR 1 code d erreur lisibilit des exemples Les quelques implantations C de m thodes l mentaires de manipulation de la liste cha n e conformes au contrat du type abstrait pourront s av rer utiles dans l criture de vos programmes d implantation C de vos algorithmes notamment en purant votre code d une trop grande quantit 47 Chapitre 2 Structures s quentielles simples de gt et amp qui nuisent leur lisibilit Vous pourrez ainsi vous rapprocher de la vision algorithmique du qu est ce que a fait plut t que de la vision programmatique du comment a se fait lt element gt content list 1 return 1 gt content int isempty list 1 return 1 NULL list succ list 1 return 1 gt succ int islast list 1 return isempty succ 1 pour les solutions algorithmiques les fonctions sont les suivantes FONCTION content 1 list DEBUT RETOURNER 1 gt content FIN FONCTION isempty 1 list VAR vide bool en DEBUT SI 1 NULL ALORS vide lt vrai SINON vide faux FINSI RETOURNER vide FIN FONCTION succ l list list DEBUT RETOURNER 1 succ FIN FONCTION islast l list DEBUT RETOURNER isem
116. e r gles qui sont tr s simples cela revient r soudre des petits probl mes de logiques Les op rateurs bool ens sont galement tr s simples comprendre et manipuler Les op rateurs bool ens de comparaison sont pr sent s dans le tableau 1 1 page suivante Gr ce ces op rateurs 1l est possible d crire des conditions l mentaires pour r aliser des tests simples 1 5 2 Ex cution conditionnelle d instructions Structure SI ALORS La structure de contr le SI ALORS permet d ex cuter des instructions en fonction de la valeur d une condition qui n est autre que le r sultat d un test Chapitre 1 Les bases de la programmation Tableau 1 1 Nom Utilisation Role R sultat E valeur1 valeur2 galit VRAI si les deux valeurs test es sont gales valeur1 valeur2 In galit VRAI si les deux valeurs test es sont diff rentes gt valeur1 gt valeur2 Sup rieur strictement VRAI si valeur1 strictement sup rieure valeur2 lt valeur1 lt valeur2 Inf rieur strictement VRAI si valeur1 strictement inf rieure valeur2 gt valeur1 gt valeur2 Sup rieur ou gal VRAI si valeur1 sup rieure ou gale valeur2 lt valeur1 lt valeur2 Inf rieur ou gal VRAI si valeur1 inf rieure ou gale valeur2 La syntaxe est la suivante SI condition ALORS instruction s FINSI Implantation C if condition instruction s
117. ecrire ptr_elt Implantation C typedef struct elt T info bool en alire struct elt suivant elt typedef ptr_elt elt typedef struct liste_circ ptr_elt lire ptr_elt ecrire liste_circ Tiste circ 3 2 Les files bool en 97 Chapitre 3 Structures s quentielles complexes Rien dans les types ne traduit que le premier l ment de la liste est le successeur du dernier ceci devra tre rendu explicite dans les algorithmes En approche statique il s agit de l op ration modulo N En approche dynamique il s agit du passage au suivant NONC S DES EXERCICES ET DES PROBL MES EXERCICES wrk Exercice 3 1 Afficher une liste chain e Ecrire un algorithme pour afficher une liste chain e d entiers sous la forme suivante Si la liste est lin aire Nom_liste gt elt gt eltz gt gt eltn gt eltiast Si la liste est circulaire Nom_ liste gt elt gt eltz gt gt eltn gt eltiast Si certains maillons contigus sont doublement chain s afficher lt gt au lieu de gt Apportez une attention particuli re aux traitements sp cifiques de d but milieu et fin de liste ainsi qu aux cas sp ciaux comme la liste vide ou singleton Exercice 3 2 Construire une liste circulaire ordonn e crire un algorithme qui cr e une liste circulaire ordonn e d entiers partir d un tableau non ordonn d entiers Exercice 3 3 R aliser le cha nag
118. ed Ves S COMPLEXES 22224 2eme an annee nen 3 2 3 Manipulation d une file m thode avec deux pointeurs nonc s des exercices et des probl mes Corrig s des exercices et des probl mes VI 25 27 28 29 30 31 31 31 32 33 34 35 35 35 35 35 37 43 45 47 87 87 87 87 88 88 90 90 91 91 98 99 Table des mati res CHAPITRE 4 e STRUCTURES ARBORESCENTES 127 Rappels de COU 222 ccc8cec cee cei i chs babel eemteeebiuetie ciedmseds 127 AN Arbres binaires 52e Es ENEE DE EE UEA AE ET NARA 127 4 1 1 D finition EEE EE ETETE 128 4 1 2 Repr sentations 7 1625 40 iii ee ne aaa daaa E rE ent 128 4 1 3 Algorithmes de parcours d un arbre binaire 129 4 1 4 Arbres binaires de recherche ABOH Arbres Binaires Ordonn s Horizontalement 132 nonc s des exercices et des probl mes 142 Corrig s des exercices et des probl mes 146 CHAPITRE 5 e AUTOMATES 1 2 1 2 043 40 smardememmancemst diese 169 Rappels de COURS ne de oc Des 169 Sol JHISIONQHES iii ii nier ont etebacdas ceadade easeeaesacie 169 5 2 Quelques d finitions A Sand Red ere cc 170 5 3 L interpr tation INMUNIVG csc cdeedanecdtntes diesel outre 170 5 3 1 Automates d terministes
119. ee t sad SI sadMin lt min ALORS min lt sadMin FINSI FINSI RETOURNER min FIN Attention cette fonction n est pas d finie pour un arbre vide FONCTION maxOfTree t tree entier VAR max sagMax sadMax entier DEBUT max lt t content SI isEmptyTree t sag ALORS sagMax maxOfTree t sag SI sagMax gt max ALORS max lt sagMax FINSI FINSI SI isEmptyTree t sad ALORS sadMax max0OfTree t sad 150 Dunod La photocopie non autoris e est un d lit Corrig s des exercices SI sadMax gt max ALORS max sadMax FINSI FINSI RETOURNER max FIN Exercice 4 5 mesurer la hauteur d un ABOH Sp cification de l algorithme FONCTION getDepth t tree entier VAR sagDepth sadDepth maxDepth entier DEBUT SI isEmptyTree t ALORS RETOURNER 0 SINON sagDepth getDepth t saqg sadDepth getDepth t sad SI sagDepth gt sadDepth ALORS maxDepth sagDpeth SINON maxDepth sadDepth FINSI RETOURNER 1 maxDepth FINSI FIN Exercice 4 6 valuer l quilibre d un AB tude L quilibre partiel d un arbre binaire est d termin sur la base du diff rentiel des mesures des hauteurs des fils droit et gauche de la racine Par extension nous proposons une solution qui peut s appuyer sur diff rentes mesures autres que la hauteur pour valuer le statut d quilibre partiel d un arbre dans une vari t largie de termes Le d nominateur commun
120. els ou bien les renommer par par exemple A B C et remplacer dans les transitions tout tat par le nom de son groupe Sie r e A r B o les groupes A B 6 4 alors dans l automate minimis on a AB o maintenant on consid re A et B comme tats de l automate minimis Cette remarque deviendra tout fait claire la fin de l exemple suivant Exemple 1 Minimisons l automate d terministe complet Figure 5 11 179 Chapitre 5 Automates d crit par le tableau de transitions suivant Tableau 5 8 aa Etats r sultant en lisant a en lisant b initial 0 1 2 1 1 3 2 1 2 3 2 4 terminal 4 1 2 l unique tat terminal est l tat 4 Donc la partition initiale 0 1 2 3 4 Notons les groupes non terminal et terminal Z 0 1 2 3 et II 4 On ne peut pas videmment essayer de s parer le groupe II qui consiste d j en un seul tat On regarde donc dans quel groupe tombent les transitions a partir des tats du groupe Tableau 5 9 Groupes r sultant en lisant a en lisant b WIN o Donc le groupe J se s pare en deux et ona 0 1 2 3 4 Notons les groupes en recyclant la notation Z 0 1 2 11 3 I 4 Maintenant essayons de s parer le groupe J en regardant o tombent les transitions partir de ses tats dans les termes de la s paration
121. emier puis concevez le dernier en exploitant le second Exercice 2 6 Inverser une liste crire un algorithme qui inverse une liste chain e sans recopier ses l ments R aliser une version it rative et une autre r cursive Exercice 2 7 Construire une liste partir d une source de donn es Concevoir un premier algorithme qui construit une liste cha n e lin aire partir d un tableau et un second qui duplique une liste chain e existante Exercice 2 8 Refermer une liste sur elle m me Concevoir un algorithme qui transforme une liste simplement chain e lin aire en liste simplement chain e circulaire Exercice 2 9 Effectuer et retourner deux calculs sur une liste Concevoir un algorithme qui calcule et retourne respectivement le produit des l ments positifs et celui des l ments n gatifs d une liste simplement cha n e d entiers Exercice 2 10 Couper une liste en deux Concevoir un algorithme qui s pare une liste simplement cha n e d entiers en deux listes e A partir d un pointeur sur le maillon qui devient t te de la seconde liste de sortie e B juste devant le premier maillon contenant une valeur donn e x e C partir de la k position c est dire k maillons dans la premi re liste de sortie et le reste dans la seconde e D juste devant le maillon contenant la valeur minimale de la liste e E telles que les deux listes de sortie aient m me lo
122. emp sPush valeur p_s TANTQUE isEmptyStack temp RETOURNER p_rev_s FIN Implantation C Entr e la pile source dont il s agit de construire l inverse Sortie la pile inverse Cr e la pile inverse de la pile p_s 1Stack reverseStack 1Stack p_s if p_s NULL fprintf stderr reverseStack error null stack return NULL int val 1Stack p_rev_s newEmptyStack la pile inverse retourn e 1Stack p_tmp_s newEmptyStack une pile pour restituer p_s do 110 Dunod La photocopie non autoris e est un d lit Corrig s des exercices sPop amp val p_s d pilement depuis la pile d entr e p_s sPush val p_rev_s empilement dans la pile r sultat sPush val p_tmp_s pour reconstruction de p_s while isEmptyStack p_s reconstruction de p_s do sPop amp val p_tmp_s sPush val p_s while isEmptyStack p_tmp_s free p_tmp_s Soyons diligents avec la m moire return p_rev_s void testStackReversing printf n ninversion d une file n n int val 10 1Queue p_q newEmptyQueue do qPush val p_q while val gt 0 printListGraph p_q gt head input queue 1Queue p_rev_q reverseQueue p_q printListGraph p_rev_q gt head reversed queue printListGraph p_q gt head unchanged input queue Exercice 3 5 Simuler la r cursivit l aide d une
123. en indiquant quelle place en m moire occupe la valeur et quelle est la technique de codage utilis e Nous distinguons quatre types l mentaires en algorithmique e Le type entier sera utilis pour stocker des valeurs enti res positives ou n gatives Un entier occupe quatre octets 32 bits en m moire e Le type r el sera utilis pour stocker les nombres virgule Un r el occupe huit octets 64 bits en m moire e Le type caract re sera utilis pour stocker les caract res Un caract re occupe un octet 8 bits en m moire e Letype boole n sera utilis pour stocker les valeurs de type vrai faux Un bool en occupe un octet 8 bits en m moire Attention au type dit r el En effet un ordinateur ne stocke ses valeurs que sur une place limit e il ne stocke donc qu un nombre limit de d cimales apr s la virgule Les valeurs de type r el en algorithmique ne sont donc que des valeurs approch es de leur version math matique Remarque Le type utilis pour stocker des caract res est un peu particulier car un caract re est en fait un nombre entier L ordinateur utilise une table de correspondance qui associe une valeur enti re un code un caract re qu il s agit de manipuler c est dire la plupart du temps pour l afficher a l cran Cette table de correspondance se nomme la table de symboles table ASCII Unicode Pour la table ASCH un caract re est stock dans un octet un groupement de
124. ephList int longueur int first if longueur lt 1 return NULL cas de la liste vide initialisation de la cha ne avec la cr ation de la t te list head malloc sizeof place allocation m moire head gt contenu first affectation du contenu head gt succ newJosephList longueur 1 first 1 return head retour du pointeur sur la t te e Retrait du Ki l ment Sp cification de l algorithme FONCTION removekst pl list k entier list VAR t te courant prev list VAR circulaire bool en p rim tre entier DEBUT t te pl courant pl SI courant NULL ALORS RETOURNER NULL FINSI circulaire lt isCircular courant p rim tre getCLength courant SI circulaire vrai ET p rim tre 1 ALORS pl lt NULL RETOURNER pl FINSI SI circulaire vrai ALORS prev getKstElement pl p rim tre 1 SINON prev NULL FINSI TANTQUE courant succ NULL ET k gt 1 FAIRE lt k 1 prev lt courant courant courant succ FAIT SI courant succ NULL ET k gt 0 ALORS RETOURNER pl FINSI SI circulaire vrai ALORS prev succ courant succ 120 Dunod La photocopie non autoris e est un d lit Corrig s des probl mes SI courant t te ALORS pl lt courant succ FINSI LIBERER courant RETOURNER prev succ SINON SI prev NULL ALORS pl lt courant succ LIBERER courant RETOURNER pl SINON SI courant succ N
125. erminisation Soit C Q 1 T E un automate fini Notons II l ensemble des parties de Q C est un ensemble fini puisque si Q an l ments II en a On Un automate d terministe D correspondant a C prend e comme ensemble d tats un sous ensemble P de l ensemble II des parties de Q 173 Chapitre 5 Automates e comme unique tat initial l ensemble 7 des tats initiaux de C e comme ensemble d tats terminaux l ensemble s u Plu NT des parties de Q qui contiennent au moins un tat terminal de C e comme fl ches l ensemble des u a v o u P et v est l ensemble de tous les tats q Q tels qu il existe un tat p dans u avec p a q E Cet algorithme formel s explique le plus facilement sur un exemple Exemple de d terminisation Prenons l automate non d terministe pr c dent b Figure 5 4 e D terminisation Tableau 5 4 7 tats r sultant Etat p en lisant a en lisant b entr e 0 0 1 0 0 1 0 1 0 2 0 2 0 1 3 0 0 1 3 0 1 4 0 2 sortie 0 1 4 0 1 0 2 e Explications On commence par l tat initial qui dans ce cas particulier coincide avec l tat initial de l automate non d terministe 0 car notre automate non d terministe n en a qu un seul S il en avait plusieurs on les aurait regroup s pour former l tat initial de l automate d terministe A partir de cet tat 0 en a on va ver
126. est notamment possible de d finir des variables dont le type est un type compos ou structure en utilisant la syntaxe classique de d finition d une variable VAR nom_de_variable type VAR var_comp t_complexe est une d finition de variable tout fait correcte et dont la signification est la variable nomm e var_comp est de type t_complexe 1 9 1 Acc s aux champs L op rateur utilis pour acc der un champ partir du nom d une variable est l op rateur dont la syntaxe d utilisation est la suivante q nom_de_variable nom_du_champ Cela s interpr te comme le champ nom_du_champ de la variable nom_de_variable Cette criture est une expression dont le type est celui du champ r f renc Exemple Soit la d finition de variable suivante VAR z t_complexe Afin d initialiser cette variable z il est n cessaire d acc der individuellement ses champs car l ordinateur est incapable d initialiser directement une variable de type t_complexe 30 Dunod La photocopie non autoris e est un d lit ne 1 9 Cr ation de types par le programmeur les types compos s ou structures Pour stocker la valeur 1 2i dans la variable z il faut en r alit stocker la valeur 1 dans la partie r elle de z et 2 dans la partie imaginaire de z ce qui s crit z re 1 0 z im 2 0 Une confusion fr quente consiste faire pr c der le du nom du type d fini l aide de
127. et p malloc sizeof term allocation p gt coeff atol coeffStr p gt expon atol exponStr important car la valeur par d faut n est pas forc ment NULL prev_p gt nextlerm p printf coeff d gt size scanf s coeffStr p gt nextTerm NULL e Normalisation du polyn me saisi Sp cification de l algorithme FONCTION normalizePolynomial pp polynome VAR 222 DEBUT 222 FIN 81 Chapitre 2 Structures s quentielles simples Implantation C void normalizePolynomial polynomial pp A VOUS DE JOUER e Evaluation du polyn me instanciation 82 Sp cification de l algorithme FONCTION evalPolynomial p polynome x r el r el VAR r sultat valeur r el DEBUT r sultat 0 SI p NULL ALORS RETOURNER r sultat FINSI r sultat r sultat p coeff puissance x p exposant TANTQUE p suivant NULL FAIRE p p suivant valeur lt p coeff puissance x p exposant r sultat r sultat valeur FAIT RETOURNER r sultat FIN Implantation C long evalPolynomial polynomial p long x long res 0 if p NULL return res res p gt coeff powl x p gt expon printf first term eval 41d n res while p gt nextTerm NULL p p gt nextTerm long termVal p gt coeff powl x p gt expon printf next term eval 1d n termVal res termVal return res Dunod
128. ette valeur not e NULL Exemple d utilisation de NULL PROGRAMME test_NULL lire le contenu de p_val est de type r el VAR p_val r el initialisation de p_val avec NULL que l on sait inaccessible p_val lt NULL plus loin dans le programme SI p_val NULL Dunod La photocopie non autoris e est un d lit 21 Chapitre 1 Les bases de la programmation instructions dans lesquelles on peut acc der p_val SINON AFFICHER attention p_val vaut NULL on ne peut acc der p_val FINSI Dans ce cas le programme affiche un message d avertissement plut t que de provoquer une erreur qui n est pas vidente rep rer et corriger ce type de programmation est privil gier dans la mesure o le programmeur ma trise beaucoup mieux ce qui se passe au sein du programme Les adresses de variables existantes Les variables que l utilisateur d finit au sein de son propre programme ont forc ment des adresses valides Pour rappel l adresse d une variable est accessible au moyen de l op rateur amp Exemple Voici donc un exemple d initialisation de pointeur tout fait Valide VAR ptr_c caract re VAR lettre caract re ptr_c amp lettre Les types sont compatibles car ptr_c pointe vers un caract re autrement dit stocke l adresse d une valeur de type caract re et amp lettre est l adresse d une variable de type caract re Que se passe t il exactement
129. eule et unique liste au moment du d pilement final de l appel initial de la fonction 157 Chapitre 4 Structures arborescentes e M thodes de construction Un arbre vident dont tous les fils sont premiers avec leur parent est I arbre qui ne contient que des nombres premiers Une autre fa on de construire un tel arbre est d effectuer la r p tition d un motif appropri e de trois l ments premiers entre eux par exemple 4 9 et 25 par exemple 4 prend la place de racine 9 celle de fils gauche 25 celle de fils droit puis 4 prend la place de fils gauche de 9 et de 25 et 25 celle de fils droit de 9 et 9 celle de fils droit de 25 et ainsi de suite Il existe une multitude de fa ons de proc der la construction d un arbre qui poss de cette propri t de primalit relative parent enfant Cependant l exactitude math matique invite pr ciser qu en r alit il n existe aucune fa on de construire un tel arbre qui n existe pas En effet la racine de l arbre ne peut tre premi re avec son parent qui n existe pas Sp cification de l algorithme XX Retourne la liste cha n e des l ments d un arbre d entiers premiers avec leur parent FONCTION getPrimeChildren t tree list VAR sagprimechildren sadprimechildren primechild list DEBUT SI t NULL ALORS RETOURNER NULL FINSI sagprimechildren NULL sadprimechildren NULL SI t sag NULL ALORS sagprimechildren
130. fichiers dans des syst mes d exploitation tels qu UNIX c est aussi sous forme d arbres que sont repr sent s les programmes trait s par un compilateur Une propri t intrins que de la structure d arbre est la r cursivit et les d finitions des carac t ristiques des arbres aussi bien que les algorithmes qui manipulent des arbres s crivent tr s naturellement de mani re r cursive 4 1 ARBRES BINAIRES Examinons tout d abord quelques exemples simples repr sent s par des arbres binaires Figure 4 1 Les r sultats d un tournoi de tennis au premier tour Jean a battu Jules Marc a battu Francois Paul a battu Yves et Luc a battu Pierre au deuxi me tour Jean a battu Marc et Paul a battu Luc etJeana gagn en finale contre Paul jonnerre Figure 4 2 Le pedigree d un cheval Zoe son p re est Tonnerre et sa m re est Belle la m re de Belle est Rose et le p re de Belle est Eclair 127 Chapitre 4 Structures arborescentes Figure 4 3 Une expression arithm tique dans laquelle tous les op rateurs sont binaires 4 5 8 La structure d arbre binaire est utilis e dans tr s nombreuses applications informatiques de plus les arbres binaires permettent de repr senter les arbres plus g n raux 4 1 1 D finition Le vocabulaire concernant les arbres informatiques est souvent emprunt la botanique ou la g n alogie tant donn un arbre B lt o B1 B2 gt
131. geur l aide d une file Parcours en profondeur d abord Pr ordre Principe Si arbre non vide alors traiter la racine parcourir en Pr ordre le sag parcourir en Pr ordre le sad Algorithme en pseudo C Donn e ptr_arbre p FONCTION pr ordre a ptr_arbre DEBUT SI a NULL ALORS afficher a info pr ordre a sag pr ordre a sad FINSI FIN Exemple Figure 4 6 Parcours en pr ordre On affiche acmutbyo 130 4 1 Arbres binaires Il n y a pas de priorit sur le parcours des sous arbres On pourrait commencer par traiter le sad avant le sag Ordre Principe SI arbre est non vide alors parcourir le sag traiter la racine parcourir le sad Algorithme Donn e ptr_arbre a FONCTION ordre a ptr_arbre DEBUT SI a NULL ALORS ordre a sag afficher a info ordre a sad FINSI FIN Cet algorithme nous permet d obtenir les informations dans un ordre total On peut rentrer les informations dans un arbre binaire de fa on tri e Exemple Figure 4 7 Parcours en ordre On affiche umctayob 131 Chapitre 4 Structures arborescentes Postordre SI arbre n est pas vide parcourir en post ordre le sag parcourir en post ordre le sad traiter la racine Algorithme Donn e ptr_arbre a FONCTION postordre a ptr_arbre DEBUT SI a NULL ALORS postordre a sag postordre a sad afficher a info FINSI FIN Figure 4 8 Parcours en postordre On
132. grouper ces instructions d affichage pour n en avoir qu un seul exemplaire et de pouvoir s en servir lorsqu on en a besoin sans avoir saisir les lignes dans le programme C est cela que sert une fonction elle regroupe des instructions auxquelles on peut faire appel c est dire utiliser en cas de besoin Il s agit en r alit d un petit programme qui sera utilis par le programme on parle aussi de sous programme pour une fonction Ce sous programme fonctionne en bo te noire vis vis des autres sous programmes c est dire qu ils n en connaissent que les entr es valeurs qui sont fournies la fonction et sur lesquelles son traitement va porter et la sortie valeur fournie par la fonction qui peut tre r cup r e par les autres fonctions ou par le programme Une analogie avec une fonction math matique permet d illustrer clairement les notions d entr es et de sorties Soit la fonction suivante d finie avec le formalisme des math matiques F RxR R x y ax 4xyty Les entr es sont les donn es que l on fournit la fonction pour qu elle puisse les traiter et fournir un r sultat il s agit des valeurs x et y La sortie est le r sultat que donne la fonction il s agit de la valeur calcul e x xy y Types des entr es et sorties D apr s la d finition math matique de la fonction le type informatique des entr es et de la sortie peut tre d termin ce sont de
133. hildren 123 p primeChildrenTestTree 3 1 2 1 simplePrintTreeGraph p ptest 121 Corrig s des exercices primechildren getPrimeChildren p printListGraph primechildren primechildren 121 p primeChildrenTestTree 3 2 2 2 simplePrintTreeGraph p ptest 222 primechildren getPrimeChildren p printListGraph primechildren primechildren 222 Exercice 4 10 produire des coupes transversales d un arbre Sp cification de l algorithme Retourne sous forme de liste la coupe tranversale d un arbre du niveau de pronfondeur depth zi FONCTION getLevelList t tree depth entier list VAR sagll sadll list DEBUT SI getDepth t lt depth ALORS RETOURNER NULL FINSI SI depth 1 ALORS SI t NULL ALORS RETOURNER NULL SINON RETOURNER newSingletonList t content FINSI SINON depth depth 1 sagll getLevelList t sag depth sadl l getLevelList t sad depth RETOURNER concat amp sagll amp sadll FINSI FIN 161 Chapitre 4 Structures arborescentes CORRIG S DES PROBL MES Probl me 4 1 le triangle chinois de Pascal Analyse e Traduction du chinois vers l arabe latin Figure 4 24 e Ce qui est demand De passer d une structure qui n est pas un arbre mais s en approche un format d arbre Pour cela on transforme les filiations crois es en filiations simples en supprimant les relations parent enfant sur la gauche sauf pour le
134. ice 3 1 Afficher une liste cha n e Sp cification de l algorithme FONCTION printlistGraph l list nom caracterel VAR t te list DEBUT SI 1 NULL ALORS AFFICHER nom la liste est vide SINON t te AFFICHER nom SI t te prev NULL ALORS d but de liste AFFICHER gt t te content SINON AFFICHER lt gt t te content FINSI TANTQUE 1 succ NULL ET 1 succ t te FAIRE 1 1 succ SI 1 prev NULL ALORS AFFICHER gt I content SINON AFFICHER lt gt 1 content FINSI FAIT SI 1 succ NULL ALORS AFFICHER SINON AFFICHER FINSI FINSI FIN R alisation en C void printListGraph list 1 char nom if 1 NULL printf s empty list nom else 101 Chapitre 3 Structures s quentielles complexes list head 1 printf s nom if head gt prev NULL printf gt 4 d head gt content else printf lt gt d head gt content while 1 gt succ NULL amp amp 1 gt succ head 1 1 gt succ if 1 gt prev NULL printf gt d 1 gt content else printf lt gt d 1 gt content 1 gt succ NULL printf printf printf n Exercice 3 2 Construire une liste circulaire ordonn e Analyse Dans cet exercice la circularit de la liste produire est accessoire Il est naturel de penser travailler sur une
135. igne 1 SI 1 succ NULL ET 1 succ t2 ALORS longueurLin aire longLigne longueurCirculaire longueur longLigne RETOURNER longueur FINSI 123 Chapitre 3 Structures s quentielles complexes FAIT FAIT longueurlin aire longueur longueurCirculaire 0 RETOURNER longueur FIN Implantation C XX Retourne la longueur totale de la liste et pr cise en modifiant les param tres lineLength et looplength les longeurs respectives du segment amont ventuel et de la partie circulaire aval ventuelle Les valeurs possibles sont 0 0 0 liste vide 7 1 0 liste lin aire longueur p 0 p liste circulaire p rim tre on 1 p liste hegat compos e d une liste lin aire en amont et d une liste circulaire en aval int getHLength list 1 int lineLength int loopLength 124 cas de la liste vide if 1 NULL ineLength loopLength return 0 0 0 partir de l il est certain qu il existe au moins un l ment cas du sigleton circulaire if l gt succ 1 ineLength 0 loopLength 1 return 1 c est partir de l que le vrai travail commence int linel 0 la partie lin aire pr fixe mesure au moins un int length 1 on m morise la t te list head 1 tant qu il est possible d it rer sans retomber sur la t te Dunod La photocopie non autoris e est
136. ignifie d crire une m thode de raisonnement un programme qui d termine la solution d un probl me en un nombre fini d tapes de calcul il se peut que le temps n cessaire ce calcul place le r sultat final hors de port e C est ici qu interviennent les notions d quifinalit notion pr lev e sur le vocabulaire strat gique et de complexit algorithmique Une m thode de r solution n est jamais unique et les strat gies alternatives c est dire les diff rentes fa ons d aboutir au m me r sultat ne sont pas tactiquement gales Certaines sont plus 1 Notion pr lev e sur le vocabulaire cybern tique et strat gique l quifinalit traduit la possibilit pour un syst me d atteindre un m me but par diff rents chemins i e une seule strat gie le but mais plusieurs tactiques pour r aliser la strat gie Exercices et probl mes d algorithmique co teuses que d autres en termes de ressources temps en termes de ressources mn moniques mobilis es Savoir valuer avant de l ex cuter l efficacit d un algorithme chercher syst matiquement minimiser ce co t au moment de le concevoir c est assur ment ce qui pose l algorithmique comme un art COMMENT DEVENIR ALGORITHMICIEN L apprentissage traditionnel de l algorithmique lude les aspects les plus formels et sophistiqu s de la d cidabilit de la calculabilit et de la complexit qui s ils sont fondament
137. int ALORS lt l ment point ALORS ent dans le sag ent dans le sad 133 Chapitre 4 Structures arborescentes Algorithme Donn e ptr_arbre a T x R sultat de type bool en FONCTION recherche x T a ptr_arbre bool en VAR ok bool en DEBUT SI a NULL ALORS ok faux SINON SI a info x ALORS ok vrai FINSI SINON SI a info gt x ALORS recherche x a sag ok SINON recherche x a sad ok FINSI FINSI RETOURNER ok FIN Cet algorithme renvoie la premi re occurrence du terme cherch c est dire qu il ne consid re que la premi re fois o il rencontre l ment cherch Si on recherche la ni occurrence de l l ment dans l arbre il faut utiliser un compteur e Ajout d un l ment dans un ABOH Principe Placer l l ment dans l arbre en conservant l ordre et faisant le moins de r organisation possible Un ajout d l ment dans un ABOH se fait syst matiquement aux feuilles SI arbre est vide ALORS cr ation et ajout SI non vide ALORS trouver la feuille Trouver la feuille parcourir l arbre et rechercher la position de l l ment c est dire comparer l l ment ajouter la racine SI racine gt l ment ajouter ALORS ajout dans le sag donc retour en 1 avec le sag SI racine lt l ment ajouter ALORS ajout dans le sad donc retour en 1 avec le sad 134 Dunod La photocopie non autoris e est un d lit Exemp
138. int found list head newSingletonList data 0 list sl_val 1 head for i 1 i lt size i val data i found 0 sl_val newSingletonList val insertion en t te de liste if val lt 1 gt content sl_val gt succ l 1 sl_val head l else insertion en milieu de liste while 1 gt succ NULL amp amp found if val lt 1 gt succ gt content sl_val gt succ 1 1 gt succ 1 gt succ sl_val found 1 else 1 gt succ insertion en fin de liste if 1 gt succ NULL 1 gt succ sl_val concat amp head amp head return head 104 Dunod La photocopie non autoris e est un d lit e M thode r cursive Sp cification de l algorithme Corrig s des exercices Construit une liste circulaire ordonn e d entiers partir d un tableau non ordonn d entiers FONCTION newOrdoredCircListRec donn es entier size entier list VAR valeur entier trouv bool en 1 t te l_succ listed list DEBUT SI size 0 ALORS RETOURNER NULL FINSI SI size 1 ALORS listed newSingletonList donn es 0 liste0O succ listo RETOURNER liste0 FINSI appel r cursif o donn es 1 repr sente le sous tableau du tableau donn es commen ant l indice suivant on a supprim 1 lt newOrdoredCircLlistRec donn es l size 1 t te valeur donn es 0 trouv lt faux TANTQUE 1
139. int max maxOfRec succ 1 if content gt max return content return max Exercice 2 2 Concat ner deux listes Etude La contrainte d entiers positifs du premier exercice disparait mais pas le cas des listes vides Nous avons quatre cas consid rer e 1 et h vides e 1 vide mais pas b e lh vide mais pas l4 e ni J ni h vides Si h est vide on laisse l inchang e Si est vide mais pas D on affecte directement l l4 Si ni l ni h ne sont vides on parcourt jusqu sa derni re cellule et on y rattache l2 Chapitre 2 Structures s quentielles simples Figure 2 5 Concat nation standard Enfin si on va un peu trop vite dans tude on peut oublier le cas 1 J c est dire m me liste et non pas listes dont les valeurs sont gales cas particulier qui croise le premier et le dernier des quatre cas Ce cas donne une bonne illustration de la diff rence entre copies et r f rences GO Figure 2 6 Concat nation circulaire Ce dernier cas d utilisation de la fonction de concat nation revient si on l autorise transformer la liste chain e lin aire en liste cha n e circulaire Autorisons le en notant que nous avons alors un constructeur de liste circulaire par fermeture d une liste cha n e lin aire nous utiliserons cette facilit dans le probl me 3 1 probl me de Joseph Pour la concat nation une approche it rative s impose d elle m me un proc d r
140. ion blanche 1 OK une coupe a t effectu e FONCTION scinder modif 11 lo liste c crit re statut VAR p place Corrig s des exercices DEBUT c mettre_da_jour c l1 SI estvalide c ALORS RETOURNER ERR FINSI SI estvide l ALORS RETOURNER ID FINSI p t te l SI est_successeur_point_de_coupe p ALORS lo a li l RETOURNER OK FINSI TANTQUE dernier p A est_successeur_point_de_coupe succ p FAIRE p lt succ p c mettre_ ventuel lement_a_jour c FAIT SI dernier p ALORS RETOURNER ID SINON t te l succ p succ p RETOURNER OK FINSI FIN Exercice 2 11 Supprimer un sous ensemble d une liste Etude Cet exercice avec ses cing cas de figure est une extension du principe algorithmique vu dans l exercice 2 5 supprimer des l ments La fa on de d finir le crit re de s lection des n uds supprimer change selon les cas mais le sch ma g n ral ne change pas Dans tous les cas il s agit de traiter sp cialement la cha ne pr fixe de t te constitu d une succession de n uds liminer puis s il reste au moins un l ment d liminer tous les l ments r pondant au crit re et situ s au del de la t te Le cas A donne lieu une version simplifi e de l algorithme g n ral laquelle profite plein de la r gularit des intervalles de suppression e Sch ma g n ral pour les cas B E La m thode g n rale de r solution reste la m me
141. ir de n importe quel tat on peut acc der a un tat terminal Accessible coaccessible mond Un ensemble de mots X est un langage reconnaissable ssi il existe un automate fini D qui le reconna t Si X est un langage reconnaissable sur l alphabet A on peut le reconna tre avec un automate d terministe et complet car l automate D figurant dans la d finition du langage reconnaissable est toujours quivalent un automate d terministe et complet F crivant F Q i T E on a alors w X ssi i w T et donc w X ssii w GT 176 Dunod La photocopie non autoris e est un d lit 5 3 L interpr tation intuitive e Le compl ment d un langage reconnaissable Le compl ment d un langage reconnaissable l ensemble de mots sur le m me alphabet n apparte nant pas au langage en question est encore reconnaissable Soit D un automate d terministe et complet reconnaissant le langage X Pour construire un automate reconnaissant le compl ment de X il suffit de prendre comme ensemble d tats terminaux le compl ment de l ensemble d tats terminaux de D Exemple Construisons un automate sur A a b qui reconna t l ensemble des mots n ayant pas aba en facteur On commence par la construction d un automate non d terministe reconnaissant tous les mots ayant aba en facteur su Figure 5 8 Appliquons l algorithme de d terminisation Tableau 5 7 tats r sulta
142. irc Initialisation D clarations Donn e int n Donn e modifi e iste_circ 1 En t te void init liste_circ 1 Algorithme FONCTION init l liste_circ VAR i entier DEBUT POUR i DE 0 A n 1 FAIRE 1 donn el il lire lt faux j lecteur 0 1l ecrivain 0 FAIT FIN Lecture Donn e int n Donn e modifi e T elt_a_lire liste_circ 1 R sultat de type bool en En t te int lecture liste circ 1 T elt_ _ lire FONCTION lecture 1 liste circ elt_ _ lire T VAR ok bool en DEBUT SI I donn e 1 lecteurl lire faux ALORS ok faux SINON ok vrai elt_a_lire 1 donn e 1 lecteur info 1 donn e 1 1lecteur l lire faux J lecteur l lecteur 1 mod n FINSI RETOURNER ok FIN 96 Dunod La photocopie non autoris e est un d lit criture Donn e int n T elt_ecr Donn e modifi e 1iste_circ R sultat de type bool en En t te int criture T elt_ecr liste _circ 1 FONCTION criture elt_ecr T VAR ok bool en DEBUT SI I donn e 1 ecrivainl l lire vrai ALORS ok faux SINON ok vrai 1 donn el 1 ecrivainl info elt_ecr jJ donn e l ecrivain alire lt vrai l ecrivain l ecrivain 1 mod n FINSI RETOURNER ok FIN Mod le dynamique Pseudo code formel STRUCTURE elt info T lire bool en suivant elt TYPE ptr_elt elt STRUCTURE liste_circ lire ptr_elt
143. ison un en partant de un puis repli de cette liste sur elle m me gr ce au concat amp l amp 1 Figure 3 4 Liste Joseph 116 Dunod La photocopie non autoris e est un d lit Corrig s des probl mes e Phase de suppressions Suppressions jusqu puisement de la liste un nouvel ordre merge celui des liminations Appelons donc cette nouvelle liste Jos phine Figure 3 5 Liste Jos phine e Finalisation Pour la finalisation d une liste circulaire doublement cha n e reste deux puis un l ment il convient d tre prudent succ prev succ Prev 2 f succ i prev succ z ry 4 x ee x oe SUC urge lt prev prev Figure 3 6 Finalisation d une LDCC Liste doublement chain e circulaire 117 Chapitre 3 Structures s quentielles complexes Architecture fonctionnelle ys eph gt gt Pneu joseph gt gt playJoseph newJosephCList int n int k int n Pare destr gt gt Pon C gt gt removeKst malloc list pl int k size_t Aron LS joseph gt gt concat newJosephList list 11 list 12 int length int 1stVal Figure 3 7 Architecture fonctionnelle de PlayJoseph e Fonction principale Sp cification de l algorithme FONCTION playJoseph n entier k entier VAR joseph list i entier DEBUT AFFICHER Joseph pour n n et k k joseph newJosephCList n printListGraph joseph 1 i lt 2 TANTQUE joseph NULL FAIRE
144. l malloc si list 1 pl 1 gt contenu atoi 1 gt prev NULL printf Zd gt si zeof listNode affectation du contenu en pour liste doublement cha n e input ze scanf s input list prev_l while strcemp fin input 0 contenu 0 prev_l 1 1 1 gt succ it ration 1 malloc sizeof listNode allocation 1 gt contenu atoi input affectation du contenu important car la valeur par d faut n est pas forc ment NULL prev_1 gt succ l 1 gt prev prev_l en pour liste doublement chafn e printf Zd gt size scanf s input 1 gt succ NULL return size 2 Supprimer un l ment de la liste Sp cification de l algorithme supprimer un l ment d une liste FONCTION supprimer l liste lt l ment gt x VAR p prec cour VAR ok bool en DEBUT ok faux p t te l SI contenu p prec p p lt succ p ok vrai l ment bool en place x ALORS suppression du premier l ment LIBERER prec SINON prec p cour lt succ p TANTQUE ok faux A cour listevide FAIRE cour pointe sur celui supprimer prec pointe sur le pr c dent SI contenu cour x ALORS ok vrai 41 Chapitre 2 Structures s quentielles simples 42 cr ation du lien pour supprimer un l ment situ entre les deux qui sont li s succ prec su
145. l ment de la liste Exemple de d finition d une structure de pile cha n e Pseudo code formel STRUCTURE pile sommet liste nb_elt entier Implantation C typedef struct pile liste sommet int nb_elt pile 3 1 3 Manipulation d une pile Initialiser une pile juste d clar e D clarations R sultat de type pile En t te pile init Algorithme initialiser FONCTION init pile VAR p pile DEBUT p sommet NULL p nb_elt 0 RETOURNER p FIN Tester si la pile est vide D clarations Donn e pile p R sultat de type bool en En t te en C int pile vide pile p 88 Dunod La photocopie non autoris e est un d lit 3 1 Piles Algorithme pile vide FONCTION pilevide p pile bool en VAR vide bool en DEBUT SI p nb_elt 0 ALORS vide vrai SINON vide faux RETOURNER vide FIN Placer un l ment au sommet de la pile empiler D clarations Donn e T elt_ _emp Donn e modifi e pile pp En t te en C void empiler T elt_a_emp pile pp Algorithme empiler FONCTION empiler elt_a_emp T pp pile VAR courant liste DEBUT RESERVER courant courant info elt_ _emp si la pile tait vide alors sommet tait NULL et on cr e la pile courant suivant pp sommet pp sommet courant rattache ancien sommet pp nb_elt pp nb_elt 1 FIN Retirer un l ment du sommet de la pile d piler D clarations D
146. l et qu en lisant le mot w on atteint un tat terminal la fin de la lecture Le langage L reconnu par automate fini est l ensemble de tous les mots reconnus Exemple d exercice type Construire un automate fini reconnaissant les entiers crits en base deux et divisibles par trois Solution Ajout d un 0 la fin d un nombre binaire le multiplie par 2 Ajout d un 1 la fin d un nombre binaire le multiplie par 2 et lui ajoute 1 Marquant les tats par le reste de la division enti re par 3 Tableau 5 2 N N mod3 ajout d un 0 la fin reste ajout d un 1 la fin reste 3n 0 6n 0 6n 1 3 x 2n 1 1 3n 1 1 6n 2 3 x 2n 2 2 6n 3 3 x 2n 1 0 3n 2 2 6n 4 3 x 2n 1 1 1 6n 5 3 x 2n 1 2 2 Notons les tats par le reste de la division enti re par 3 On obtient Tableau 5 3 tat r sultant o NJO o NIOo Figure 5 2 En fait cet automate est bon pour reconna tre des nombres en criture binaire avec n importe quel reste de la division enti re par 3 au prix de choisir quel tat est terminal L tat terminal 0 correspond au reste 0 divisibilit par 3 l tat terminal 1 au reste 1 l tat terminal 2 au reste 2 172 Dunod La photocopie non autoris e est un d lit 5 3 L interpr tation intuitive 5 3 1 Automates d terministes On distingue des automates finis d terministes et non d terministes L automate que no
147. la notion de partitionnement de l ensemble d tats de l automate Principe Tout d abord si l automate minimiser n est pas complet il faut lui ajouter l tat poubelle pour qu il le devienne Sinon on risque de faire une erreur grave qui se manifeste facile ment au cas d un automate d terministe non complet dont tous les tats sont des tats terminaux essayez le voir vous m mes apr s avoir compris l algorithme de minimisation On s pare tous les tats de l automate d terministe initial en deux groupes terminaux et non terminaux Puis on analyse la table des transitions en marquant vers quel groupe va chaque transition On repartitionne les groupes selon les patterns des transitions en terme de groupes On r p te ce processus en utilisant cette nouvelle partition et on r it re jusqu ce qu on arrive ne plus pouvoir partitionner Les groupes restants forment l automate minimal On appelle souvent les it rations les tapes Description du processus de partitionnement it ratif Soit un automate fini d terministe complet D Q i T E R sultat obtenir Un automate fini d terministe complet D qui reconna t le m me langage que D et qui a aussi peu d tats que possible M thode Construire une partition initiale Op de l ensemble des tats avec deux groupes les tats terminaux T et les tats non terminaux Q T 178 Dunod La photocopie non autoris e est un d lit
148. le Figure 4 10 On veut ajouter 10 et 50 Figure 4 11 On veut ajouter 5 et 15 Figure 4 12 On veut ajouter 6 et 12 Figure 4 13 4 1 Arbres binaires 135 Chapitre 4 Structures arborescentes Recherche dichotomique de la position Aucune r organisation a produire on se contente d ajouter un l ment _7 En statique ajouter un l ment c est ajouter un l ment dans le tableau Algorithme en r cursif Donn e T x Donn e modifi e ptr_arbre aa FONCTION ajout x T aa arbre DEBUT SI aa NULL ALORS reserver aa aa info x aa sag NULL aa sad NULL SINON SI aa info lt x ALORS ajout x amp aa sad SINON ajout x amp aa sag FINSI FINSI FIN aa est en donn e modifi e donc on g re bien le lien avec la r cursivit 0 1 Le mode de transmission par r f rence cr e automatiquement le lien entre le p re et le fils 2 Ce qui ne marche pas q aa sad ajout x amp q Dans ce cas le lien est cass car q est une variable locale C est ce qu il ne faut surtout pas faire e Suppression d un l ment dans un ABOH L l ment est une feuille Suppression simple lib ration m moire mise jour du pointeur concern dans le p re Figure 4 14 136 Dunod La photocopie non autoris e est un d lit 4 1 Arbres binaires L l ment est le p re d un seul sous arbre Mise jour du
149. le et moins compr hensible Afin d viter cela il est possible de regrouper plusieurs conditions en une seule en utilisant d autres op rateurs logiques bool ens encore appel s connecteurs logiques Ces op rateurs permettent d effectuer des calculs avec des valeurs de type VRAI ou FAUX et de fournir un r sultat de type VRAI ou FAUX Nous en pr sentons trois nomm s ET OU et NON en indiquant simplement les r sultats qu ils produisent Ces tableaux sont nomm s tables de v rit e ET intuitivement la condition cl ET c2 est VRAI si et seulement si la condition cl est VRAI ET si la condition c2 est VRAI e OU la condition cl OU c2 est VRAI si et seulement si la condition cl est VRAI OU si la condition c2 est VRAI e NON l op rateur NON change quant lui la valeur de la condition qu il pr c de Il se note galement Tableau 1 2 Op rateur ET Op rateur OU Op rateur NON c1 c2 c1 ET c2 c1 c2 c1 OU c2 ci NON c1 FAUX FAUX FAUX FAUX FAUX FAUX FAUX VRAI FAUX VRAI FAUX FAUX VRAI VRAI Implantation C ET se note amp amp OU se note i se note 11 Chapitre 1 Les bases de la programmation 1 5 3 Iterations et boucles Certains algorithmes n cessitent de r p ter des instructions un certain nombre de fois avant d ob tenir le r sultat voulu Cette r p tition est r alis e en utilisant une structure de contr le de type it ratif nomm e boucle Il existe trois types de boucles La bou
150. le nom de la fonction et expri o i est compris entre 1 et n est une expression dont le type est celui de l entr e i Gestion des entr es les arguments Lors de l appel de la fonction une expression donnant une valeur une entr e de la fonction est appel e argument de la fonction f Retenez bien qu un argument n est pas forc ment une variable mais peut tre une expression O Dans tous ces cas l ordinateur r alise les deux tapes suivantes e Calcul de la valeur de l expression pour chacun des arguments e Transmission de cette valeur l entr e de la fonction correspondante pour que la fonction s ex cute avec les valeurs transmises Gestion de la valeur de sortie de la fonction affectation Lorsqu une fonction est appel e de cette mani re la valeur de la sortie retourn e par la fonction appel e est obtenue ainsi la valeur num rique de l expression suivant l instruction RETOURNER est calcul e puis transmise la fonction appelante Au sein de cette fonction appelante criture nom_de_fonction liste_des_arguments est en r alit une expression dont le type est celui de la sortie de la fonction qui est pr cis dans l en t te de cette derni re Il s agit donc d une valeur num rique que l on doit affecter une variable si on veut la conserver Lorsque vous voulez conserver le r sultat retourn par une fonction appel e il faut affecter ce r sultat obtenu par un ap
151. meChildren t gt sad if gcd t gt content t gt sad gt content 1 primechild newSingletonList t gt sad gt content if primechild NULL primechild gt succ sadprimechildren 159 Chapitre 4 Structures arborescentes sadprimechildren primechild return concat amp sagprimechildren amp sadprimechildren unsigned gcd unsigned numerator unsigned denominator if denominator 0 return numerator else return gcd denominator numerator denominator Pour tester Retourne un arbre parfait de profondeur p et dont les 3 valeurs vl v2 v3 initient la r currence suivante vl est la valeur de la racine v2 celle de son fils gauche v3 celle de son fils droit si un n ud a pour valeur v i alors son fils gauche a pour valeur v i 1 mod 3 et son fils droit v i 2 mod 3 tree primeChildrenTestTree unsigned p unsigned vl unsigned v2 unsigned v3 Condition d arr t tree t newSingletonTree vl if p 0 return t Sinon Pre t gt sag primeChildrenTestTree p v2 v3 vl t gt sad primeChildrenTestTree p v3 vl v2 return t void testPrimeChildren 160 printf gt gt tree prime children n tree p primeChildrenTestTree 3 1 2 3 simplePrintTreeGraph p ptest 123 list primechildren getPrimeChildren p printListGraph primechildren primec
152. ment ignor e ce qui fait que cette instruction s emploie forc ment comme derni re instruction d une fonction La seule contrainte respecter est que le type de l expression soit le m me que celui de la sortie qui est indiqu dans l en t te de la fonction Lorsqu une fonction ne poss de pas de sortie il n est pas indispensable d utiliser l instruction retourner part pour indiquer que la fonction se termine ce qui peut aussi tre rep r par le mot FIN de la fonction 1 8 2 Appel des fonctions L appel d une fonction correspond une demande de son utilisation ceci est fait dans une autre fonction dont par exemple le programme principal Afin d appeler une fonction on doit pr ciser son nom ainsi que les valeurs que l on fournit pour les entr es On ne pr cise pas la valeur de la sortie car c est la fonction appel e qui est en charge de la fournir La fonction ou programme principal qui appelle ou utilise une fonction est dite fonction appelante la fonction qui est utilis e est dite fonction appel e Exemple Soit une fonction nomm e fonc et poss dant une liste d entr es typel entreel type2 entree2 typen entreen Son en t te est donc FONCTION fonc entreel typel entree type2 entreen typen type_sortie 25 Chapitre 1 Les bases de la programmation Pour appeler cette fonction la syntaxe est la suivante fonc exprl expr2 exprn o fonc est
153. mettant de d terminer l endroit de la m moire consulter e un type Cette information de type indispensable a la d finition d un pointeur est exploit e pour savoir combien d octets doit manipuler I ordinateur lors de l acc s la m moire Les champs d une variable de type compos sont stock s les uns la suite des autres de mani re cons cutive dans la m moire cette variable forme un bloc en m moire Elle a donc une adresse comme pour les tableaux celle du d but du bloc ou plus pr cis ment une seule adresse permet de la rep rer En ce qui concerne la taille de cette variable le raisonnement est encore plus simple la taille d une variable de type structure est la somme de la taille de tous ses champs Ayant une taille fixe et calculable par la m thode expos e ci dessus et une adresse unique une variable de type structure peut tre manipul e comme un contenu et donc il est possible de d finir un pointeur vers une variable de type structure Aspects syntaxiques Les notions d adresse de valeur de contenu restent dans ce cas tout fait valides et les notations usuelles s appliquent Soit t_com un type compos une structure D finir un pointeur ptr vers un contenu de type t_com s crit donc naturellement VAR ptr t_com Pour initialiser ce pointeur ptr les r gles ne changent pas il faut lui donner une adresse valide celle d une variable existante ou l adresse d une zo
154. n pas coaccessible e D terminisation Tableau 5 25 Etat 0 1 A AB B AB ABC BC ABC ABC BC B c c a BC c On voit que C est l tat poubelle Figure 5 45 1 0 1 0 1 0 1 Corrig s des exercices Ici on a obtenu donc un automate d terministe avec poubelle Mais il y avait une poubelle d s le d but l tat C dont on ne pouvait pas revenir On aurait pu construire d abord un automate non d terministe plus simple qui reconna t le m me langage qu Ag o Q Figure 5 46 et le d terminiser En ce faisant on arrive un automate d terministe nettement plus simple que tout l heure 197 Chapitre 5 Automates Tableau 5 26 tat 0 1 A AB B AB AB B B P P P P P 1 1 Figure 5 47 Dans l exercice 10 on va voir que cet automate est en effet minimal Solution As e On ne d crit pas le langage c est trop compliqu ce stade e Il est mond e D terminisation Tableau 5 27 tat a b 0 12 P 12 12 0 b a b Figure 5 48 198 Dunod La photocopie non autoris e est un d lit Corrig s des exercices Maintenant il devient bien plus facile de d crireL As si l on veut il consiste en tous les mots commen ant par a finissant par a et o tout b est entour par des a de fa on ne jamais avoir bb Exercice 5 7 Figure 5 49 Exercice 5 8 Solution
155. n premier parcours complet de la liste Tous les cas sauf le cas E doivent int grer la possibilit d une coupure devant la t te de liste Le cas E revient quasiment au cas B apr s l identification du minimum de la liste Dans tous les cas il est pertinent de retourner un statut d ex cution qui indique si l op ration a t effective ou bien transparente auquel cas il n y a pas eu production d une seconde liste Il peut y avoir erreur si l un ou l autre des deux pointeurs sur les listes modifier est NULL ou bien dans le cas particulier du A B et C sont discutables si le pointeur donn pointe sur une autre liste Comme nous sommes scrupuleux nous indiquons galement par le statut d ex cution si la seconde liste n tait pas initialis e NULL avant l op ration effective mise en garde crasement d une ancienne valeur Implantation C Sch ma commun Donn es modifi es l la liste d entr e coup e en deux qui devient la liste amont et l2 la liste aval ventuellement produite en sortie R sulat un entier comme statut d ex cution 1 ERR ERREUR 71 Chapitre 2 Structures s quentielles simples 0 op ration blanche 1 une coupe a t effectu e 2 Statut 1 1 n tait pas nulle int cut lt Version gt plist pll plist pl2 if p11 NULL p12 NULL return ERR list 11 pll if 11 NULL return 0 on fixe le statut par d faut selon que pl
156. n qui sera traduite en d finition de variable de la mani re suivante VAR ptr entier se lisant le contenu de ptr est de type entier Puisque le contenu de ptr est de type entier il est ais d en d duire que ptr est un pointeur vers un entier Attention ce point qui ne semble pas tr s important mais qui est fondamental Il en est de m me pour les autres types point s la d finition d un pointeur nomm ptr_reel vers un r el est la suivante VAR ptr_reel r el se lisant le contenu de ptr_reel est de type reel Enfin la d finition d un pointeur nomm p_cgs vers un caract re est la suivante VAR p_cgs caractere se lisant le contenu de p_cgs est de type caractere Dans les exemples de d finition de pointeurs pr c dents la convention de nommage d un pointeur veut que son nom d bute par ptr ou p_ Cependant un pointeur tant une variable le choix de son nom n est contraint que par les r gles de nommage de variables expos es en d but de chapitre 1 7 3 Initialisation Les dangers de l op rateur Comme pour toute variable un pointeur doit tre initialis avant d tre manipul Comme un pointeur stocke une adresse il ne peut tre initialis comme une simple variable de type entier reel ou caractere car les adresses sont g r es par la machine et non par l utilisateur Acc der un contenu est une op ration d licate car elle est en relation avec la m moire
157. nc de type entier puisqu il s agit d un num ro de case La valeur stock e dans la case d indice i d un tableau tab se nomme tabli Tableau 1 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 2 7 tab 0 tab 2 tab 6 tab 14 Remarque Cette sch matisation sera employ e a de nombreuses reprises dans cet ouvrage N h sitez pas a l utiliser lors de la r solution des exercices elle aide visualiser le d roulement des algorithmes Il ne faut pas confondre la valeur not e entre crochets lors de la d finition du tableau la taille maximale et la valeur not e entre crochets lors des instructions l indice Toute expression qui donne une valeur enti re peut jouer le r le d indice lors de l acc s aux valeurs stock es dans un tableau La notation t i o t est un tableau et i un indice est quivalente une variable et peut tre utilis e comme telle dans un programme Cette variable est consid r e comme ayant le type des l ments stock s dans le tableau Soient les d finitions de variables suivantes VAR x r el VAR z r el 20 z est un tableau stockant au plus 20 r els VAR idx entier variable utilis e comme un indice 15 Chapitre 1 Les bases de la programmation Les instructions suivantes sont alors valables x 1 205E 17 z 2 x car z 2 et x sont tous deux des r els idx 4 zLidx x zLidx 2 soit z 4 x z 2 Taille utile Le fait
158. ncr te des types et des op rations qui peut tre encore un type abstrait et ceci jusqu obtenir un programme ex cutable NOTION DE STRUCTURE DE DONN ES Une structure de donn es est un ensemble organis d informations reli es logiquement ces infor mations pouvant tre trait es collectivement ou individuellement L exemple le plus simple le tableau monodimensionnel un vecteur est constitu d un certain nombre de composantes de m me type On peut effectuer des op rations sur chaque composante prise individuellement mais on dispose aussi d op rations globales portant sur le vecteur consid r comme un seul objet Exercices et probl mes d algorithmique Une structure de donn es est caract ris e par ses composantes et leur arrangement mais surtout par son mode de traitement Ainsi deux structures ayant les m mes composantes les m mes arrangements comme les PILES et FILES d ATTENTE sont consid r es comme diff rentes car leurs modes d exploitation sont fondamentalement diff rents LES BASES DE LA PROGRAMMATION 1 1 LES TYPES DE DONNEES Un type en algorithmique est une information permettant de traduire les valeurs depuis une repr sen tation binaire celle de l ordinateur vers une autre repr sentation plus adapt e leur programmation dans un langage volu Cette notion est tellement importante que toute valeur a forc ment un type Le r le du type est d assurer cette traduction
159. ne de m moire obtenue par l emploi de la r servation Acc s aux champs Comment acc der aux champs d une variable de type structure lorsque l on ne dispose que d un pointeur vers cette variable et non de sa valeur Dans ce cas la valeur de la variable n est autre que le contenu du pointeur 32 Dunod La photocopie non autoris e est un d lit 1 9 Cr ation de types par le programmeur les types compos s ou structures Exemple Soit p_tot un pointeur d fini de la mani re suivante VAR p_tot t complexe Son initialisation est la suivante RESERVER p_tot C est donc le contenu de la zone m moire point e par p_tot et not p_tot qui est de type t_complexe regardez la d finition du pointeur p_tot elle ne dit pas autre chose Il est alors possible d acc der ses champs comme pour n importe quelle autre variable de ce type l aide des notations classiques p_tot re lt une valeur p_tot im lt une valeur La notation fl che Dernier op rateur abord pour ce qui concerne les structures l op rateur n est pas propre ment parler indispensable son r le est de procurer une syntaxe plus intuitive que le couple et gt voqu dans le paragraphe pr c dent L utilisation de cet op rateur est des plus simples Exemple Soit ptr un pointeur vers une variable de type structure et soit ch un des champs de cette variable Dans ce cas deux critu
160. ne programmation d un jeu de dames utilisera donc de mani re naturelle un tableau deux dimensions une pour les lignes l autre pour les colonnes L tat de chacune des cases du damier sera stock sous la forme d un entier 1 pour vide 2 pour pion blanc etc Ainsi la d finition 17 Chapitre 1 Les bases de la programmation d un tableau dans ce cadre sera la suivante 10 lignes chaque ligne ayant 10 colonnes soit 100 cases entier damier 10 10 Cette d finition permet de simplifier la repr sentation et donc la r solution du probl me Utilisation d indices dans les tableaux deux dimensions chaque l ment du tableau est rep r par un num ro de ligne et un num ro de colonne Ainsi si 1ig et col sont deux indices donc des entiers valides compris entre 0 et 9 pour l exemple du damier damier 1ig co1 est l entier situ la ligne lig et la colonne col du tableau deux dimensions pris en exemple Attention tout de m me cet exemple les notions de ligne et colonne ne sont pas connues par l ordinateur qui ignore ce qui est fait des valeurs qu il stocke O 1 7 POINTEURS Abordons maintenant un point souvent redout tort les pointeurs Un peu de logique et de rigueur suffisent bien comprendre cette notion fondamentale Une fois de plus la notion de type sera essentielle dans cette partie 1 7 1 Notion d adresse Toute variable poss de trois caract ristiques un nom et
161. nger si on retire le ler pl pointe alors dans le vide if curr head pl curr gt succ free curr return prev gt succ liste lin aire la suite n est pas indispensable pour Joseph else tete d une lin aire if prev NULL pl curr gt succ free curr return pl else if curr gt succ NULL queue d une lin aire prev gt succ NULL free curr return NULL else milieu d une lin aire comme pour une circulaire prev gt succ Curr gt succ free curr Dunod La photocopie non autoris e est un d lit Corrig s des probl mes return prev gt succ Probl me 3 2 Mesurer la longueur d une liste de type Heqat Sp cification de l algorithme FONCTION getHLength 1 list 1 longueurLin aire entier longueurCirculaire entier entier VAR longLigne longueur entier t te t2 list DEBUT SI 1 NULL ALORS longueurLin aire 0 longueurCirculaire 0 RETOURNER 0 FINSI SI 1 succ 1 ALORS longueurLin aire 0 longueurCirculaire 1 RETOURNER 1 FINSI longLigne 0 longueur 1 t te TANTQUE 1 succ NULL ET 1 succ t te FAIRE T 1 succ longueur longueur i SI 1 succ NULL ET 1 succ t te ALORS longueurLin aire 0 longueurCirculaire longueur RETOURNER longueur FINSI t2 t te longLigne 0 TANTQUE t2 1 ET t2 succ NULL FAIRE t2 t2 succ longLigne longL
162. ngueur n ou que la premi re soit de longueur n 1 et la seconde de longueur n 46 Dunod La photocopie non autoris e est un d lit Probl me Exercice 2 11 Supprimer un sous ensemble d une liste Concevoir un algorithme qui supprime e un maillon sur deux en commen ant par la t te de liste e B les maillons contenant des l ments impairs e C les maillons contenant des l ments pairs e D les maillons contenant des l ments sup rieurs un seuil donn e E les maillons contenant des l ments inf rieurs un seuil donn d une liste simplement cha n e d entiers PROBL ME Probl me 2 1 Saisir enregistrer puis valuer un polyn me Enregistrer les coefficients et les exposants d un polyn me dans une liste cha n e valuer ce polyn me pour une valeur donn e de x Utiliser au moins deux modules dans ce programme e l un pour construire la liste sur la base des coefficients et des exposants qui sont saisis au clavier e et le second afin d valuer le polyn me pour la valeur x galement saisie au clavier Corrig s des exercices et des probl mes EN PR AMBULE Pour la r alisation en C de tous les algorithmes sp cifi s ci dessous on d finit la structure de liste chain e suivante dont on pr cisera au cas pas cas le type lt element gt Les structures utilis es pour les sp cifications des algorithmes portent le m me nom et sont construites de la m m
163. nt Etat en lisant a en lisant b initial 0 0 1 0 0 1 0 1 0 2 0 2 0 1 3 0 terminal 0 1 3 0 1 3 0 2 3 terminal 0 2 3 0 1 3 0 3 terminal 0 3 0 1 3 0 3 a a X a Figure 5 9 Cet automate d terministe et complet reconna t tous les mots ayant aba en facteur Il a trois tats terminaux 0 1 3 0 2 3 et 0 3 177 Chapitre 5 Automates Maintenant pour obtenir un automate lui aussi d terministe et complet reconnaissant tous les mots qui n ont pas aba en facteur il suffit de faire de tous les tats terminaux des tats non terminaux et vice versa b a a 9 a Qbe Figure 5 10 l tat poubelle videmment ceci n est pas toujours le cas Si on a affaire un automate non complet on n a pas le droit de remplacer directement les tats terminaux par des tats non terminaux et vice versa il faut d abord le compl ter Alors l tat poubelle qui ne peut pas tre terminal devient un tat terminal de l automate reconnaissant le compl ment du langage lci on a obtenu un automate complet sans qu il y ait besoin de le compl ter en introduisant Minimisation Pour tout langage reconnaissable il existe le plus petit c d contenant le plus petit nombre d tats automate d terministe qui le reconna t et il est unique c est l automate minimal du langage e Algorithme de minimisation par la m thode des quivalences Il est bas sur
164. nt lt 0 RETOURNER FINSI signedAverages t sag amp Sag_po_sum amp Sag_po_count amp sag_ne_sum amp sag_ne_count signedAverages t sad amp sad_po_sum amp sad_po_count amp sad_ne_sum amp sad_ne_count ppo_sum sag_po_sum sad_po_su ppo_count sag_po_count sad_po_count pne_sum sag_ne_sum sad_ne_su pne_count sag_ne_count sad_ne_count SI t content lt 0 ALORS pne_sum lt pne_sum t content pne_count lt pne_count 1 SINON ppo_sum lt ppo_sum t content ppo_count ppo_count 1 FINSI FIN e R alisation en C Une fonction principale r alise et retourne les deux moyennes en s appuyant sur une fonction r cursive secondaire qui calcule les quatre grandeurs Fonction principale simple void signedAveragesMain tree t double ppo_av double pne_av int po_sum po_count ne_sum ne_count signedAverages t amp po_sum amp po_count amp ne_sum amp ne_count ppo_av po_count 0 1 double po_sum double po_count pne_av ne_count 0 1 double ne_sum double ne_count 155 Chapitre 4 Structures arborescentes Fonction secondaire r cursive void signedAverages tree t int ppo_sum int ppo_count int pne_sum int pne_count Condition d arr t if t NULL ppo_sum ppo_count pne_sum pne_count return 0 0 0 0 Sinon int sag_po_sum sag_po_co
165. nt pas forc ment adapt es pour une application pr cise Un logiciel de gestion de compte bancaire n aura par exemple pas besoin de conna tre la taille le poids la couleur des cheveux ni le plat pr f r d une personne Pour d finir un type compos il faut en premier lieu lui choisir un nom puis dresser la liste de toutes les propri t s galement appel es champs que l on souhaite stocker l int rieur de ce type Chacun des champs est identifi par un nom ce qui permet au programmeur de le choisir parmi ceux qui sont stock s dans le type compos et d un type pour que l ordinateur sache le manipuler 29 Chapitre 1 Les bases de la programmation Par convention de nommage un nom de type compos doit syst matiquement commencer par Lis Pour d finir un type compos aussi appel structure on utilise simplement la syntaxe sui vante STRUCTURE nom_du_type nom_champ_1 type_champ_1 nom_champ_n type_champ_n Le mot STRUCTURE permet de d finir un nouveau type et non pas une variable D finition du type complexe pour repr senter un nombre complexe STRUCTURE t_complexe les d finitions de champ sont comme les d finitions de variables il est possible de les regrouper re reel im reel Une fois ce type compos d fini il est utilisable dans un programme presque au m me titre que les types de base de l algorithmique qui sont entier r el et caract re Il
166. ntre une valeur au clavier et la valide en appuyant sur la touche entr e ou enter aucun message ne s affiche pour indiquer l utilisateur ce qu il doit faire c est donc au programmeur de penser a afficher un message pour indiquer qu une saisie doit tre faite Exemple VAR a entier d finition de la variable enti re a SAISIR a saisie de la variable l utilisateur doit entrer une valeur au clavier et la valider par la touche entr e 0 Contrairement l op rateur AFFICHER on ne peut saisir que des variables avec SAISIR O Dunod La photocopie non autoris e est un d lit 1 5 STRUCTURE DE CONTR LE Les structures de contr le branchements conditionnels et boucles permettent un programme de ne pas tre purement s quentiel cha ne lin aire d instructions L exemple le plus simple traiter est celui de la r solution d une quation du second degr dans R qui a deux une ou aucune solution en fonction de la valeur des coefficients Le programme qui doit r soudre ce probl me devra donc adapter son comportement en fonction des valeurs prises par certaines variables notamment le discriminant de l quation 1 5 1 Conditions et tests Une condition est une expression dont le r sultat n est pas une valeur num rique mais VRAI ou FAUX qui sont les deux l ments de l alg bre dite bool enne ou encore logique Le calcul bool en respecte un certain nombre d
167. ode d erreur pour les cas suivants e Liste vide mais ou v non null e Liste non vide mais ou v pointant nul ou pointant un l ment n appartenant pas la liste e La fonction retournera 1 en cas d erreur O sinon Pour le reste l id e est d identifier les deux l ments et d interchanger en utilisant une variable temporaire les pointeurs de leurs pr d cesseurs respectifs et de leurs successeurs respectifs Figure 2 8 Permutation le cas g n ral Les cas suivants feront l objet d un traitement sp cial e Les pointeurs f et v sont gaux c est l op ration identit il n y a rien faire sinon ne rien faire e L un de deux pointeurs ou les deux sont respectivement t te ou queue d but ou fin de liste Les deux pointeurs identifient des places contigties cf figure 2 9 ce cas est dangereux si trait comme pr c demment Figure 2 9 avec son exception dangereuse en l absence de traitement sp cifique 56 Dunod La photocopie non autoris e est un d lit Corrig s des exercices Sp cification de l algorithme FONCTION swap modif pl list modif t v place entier VAR resultat entier term_1 term_t term_v 1 list VAR prec_t succ_t prec_v succ_v list DEBUT SI pl NULL ALORS SI t NULL ET v NULL ALORS RETOURNER 0 SINON RETOURNER 1 FINSI SINON SI t NULL OU v NULL ALORS RETOURNER 1 FINSI term_1 lt dernierElt pl
168. oeff SINON SI p exposant 1 ALORS AFFICHER p coeff x SINON AFFICHER p coeff x p exposant FINSI FINSI FINSI FIN 84 Dunod La photocopie non autoris e est un d lit Corrig du probl me Implantation C void printlerm polynomial p if p NULL return if p gt coeff 0 return if p gt coeff 1 if p gt expon 0 printf 1 else if p gt expon 1 printf X else printf X 1d p gt expon return if p gt coeff 1 if p gt expon 0 printf 1 else if p gt expon 1 printf X else printf X 1d p gt expon return if p gt coeff lt 0 if p gt expon 0 printf 4ld p gt coeff else if p gt expon 1 printf 41dX p gt coeff else printf 1dX 1d p gt coeff p gt expon else if p gt expon 0 printf 1ld p gt coeff else if p gt expon 1 printf 1dX p gt coeff else printf 1dX 1d p gt coeff p gt expon e Fonction principale saisie et valuations de polyn mes void testPolynomial printf n t t gt gt TD 1 10 Saisie et evaluation de polynomes lt lt n n int i 1 char input 10 polynomial newPolynomial printf nSouhaitez vous creer un nouveau polynome depuis la ligne de commande QUI n n printf newPolynomial d gt i scanf s input printf n 85 Chapit
169. onn e modifi e pile pp T elt_dep R sultat de type bool en En t te en C int depiler pile pp T elt_dep Algorithme d piler FONCTION depiler pp pile elt_dep T bool en VAR courant ptr_poste ok bool en DEBUT SI non pile_vide pp ALORS ok vrai elt_dep pp sommet info pp nb_elt pp nb_elt 1 lib ration de l espace m moire courant pp sommet si la pile contenait un seul l ment 89 Chapitre 3 Structures s quentielles complexes elle devient vide et pp sommet devient NULL pp sommet pp sommet suivant LIBERER courant SINON ok faux RETOURNER ok FIN 3 2 LES FILES Dans le cas d une file on fait les adjonctions une extr mit les acc s et les suppressions l autre extr mit Par analogie avec les files d attente on dit que l l ment pr sent depuis le plus longtemps est le premier on dit aussi qu il est en t te Les files sont aussi appel es FIFO pour First In First Out c est dire premier entr premier sorti Les op rations sur les files sont e tester si la file est vide e acc der au premier l ment de la file e ajouter un l ment dans la file e retirer le premier l ment de la file 3 2 1 Repr sentation contigu des files Dans ce cas on doit conserver l indice i du premier l ment et l indice j de la premi re case libre apr s la file On fait progresser ces indices modulo la taille
170. ount signedAveragesMain t amp po_av amp ne_av printf ttest positives average 4f d d po_av po_sum po_count printf negatives average 4f d d n ne_av ne sum ne count Exercice 4 9 extraire une liste d l ments d un arbre tude e Analyse Il s agit d extraire d un arbre tous les fils premiers avec leur parent pour les restituer sous forme de liste chain e Rien n indique qu il s agit d extraire une liste sans r p titions voir exemple d arbre avec rotation a trois l ments ci dessous dans la section r alisation C pour tester Nous nous proposons de r aliser un algorithme bas sur le calcul du PGCD parent enfant a l aide de l algorithme d Euclide esp rant ainsi obtenir un bonus de la part du correcteur le PGCD doit valoir 1 pour caract riser la primalit respective du parent et de l enfant Mais la simple v rification de la nullit du modulo de l un par l autre est suffisante pour d terminer cette propri t Peu importe le type de parcours choisi pr in ou post fixe l algorithme est naturellement r cursif et bas sur la fusion de proche en proche des listes d enfants premiers de chaque sous arbre les parents des feuilles retournent les premi res listes singletons lesquelles sont enrichies et concat n es l op ration de fusion au fur et mesure du d pilement de la pile d appel et finalement fusionn es en une s
171. ours a la variable found et mieux factoriser la boucle d it ration avec la forme logique quivalente suivante while 1 gt succ l_head amp amp 106 Dunod La photocopie non autoris e est un d lit Corrig s des exercices val gt 1 gt content val gt 1 gt succ gt content scan gt 1 gt succ gt content amp amp val gt 1 gt content val gt 1 gt succ gt content 1 gt content gt 1 gt succ gt content 1 1 gt succ e Pour effectuer des tests void testOrderedCirc printf gt gt ordered circular lists n int data 12 29 23 17 11 5 2 3 7 13 19 25 31 printListGraph newOrdoredCircListLRec data 12 OCL 29 31 printListGraph newOrdoredCircListLRec NULL 0 OCL CNULL printListGraph newOrdoredCircListLRec int 1 1 OCL 1 Exercice 3 3 R aliser le chainage arri re d une liste doublement chain e Sp cification de l algorithme FONCTION doubleChain 1 list VAR t te list DEBUT SI 1 NULL ALORS RETOURNER ceci termine la fonction FINSI t te TANTQUE 1 succ NULL ET 1 succ t te FAIRE SI 1 succ prev NULL ALORS succ prev lt FINSI TT 1 succ FAIT SI 1 succ NULL ALORS t te prev 107 Chapitre 3 Structures s quentielles complexes FINSI RETOURNER FIN Implantation C void doubleChain list 1 if 1
172. pe pointeur n existe pas en tant que tel Il 19 Chapitre 1 Les bases de la programmation est n cessaire d ajouter des informations suppl mentaires afin que l ordinateur puisse exploiter correctement ces pointeurs En r alit un pointeur a besoin d informations sur son contenu sinon il ne peut rien en faire La valeur d un pointeur n est qu une adresse mais cette information n est pas suffisante pour g rer les contenus possibles Les diff rents types d j voqu s auparavant entier reel et caractere ont des tailles diff rentes un entier occupe quatre octets ou cellules un r el en occupe huit et un caract re un seul Lorsque l ordinateur cherche acc der au contenu d un pointeur en m moire il doit savoir combien de cellules seront concern es par cette op ration Le type de contenu encore appel type point est indispensable la d finition d un pointeur Il lui est m me tellement li qu un pointeur ne peut pointer qu un seul type de contenu Il n existe donc pas de pointeur g n rique vers n importe quel type de contenu mais des pointeurs sur ou vers des entier des pointeurs sur des reel des pointeurs vers des caractere Un pointeur se d finit par le type de son contenu Pour la cr ation d un pointeur nomm ptr qui pointe sur des entiers sa d finition s crit le contenu de ptr est de type entier En langage informatique c est cette notatio
173. pel dans une variable du m me type que celui de la sortie de la fonction appel e Le passage des param tres Nous allons tudier dans cette partie le m canisme de passage des param tres qui est un point fondamental concernant les fonctions Nous allons voir en d tail la mani re dont se fait la commu nication entre les arguments fournis par la fonction appelante et les param tres ou entr es re us par la fonction appel e Ce passage de param tre est effectu chaque appel d une fonction Le m canisme de recopie Les actions effectu es par l ordinateur lors du passage des param tres transmission de la valeur des arguments au moment d un appel de fonction sont les suivantes e les valeurs des arguments sont calcul es ou valu es 26 1 8 Les sous programmes ou fonctions e ces valeurs sont recopi es dans les param tres correspondants de la fonction l ordre de recopie est celui dans lequel les entr es ou param tres de la fonction sont crits dans l en t te de la fonction l argument 1 dans le param tre 1 et ainsi de suite e la fonction est ex cut e et r alise ses calculs et instructions e instruction RETOURNER est ex cut e l expression contr l e par cette instruction est valu e et retourn e au surprogramme qui a appel cette fonction en tant que sous programme Int grit des variables locales Les variables locales un programme ou une fonction ne peuvent pas
174. peut commencer if t v return 0 identit tout va bien 58 Dunod La photocopie non autoris e est un d lit Corrig s des exercices note le cas du singleton est implicitement d j trait on travaille maintenant sur une liste 1 multiple Sinon cas g n ral list 1 pl list prec_t succ_t getPrecAndSucc l t amp prec_t amp succ_t 1 pl list prec_v succ_v getPrecAndSucc 1 v amp prec_v amp Succ_v cas de contig it gt v J gt t gt ou gt t gt v gt if prec_v t prec_t v cas gt t gt v gt gt gt v gt t gt if prec_v t cas gt t gt gt v vs autres cas if prec_t NULL printf case gt t gt Lv gt gt gt LEv gt t gt n pl v else printf case gt t gt Lv gt gt C 1 gt CvI gt Ct gt n prec_t gt succ v v gt succ t t gt succ SUCC_V Ii cas 2 SvJ LEI gt gt ALEJ y else cas gt v gt gt t vs autres cas if prec_v NULL printf case gt v gt t gt gt t gt v gt n pl t else printf case J gt v gt t gt gt gt 0t gt fv gt n prec_v gt succ t 59 Chapitre 2 Structures s quentielles simples t gt succ V v gt succ SUCC_t cas gt v gt gt t gt ou gt t gt gt v gt else
175. pile Sp cification de l algorithme FONCTION triangularSum n entier entier VAR valeur r sultat entier p pile DEBUT SI n 0 ALORS RETOURNER 0 FINSI p initPile valeur n r sultat 0 FAIRE les valeurs sont mises sur la pile empil es empiler valeur amp p valeur valeur 1 TANTQUE valeur gt 0 111 Chapitre 3 Structures s quentielles complexes FAIRE puis les valeurs sont sorties de la pile d pil es depiler amp val amp p r sultat r sultat valeur TANTQUE estPileVide p RETOURNER res FIN Implantation C int triangularSum unsigned n if n 0 return 0 pile p initPile int val n int res 0 do empiler val amp p while val gt 0 do depiler amp val amp p res val while estPileVide p return res Exercice 3 6 Ins rer et supprimer dans une liste doublement chain e tude On proc de de la m me mani re que pour le cas d une liste simplement chain e ceci pr s que P algorithme est plus simple En effet le probl me pour une liste simplement chain e consiste rep rer le pr d cesseur direct du point d insertion ou d limination et implique donc un parcours lin aire en repartant de la t te Dans le cas d une liste doublement chain e on dispose d un acc s direct sur l l ment pr c dent de la cha ne liminant ainsi cette difficult Pour le reste il s agit de mettre jour les pr d
176. plicite d auto mates asynchrones Dans tous les exemples que nous allons traiter jusque ce point l on pourra donc d finir l ensemble E comme faisant partie de Q x A x Q 5 3 L INTERPR TATION INTUITIVE chaque instant l automate se trouve dans l un des tats p de l ensemble d tats Q Il lit alors l une des lettres a de l alphabet A la lettre suivant du mot qui vient l entr e et passe dans un tat q tel que p a q soit une fl che Exemple P A a b Q 0 1 2 3 4 I 0 T 4 Figure 5 1 170 Dunod La photocopie non autoris e est un d lit 5 3 L interpr tation intuitive La lecture du mot w se termine dans l tat 4 ssi w se termine par abaa Le m me automate peut tre repr sent par une table de transitions Tableau 5 1 Eat tat r sultant en lisant a en lisant b entr e 0 1 0 1 1 2 2 3 0 3 4 2 sortie 4 1 2 Remarque Si vous regardez cet automate de pr s vous verrez que nous avons libell les tats de telle fa on que l automate se trouve dans l tat num ro i ssi le plus long suffixe du mot d j lu qui est en m me temps un pr fixe de abaa est de longueur i On peut montrer que cet automate r alise de fa on optimale l algorithme de recherche de la s quence abaa dans un texte il r sout pour ce mot l algorithme du string matching utilis par exemple dans les diteurs de textes La lecture
177. pointeur concern dans le p re de l l ment supprim avec l adresse du sous arbre de l l ment supprim Figure 4 15 L l ment deux sous arbres Figure 4 16 On veut supprimer le 8 Rechercher le plus grand du sag ou le plus petit du sad Recopier sa valeur la place de 1 l ment supprimer Supprimer le plus grand du sag ou le plus petit du sad par la m thode 1 ou 2 feuille ou un seul sous arbre Principe Si l arbre est vide retourner faux Si l information est plus petite l l ment retour en 1 avec le sad Si l information est plus grande l l ment retour en 1 avec le sag 137 Chapitre 4 Structures arborescentes Si info l ment on a trouv l l ment supprimer Ni sag ni sad gt lib ration et retour avec vrai sad et non sag ou sag et non sad gt mise a jour du p re lib ration et retour avec vrai sag et sad recherche du plus petit l ment dans le sad remplacement d l ment par le plus petit suppression du plus petit avec a ou b Dretour avec vrai Algorithmes sur l quilibre des arbres binaires D s quilibre possible d un ABOH Figure 4 17 Arbre totalement d s quilibr Si un arbre est d s quilibr ses performances sont instables Les performances d pendent de la fa on d entrer les informations La recherche n est plus r ellement dichotomique dans un arbre d s quilibr e D finition d un arbre quilibr
178. pty succ 1 FIN 48 Dunod La photocopie non autoris e est un d lit Corrig s des exercices Enfin le constructeur suivant pourra vous aider simplifier vos critures pour l allocation d un nouveau n ud de liste list newSingletonList int content list 1 malloc sizeof listNode allocation m moire 1 gt content content affectation du contenu 1 gt succ NULL return l Et son quivalent en pseudo langage FONCTION newSingletonList content entier list VAR nouveau list DEBUT RESERVER nouveau nouveau content content nouveau succ NULL RETOURNER nouveau FIN CORRIGES DES EXERCICES Exercice 2 1 Rechercher l lement maximal d une liste Sp cification de l algorithme it ratif C est une simple adaptation de l algorithme recherche b du rappel de cours vu plus haut Entr e liste de positifs non vide Sortie un positif FONCTION maxOf 1 liste lt positif gt positif VAR max positif p place DEBUT p t te 1 max lt contenu p TANTQUE dernier p FAIRE p succ p SI contenu p gt max ALORS max lt contenu p FINSI FAIT RETOURNER max FIN 49 Chapitre 2 Structures s quentielles simples R alisation en C de l algorithme it ratif Ici le champ content est de type unsigned int maxOf list lt unsigned gt 1 if 1 NULL return ERR int max 1 gt content valeur en premi re place while 1 gt succ NUL
179. que de votre vie la lecture du premier chapitre vous sera n cessaire Sinon elle n est pas indispensable sauf ventuellement comme r f rence pour le langage algorithmique utilis dans les corrig s Si vous d marrez avec quelques notions de programmation les deux chapitres sur les structures s quentielles et arborescentes vous donneront les bases n cessaires pour raisonner en termes algorithmiques et aborder par la suite des structures et algorithmes plus complexes b tis sur ces l ments de bases Enfin quel que soit votre niveau le dernier chapitre sur les automates vous sensibilisera sur les fondements math matiques de l algorithmique notamment des logiques d ex cution Avec les structures s quentielles et les approches it ratives les structures arborescentes et les approches r cursives et enfin avec les automates et les logiques g n rales d ex cution vous munirez votre arc de trois cordes essentielles pour aborder la suite de votre apprentissage x A PROPOS DES AUTEURS e Nicolas Flasque Ing nieur HE depuis 1992 et docteur en informatique depuis 2001 Apr s avoir travaill une ann e en tant que responsable logiciel sur les systemes embarqu s automobiles il reprend ses tudes et obtient un doctorat de l universit de Caen sur la reconnaissance de vaisseaux sanguins pour l imagerie m dicale En poste l EFREI depuis septembre 2001 il enseigne l algorithmique ainsi que la programmation d
180. qui est une ressource indispensable au fonctionnement de l ordinateur Chaque programme y stocke les valeurs dont il a besoin pour s ex cuter correctement tant donn qu un ordinateur de type PC classique fait cohabiter plusieurs dizaines de programmes diff rents au m me instant il doit d l guer la gestion de la m moire un programme particulier nomm le syst me d exploitation Le r le de ce dernier est de veiller au bon fonctionnement de la partie hardware de l ordinateur partie qui concerne la m moire 20 1 7 Pointeurs En imaginant qu un pointeur puisse stocker n importe quelle valeur acc der au contenu se r v lerait particuli rement dangereux pour la stabilit du syst me Un simple exemple devrait vous en convaincre Exemple Soient la d finition et l initialisation de pointeur suivantes VAR ptr entier lire le contenu de ptr est de type entier ptr lt 98120 initialisation de la valeur du pointeur ptr donne acc s la valeur de ptr ptr 74 initialisation du contenu du pointeur ptr ptr est le contenu de ptr Ces simples instructions permettraient au programme d crire une valeur arbitraire n importe quelle adresse de la m moire de l ordinateur ce qui n est pas du go t du syst me d exploitation Dans le cas d un acc s une adresse non autoris e ce dernier met une fin brutale l ex cution du programme responsable de cet acc s c est une des
181. r parent ne divise pas Citez au moins deux fa ons de construire des arbres pour lesquels cet algorithme retourne n cessai rement la liste de tous ses l ments x Exercice 4 10 Produire des coupes transversales d un arbre Coupe transversale d un arbre sur un niveau donn restitu e sous forme de liste crire un algorithme qui retourne la coupe transversale PROBL MES RER Probl me 4 1 Le triangle Chinois de Pascal Isaac Newton a donn une formule g n rale du d veloppement de la puissance ni d un bin me n oy Sy cay k 0 n o C i le coefficient binomial alternativement d not par se calcule par la formule n ck c klin k n En combinatoire Os d compte le nombre de combinaisons de k l ments parmi n Le triangle de Pascal ou triangle arithm tique Chinois date du XIII si cle et n a donc pas t invent par notre Blaise national Vous avez certainement d j rencontr cet objet math matique qui exploite une m thode de construc tion par r currence pour produire un arrangement g om trique arborescent des coefficients bino miaux En effet 1l est trivial de constater que ck SC pe 1 Cs avec pour chaque ligne 0 n Om on I et en particulier pour la premi re 0 o Y o A g Il vous est demand de r aliser l algorithme it ratif qui construit le triangle sous forme d un arbre binaire non quilibr jusqu un niveau de profondeur n
182. r qo qm Figure 5 16 e Le nombre de s transitions droite ou gauche de la transition p qo peut tre nul dans ce cas Pn PoOU Pn po 183 Chapitre 5 Automates Exemple a Prenons un automate asynchrone O o o Ici suivant le raisonnement pr c dent il existent les chemins lal 1a2 1b2 1c3 2b2 2c3 b Donc cet automate est quivalent l automate non d terministe suivant Figure 5 17 A1 Figure 5 18 A2 c Maintenant on peut le d terminiser Tableau 5 13 Etats r sultant Etat en lisant a en lisant b en lisant c 1 1 2 2 3 1 2 1 2 2 3 2 2 3 3 a c b c Figure 5 19 A3 184 Dunod La photocopie non autoris e est un d lit 5 3 L interpr tation intuitive ou bien en ajoutant l tat poubelle Tableau 5 14 tats r sultant en lisant a en lisant b en lisant c C b a b c b c a b a b c d Mais en r alit il est plus simple de se passer de l tape b et construire un automate d terministe directement partir d un automate asynchrone Redessinons l automate Al a b L tat initial de automate d terministe correspondant AT est 1 2 car en lisant le mot vide on arrive et en 1 et en 2 Continuons a d terminiser en marquant dans les colonnes correspondant la lecture de chaque caract re tous les tats o on arrive apr s la lecture du caract re en ques
183. raison ne connaissent ni leur nom ni leur type ni leur valeur ni leur adresse Elles ne peuvent les utiliser Les entr es de la fonction pr cis es dans l en t te sont galement consid r es comme des variables locales de la fonction c est pour cela que la syntaxe d criture des entr es est si proche de la syntaxe d une d finition de variable Enfin les d finitions des variables locales la fonction suivent exactement les m mes r gles que celles que nous avons d j rencontr es pour les d finitions de variables d un programme e L instruction de retour Pour traiter int gralement les fonctions nous avons besoin d une nouvelle instruction permettant que la fonction communique sa sortie la fonction qui l utilise La sortie d une fonction il y en a au maximum une est en fait une valeur num rique que celle ci fournit et la seule information n cessaire la bonne interpr tation de cette valeur num rique est son type c est pourquoi on ne pr cise que le type de cette sortie il est inutile de lui associer un nom Il nous faudrait donc une instruction dont l effet serait r pondre la fonction appelante la valeur qu elle demande Cette instruction existe son nom est RETOURNER Exemple Syntaxe RETOURNER expression Effet transmet la valeur de l expression et met fin l ex cution de la fonction Toute instruction plac e apr s l instruction RETOURNER est purement et simple
184. re 2 Structures s quentielles simples while stremp OUI input 0 recordPol ynomial amp newPolynomial printf Le polynome saisi est printPolynomial newPolynomial printf n testEvalPolynomial newPolynomial printf nSouhaitez vous creer un nouveau polynome depuis la ligne de commande OUI n n printf newPolynomial d gt i scanf s input printf n e Fonction principale d l gu e valuations d un polyn me void testEvalPolynomial polynomial p int i 1 char input 10 long x printf nSouhaitez vous evaluer le polynome pour une nouvelle valeur de x OUI n n printf eval d gt i scanf s input printf n while stremp OUI input 0 printf x d gt i scanf s input printf n x atol input long result evalPolynomial p x printPolynomial p printf x 41d gt amp 4ld n x result i printf nSouhaitez vous evaluer le polynome pour une nouvelle valeur de x OUI n n printf eval d gt i scanf s input printf n 86 STRUCTURES SEQUENTIELLES COMPLEXES RAPPELS DE COURS 3 1 PILES Pour beaucoup d applications les seules op rations a effectuer sur les listes sont des insertions et des suppressions aux extr mit s Dans les piles les insertions et les suppressions se font une seule extr mit appel e sommet de pile Les piles sont aussi appel
185. re d arbre binaire suivante dont on pr cisera au cas pas cas le type lt element gt prototype Pseudo code formel STRUCTURE treeNode content lt l ment gt sag sad treeNode TYPE tree treeNode TYPE ptree tree Implantation en C typedef struct treeNode lt l ment gt content struct treeNode sag sad treeNode typedef treeNode tree typedef tree ptree Qelques fonctions utilitaires facultatives pour am liorer la lisibilit algorithmique de vos impl mentations tree newSingletonTree unsigned content tree t malloc sizeof treeNode allocation m moire t gt content content affectation du contenu 146 Dunod La photocopie non autoris e est un d lit Corrig s des exercices t gt sag NULL t gt sad NULL return t int isEmptyTree tree t return t NULL int isSingletonTree tree t return isEmptyTree t gt sag amp amp isEmptyTree t gt sad La structure de liste simplement cha n e du second chapitre et en particulier la fonction concat de l exercice 2 2 sont r guli rement r utilis es CORRIG S DES EXERCICES Exercice 4 1 traiter un arbre en post ordre tude Il s agit d une application directe des rappels de cours Pour rester g n rique nous interpr tons l nonc en retournant une liste cha n e des l ments de l arbre ordonn s en post ordre Cette liste peut ensuite faire l objet de tout traitement
186. res sont quivalentes ptr ch lt ptr ch Ainsi l exemple pr c dent peut tre crit p_tot im une valeur p_tot im une valeur 1 9 6 Types pointeurs et raccourcis de notation Il est parfois pratique de disposer d un nom de type raccourci pour d signer un pointeur vers une structure Ce nom raccourci de type se d finit avec la syntaxe suivante TYPE type_pointeur type Exemple TYPE ptr_comp t_complexe Le raccourci de type pr c dent signifie que le type ptr_comp d signe un pointeur vers un t_complexe Ainsi les deux d finitions de variables suivantes sont quivalentes VAR pz t_complexe VAR pz ptr_comp Dans les deux cas la variable pz stocke l adresse d une valeur de type t_complexe 33 Chapitre 1 Les bases de la programmation 1 9 7 Structures et fonctions Passage de param tres de type compos Les structures se comportent comme les autres types en ce qui concerne les fonctions il est possible de sp cifier des entr es dont les types sont des structures auquel cas le m canisme de passage de param tre reste valable La diff rence r side dans le fait que plusieurs valeurs num riques doivent tre transmises entre l argument et le param tre Pour r aliser cette transmission c est en r alit l op rateur d affectation qui sera employ pour recopier la valeur de l argument expression dans le param tre correspondant Param tres adresses de struct
187. retourn e par une fonction sont les suivantes ce sont des r gles de programmation respecter de fa on tr s stricte e une fonction ne doit jamais retourner l adresse d un de ses param tres e une fonction ne doit jamais retourner l adresse d une de ses variables locales e une fonction ne doit jamais retourner un tableau statique local d fini dans la fonction e une fonction peut retourner une allocation obtenue par la fonction RESERVER 1 9 CR ATION DE TYPES PAR LE PROGRAMMEUR LES TYPES COMPOSES OU STRUCTURES A l instar des tableaux permettant de regrouper des variables de m me type il existe la possibilit de regrouper des variables de types quelconques au sein de types cr es par le programmeur en fonction de ses besoins En effet les types de base que sont r el entier caract re et pointeur adresses sont souvent tr s limitatifs lorsque le programmeur souhaite d velopper des applications professionnelles Sans entrer dans les d tails de l utilisation pr cise de ces nouveaux types il est possible de dire que ces types sont issus d un travail de mod lisation travail dont le but est de choisir pour un objet du monde r el qui doit tre manipul dans une application informatique la liste des propri t s valeurs qui vont repr senter cet objet Exemple L objet personne du monde r el poss de norm ment de propri t s vous pourriez en dresser une liste tr s longue mais toutes ne so
188. roches sont possibles selon que e On travaille partir de la liste de d part en la pr servant copie des l ments ou bien en recyclant ses cellules r utilisation des l ments e On r alise une seule fonction complexe qui produit simultan ment les deux listes ou bien deux fonctions simples sp cialis es appel es successivement e On labore une structure complexe nouvelle pour combiner les deux listes produites dans l unique sortie de la fonction ou bien on passe deux pointeurs respectivement sur les deux listes pointeurs sur pointeurs initialement non initialis s param tres inout ja Figure 2 7 D construction d une liste avec reconstruction sous forme de deux listes Nous nous proposons d utiliser le m me algorithme it ratif pour r aliser l op ration que ce soit par copie ou par r f rence Cet algorithme consiste parcourir la liste de d part et aiguiller chaque nouvel l ment rencontr vers l une ou l autre des deux listes selon sa valeur en les compl tant ainsi progressivement jusqu puisement de la liste de d part Il existe d autres solutions Sp cification de l algorithme Entr es modifi es e La liste d entier initiale e Les deux listes d entiers produites FONCTION separer lo 11 lo liste lt entier gt VAR Po Pi pz place DEBUT SI estvide lg ALORS Po t te lo SI contenu po 2 0 ALORS p t te 1 t te lo SINON po t te l
189. ruction du langage e La d sallocation est galement effectu e par l interm diaire d une instruction e Il n est donc pas n cessaire de r server d s la compilation tout un espace m moire e On utilise la place juste lorsqu on en a besoin puis on peut la r utiliser par autre chose Exemples Les exemples sont toujours donn s en langage algorithmique Les donn es les donn es modifi es et les sorties sont syst matiquement pr cis es en pr ambule des d clarations titre d illustration une r alisation ou implantation ou impl mentation est donn e en C99 pour chacun des types abstraits et algorithmes propos s 37 Chapitre 2 Structures s quentielles simples 38 D finition d une structure de liste simplement chain e Pseudo code formel STRUCTURE place info T suiv place TYPE list place Implantation C typedef struct place lt type gt content struct place succ place typedef place list Tester la pr sence d un l ment dans une liste chain e Sp cification de l algorithme recherche a FONCTION recherche l liste lt l ment gt x l ment bool en VAR trouve bool en p place DEBUT trouve faux SI estvide 1 ALORS p t te l TANTQUE dernier p A trouve faux FAIRE SI contenu p x ALORS trouve vrai SINON p succ p it ration vers la cellule suivante FINSI FAIT SI contenu p x ET trouve faux ALORS trouve vrai FINSI FINSI
190. s les tats 0 1 de l automate initial Pour automate d terministe on les regroupe dans l tat qu on appelle 0 1 En b on va vers l tat 0 de l automate initial Donc 0 est lui aussi un tat de l automate d terminis Chaque fois qu on obtient un tat de l automate d terminis on le met dans la colonne de gauche pour agir sur cet tat par les lettres de l alphabet Ainsi on obtient la deuxi me ligne o figure un nouvel tat 0 2 On proc de ainsi tant qu il y reste des tats non trait s Les tats finaux sont ceux qui contiennent un tat final de l automate initial Dans notre cas il n y enaqu un 0 1 4 174 5 3 L interpr tation intuitive b b Figure 5 5 Automate d terminis Voici l automate d terminis La d monstration montrant que et C reconnaissent le m me langage se fait par r currence Un automate d terministe peut tre ou ne pas tre complet Automate d terministe complet d finition Pour Vu P et Va A 3v E P tel que u a v C est a dire que de chaque tat sortent des fl ches avec toutes les tiquettes possibles L automate D de l exemple pr c dent est un automate complet N importe quel automate non d terministe est quivalent 4 un automate d terministe et complet il suffit dans l automate d terminis d introduire un tat poubelle s il n est pas d j complet
191. s r els dans cet exemple 23 Chapitre 1 Les bases de la programmation La fonction propos e en exemple a comme entr es deux valeurs de type r el effectue un calcul et a comme sortie une valeur de type r el 1 8 1 D finition d une fonction Comme de nombreuses entit s en informatique une fonction doit tre d finie avant d tre utilis e c est dire que l on doit indiquer quelles sont les instructions qui la composent il s agit de la d finition de la fonction o l on associe les instructions l identification de la fonction On doit donc trouver une d finition de la fonction qui comporte e Une identification ou en t te de la fonction suivie des instructions de la fonction ou corps de la fonction La fonction doit tre d finie et comporter un en t te pour l identifier et un corps contenant ses instructions pour la d finir Comment crire une d finition de fonction e En t te L en t te d une fonction contient les informations n cessaires pour identifier la fonction son nom ses entr es et leur type le type de sa sortie sans la nommer car c est inutile Syntaxe de l en t te FONCTION nom liste entr es avec leurs types type de la sortie La liste des entr es avec leur type suit exactement la m me syntaxe que les d finitions de variables et ceci n est pas un simple hasard car les entr es sont des variables de la fonction La seule diff rence r si
192. s sa saisie et avant son emploi pour des valuations optimisation e La structure de donn e Pseudo code formel STRUCTURE terme coeff r el exposant entier suivant terme TYPE polynome terme Implantation C typedef struct term long int coeff intervalle 2 147 483 648 2 147 483 647 long int expon struct term nextTerm term typedef term polynomial e Saisie du polyn me Implantation C Fonction d riv e de la fonction constr newListFromStandardInput list pl int void recordPolynomial polynomial pp pp NULL int size 1 char coeffStr 11 80 Dunod La photocopie non autoris e est un d lit Corrig du probl me char exponStr 11 printf Saisissez une serie de coefficient et exposants n printf puis terminez votre saisie par le coeff fin n printf coeff d gt size scanf s coeffStr if stremp fin coeffStr 0 return printf expon d gt size scanf s exponStr Size pp malloc sizeof term allocation et rattachement t te polynomial p pp p gt coeff atol coeffStr p gt expon atol exponStr p gt nextTerm NULL printf coeff d gt size scanf s coeffStr if stremp fin coeffStr 0 return polynomial prev_p while stremp fin coeffStr 0 prev_p p p p gt nextTerm it ration printf expon d gt size scanf s exponStr Siz
193. sents pour indiquer que le type de l entr e est un tableau contenant des valeurs d un certain type Lorsque l on voudra traiter les valeurs stock es dans ce tableau il faudra par contre avoir une information concernant la taille utile de ce tableau il faudra donc associer syst matiquement cette entr e une entr e de type tableau N oubliez pas que m me si la taille utile est d finie dans le programme principal ou dans une autre fonction que celle qui traite le tableau cette taille utile sera stock e dans une variable laquelle la fonction ne pourra pas acc der Il faudra donc la lui transmettre Appel d une fonction avec un argument de type tableau Lorsqu un tableau est utilis comme un argument il est inutile d utiliser la notation avec les crochets En effet ces crochets sont utilis s pour d finir le tableau ou pour acc der un l ment 27 Chapitre 1 Les bases de la programmation particulier stock dans le tableau Le tableau lui m me c est dire l adresse laquelle sont stock es les valeurs est rep r par son nom sans les crochets Exemple Soit la d finition suivante tab_car caractere 20 cela indique que tab_car est un tableau contenant au plus 20 caract res Donc tab_car est de type tableau de caractere ou encore pointeur vers des caract res tab_car est une adresse Lorsque l on veut fournir une fonction un argument qui est un tableau on doit lui fo
194. simples guillemets Ces simples guillemets se lisent alors code ASCII de Exemple de programme d affectation programme affectations VAR a entier VAR x r el VAR ma_var caract re a 6 Chapitre 1 Les bases de la programmation x 6 022E 23 Ma_var Y quivaut ma_var 101 car le code ASCII de Y vaut 101 1 4 3 Op rateurs arithm tiques et expressions Il est galement int ressant de pouvoir effectuer des calculs et d en affecter le r sultat une variable Nous retrouvons sans surprise les op rateurs arithm tiques les plus classiques e Addition e Soustraction e Multiplication e Division e Modulo Ces op rateurs agissent avec des constantes et ou des variables dont la valeur est utilis e pour le calcul a effectuer Avec ces op rateurs les variables et les constantes il est possible d crire ce que l on appelle des expressions une expression est une suite d op rateurs et de termes qui est compr hensible et que l on peut calculer x 3 2 4 x 7 est une expression car on peut appliquer les op rations mais 2 5 x 8 9 n est pas une expression bien que tout ce qui la compose soit des op rations des termes et des parenth ses Lors du traitement de l affectation g n rique variable expression l ordinateur calcule dans un premier temps la valeur num rique de l expression fournie droite de l op rateur d affectation
195. spectivement positifs et n gatifs de arbre e Sp cification de l algorithme Fonction principale simple XX Retourne la moyenne des l ments positifs et celle des l ments n gatifs d un arbre d entiers Si l arbre est vide ppo_av et pne av sont fix s 1 Sinon retour respectif des deux moyennes en valeur absolue FONCTION signedAveragesMain t tree ppo_av r el pne_av r el VAR po_sum po_count ne_sum ne_count entier DEBUT signedAverages t amp po_sum amp po_count amp ne_sum amp ne_count SI po_count 0 ALORS ppo_av lt 1 SINON ppo_av po_sum po_count FINSI SI ne_count 0 ALORS pone_av 1 SINON pne_av ne_sum ne_count FINSI FIN Fonction secondaire r cursive ae Fonction priv e r cursive qui calcule respectivement les sommes et comptes de positifs et n gatifs ppo_sum somme des positifs ppo_count nombre de positifs pne_sum somme des n gatifs pne_count nombre de n gatifs 154 Dunod La photocopie non autoris e est un d lit Corrig s des exercices FONCTION signedAverages t tree ppo_sum entier ppo_count entier pne_sum entier pne_ count entier VAR sag_po_sum sag_po_ count sag_ne_ sum sag_ne_count entier VAR sad_po_sum sad_po_ count sad_ne_ sum sad_ne_count entier DEBUT Condition d arr t SI t NULL ALORS ppo_sum 0 ppo_count lt 0 pne_sum 0 pne_cou
196. succ t te ET trouv SI 1 content gt 1l succ content ALORS la premi re case du tableau faux FAIRE SI val gt l content OU val gt 1 succ content ALORS trouv vrai SINON lt I succ FINSI SINON SI val gt l content ET val gt 1 succ content ALORS trouv lt vrai SINON TT I succ FINSI FINSI FAIT 1_succ succ succ newSingletonList donn es 0 l succ succ 1_succ 1 lt 1 succ RETOURNER 1 FIN 105 Chapitre 3 Structures s quentielles complexes Implantation C Construit une liste circulaire ordonn e d entiers partir d un tableau non ordonn d entiers list newOrdoredCircListRec int data unsigned size if size 0 return NULL if size 1 list 10 newSingletonList dataL0 10 gt succ 10 return 10 list 1 newOrdoredCircListRec data 1 size 1 list l_head 1 int val data 0 int found 0 while 1 gt succ 1 _ head amp amp found if 1 gt content gt 1 gt succ gt content if val gt 1 gt content val gt 1 gt succ gt content found else 1 1 gt succ else if val gt 1 gt content amp amp val gt 1 gt succ gt content found else 1 1 gt succ list 1 succ 1 gt succ 1 gt succ newSingletonList data 0 1 gt succ gt succ _sSucc 1 gt succ return 1 Remarque On peut liminer le rec
197. t ration de la liste 1 gt succ pl Exercice 2 9 Effectuer et retourner deux calculs sur une liste tude Il s agit de parcourir la liste et de faire le produit d une part les entiers positifs et d autre part celui des entiers n gatifs La pr sence ventuelle du 0 qui selon le statut qu on lui donne est un positif ou non positifs strictement ou non peut poser un probl me d interpr tation de l nonc Le minimum est d en parler Disons pour ce corrig qu il n est ni positif ni n gatif et qu il doit donc ne pas intervenir dans aucun produit qu il annulerait Les cas sp ciaux sont les suivants e Liste vide ou ne contenant que des z ros le r sultat est ind termin e Absence de positifs ou exclusif absence de n gatifs le r sultat est partiellement ind termin 68 Dunod La photocopie non autoris e est un d lit Corrig s des exercices La difficult de cet exercice tient galement au probl me du double r sultat qu il s agit de retourner Plusieurs solutions sont possibles la plus simple consistant utiliser deux entr es modifi es On utilisera un code de statut pour rendre compte des r sultats sp ciaux vs standard dont les valeurs signifient les configurations suivantes e 4 au moins un positif et au moins un n gatif e 2 au moins un positif mais aucun n gatif e 1 au moins un n gatif mais aucun positif e 0 ni n gatif ni positif liste vide ou
198. t simplement adresse de et pr c de uniquement un nom de variable Exemple Soit la d finition de variable suivante VAR x r el Cette simple d finition attribue la variable un nom x un type r el une valeur inconnue et galement une adresse de mani re automatique 18 1 7 Pointeurs La notation amp x signifie donc adresse de x La valeur pr cise de cette adresse ne nous est en r alit d aucun int r t mais il sera parfois n cessaire de la manipuler Toute variable poss de une et une seule adresse _ Dunod La photocopie non autoris e est un d lit 1 7 2 D finition et contenu Un pointeur est une variable un peu particuli re car elle ne stocke ni un entier ni un r el ni un caract re mais une adresse Il est tentant de penser qu une adresse tant un num ro de cellule dans la m moire elle est comparable un entier Cependant une adresse ne s utilise pas comme un entier puisqu une adresse ne peut pas tre n gative et ne sert pas faire des calculs Une adresse est donc en ce sens un nouveau type Notion de contenu Soit p un pointeur il sera temps de passer la syntaxe exacte de d finition de pointeur lorsque toutes les notions n cessaires auront t abord es p tant un pointeur il est galement une variable et donc poss de un nom une valeur qui est une adresse et un type Un pointeur poss de en plus une autre caract ristique qui
199. teur a ptr_arbre entier VAR n entier DEBUT SI a NULL ALORS n 0 140 Dunod La photocopie non autoris e est un d lit 4 1 Arbres binaires SINON n 1 maximum compter a sag compter a sad FINSI RETOURNER n FIN quilibre parfait SI l arbre est vide il est parfaitement quilibr SINON compter le nombre de n uds du sag compter le nombre de neuds du sad SI ng nd gt 1 gt retourner faux SINON v rifier l quilibre parfait du sag SI oui gt v rifier l quilibre parfait du sad SI oui gt retourner vrai SINON gt retourner faux SINON gt retourner faux Algorithme Donn e ptr_arbre a R sultat de type entier FONCTION quilibre _parfait a ptr_arbre bool en VAR ok bool en cptgauche cptdroit entier DEBUT SI a NULL ALORS ok vrai SINON cptgauche compter a sag cptdroit compter a sad SI cptgauche cptdroit gt 1 ALORS ok faux SINON SI quilibre_parfait a sag ET quilibre _parfait a sad ALORS ok vrai SINON ok faux FINSI FINSI FINSI RETOURNER ok FIN 141 Chapitre 4 Structures arborescentes NONC S DES EXERCICES ET DES PROBL MES EXERCICES Exercice 4 1 Traiter un arbre en post ordre e a crire un algorithme r cursif de traitement en post ordre d un arbre binaire e b D rouler l algorithme sur l exemple suivant Figure 4 21 Exercice 4 2 Afficher le contenu des feuilles d un arbre crire
200. tion c d non seulement l tat o m ne la fl che tiquet e par ce caract re disons a mais aussi tous les tats o on peut arriver en lisant ae age etc Dans notre cas particulier il n y a pas de telles transitions mais il faut syst matiquement en tenir compte Figure 5 20 A4 Figure 5 21 Al 185 Chapitre 5 Automates Tableau 5 15 Etats r sultant en lisant a 1 2 en lisant b en lisant c a Figure 5 22 A5 On voit que l automate A5 n est pas le m me que l automate A3 ou A4 Pourquoi Parce que l automate d terministe reconnaissant un certain langage n est pas unique ce n est qu en minimisant qu on arrive un automate unique En minimisant A4 et A5 on doit obtenir la m me chose Minimisons A4 donc on rappelle la table de transitions Tableau 5 16 tats r sultant en lisant a en lisant b en lisant c 1 1 2 2 3 1 2 1 2 2 3 P 2 3 P P P P P P Ici on voit imm diatement que les tats 1 et 1 2 ne se s pareront jamais Oo 1 1 2 2 P 3 1 3 Utilisons une notation un peu plus intelligente pour ne pas modifier le sens des chiffres romains sans cesse Tableau 5 17 A Groupes r sultant Etat en lisant a en lisant b en lisant c 1 l l 3 1 2 l l 3 2 3 P l l l 5 se s pare en formant un groupe a part c est toujours le cas 186
201. tion du droit de copie CFC 20 rue des Grands Augustins 75006 Paris Dunod Paris 2010 ISBN 978 2 10 055072 2 Le Code de la propri t intellectuelle n autorisant aux termes de l article L 122 5 2 et 3 a d une part que les copies ou reproductions strictement r serv es l usage priv du copiste et non destin es une utilisation collective et d autre part que les analyses et les courtes citations dans un but d exemple et d illustration toute repr sentation ou reproduction int grale ou partielle faite sans le consentement de l auteur ou de ses ayants droit ou ayants cause est illicite art L 122 4 Cette repr sentation ou reproduction par quelque proc d que ce soit constitue rait donc une contrefa on sanctionn e par les articles L 335 2 et suivants du Code de la propri t intellectuelle TABLE DES MATIERES AVANT PROPOS 0223 25 seen dee de SR ob Mak Jo eae es LRO a ohh Ves IX INTRODUCTION 0 c cece cece eee eee eee eee 1 CHAPITRE 1 e LES BASES DE LA PROGRAMMATION 5 1 1 Les types de tonnes eck dec usine ere nd eek eel es 5 1 2 Les variables 22 6 1 3 Quelques l ments de syntaxe pour le langage algorithmique 6 1 4 Op rations et op rateurs de base 7 14 1 Affectation
202. tion se fera ensuite o 0 0 0 0 Figure 5 55 Cet automate lit tous les mots se terminant en e D terminisation Tableau 5 30 Etat a b 0 01 0 01 01 02 02 013 0 013 014 02 014 01 025 025 013 0 201 Chapitre 5 Automates a a a a b a b Cet automate est d j complet sinon il faudrait le compl ter en ajoutant une poubelle L automate d terministe lisant tous les mots ne se terminant pas par abaab s obtient comme as Il n est pas minimisable c a d qu il est d j minimal Pour le voir il faut essayer de le minimiser Oo 1 11 avec I 025 11 0 01 02 013 014 Figure 5 56 Figure 5 57 Tableau 5 31 Etat a b a b 0 01 0 Il Il 01 01 02 Il Il 02 013 0 Il Il 013 014 02 Il Il 014 01 025 Il 025 013 0 Il Il 202 Dunod La photocopie non autoris e est un d lit Corrig s des exercices Le groupe non terminal consiste en un seul tat et n a pas lieu se s parer Le groupe terminal se s pare en deux O 1 11 111 avec I 025 11 0 01 02 013 IZI 014 Tableau 5 32 tat a b a b 0 01 0 Il Il 01 01 02 Il Il 02 013 0 Il Il 013 014 02 nl Il Le groupe II se s pare en deux 1 11 111 1V avec I 025 H 0 01 02 IN 014 IV 013 Tableau 5 33 tat a b a b 0 01 0 Il Il 01 01 02 Il Il 02 013 0 IV Il
203. truction de l arbre Retourne l arbre de Syracuse t te valant 1 jusqu la profondeur maxDepth AL FONCTION syracuseTreeGrowth pt ptree maxDepth entier VAR n prec_inf_n entier t tree DEBUT SI maxDepth 0 ALORS RETOURNER FINSI t pt SI t NULL ALORS 167 Chapitre 4 Structures arborescentes t lt newSingletonTree 1 pot t FINSI n t content maxDepth maxDepth 1 t sad newSingletonTree 2 n syracuselreeGrowth amp t sad maxDepth prec_inf_n lt precInf n SI prec_inf_n gt 1 ALORS t sag newSingletonTree prec_inf_n syracuselreeGrowth amp t sag maxDepth FINSI FIN 168 AUTOMATES RAPPELS DE COURS 5 1 HISTORIQUE Alan Turing a d crit 1936 un mod le de machine id ale auquel il a laiss son nom D autres mod les furent propos s qui sont tous quivalents la machine de Turing Church a d montr dans sa th se que ces mod les sont les plus g n raux possibles Ces travaux amen rent distinguer entre les fonctions qui sont calculables en th orie de celles qui ne le seraient m me pas Toute fonction calculable peut tre calcul e par la machine de Turing en temps nombre d op rations fini Un mod le plus simple mais fort utile est celui d un automate fini Un automate fini est une machine abstraite constitu e d tats et de transitions Cette machine est destin e traiter des mots fournis en entr e l a
204. ucture classique un chapitre introductif r sume les bases minimales de la programmation informatique Les corrig s sont donn s sous la forme suivante e 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 e une sp cification en langage algorithmique pseudo code de la ou des solutions envisag es e une ventuelle proposition de r alisation en C99 des solutions propos es Des sch mas intuitifs Les sch mas descriptifs de principe facilitent la compr hension des principes de fonctionnement des algorithmes propos s La liste suivante vous sera utile notamment pour interpr ter les sch mas du second chapitre G e g Une place quelconque Un pointeur sur une Une place pointant Une place place non vide et donc sur la suivante interm diaire le d but d une liste de place contenant l l ment 6 places interm diaire Exercices et problemes d algorithmique Gr rs Owe Crowe La liste vide un Une place terminale Un singleton liste Une liste l ments pointeur ne pointant par composition un seul l ment multiples sur rien cpg Le cas particulier du couple liste deux Repr sentation des l ments modifications effectu es pointill s apr s vs traits pleins avant Un plan de travail qui peut tre adapt Si vous d butez et n avez jamais crit le moindre programme informati
205. uctures s quentielles complexes quelques fonctions utiles on fournit leurs en t tes FONCTION newEmptyQueue 1Queue FONCTION isEmptyQueue p_q 1Queue bool en FONCTION qPush e entier p_q 1Queue FONCTION qPop pe entier p_q lQueue entier Implantation en C structure de file r alis e avec une liste simplement cha n e dont la t te est l entr e la queue la sortie typedef struct lQueue list head list queue int length 1Queue Op rations Queue newEmptyQueue int isEmptyQueue lQueue p_q void qPush int e 1Queue p_q int qPop int pe lQueue p_q Repr sentation d une structure de pile l aide d une liste Pseudo code formel STRUCTURE 1Stack top list depth entier quelques fonctions utiles on fournit leurs en t tes FONCTION newEmptyStack 1Stack FONCTION isEmptyStack p_s 1Stack bool en FONCTION sPush e entier p_s 1Stack FONCTION sPop pe entier p_s IStack entier Implantation en C structure de pile r alis e avec une liste simplement cha n e dont la t te est le sommet la queue la base typedef struct 1Stack list top int depth Stack Op rations 100 Dunod La photocopie non autoris e est un d lit Corrig s des exercices 1Stack newEmptyStack int isEmptyStack 1Stack p_s void sPush int e IStack p_s int sPop int pe IStack p_s CORRIG S DES EXERCICES Exerc
206. ues de la file et de la pile sont respectivement le parcours en largeur et le parcours en pronfondeur d un graphe dont arbre est un cas particulier Ces deux algorithmes vous pr parent 4 ceux a peine plus compliqu s pour le parcours it ratif des graphes g n raux Sp cification de l algorithme FONCTION depthWalkerPrinter t tree VAR curr tree s IStack DEBUT SI t NULL ALORS RETOURNER FINSI s lt newEmptyStack sPush t s AFFICHER dedpthWalkerPrinter TANTQUE isEmptyStack s FAIRE sPop amp curr s AFFICHER curr content SI t sag NULL ALORS sPush t sag s FINSI SI t sad NULL ALORS sPush t sag s FINSI FAIT FIN FONCTION widthWalkerPrinter t tree VAR curr tree q IQueue DEBUT SI t NULL ALORS RETOURNER FINSI q lt newEmptyQueue qPush t q AFFICHER widthWalkerPrinter TANTQUE isEmptyQueue q FAIRE qPop amp curr q AFFICHER curr content SI t sag NULL ALORS qPush t sag q 153 Chapitre 4 Structures arborescentes FINSI SI t sad NULL ALORS qPush t sag q FINSI FAIT FIN Exercice 4 8 effectuer un calcul complexe sur un arbre Etude L ordre de parcours de l arbre importe peu de m me que la m thode it rative ou r cursive mais il est n cessaire de parcourir int gralit de l arbre pour calculer quatre grandeurs les sommes et d nombrements respectifs des l ments re
207. uestions pr alables toute tentative de r solution et dont les r ponses ne vont pas toujours d elles m mes et ne sont pas n cessairement affirmatives Ce sont les deux questions de d cidabilit e La premi re est celle de la d cidabilit logique ou th orique ce probl me est il soluble Construire la r ponse rel ve des math matiques pures et non pas de l art algorithmique proprement parler R pondre cette question par la n gative peut viter la vaine recherche d une r ponse la seconde e La certitude d une possibilit de r solution acquise se pose la seconde question de la d cidabilit algorithmique ou pratique comment trouver la solution R soudre en pratique un probl me th oriquement soluble c est concevoir et op rer une m thode de raisonnement qui partant d un nonc qualitatif et quantitatif permet de construire en un nombre fini d tapes l nonc de sa solution Un algorithme est la description d une telle m thode de raisonnement comme succession d tapes l mentaires et interm diaires de r solution ce qu on appelle commun ment un calcul Ainsi un algorithme se con oit il naturellement comme une d composition d un probl me en sous probl mes plus simples individuellement faciles r soudre et dont la composition donne la solution plus complexe du probl me principal Mais est ce la meilleure fa on de proc der Si d crire un algorithme s
208. uivant se trouve dans la case d indice j alors la case d indice i de second tableau contient I entier j On peut extraire les l ments du premier tableau dans l ordre alphab tique si on conna t le point de d part 1 dans notre cas Ce point de d part doit videmment tre pr cis l entr e de 35 Chapitre 2 Structures s quentielles simples Tableau 2 1 A d b 0 0 1 2 3 4 5 Tableau 2 2 3 5 2 0 1 2 3 4 5 chaque algorithme utilisant la repr sentation en question Dans la case 1 du deuxi me tableau on trouve 3 qui est l indice du deuxi me l ment du premier tableau etc Finalement dans la case 2 du deuxi me tableau on trouve 5 et dans la case 5 du premier tableau on a le marqueur de fin Si on ins re c dans le premier tableau on peut l ins rer dans la premi re case libre c est la case 0 et il n y a que deux changements faire au niveau du deuxi me tableau On met 0 dans la case 3 et on met 2 dans la case 0 Les tableaux 2 3 et 2 4 pr sentent les r sultats Tableau 2 3 c a D b 0 1 2 3 4 5 Tableau 2 4 2 3 5 0 0 1 2 3 4 5 Cette repr sentation n est pas tr s int ressante les fonctions de traitement sont relativement lourdes 7 Repr sentation chain e On utilise des pointeurs pour cha ner entre eux les l ments successifs et la liste est alors d termin e par l adresse de son premier l ment On va d finir des enregistrements structures dont un des
209. un d lit while 1 gt succ NULL amp amp 1 gt succ head Corrig s des probl mes iteration ler passage 1I pointe sur le second l ment 1 gt succ length s il existe au moins un suivant et si alors ce troisi me l ment est la t te c est qu on a une circulaire en l occurrence if 1 gt succ NULL if 1 gt succ head ineLength 0 oopLength length return length Sinon on remet le pointeur h z ro i e on le refait pointer sur la t te list h head lineL 0 on reprend le d compte le triangle tant que h n a pas rattrap 1 et qu il reste it rable while h 1 amp amp h gt succ NULL h h gt succ it rons le donc lineL si l est it rable et si alors son suivant EST h il y a boucle if 1 gt succ NULL if 1 gt succ h lineLength lineL loopLength length lineL return length si on arrive l c est une lin aire classique terminant en NULL lineLength length loopLength 0 return length 125 STRUCTURES ARBORESCENTES RAPPELS DE COURS Un arbre est un ensemble de n uds organis s de fa on hi rarchique partir d un n ud distingu appel racine La structure d arbre est l une des plus importantes et des plus sp cifiques de l informatique par exemple c est sous forme d arbre que sont organis s les
210. un entier comme statut d ex cution 1 ERR erreur 0 ID op ration blanche 1 OK au moins une suppression a t effectu e int removeAll lt V gt plist pl param lt V gt if pl NULL return ERR cas d erreur list 1 pl Dunod La photocopie non autoris e est un d lit Corrig s des exercices if 1 NULL return ID cas d op ration blanche list killed cas de suppression de toute la cha ne pr fixe d l ments impairs while 1 NULL amp amp tosuppr lt V gt 1 gt content param lt V gt killed 1 1 killed gt succ free killed pl 1 partir de ce point cha ne vide soit t te non supprim e supression des l ments cf crit re et au del de la t te while 1 NULL while 1 gt succ NULL amp amp tosuppr lt V gt 1 gt succ gt content param lt V gt killed 1 gt succ 1 gt succ killed gt succ free killed on passe soit au conserv suivant soit NULL fin de cha ne 1 1 gt succ return OK e Adaptations pour les cas B E Les correspondances suivantes permettent de sp cialiser le sch ma g n ral pour r pondre au quatre cas de figure B C D E Sp cification de l algorithme FONCTION crit re _estPair n entier bool en casB VAR pair bool en DEBUT SI n 2 0 ALORS pair lt vrai SINON pair faux FINSI RETOURNER pair FIN FONCTION crit re_estImpair n entier
211. unt sag_ne_sum sag_ne_count int sad_po_sum sad_po_count sad_ne_sum sad_ne_count signedAverages t gt sag amp Sag_po_sum amp Sag_po_count amp sag_ne_sum amp sag_ne_count signedAverages t gt sad amp sad_po_sum amp sad_po_count amp sad_ne_sum amp sad_ne_count ppo_sum Sag_po_sum sad_po_sum ppo_count sag_po_count sad_po_count pne_sum Sag_ne_sum sad_ne_sum pne_count sag_ne_count sad_ne_count if t gt content lt 0 pne_sum t gt content pne_count else ppo_sum t gt content ppo_count Pour tester tree treeAveragesTestTree int n unsigned p 156 Retourne un arbre parfait de racine de valeur th et profondeur dont chaque sag a pour valeur celle de son parent 1 et dont chaque sad a pour valeur celle de son parent 1 mae Ps Dunod La photocopie non autoris e est un d lit Corrig s des exercices Condition d arr t tree t newSingletonTree n if p 0 return t Sinon p t gt sag treeAveragesTestlree n 1 p t gt sad treeAveragesTestTree n 1 p return t void testEx2 printf gt gt tree averages n tree t treeAveragesTestTree 0 10 simplePrintTreeGraph t ttest double po_av ne_av signedAveragesMain t amp po_av amp ne_av int po_sum po_count ne_sum ne_count signedAverages t amp po_sum amp po_count amp ne_sum amp ne_c
212. ures Les types compos s ne diff rent gu re des types de base mis part l impossibilit d employer les op rateurs arithm tiques et logiques avec les types compos s Il en est de m me avec leurs adresses une fonction pouvant accepter une adresse en entr e param tres de type pointeur elle peut donc a fortiori accepter une adresse dont le contenu est d un type quelconque et notamment un type compos Il suffit dans ce cas d utiliser la notation l int rieur de la fonction pour acc der aux champs de la structure dont l adresse est fournie la fonction Retour de valeurs de type compos Une fonction peut tout fait retourner une valeur de type compos partir du moment o ce type est d fini il peut alors tre utilis en type de sortie de fonction sans aucun probl me ce qui est d ailleurs souvent le cas en informatique Retour d adresses de structures En synth se des deux derniers paragraphes une fonction peut galement retourner l adresse d une valeur de type quelconque notamment un type compos 34 STRUCTURES SEQUENTIELLES SIMPLES RAPPELS DE COURS 2 1 LISTES LINEAIRES Exemple Imaginons la gestion d un tableau contenant les r f rences des livres d une biblioth que Ce tableau est rang dans l ordre alphab tique Lorsqu un nouveau livre est achet son insertion dans le tableau en respectant l ordre requiert de d placer toutes les r f rences qui
213. urnir une adresse C 1 8 4 Les fonctions et les pointeurs Le passage de tableau en param tre est en fait une tr s bonne illustration des effets de la transmission d une adresse une fonction le m me ph nom ne entre en jeu lorsque ce sont des pointeurs qui sont utilis s pour ce passage de param tres puisqu un tableau est un pointeur Nous avons ainsi remarqu que le passage d une adresse dans le cas d un tableau permet d obtenir un acc s une variable du programme principal partir d une fonction recevant l adresse de cette variable Nous allons donc utiliser explicitement cette transmission adresse de variable pour avoir un acc s son contenu et ce gr ce la notation d j trait e dans la section concernant les pointeurs Param tre de type adresse de La syntaxe utilis e pour un param tre de fonction lors de la d finition de celle ci lorsque le param tre est un pointeur est la suivante nom_du_param tre type_point Cela revient donc 4 utiliser la syntaxe de d finition d une variable de type pointeur Pour un param tre cette criture s interpr te un peu diff remment m me si cette interpr tation est tout a fait coh rente avec tous les aspects abord s avec les pointeurs Exemple Le param tre nom_du_param tre est l adresse d une valeur de type_point Pourquoi faire cette distinction ici Tout simplement parce qu un argument fourni un
214. us avons montr pr c demment est d terministe Voici l exemple d un automate non d terministe Q 9 9 0 Figure 5 3 Cet automate reconna t tous les mots qui se terminent par abaa Il est tr s facile construire Le fait qu il n est pas d terministe se manifeste en ce que en lisant a partir de l tat 0 on peut aller et l tat 0 et l tat 1 ce qui ne serait pas possible pour un automate d terministe On va montrer dans ce qui suit que l on peut toujours construire partir d un automate fini quelconque un autre automate qui est d terministe et qui lui est quivalent reconna t le m me langage Automate d terministe d finition L automate C Q 1 T E est d terministe ssi pour Vp Q et Va A il existe au plus un tat q Q tq p a q et qu il y ait un seul tat initial 7 i On peut donc caract riser un automate d terministe C par un quadruplet Q i T E o i est l tat initial Si la transition p a q existe on notera p a q Si elle n existe pas on conviendra que p an a pas de valeur On peut facilement v rifier par r currence sur la longueur des mots que pour un automate d terministe C pour Vp Q et V mot u A il existe au plus un tat q Q tq p gt 4 On notera alors p u gen convenant que p u n est pas d fini quand il n existe pas de tel tat q et on aura pour deux mots u v A p u v p u v D t
215. utomate passe d tat en tat suivant les transitions la lecture de chaque lettre de l entr e L automate est dit fini car il poss de un nombre fini d tats distincts il ne dispose donc que d une m moire born e ind pendamment de la taille de la donn e sur laquelle on effectue les calculs Un automate fini forme un graphe orient tiquet dont les tats sont les sommets et les transi tions les arcs tiquet s Les automates finis fournissent un outil de construction d algorithmes particuli rement simple Il existe plusieurs types de machines tats finis Les accepteurs produisent en sortie une r ponse oui ou non c est dire qu ils acceptent oui ou rejettent non l entr e Les syst mes de reconnaissance classent l entr e par cat gorie Les capteurs produisent un certain r sultat en fonction de l entr e Les automates finis peuvent caract riser des langages c est dire des ensembles de mots finis le cas standard des langages de mots infinis automates de Rabin automates de B chi ou encore divers types d arbres automates d arbres Les machines tats finis se rencontrent galement dans les circuits digitaux o l entr e l tat et le r sultat sont des vecteurs de bits de taille fixe machines de Moore et machines de Mealy Dans les machines de Mealy les actions sorties sont li es aux transitions tandis que dans les machines de Moore

Download Pdf Manuals

Related Search

Related Contents

  Viewsonic WPG-370  Samsung 23,6" LED-TV Monitor TE310  ASUS (ME176CX) User's Manual  User Manual - vermietung  ILS ONT TESTE  Manual de Instruções  Model 1063 - Ronnoco Sales Ltd.  Untitled  

Copyright © All rights reserved. Failed to retrieve file