Home

INFO-F101 : Programmation Syllabus d`exercices

1. D FIGURE 13 1 Exemple addChecksum filename Code correcteur L id e de ce code est de modifier le code d tecteur pour pouvoir aussi cor riger des erreurs On va donc ajouter les bits de parit pour chaque ligne et pour chaque colonne voir l exemple Figure Ce code permet de corriger au plus une erreur 1 Ecrivez une fonction addC hecksumC orr filename qui lit le contenu d un fichier cal cule le checksum et l ajoute la fin de fichier 2 Ecrivez une fonction veri fyAndCorrect filename qui lit un fichier avec le checksum verifie si le checksum est correcte et corrige le fichier si le fichier est corrompu Ex 13 5 Faites l exercice sans supposer que le fichier contient que des 1 et des 0 et sans supposer que tous les lignes ont la m me longueur Ex 13 6 crivez une fonction deepprint dico depth qui va afficher les l ments d un dictionnaire en pr cisant pour chaque l ment du dictionnaire la cl et sa valeur Si la valeur est elle m me un dictionnaire il faudra effectuer r cursivement son affichage en indentant l affichage le param tre depth est en entier qui permet de pr ciser quel niveau d indentation on se situe 0 signifie pas d indentation 1 signifie qu on a un niveau d indentation etc Voici un exemple d affichage Nom Pierre Paul Pr enom Jacques Age 26 Cours 58 File 0 0 1 0 O0 0 1 0 1 O Calcule de bits de parit 9 0
2. 72 Fonction EN Cha nes de caract res un Listes Matrices et tableaux Dictionnaires Complexit Logique et invariants 7 0 R cursivit 1 Fichiers et exceptions 2 Introduction aux classes 3 R vision i Swampy Turtle lez Python Imaging Library 11 16 21 26 30 35 41 47 49 52 56 63 66 Chapitre 1 S ance introductive Exercices pr paratoires Mati re r viser les variables les fonctions print ettype les op rateurs x x les commandes en terminal 1s et cd Lisez le Mode d emploi introductif pour les salles du NO4 et NO3 partie 1 Introduction et la partie 2 La console Linux seulement 2 1 commandes 1s et cd Exercices en s ance EX 1 1 Allez dans le menu Applications et lancez l application Terminal situ e dans l onglet Accessoires Lancez Python 3 en tapant la commande python3 dans le Terminal Ex 1 2 Entrez les expressions suivantes dans l interpr teur et regardez le r sultat 1 5 2 5h 3 x 5 4 x 1 5 x x 1 6 x Ex 1 3 Utilisez l interpr teur pour afficher les textes suivants rappel print Hello World Aujourd hui SD N e C est Dommage 4 Hum 0 Allez dans le menu Applications et lancez l diteur de texte voir Mode d emploi des salles informatiques situ e dans l o
3. N Il p m a O ps Il Pr p 2 7 Qu crit sur output le programme suivant quand on lui fournit en input 1 les valeurs 1 et 6 2 les valeurs 8 et 2 5 a float input b float input test a gt b if test or a lt 0 print Oui else print Non Pr p 2 8 Que fait cette suite d instructions a 1 while a lt 5 print a end a 1 print a Pr p 2 9 Que fait cette suite d instructions a 1 while a lt 5 a end Pr p 2 10 Que fait cette suite d instructions i 0 for j in range 10 i print i Pr p 2 11 Quelle est la diff rence entre les quatre instructions suivantes Expliquez ce qu elles font et essayez de les utiliser avec une boucle for range 42 range 42 69 range 42 69 3 range 42 69 1 Exercices en s ance Ex 2 1 crire un programme qui affiche at a lu sur input en employant le moins de multiplications possibles sans utiliser l op rateur ni de boucle Ex 2 2 crire un programme qui affiche 18 x a a lu sur input uniquement gr ce des addi tions assignations et print pas d op rateurs ni de boucle en employant le moins d additions possible Branchements conditionnels EX 2 3 crire un programme qui lit 3 nombres et qui si au moins deux d entre eux ont la m me valeur imprime cette valeur le programme n imprime rien dans le cas contraire EX 2 4 P
4. l ments L n a pas forc ment de solution Par exemple la liste 4 5 n a pas de solution Nous supposerons que la liste L donn e en entr e de votre fonction contient une solution 62 Annexe Swampy Turtle Exercices pr paratoires Mati re r viser g om trie euclidienne de base angles suppl mentaires compl mentaires p rim tre d un polyg ne circonf rence d un cercle somme des angles dans un polyg ne r gulier angles d un polyg ne r gulier Exercices en s ance Pour cette s ance vous devez d abord t l charger Swampy pour Python 3 sur le site Une fois le dossier d compress cr ez y un fichier lt filename gt py Pour commencer tapez le code suivant dans le fichier que vous venez de cr er import turtle turtle reset Ce morceau de code ne fait que cr er un monde et une tortue Dans Turtle chaque tortue peut avancer forward tourner gauche left ou tourner droite right De plus sous chaque tortue se trouve un crayon permettant de tracer un trait si le crayon est baiss La commande up permet de lever le crayon alors que la commande down permet de le bais ser Les fonctions left et right prennent un param tre qui repr sente l angle de rotation turtle left 45 fera tourner la tortue de 45 degr s vers la gauche Pour tracer un angle droit il faut ajouter apr s avoir cr la tortue turt le le code suivant turtle forward 100 tur
5. une liste de 1000 valeurs Il peut par exemple tre vu que plus de 400 valeurs mesur es se trouvaient dans l intervalle 0 0 0 2 donn l histogramme pourrait alors d crire combien d tudiants ont eu une note entre 0 et 4 entre 5 et 9 entre 10 et 14 et entre 15 et 20 par exemple Notez que le nombre de cat gories c est dire de gammes de valeurs est arbitraire Nous vous demandons d crire une fonction histogramme qui prendra deux param tres une liste L de valeurs r elles ventuellement n gatives ainsi qu une liste I d au moins deux valeurs r elles distinctes et tri es dans l ordre croissant La liste I donne les bornes d intervalles successifs sur la droite r elle Par exemple si cette liste est 5 2 9 5 elle symbolise deux intervalles les valeurs entre 5 inclus et 2 non inclus ainsi qu entre 2 inclus et 9 5 non inclus Votre fonction histogramme doit renvoyer un dictionnaire o chaque clef est un string de la forme a b si l on suppose que a est la borne inf rieure incluse de l intervalle et que b est la borne sup rieure non incluse la valeur associ e chaque clef sera un entier qui dira combien de valeurs de la liste L sont incluses dans l intervalle consid r Dans un second temps nous vous demandons d crire une fonction intervalles qui prendra trois param tres deux r els inf et sup il est suppos que sup gt inf ainsi qu un entier st
6. surcharge d op rateur Pr p 12 1 Que fait le code suivant Expliquez class A def _init _ self msg bright self attr msg def __repr__ self return self attr def set self msg self attr msg Pr p 12 2 Ecrivez une classe Point qui va d finir un point dans un espace de dimension 3 Nous vous demandons de d finir un constructeur avec valeurs par d faut de d finir la m thode repr self de la classe pour pouvoir utiliser print sur vos objets Point et de d finir la m thode distance self point qui prend un objet de type Point en entr e et qui renvoie la distance entre les deux points Exercices en s ance Ex 12 1 Ecrivez une classe StopWatch qui mod lise un chronom tre Cette classe doit contenir les m thodes suivantes __init__ qui cr e un nouveau chronom tre et le d marre 52 53 _ repr_ qui renvoie une repr sentation de type sting du chronom tre sous le format Stop Watch timel time2 o timel donne le moment de la cr ation ou du dernier lancement start du chronom tre et time2 le moment du dernier arr t du chronom tre et le string None si le chronom tre n a pas encore t arr t _ str_ qui renvoie la m me information que _repr___ __str___ est utilis lors des print get_start_time qui renvoie l heure laquelle le chronom tre a t lanc pour la der ni re fois get_end_ time qui renvoie l heure laquell
7. 1 1 0 0 0 1 0 O 1 101 Fichier apres l execution de addChecksumCorr Oorr H FIGURE 13 2 Exemple addChecksum filename INFO F 101 NoteFinale 14 InterroJanvier 12 Projets 10 INFO F 102 17 Matricule 372910 EX 13 7 On stocke dans un fichier le nom et l adresse de diff rentes personnes une personne et son adresse par ligne Par exemple David Roman Rue des chateaux 123 1100 Youplala Belgique Eric Degeers Avenue de l avenue 13 11800 Mouahahah France John Meersman Route de la vie 55 1000 Forest Belgique Vous devez r aliser un programme qui permettra l utilisateur d afficher ces informations selon diff rents tris En fonction du nom puis du code postal puis du pays En fonction du pays puis de la rue puis du nom En fonction du code postal puis du nom Le programme devra continuellement demander l utilisateur comment il veut afficher les in formations jusqu ce que ce dernier demande de stopper le programme Ex 13 8 On vous demande d impl menter la fonction tassement qui prends en argument une liste L qui contient des nombres naturels La fonction doit modifier la liste L pour que tous les l ments 0 se retrouvent la fin de la liste On vous demande d impl menter cette fonction de deux fa ons voir les exemaples L ordre de tous les l ments diff rents de 0 peut tre modifi tassementNonOrd
8. Polynome Monome 2 5 Monome 4 0 Monome 10 1 gt gt gt p3 pl p2 gt gt gt p4 pl x p2 gt gt gt print p3 5 0 X 5 2 0 x 4 10 0 x 13 0 gt gt gt print p4 6 0 x 10 4 0 x 9 30 0 x7 6 50 0 x 5 8 0 x 4 90 0 x 36 0 Ex 12 6 Ecrivez une classe Rational qui va d finir un nombre rationnel Un nombre rationnel est un nombre qui peut s exprimer comme le quotient de deux entiers o a et b sont deux entiers avec b non nul On appelle a le num rateur et b le d nominateur Votre classe 55 devra avoir deux champs attributs et d finir les m thodes suivantes __init__ __repr __str__ __add__ __sub__ __mul__ __div__ Ex 12 7 Ajoutez la classe Polynome la m thode composition qui va faire la com position entre deux polyn mes Exemple Si pour tout r el x f x 3 x 4x 02 glz 4x 1 alors le polyn me f o g est le polyn me d fini pour tout r el x par g x 4 g x 1 2 4z 1l 4 4x 1 2 3 16 2 8x 1 4 4r 1 2 48 x 24 x 3 16 7 4 2 48 x 40 x 9 fog x f g x 29 az Par contre g o f est le polyn me d fini pour tout r el x par go f g f x Af f x 1 4 3 x 4 x 2 1 12 z 16 x 8 1 12 z 16 x 9 Chapitre 13 R vision Exercices pr paratoires Pr p 13 1 Revoir toute la mati re Exercices en s ance Ex 13 1 crivez une fonction
9. clef est une forme canonique et o la valeur correspondante est la sous liste des mots pass s en param tres respectant cette forme Par exemple equivalence canonique BBB CCC BABA ABBA devra renvoyer un dictionnaire de la forme AAA BBB CCC AZAZ BABA ABBA ABBA EX 7 4 Ecrivez une fonction values dico qui doit fournir partir du dictionnaire donn en param tre une liste des valeurs du dictionnaire telles qu elles soient tri es sur base de la clef du dictionnaire Vous pouvez supposer que les clefs du dictionnaire sont des strings et vous pouvez utiliser la m thode sort sur les listes pour vous aider Ex 7 5 Ecrivez une fonction primes_odds_numbers numbers qui re oit une liste de nombres et qui renvoie un couple d ensembles contenant respectivement les nombres im pairs de cette liste ainsi que les nombre premiers Votre fonction doit faire appel deux autres fonctions even max qui renvoie l ensemble des entiers pairs inf rieurs max prime _ numbers max qui renvoie l ensemble des nombres premiers inf rieurs max que vous devez galement coder Ex 7 6 Ecrivez une fonction store_email liste_ mails qui re oit en param tre une liste d adresse e mail et qui renvoie un dictionnaire avec comme clefs le domaine des adresses e mail et comme valeurs les listes d utilisateurs correspondantes Par exemple la liste d adresse suivant
10. d qui renvoie True si et seulement si l entier positif n est un multiple de l entier positif d Vous ne pouvez pas utiliser les op rateurs ni ni Ex 10 9 Une fonction div_entiere n d qui renvoie la division enti re entre n et d ie n d sans utiliser l op rateur Ex 10 10 Une fonction concatenation L1 L2 qui renvoie une liste L la concate nation de listes L1 et L2 par exemple si L1 1 2 etL2 3 4 alors la fonction concatenation Li L2 doit renvoyer la liste 1 2 3 4 Vous ne pouvez pas utiliser l op rateur ni la m thode extend Chapitre 11 Fichiers et exceptions Exercices pr paratoires Mati re r viser la fonction open file mode avec modes d ouverture read write et append les m thodes close write read readline readlines seek sur les objets fichiers le module os et la notion de chemins absolus et relatifs les exception plus fr quentes ValueError TypeError IndexError IOError lever une exception via raise g rer des exceptions via try except les fonctions ord et chr voir exercice 4 7 p T8 Lisez le Mode d emploi introductif pour les salles du NO4 et NO3 partie la console Linux Pr p 11 1 crivez une fonction Lecture nomFichier qui affiche le contenu du fi chier Pr p 11 2 crivez une fonction ecriture nomFichier chaine qui cr e un fichier vide portant le nom nomFi
11. dans la case de A l indice O puis la valeur de l indice 1 est plac e dans la case de l indice 3 puis la valeur de l indice 3 est plac e dans la case de A l indice 1 OS On A D et enfin la valeur de la derni re case n est pas d plac e 3 2 2 KINAN REDE a 41310 1 215 a Tableau b Tableau P a211171019 8 c Tableau A FIGURE 6 3 Exemple de tableau A figure a de tableau P figure b et de tableau A figure c repr sentant l application de la permutation P sur A 29 Ex 6 9 crivez une fonction rotation M qui effectue une rotation en place de 90 degr s dans le sens trigonom trique d une matrice carr e M de taille n x n Ex 6 10 mini projet Le jeu du Morpion est un jeu dans lequel s opposent deux joueurs Le but dans ce jeu est d aligner 5 fois un m me jeton dans la grille de taille 5 x 5 de d part Il vous est demand d impl menter une version du Morpion en suivant les consignes suivantes Cr ez une fonction create_morpion n qui cr e et renvoie une grille de taille n x n sur laquelle les joueurs seront amen s jouer Cr ez une fonction next_turn morpion player i j qui simule l ajout d un jeton en position j par le joueur player 1 ou 2 Cette fonction renvoie une nouvelle grille correspondant l ajout du jeton sur la grille morpion pass e en param tre Si le coup jou n est pas va
12. des figures math matiques d crites plus facilement sous forme d quation polaire reliant un rayon un angle que sous forme cart sienne reliant une abcisse une ordonn e tels des cercles ou des spirales Nous vous demandons en premier lieu d crire une fonction relier_points qui prendra en param tres une tortue ainsi qu un nombre arbitraire de tuples de deux entiers z1 y1 x2 ya Ln Yn repr sentant des points dans le plan L id e de cette fonction sera de consid rer que la position courante de la tortue est l origine 0 0 et d ensuite la faire passer dans l ordre par tous les points x1 y1 x2 y2 etc Pour ce faire l algorithme suivant peut tre utilis Soit 0 Consid rer le point x yi dans la liste L avec zo yo 0 Calculer Az Ay i 1 Ti Yi 1 Yi Calculer d y Ax Ay Si Az gt 0 calculer a arctg 22 Si Az lt 0 calculer arctg 32 7 Sinon si Ax 0 il y a trois autres cas consid rer si Ay 0 alors a 0 si Ay gt 0 alors 17 a 5 Sinon a 5 ESP TO OT Faire tourner la tortue de 300a degr s vers la gauche left 6 7 Avancer la tortue d une distance d forward 8 Faire tourner la tortue de 360a degr s vers la droite rt 9 Incr menter et recommencer l tape 2 si i lt n Dans un second temps nous vous demandons d impl menter une fonction spirale d un seul param
13. effectuer ce genre de d calages nous pouvons utiliser la correspondance entre lettres et leur valeur num rique dans un encodage particulier par exemple l ASCII La Table 4 1 reprend la correspondance entre les majuscules de A Z et leur valeur num rique dans l encodage 19 ASCII Il est important de remarquer que les valeurs se suivent en s quence en d autres termes pour obtenir la valeur num rique correspondant la lettre D il suffit d ajouter 3 la valeur num rique de la lettre A Lettre Valeur ASCII A 65 B 66 Y 89 Z 90 TABLE 4 1 Correspondances entre majuscules et leur valeur dans l encodage ASCII La fonction ord en Python permet d obtenir pour une lettre donn e pass e en param tre sa valeur num rique dans l encodage ASCII Par exemple ord A renverra la valeur 65 La fonction chr prend quant elle une valeur num rique de l encodage ASCII et renvoie la lettre correspondante chr 67 renverra la lettre C l aide de ces deux fonctions crivez les fonctions suivantes caesar mot k qui renvoie le r sultat du d calage de k unit s du mot mot re u en param tre une cha ne de caract res canonique mot qui renvoie une version canonique d un mot On d finit la version ca nonique d un mot comme tant l unique d calage de ce mot donnant un mot d butant par la lettre A Expliqu
14. en Python qui permutera les l ments d un tableau A en fonction d un tableau de permutation P Le traitement doit tre effectu sans utiliser de structure interm diaire c est dire pas de dictionnaire pas de nouvelle liste ou de tableau etc En d autres mots vous avez le droit de modifier le tableau le tableau P ainsi que d utiliser des variables ne contenant que des entiers La Figure 6 2 vous montre un exemple de tableau de tableau P et enfin d un tableau 4 qui est le tableau apr s permutation des l ments gr ce au tableau P On y voit que l entier 9 en position 1 0 2 dans le tableau A i e A 1 0 2 doit se trouver en position 0 dans le tableau A apr s r organisation donc en A 0 0 0 La Figure 6 3 vous affiche un autre exemple de tableau d un tableau P et enfin d un tableau A qui est le tableau A apr s permutation des l ments gr ce au tableau P Les fl ches mises c Tableau A FIGURE 6 2 Exemple de tableau figure a de tableau P figure b et de tableau A figure c repr sentant l application de la permutation P sur A dans la Figure 6 3 a vous permettent de voir comment sont permut es les valeurs dans le tableau A On y voit que 1 la valeur de A l indice 0 est plac e dans la case de A l indice 4 puis la valeur de A l indice 4 est plac e dans la case de A l indice 2 puis la valeur de l indice 2 est plac e
15. et un entier n en param tres La fonction devra renvoyer une liste correspondant la liste re ue tri e par ordre non d croissant o n a t ins r e tout en la maintenant tri e Vous pouvez supposer que la liste est bien form e de valeurs enti res tri es Essayez de tester les autres cas d erreur et dans ce cas renvoyez None Ex 5 6 M me exercice que le pr c dent mais ici la fonction modifie la liste donn e en param tre et renvoie lt None Quelle version entre celle ci et celle de l exercice pr c dant est la plus propre au niveau du style de programmation Ex 5 7 Ecrivez une fonction my_count qui prend une liste 1st et un l ment e en pa ram tres La fonction doit renvoyer le nombre de fois que l l ment e appara t dans la liste N oubliez pas de tester tous les cas possibles Ex 5 8 Ecrivez une fonction my_remove qui prend une liste 1st et un l ment e en para m tre et qui effacera la premi re apparition de l l ment e dans la liste N oubliez pas de tester tous les cas possibles D finissez une version qui modifie 1st et renvoie None et une autre qui ne modifie pas 1st et renvoie la liste modifi e Ex 5 9 Ecrivez une fonction my_map qui prend une liste 1st et une fonction f en para m tres et qui renverra une nouvelle liste o un l ment la position contiendra la valeur de retour de la fonction f appliqu e au l ment de la liste 1st A nouveau n oubliez pas de
16. gti gs eg pour la classe Monome d finie pr c demment en respectant les contraintes suivantes le m thode _add_ __sub__ __mul__ __truediv__ doivent renvoyer un mo n me siles mon mes ont des degr s diff rents les m thodes _add_et__sub__ doivent lever une exception nous souhaitons que la relation d ordre entre deux mon mes soit la suivante a op bd lt gt x op y o op est un op rateur de l ensemble lt lt gt gt Exemple 2x gt 3x est vrai Ex 12 4 Ecrivez une classe Polynome qui va d finir un polyn me Un polyn me est une somme finie de mon mes nous pouvons donc repr senter un polyn me par une liste de mo n mes et utiliser la d finition de la classe Monome de l exercice pr c dant Aucun coeffi cient de mon me ne sera nul except pour le polyn me 0 0 qui contient dans sa liste le seul Monome 0 0 0 Deux Mon mes d un Polyn me n ont jamais le m me degr Si deux ou 54 plusieurs Mon mes introduits lors de l initialisation ou comme r sultat d une m thode sont de m me degr votre m thode doit fusionner ceux ci en les additionnant Un polyn me contient toujours au moins un mon me par d faut le mon me unique 0 0x Nous vous demandons d crire les m thodes __init__ qui cr e un Polynome partir des mon mes pass s en param tre votre m thode doit trier les Monomes par degr croissant et s assurer que deux Mon
17. lui passant selon que vous d sirez une sym trie d axe vertical ou horizontal respectivement Image FLIP_LEFT RIGHT ou Image FLIP_TOP_BOTTOM Voici un exemple gt gt gt rectangle 65 65 800 800 gt gt gt picture picture crop rectangle gt gt gt picture picture rotate 90 gt gt gt picture picture transpose Image FLIP_ TOP _ BOTTOM 68 Ex B 4 crivez une fonction traitement_miroir liste_noms qui prend en pa ram tre une liste de noms de fichiers Vous avez fait une s ance de shooting photo malheu reusement l angle de vue tait faite sur un miroir l appareil inclin de 30 degr s Nous vous demandons de traiter toutes ces photos dont la liste des fichiers est pass e en param tre Ces photos doivent tre recadr es avec un rectangle 30 30 500 500 doivent tre invers es par rapport l axe vertical et subir une rotation permettant de redresser l image Le r sultat de ces manipulations pour chaque photo doivent remplacer le fichier d origine B 3 Filtres Vous pouvez galement appliquer diff rents filtres d image l aide du module ImageFilter dont voici un exemple import ImageFilter picture2 picture filter ImageFilter BLUR Il existe beaucoup d autres modules de retouche Si vous voulez aller plus loin vous pouvez vous documenter sur la biblioth que disponible l adresse suivante http www pythonware com library pil Ex B 5 Jouez maintenan
18. mais utilisez la boucle while 4 a pairs entre 0 et n compris de mani re croissante utilisez la boucle for 4 b idem 4 a mais utilisez la boucle while 5 multiples de 7 entre 0 et n bornes non compris de mani re croissante utilisez la boucle for 6 multiples de 5 entre 0 et n compris de mani re d croissante utilisez la boucle for Ex 2 16 crire un programme qui calcule la taille moyenne en nombre de personnes des Petites et Moyennes Entreprises de la r gion les tailles tant donn es en input la fin des donn es tant signal e par la valeur sentinelle 1 on suppose aussi que la suite des tailles contient toujours au moins un l ment Exemple d ex cution LT 8 14 5 1 La moyenne est de 9 5 Ex 2 17 crivez un mini jeu le programme choisit un nombre naturel nombre secret entre O et 100 de mani re al atoire le joueur doit deviner ce nombre en utilisant le moins d essais possibles A chaque tour le joueur peut faire un essai et le programme doit r pondre si le nombre secret est plus grand ou plus petit Si le joueur trouve le nombre secret alors le programme doit afficher Bravo ainsi que le nombre d essais utilis s par le joueur Le joueur a maximum 6 essais s il ne devine pas le secret apr s 6 essais le programme s arr te en crivant Vous avez perdu Pour g n rer des nombres al atoires importez le module random Pour g n rer un entier al a toire dans in
19. n raliser ces fonctions des droites quelconques dans le plan euclidien m mes verticales en supposant plut t que les droites sont repr sent es par un triplet a b c de r els qui correspondent une quation ax by 0 Ecrivez d s lors les fonctions pr c dentes en tenant compte de la possibilit d avoir des droites verticales et horizontales Chapitre 4 Cha nes de caract res Exercices pr paratoires Pr p 4 1 Pourquoi les instructions suivantes ne donnent elles pas le m me r sultat 0199 lt New int 0199 lt int 187 Pr p 4 2 Que fait l instruction suivante Tim in Castle Aaaaargh Pr p 4 3 Que fait le code suivant txt Antioch for i in range len txt print txt i Pr p 4 4 Que fait le code suivant for k in Caerbannog print k end Kk Pr p 4 5 Que fait le code suivant mon_string bonjour for k in range 10 print mon_string k Pr p 4 6 Expliquez pourquoi la seconde instruction du code suivant provoque une erreur msg Caerbannog msg 0 K Pr p 4 7 Quelle est la diff rence entre la cha ne vide et None Pr p 4 8 En supposant que le fichier test txt existe et est bien accessible que fait le code suivant Expliquez pourquoi on fait appel la m thode strip fd open test txt for i in fd print i strip fd close 16 Pr p 17 4 9 En supposant que le fichier test txt existe et e
20. pondant True la m thode isalnum Ex 11 2 crivez une fonction replace in_path out_path pattern subst qui doit ouvrir le fichier dont le chemin est in_path et remplacer dans ce dernier toutes les occurrences du string pattern par subst Le r sultat de cette modification devra tre crite dans le fichier de chemin out_path Ex 11 3 l aide d un dictionnaire crivez les fonctions suivantes file histogram fileName qui prend en param tre le nom sous forme d une cha ne de caract res d un fichier texte et qui renvoie un dictionnaire contenant la fr quence absolue c est dire le nombre d occurrences de chaque lettre dans le texte contenu dans le fichier vowels_histogram fileName qui prend en param tre le nom sous forme d une cha ne de caract res d un fichier texte et qui renvoie un dictionnaire contenant la fr quence absolue des chaque suite de voyelles par exemple i oe oui eui you etc Notez que si on trouve oe par exemple il ne faut pas compter une occurrence de o ni de e Vous ne comptabiliserez pas les voyelles avec accent uniquement les suites de AY e i KOD amp U Y words_by_length fileName qui prend en param tre le nom sous forme d une cha ne de caract res d un fichier texte et qui renvoie un dictionnaire associant une valeur enti re qui correspond une longueur d
21. prefixe est initialement un string vide et s un string n caract res Sachant que pref t initialement un str deet s un st t def Permutations prefixe s if len s print prefixe else for i in range len s Permutations prefixe s i s i s i 1 Sachant que graphe est un dictionnaire de n noms de personnes sous forme de strings de longueur maximale de 10 caract res o la valeur correspondante chaque personne est une liste de ses amis listes de noms de personnes et x est un nom de personne dans graphe donnez la complexit moyenne et maximale de la fonction connaissance_indirecte Rappel les m thodes add et pop respectivement ajoute et enl ve un l ment le dernier renvoyant sa valeur def connaissance_indirecte graphe x s set x to_do set x while len to_do gt 0 z to_do pop for y in graphel z l if y not in s s add y to_do add y return s x Exemple graphe Jean Germaine Germaine Catherine Catherine Jean j y Luc gt Michel Luc Bernadette Luc Michel Jules Jules Bernadette x Bernadette Chapitre 9 Logique et invariants Exercices pr paratoires R visez la mati re concern e vue au cours ainsi que la logique de base telle que vue au cours de math matiques Nous vous invitons galement d j essayer de r aliser l exercice O 1 du mieux que vous pouvez Rappels th ori
22. rageons crire des fonctions suppl mentaires si cela peut vous aider ou clarifier votre code Nous vous demandons d utiliser parcimonieusement la m moire vitez par exemple si possible de construire la table de Vigen re en m moire Chapitre 5 Listes Exercices pr paratoires Pr p 5 1 Quelle est la diff rence entre un tuple et une liste Pour vous aidez ex cutez en mode interactif le code suivant a 4 2 1 a 1 9 print a 1 b 4 2 1 b 1 9 print bl1 Pr p 5 2 Que r alise chaque ligne du code suivant a a append 1 print a a append 2 print a a append 3 print a a a 4 5 6 7 print a Pr p 5 3 Que donne le code suivant print 1 2 3 4 5 6 17 3 6 1 1 Pr p 5 4 Examen de janvier 2012 Que donne le code suivant x 1 x 1 2 print x Pr p 5 5 Examen de janvier 2012 Que donne le code suivant Utilisez des diagrammes d tat pour d crire l tat du programme durant les phases d ex cutions 21 22 def foo v v 3 4 x 0 1 2 foo x print x Pr p 5 6 Examen de janvier 2012 Que donne le code suivant Utilisez des diagrammes d tat x 0 1 2 y 23 yl 3 4 print x y Pr p 5 7 Construisez une liste L contenant un entier quelconque compris entre 1 et 10 Multipliez le par 2 ajoutez 8 et divisez le par 2 Soustrayez le nombre que vous avez choisi au d part ce nouveau nombre Verifiez que le r sulta
23. ro 1024 Dans quelle armoire se trouverait le volume 404 si chacune pouvait contenir 91 livres Ex 1 7 Supposez que vous ayez quatre variables a b c et d Comment pourriez vous vous y prendre pour inverser l ordre des valeurs qu elles r f rent sans utiliser l assignation multiple comme a b c d d c b a Par exemple si l initialisation a 1 b 2 c 3 0 et d True comment obtenir True 3 0 2 1 l cranenentrant print a b c d Ex 1 8 M me question que dans l exercice 1 7 en supposant que les 4 variables sont de type int Vous ne pouvez pas utiliser d autres variables que a b c et d Ex 1 9 Allez sur le site Python org et cherchez dans la documentation du langage language reference de l aide propos de print Comparez avec le r sultat obtenu dans l interpr teur lorsque vous entrez help print Cherchez vous renseigner sur d autres aspects de Python vus au cours int str les op rateurs Chapitre 2 Controle de flux Exercices pr paratoires Mati re r viser les variables l indentation les fonctions pr d finies input print range les types int float bool les op rateurs de comparaison et connecteurs logiques gt lt and or etc les instructions de branchement conditionnel 1f else if elif else les boucles for et while Faites tous les exercices pr paratoires sur papier et ensui
24. sor ont t plac s de mani re al atoire La fonction demande l utilisateur d entrer une coordonn e Elle doit demander des coordonn es r p tition jusqu ce que l utilisateur trouve le tr sor gagn ou tombe sur un pi ge perdu Ex 7 8 Examen de juin 2011 Dans les sciences exp rimentales ainsi que dans bien d autres domaines on ne peut pas simplement se contenter d effectuer des mesures mais il est galement important de pouvoir caract riser celles ci comme par exemple via le calcul de moyenne m diane variance etc Un outil particuli rement utile dans ce contexte est l histo gramme dont le r le est de pouvoir tudier la distribution de valeurs r colt es Sa repr sentation la plus typique est sous forme d un graphique en b tons voir Figure 7 2 Etant donn e une liste L de valeurs suppos es r elles nous pouvons repr senter un histo gramme par un dictionnaire qui associe pour des gammes de valeurs donn es le nombre de valeurs pr sentes dans L et ayant une valeur comprise dans cette gamme Une application par ticuli re d un histogramme serait par exemple d tudier les points d tudiants un examen 33 O Q O o o O o 5 O S LL A Q O amp o T T T 0 0 02 0 4 06 0 8 1 0 1 2 1 4 1 6 1 8 20 22 2 4 Valeurs mesur es FIGURE 7 2 Exemple d histogramme illustr sous forme graphique sur base d
25. t insert 0 8 supprimer un l ment t remove 4 copier une liste concat ner 2 listes rechercher un l ment dans une s quence x in s 35 36 Exercices en s ance Ex 8 1 Trouvez la complexit au pire cas de la fonction suivante a b et c sont des vecteurs de taille n n def produit c a b n for i in rangel n for j in rangel n cli 3j 0 for k in range n c i j a i k x b k j Ex 8 2 Trouvez la complexit au pire cas du code suivant i 0 j 0 while j lt n t j n i i if i n 1 j 1 i 0 else i 1 EX 8 3 En faisant l hypoth se que n est positif donnez la complexit au pire cas du code suivant c 0 i nxn while i gt 0 j n while j gt 0 c 1 j j 4 i i 2 print c Ex 8 4 Trouvez la complexit au pire cas de la fonction suivante a est un vecteur de taille n n def symetrie a n sym True i 0 while i lt n and sym j 0 while j lt i and sym if ali j a j il sym False j 1 i 1 return sym Ex 8 5 Trouvez les complexit s au pire cas et minimale du code suivant en supposant que la fonction boolrand renvoie True ou False avec la m me probabilit et qu elle est de complexit constante 37 for i in rangel n vi True for i in range n 1 w i boolrand w n 1 False flag True j 1 while flag if v j w j for i in range j n 1 w i boolran
26. tester tous les cas possibles Ex 5 10 Ecrivez une fonction my_filter qui prend une liste 1st et une fonction f en param tres Cette fonction renverra une nouvelle liste constitu e des l ments de la liste 1st pour lesquels la fonction renvoie True Ex 5 11 Ecrivez une fonction my_enumerate qui prend une liste 1st en param tre Cette fonction renverra une liste de tuples deux composantes Chaque tuple devra avoir en premier l ment l indice et en deuxi me l ment le l ment de la liste 1st Veuillez tester votre programme et rep rer clairement ses limites d utilisation Ex 5 12 Ecrivez une fonction reduce qui prend en param tres une liste 1st une fonction deux param tres et un l ment e La fonction devra tre initialement appliqu e l l ment e et au premier l ment de la liste 1st Ensuite il faudra successivement appliquer la fonction f sur le r sultat du pr c dent appel de fonction et l l ment suivant de la liste Si la liste est vide le r sultat est e Exemple reduce somme 1 2 3 4 0 o somme est d fini par def somme a b return atb renverra 10 0 1 2 3 4 Ex 5 13 Ecrivez une fonction my_print qui prend en param tres une liste 1st et un tuple separator de taille 3 Les l ments de la liste devront tre des nombres entiers La fonction devra afficher une cha ne de caract res contenant dans l ordre 1 le premier l ment de separa
27. tre k et qui renverra une liste de points permettant d approximer une spirale d Archi m de Celles ci se caract risent par une quation en coordonn es polaires de la forme p 0 k8 o p est le rayon 0 est l angle et k est un nombre r el strictement positif qui caract rise la spi rale Une propri t de ces objets math matiques est d avoir une distance partout gale 2km entre les bras de la spirale formellement p 8 27 p 0 2kx Pour obtenir une liste de points partielle partir d une quation quelconque en coordonn es polaires p 0 l algorithme suivant peut tre utilis 1 Soit 0 0 2 Calculer d p 0 65 FIGURE A 1 Spirale d Archim de k 2 avec Turtle 3 Calculer le point x y correspondant par les relations x dcos 0 et y dsin 0 4 Augmenter de j et recommencer l tape 2 jusqu ce que 0 gt 207 Nous vous demandons enfin d crire une fonction dessin_spirale ayant deux para m tres une tortue t et le param tre k de la spirale et qui utilise les deux fonctions pr c dentes pour dessiner une spirale d Archim de de param tre k La Figure A 1 montre quoi ressemble le dessin d une spirale d Archim de de param tre k 2 Pour vous assister vous pouvez bien entendu faire appel aux objets ad quats du module math de Python savoir les fonctions cos sin et atan qui impl mente arctg ainsi que la constante pi N oubliez pas que les fonctions t
28. un mot de fileName l ensemble des mots dans le fichier de longueur Ici vous supposerez qu un mot est une s quence de caract res alphab tiques utilisez la m thode isalpha De plus mettez vos r sultats en minuscules gr ce la m thode lower EX 11 4 belongs to _dictionary est une fonction prenant en param tre une cha ne de caract res et v rifie si elle repr sente un mot qui figure dans la liste des mots contenus dans le fichier words txt auquel cas elle renverra True Sinon la fonction renvoie False Attention les mots du fichier words txt seront stock s ligne par ligne dans le fichier Ex 11 5 Reprenez la fonction trace M crite l exercice 6 3 p 26 et ajoutez y la cap ture avec une ou plusieurs exceptions des erreurs pouvant survenir dans le cas o la matrice ne serait pas adapt e pour le calcul de trace c est dire quand elle n est pas carr e ou que les l ments de la diagonale ne peuvent tre somm s par exemple si on a un m lange de nombres et de cha nes de caract res def trace M dimension len M if dimension len M 0 res None else res 0 for i in res return res range dimension M i i 51 Chapitre 12 Introduction aux classes Exercices pr paratoires Mati re r viser notions de classe instance attribut diff rence entre fonction pure et m thode d instance m thode _init__ __str__ __repr_
29. 6666667 44 ne 140 14 5 int 3 4 7 6 3 x 3 x 3 xx 2 81 7 3 2 0 2 2 8 print Il y a 31 jours en janvier Il y a 31 jours en janvier 9 print Chuck Norris was born in 1940 Chuck Norris was born in 1940 Ex 1 6 R solvez les probl mes suivants en crivant des petits programmes dans des fichiers s par s Cr ez d abord toutes les variables n cessaires tapez ensuite la formule en une seul ligne et affichez le r sultat 1 Le volume d une sph re de rayon r est donn par ar Quel est le volume d une sph re de rayon 5 Et de rayon 8 2 Le prix affich d un livre est de 24 95 mais vous b n ficiez d une r duction de 40 Par ailleurs les frais d envoi sont de 3 Quel est le prix total pour 60 livres Quel est le prix total de 50 livres si les frais d envoi sont de 5 et que vous b n ficiez d une r duction de 43 3 Si vous parcourez 10 kilom tres en 43 minutes et 30 secondes quelle est votre vitesse moyenne en miles par heure Quelle est votre vitesse moyenne en miles par heure si vous parcourez 10 kilom tres en 45 minutes Pour rappel 1 61 km 1 mile 1 heure 60 minutes et 1 minute 60 secondes 4 L dition compl te de la s rie Les comptes de Chuck Norris est compos e de 3486 volumes et se trouve dans ses armoires num rot es dans l ordre Si chaque armoire peut contenir au plus 89 livres dans laquelle se trouve le volume num
30. 8 45 renvoie 4 6 Notez qu un appel duree 6 0 5 15 renvoie 23 15 etnon 0 45 EX 3 9 M me exercice mais sans utiliser les instructions conditionnelles Ex 3 10 Ecrivez une fonction appliquer a b f qui prend 2 entiers et une fonction f a b en param tre et qui renvoie le r sultat de la fonction f a b appliqu e aux deux param tres a et b si ce r sultat est un entier None sinon 14 Ex 3 11 Ecrivez une fonction sum a b qui prend 2 valeurs et renvoie la somme de a et de b Par d faut la valeur de a est 0 et la valeur de best 1 Ex 3 12 Le n i me nombre de Bell not Bn est le nombre de partitions possibles d un ensemble de n l ments Il se calcule partir de la formule suivante n k 1 gt k Bn Z 1 k i n 2 kl 2 Gi On vous demande d crire la fonction bell n qui renvoie le n i me nombre de Bell Vous ne pouvez pas faire appel aux fonctions du module math Nous demandons galement que le code soit le plus efficace possible Module droite Pour cette s rie d exercices nous allons cr er un ensemble de fonctions permettant de manipuler des droites non verticales dans le plan euclidien Nous allons placer ces fonctions dans un module Veuillez cr er un script fichier nomm droite py et placez y l impl mentation des fonctions d crites ci dessous Pour rappel vos fonctions peuvent se servir des autres fonctions d j impl ment es Notations N
31. INFO F101 Programmation Syllabus d exercices R alis par l quipe du cours INFO FI01 D partement d Informatique Facult des Sciences Universit libre de Bruxelles dition 2015 2016 Remerciements et historique dition 2015 2016 dition UPyLab amp co Thierry Massart dition 2013 2014 r organisation des exercices cr ation de nouveaux exercices Liran Lerman Luciano Porretta et Nikita Veshchikov coordinateur du chantier Mohamed Amine Youssef dition 2012 2013 r organisation des exercices cr ation d exercices pr paratoires pas sage Python 3 Liran Lerman Markus Lindstr m coordinateur du chantier Luciano Por retta et Nikita Veshchikov Merci galement Marie Boulvain conseill re p dagogique du Centre de Didactique Sup rieure de l Acad mie universitaire Wallonie Bruxelles pour l aide la r daction de la pr face dition 2011 2012 cr ation chapitre Instructions de base et compl ments sur com plexit et invariants St phane Fernandes Medeiros Markus Lindstr m Na m Qachri et Alessia Violin dition 2010 2011 Big Bang passage de C Python 2 St phane Fernandes Medei ros Na m Qachri et J r me Vervier Relecture par Markus Lindstr m et Alessia Violin Remer ciements galement Hadrien M lot UMons pour nous avoir laiss nous inspirer des exercices de son cours pour r aliser cette dition Les exercices du chapitre Instruc
32. L ordre de tous les l ments diff rents de 0 ne dois pas changer tassementOrd 59 Exemple gt gt gt L 1 4 2 0 4 0 3 2 0 0 1 gt gt gt tassementOrd L gt gt gt print L gt gt gt 1L 4 2 4 8 2 1 0 0 0 01 gt gt gt L 1 4 2 0 4 0 3 2 0 0 1 gt gt gt tassementNonOrd L gt gt gt print L gt gt gt Isap yA 2r r 07r 00O Ex 13 9 crivez une fonction appartient qui prend deux arguments le premier est une cha ne de caract res le deuxi me est une liste de cha nes de caract res La fonction v rifie l appartenance de chaque l ment de la liste dans le premier argument Si le test est v rifi l l ment est ajout une premi re liste sinon il est ajout dans une autre liste La fonction renvoie ensuite les deux listes cr es Note la fonction ne peut pas faire appel la fonction find Ex 13 10 Examen Septembre 2006 Info f 206 Un nombre parfait est un nombre entier naturel qui est gal la somme de ses diviseurs y com pris 1 mais except lui m me On vous demande d crire une fonction nombre_parfait nbr qui renvoie la valeur bool enne true si nbr est un nombre parfait et la valeur false sinon Exemples de nombres parfaits 6 1 2 3 28 1 2 4 7 14 496 2 4 8 16 31 62 124 248 Ex 13 11 Examen bidon 2012 Info f 206 On consid re des cha nes de caract res dans l alphabet A C G T repr se
33. Nous allons utiliser un dictionnaire pour contenir les abbr viations et leur signification Nous vous demandons d crire une fonction substitue message abbreviation qui va renvoyer une copie de la cha ne de caract res message dans laquelle les mots qui figurent dans le dictionnaire abbreviation comme cl sont remplac s par leur signification va leur Exemple d utilisation 30 31 abbrev C Chuck INT TNOTELST y opt e counted r27 2 times inf infinity print substitue C N cpt 2 to inf abbrev Ex 7 2 Ecrivez trois fonctions addition a b qui renvoie la somme de a et b soustraction a b qui renvoie la diff rence entre a et b multiplication a b qui renvoie le produit de a et b Nous vous demandons aussi de r diger un script permettant l utilisateur d agir avec ces fonc tions selon son d sir Entrez deux valeurs a 9 b 6 Choississez A dditionner a et b Mjultiplier a par b S oustraire aa b Quitter Suivant la lettre entr e au clavier par l utilisateur pour son choix cl on effectuera alors l appel de la fonction correspondante en la s lectionnant dans un dictionnaire de fonctions valeurs Ex 7 3 Reprenez l exercice 4 7 p 18 et crivez une fonction equiv_canonique pre nant un nombre arbitraire de mots en param tres Votre fonction devra renvoyer un dictionnaire o chaque
34. a V i 1 Vi i 1 return i n 1 1 Exprimez en fran ais et en logique du premier ordre la condition n cessaire et suffisante sur le vecteur V pour que la fonction test renvoie la valeur True 2 Montrez que vsisi VE y VE est un invariant correct pour la boucle 3 D montrez la terminaison de la boucle Chapitre 10 R cursivit Exercices pr paratoires Mati re r viser la gestion de m moire stack frames les fonctions Pr p 10 1 Une fonction S n qui calcule la somme des n premiers entiers Ge Sn Pr p 10 2 Une fonction F n qui calcule la n me valeur de la suite F o F 0 F 1 et Fn Fn 2 Fn_1 Pr p 10 3 Expliquez les avantages et inconv nients des proc dures r cursives c est dire o on empile des appels r cursifs de fonctions vis vis des proc dures it ratives boucles Exercices en s ance Ecrivez les fonctions suivantes de mani re r cursive Ex 10 1 Une fonction ackermann m n qui impl mente la fonction d Ackermann A m n d finie comme suit n 1 sim 0 A m n 4 A m 1 1 sim gt 0etn 0 A m 1 A m n 1 sim gt 0etn gt 0 V rifiez que ackermann 3 6 donne 509 Que se passe t il pour de plus grandes valeurs Pourquoi Ex 10 2 Une fonction pgcd x y qui calcule le plus grand commun diviseur de deux entiers positifs x et y Pour cela utilisez la m thode d Euclide Cette m thode
35. a fonction plus def plus x y while y gt 0 x 1 y 1 return x D montrez que cette boucle calcule bien la somme de x et y dans x Pour ce faire montrez que l invariant du while est Inv y gt 0 A x y zo yo o zo et yo d notent les valeurs initiales de x et y respectivement et montrez la terminaison de la fonction On suppose initialement que y 0 Ex 9 13 La boucle suivante est cens e imprimer la valeur maximale de v D montrez que Inv VYj 0 lt j lt i lt n gt V i gt V j est un invariant correct pour la boucle i 0 while i lt n 1 if v i gt v i 1 v i v i 1 v i 1 v i i 1 print v n 1 Ex 9 14 Question de janvier 2003 On se donne la fonction suivante qui fait l hypoth se que le vecteur V pass en param tre est tri def f V x n len V bi 0 bs n 1 46 while bs gt bi and VIm x if VIm lt x bi m 1 else bs m 1 m bi bs 2 return m 1 Quelle est l utilit de cette fonction 2 Montrez que TS TS H 0 lt i lt nAV x gt bi lt i lt bs bi b A O lt bi lt n 1 A 1 lt bs lt n Am est un invariant correct pour la boucle 3 D montrez la terminaison de la boucle Ex 9 15 Examen de janvier 2005 Soit le code suivant qui suppose que n est une constante enti re strictement positive def test V n len V delta 0 i 0 while i lt n 1 and V i delta lt V i 1 delt
36. ant vos r ponses sans justification la r ponse est nulle def fuse t1 t2 if len t1 return t2 elif len t2 0 return t1 elif t1 0 lt t2 0 return t1 0 fuse t1 1 t2 else return t2 0 fuse t1 t2 1 Invariants Ex 9 9 V rifiez que 0 lt i lt n A j i x m est un invariant correct pour la boucle suivante on suppose que m et n sont positifs i 0 j 0 while i n j m i 1 Ex 9 10 Soit le morceau de code suivant on suppose que n est strictement positif et que V et W sont des vecteurs d entiers de dimension n i 0 S while i lt n s V i W i i 1 1 Expliquez en fran ais ce que fait cette boucle 45 2 Exprimez l aide d une formule logique les pr condition et postcondition de la boucle 3 D montrez que i 1 lt i lt n A s X Vi x Wi j 0 est un invariant correct pour la boucle 4 Servez vous de ces informations pour d montrer que la boucle fait bien ce que vous aviez pr vu en supposant qu elle se termine Ex 9 11 quoi sert la boucle suivante q 0 r jl while r gt j2 g 1 2 D montrez que cette boucle est correcte qu elle fait bien ce que vous venez de pr dire en supposant que j1 soit un entier positif et j2 un entier strictement positif Pour ce faire v rifiez que Inv r q x j2 j1 A q N r N est un invariant et donnez la postcondition du while Ex 9 12 Voici l
37. ap a b qui renvoie b a afin de pouvoir l utiliser comme suit a b swap a b Ex 3 2 Ecrivez une fonction distancePoints qui tant donn s deux points x1 y1 et 2 Y2 re us en param tres sous forme de tuples calcule et renvoie la distance euclidienne entre ces deux points Ex 3 3 Ecrivez une fonction Longueur xpoints qui prend en param tres un nombre arbitraire de points de coordonn es x y et calcule la longueur du trait correspondant Pour calculer la longueur il faut effectuer la somme de la longueur des segments qui composent le trait Un segment de droite est compos de deux points cons cutifs pass s en param tre Pour rappel la distance entre deux points x1 y1 et x2 y2 se calcule comme suit dist y z2 z1 y2 y1 Ex 3 4 Ecrivez une fonction parallelogramme qui re oit quatre points du plan en para m tres et renvoie le p rim tre du parall logramme correspondant Les points x1 y1 2 Y2 3 y3 et x4 ya correspondent au coin sup rieur gauche au coin sup rieur droit au coin in f rieur droit et au coin inf rieur gauche La fonction renvoie None si les c t s ne sont pas gaux deux deux Ex 3 5 Soit l quation du second degr ax Bx y 0 avec les param tres a 8 et y sont des valeurs r elles entr es par l utilisateur Ecrivez une fonction rac_eq_2nd_deg qui calcule et renvoie la ou les solutions s il y en a Le r sultat sera None s i
38. atrice d entiers initiali s e la matrice nulle et de dimension m x n Ex 6 2 crivez une fonction print_mat M qui prend une matrice en param tre et affiche son contenu Ex 6 3 crivez une fonction trace M qui prend en param tre une matrice M de taille n x n et qui calcule sa trace de la mani re suivante tr A 5 Aii i 1 Ex 6 4 Une matrice M m de taille n x n est dite antisym trique lorsque pour toute paire d indices j on a Mij m Ecrire une fonction bool enne antisym trique qui teste si une matrice est antisym trique Ex 6 5 crivez une fonction produit_matriciel A B qui calcule le produit matri ciel C de taille m x entre les matrices A de taille m x n et B de taille n x Le produit matriciel se calcule comme suit n 1 Cij X AixBrj k 0 26 27 Ex 6 6 crivez une fonction xor matriciel A B qui prend en param tres deux ma trices et B de m me dimensions de taille m x n et qui renvoie une matrice r sultant C contenant les l ments de A xor s aux l ments de B Cette fonction op re comme suit Cij Aij D Bi Vi j 0 lt i lt net lt j lt m Ex 6 7 crivez une fonction rotation_ gauche A qui prend en param tre une matrice sur laquelle elle effectue des rotations gauche sur chaque ligne Le nombre de d placements effectu s par la rotation est fonction du num ro de la ligne en question Autrement dit la ligne subit une rotation
39. ce vous allez avoir besoin de plusieurs images en format png A l aide de votre diteur d images pr f r cr ez des images en format png Par exemple GIMP est un excellent logiciel libre d dition d images Entre autres pr parez des images de tailles 500 x 500 pixels 800 x 800 pixels 800 x 600 pixels 600 x 800 pixels et 100 x 100 pixels N oubliez pas d apporter ces images au TP Pr p B 5 Que fait le code suivant Utilisez la fonction help pour vous renseigner sur les fonctions utilis es import os def test x return os path isfile x and x split 1 png L os listdir L list filter test L print L 66 67 B 1 Notions de base Nous allons vous demander de vous familiariser avec une biblioth que qui vous permet de cr er des programmes de traitement d images Pour importer la biblioth que ouvrir une image et l afficher il suffit d effectuer la suite d instructions suivantes gt gt gt import Image gt gt gt picture Image open nom de _ fichier gt gt gt picture show Ex B 1 Cr ez un dossier de travail pour la s ance mettez y des images ouvrez et affichez celles ci via l interpr teur Utilisez des images en png Vous remarquerez que le principe est le m me que pour l ouverture d un fichier via la fonction open Ex B 2 Les images poss dent des informations comme leur taille leur mode de couleur leur format etc Pour les r cup rer il s
40. chier ou s il existe vide ce fichier et crit la cha ne de caract res chaine dans celui ci Pr p 11 3 crivez une fonction ajouter nomFichier chaine qui ajoute la cha ne de caract res chaine la fin du fichier dont le nom est la cha ne de caract res nomFichier Pr p 11 4 Les fonctions manipulant des fichiers l vent en cas de probl me une exception de type IOError crivez un code principal utilisant la fonction crite l exercice pr paratoire Mjet qui g re correctement cette exception Ainsi si on tente d ouvrir un fichier inexistant en lecture votre code devra le signaler par un message d erreur l utilisateur plut t que de faire planter l interpr teur Pr p 11 5 Montrez quels seront les r sultats du code ci dessous Expliquez bri vement ce que doit contenir le fichier lu pour d clencher chacun des cas d exception try f open myfile txt s f readline i int s strip except IOError print I O error except ValueError 49 50 print Could not convert data to an integer except print Unexpected error raise Exercices en s ance Ex 11 1 crivez une fonction wc nomFichier qui doit ouvrir le fichier en question et renvoyer le nombre de caract res sans compter les caract res de retour la ligne le nombre de mots et le nombre des lignes du fichier Nous d finissons ici un mot comme tant une cha ne de caract res maximale r
41. cle suivante est elle susceptible de changer leur valeur Expliquez for e in x y e foo e 4 Pr p 3 7 Le code suivant est il correct def plus2 x Renvoie la valeur donn augmentee de 2 return x 2 On renvoie x 2 Pr p 3 8 Le code suivant est il correct def plus2 x Renvoie la valeur donn augmentee de 2 return x 2 On renvoie x 2 Pr p 3 9 Entrez la fonction de l exercice dans l interpr teur et entrez la commande help plus2 Expliquez ce qui se passe Quid si vous tapez help bar Pourquoi y a t il une diff rence en tapant plut t help bar Pr p 3 10 Qu affiche le code suivant Justifiez votre r ponse def f x x 3 f x print x Pr p 3 11 Qv aurait affich le code de l exercice si la fonction f tait plut t def f x x 3 return x Pr p 3 12 Qu aurait il fallu faire dans les exercices et pour que la variable x du code principal prenne la valeur 3 apr s l appel cette derni re fonction Pr p 3 13 Que fait la fonction suivante def f x xargs print len args print x x for arg in args print arg Essayez d appeler cette fonction avec divers param tres par exemple f f 4 f 1 2 3 4 5 Pr p 3 14 Le code suivant est il syntaxiquement correct Quelle est sa s mantique qdef f x y return x y x y print f y 3 x 4 13 Exercices en s ance Ex 3 1 Ecrivez une fonction sw
42. d else flag False j 1 Ex 8 6 Examen d ao t 2010 On se donne deux fonctions expobeta et expo qui calculent toutes les deux la valeur du param tre x lev e la puissance n On suppose x et n strictement positifs et on ignore les probl mes de d bordement 1 Donnez les complexit s aux pire et meilleur cas de ces deux fonctions sous la forme d un grand en fonction du param tre n 2 La fonction expo est elle plus efficace Expliquez def expobeta x n xl x for i in rangel l n x x x1 return x def expo x n xli x while 2xi lt n X X X while i lt n x x xl i 1 return x Ex 8 7 Examen d ao t 2009 Donnez la complexit au pire cas en fonction de n et en utilisant la notation des fonctions suivantes def f V n len V i 0 j 0 while i lt n while j lt i VJI i j j 1 i 3 38 def g V n len V i n 1 while i gt 0 V i 0 for j in range i 1 VIA 7 1 i s def h V n len V for i in range n V i 0 j n while j gt 1 V i ixj j 2 Ex 8 8 Examen de juin 2010 Donnez la complexit de la fonction fuse en tenant compte des diff rentes op rations et en justifiant vos r ponses def fuse t1 t2 if len t1 return t2 elif len t2 0 return t1 elif t1 0 lt t2 0 return t1 0 fuse t1 1 t2 else return t2 0 fuse t1 t2 1 Ex 8 9 Examen de janvie
43. de i positions Comment adapteriez vous cette fonction pour effectuer une rotation droite Ex 6 8 Examen de juin 2012 Soit un tableau A 3 dimensions plans lignes colonnes de taille m x n x q contenant des entiers quelconques et un tableau P de m me taille contenant des entiers compris entre 0 et m x n x q 1 tous distincts On vous demande de r organiser le tableau de la mani re suivante l l ment l indice a b c du tableau d origine devra apr s r organisation se trouver la position num ro P a b c du tableau A le tableau P est appel e tableau de permutation des l ments du tableau A Chaque l ment du tableau P l indice a b c contient la position o se trouvera l l ment a b c de A apr s l ensemble des permutations On d finit la position d un l ment comme l indice qu aurait cet l ment dans un vecteur qui serait constitu des l ments de mis c te c te Plus pr cis ment la Figure 6 1 vous montre les positions des diff rents l ments se trouvant dans un tableau de dimension 3 x 3 x 2 On y voit par exemple que l l ment A 0 2 1 c est dire premier plan troisi me ligne deuxi me colonne contient l entier 7 et est donc en position 7 L l ment A 1 1 0 quant lui est la position 12 LL L font FIGURE 6 1 Positions des diff rents l ments dans un tableau cubique On vous demande d crire un programme
44. de programmation utilis S ance s Les exercices en s ance sont encadr s par des assistants Ces derniers constateront si l tudiant a correctement pr par chaque s ance et s ils peuvent d s lors proposer des pro bl mes d algorithmique c est dire tant donn les outils fournis par le langage de program mation et leur mise en uvre comment peut on r soudre efficacement un probl me donn Algorithmique S ances Langage Pr paration Les motivations sous jacentes cette d coupe sont multiples L exp rience nous a montr que si les tudiants ne ma trisent pas la syntaxe et la s mantique du langage utilis ils ne sont d une part pas en mesure d crire des algorithmes dans ce lan gage mais d autre part ne sont pas non plus arm s pour comprendre les explications fournies par les enseignants vu l absence de vocabulaire commun Les rappels th oriques autrefois donn s en d but de TP ne semblaient pas servir d objectif concret les tudiants ayant d j compris la mati re perdaient leur temps tandis que les autres avaient souvent trop de lacunes que pour pouvoir utiliser efficacement l information fournie La pr paration de la mati re avant chaque s ance d exercices devrait pallier ce probl me tout en permettant aux assistants de r duire le temps pass pour des rappels th oriques et d ainsi pouvoir se concentrer sur la r solution d exercices et l ac
45. des valeurs enti res quelconques dans la matrice M carr e de c t n exprimez en logique du premier ordre la condition sur le contenu de M pour que le code renvoie un r sultat vrai Donnez galement la complexit au pire cas de l algorithme def condition M n len M found True i 0 while found and i lt n found False j 0 while not found and j lt n 1 k j 1 while not found and k lt n found M i j M i k k 1 j 1 i 1 return found Ex 9 7 Examen d ao t 2009 La fonction test ci dessous re oit un vecteur en para m tre et v rifie si celui ci satisfait une certaine propri t Donnez d abord en fran ais puis sous forme d une formule logique la propri t test e En d autres termes exprimez une condition n cessaire et suffisante sur le vecteur pour que la fonction test renvoie la valeur True 44 def test V n len V stop False if n lt 3 return True diff V 1 V 0 i 1 while not stop and i lt n 1 nvdiff V i 1 Vi stop diff gt nvdiff diff nvdiff i 1 return not stop Ex 9 8 Examen de juin 2011 L algorithme suivant fusionne 2 listes tri es 1 Exprimez en logique des pr dicats les pr conditions hypoth ses sur les param tres et la postcondition r sultats de la fonction fuse 2 Donnez la complexit au pire cas de la fonction fuse en tenant compte des diff rentes op rations et en justifi
46. dite infixe o l op rateur est plac entre les deux op randes par exemple 2 3 voir Figure 13 4 On vous demande d crire une fonction evaluate qui prend en param tre une liste expression et qui renvoie un entier result r sultat de l valuation de l expression repr sent e par expression La liste expression est structur e de la fa on suivante chaque l ment est un string chaque l ment repr sente soit un entier soit un op rateur les l ments se trouvent dans la liste suivant l ordre de la notation polonaise en d autres termes nous supposons que la liste est une expression valide Voici la liste des op rations possibles avec leurs repr sentations dans la liste somme diff rence x produit division enti re reste de la division 61 Expression 12 48 44 2 Notation polonaise correspondante 123 x 42 Repr sentation sous forme de liste LIEN LE EMA L Me AM m2 R sultat 7 FIGURE 13 4 Exemple notation polonaise repr sentation de l expression sous forme d une liste Vous pouvez supposer que la liste est correctement structur e c est dire que l ordre et le nombre d l ments sont corrects Votre fonction devra toutefois signaler par le biais d une ex ception l ventualit d une division par z ro Essayez d utiliser le moins de if else possible Vous ne pouvez pas utiliser la foncti
47. e jvervierQ lit ulb andre colon stud ulb thierry profs ulb Minfo lit ulb eric ramzi stud ucl bernard profs ulb jean profs ulb 32 donnerait le dictionnaire suivant lit ulb v rvi r info stud ulb andre colon profs ulb thierry bernard jean stud ucl lt eric ramzi EX 7 7 mini projet Un dictionnaire peut nous permettre de stocker un tableau partiel c est dire uniquement les cases remplies du tableau avec comme valeur le contenu de la case en question Voici un exemple X tr sor xX 0 O pi ge FIGURE 7 1 Exemple de tableau Le tableau ci dessus peut tre impl ment de la mani re suivante MY_PRESIOUS 1 TRAP 1 map map 1 1 MY_PRESIOUS map 2 3 TRAP map 4 5 TRAP map 1 3 TRAP map 3 2 TRAP On vous demande d impl menter les fonctions suivantes create_map size trapsNbr qui re oit en param tres deux nombres naturels size et trapsNbr sup rieurs ou gaux 2 et qui renvoie un dictionnaire repr sentant une carte de taille size x size dans laquelle on place trapsNbr pi ges et un tr sor de mani re al atoire utilisez le module random play_game mapSize map qui re oit une carte de taille mapSize x mapSize sous la forme d un dictionnaire tel que d crit pr c demment dans laquelle un certain nombre de pi ges et un tr
48. e inf rieur droit afficher un rectangle Ex 2 21 Refaire l exercice en supposant que n est impair et en dessinant des O sur les deux diagonales principales la place des X Par exemple pour n 7 X X X X X O X X X X O X X x XX O X XD O XX x x O X O x x O X x OX XX D lt Ex 2 22 Refaire l exercice sans utiliser de branchement conditionnel pas de if else Chapitre 3 Fonctions Exercices pr paratoires Pour les exercices sur le module droite veuillez revoir la g om trie euclidienne de base en particulier la manipulation de droites de la forme analytique y ax b Pr p 3 1 Quel est l effet des instructions suivantes a b 1 3 5 x y b a b b a Pr p 3 2 Y a t il une diff rence s mantique entre les instructions suivantes x y a b x y a b x y a b x y a b Pr p 3 3 Que vous donnent pour r sultat les instructions suivantes Expliquez 1 2 3 4 lt 1 2 3 4 0 1 2 3 4 lt 1 1 8 4 10 1 2 3 4 lt 1 1 2 3 4 lt 1 Pr p 3 4 Essayez l instruction suivante a b c input Entrez trois chiffres avec les donn es suivantes comme entr es 123 123 abc 1b3 1 Pr p 3 5 Que fait le code suivant t tuple range 10 for x in t print x 11 12 Pr p 3 6 En supposant que x et y sont des variables bien d finies la bou
49. e code doit utiliser les fonctions pr d finies min et max Ex 5 2 Comme pour l exercice pr c dant crivez une fonction bornes nombres qui re oit en param tre une liste de nombres et renvoie un tuple comprenant le maximum et le minimum des valeurs enti res pr sentes dans cette liste Ici votre code ne peut pas utiliser les fonctions pr d finies min et max Ex 5 3 Ecrivez une fonction my_pow qui prend comme param tres un nombre entier max et un nombre flottant b et qui renverra une liste contenant les max premi res puissances de b c est dire une liste contenant les l ments allant de b b 1 Si le type des param tres n est pas celui attendu votre fonction renverra la valeur None Ex 5 4 Ecrivez une fonction prime_ numbers qui prend comme param tre un nombre entier nb et qui renverra une liste contenant les nb premiers nombres premiers Nous vous demandons de penser aux diff rents cas pouvant intervenir dans l ex cution de la fonction Pour rappel un nombre premier b est un entier naturel qui admet que deux diviseurs distincts entiers et positifs b et 1 En d autres termes b est premier si il n existe pas d entiers naturels cet d diff rents de b et de 1 tel que b c x d Math matiquement on peut d finir un nombre premier b comme tant un nombre tel que b gt 2 fa 1 lt a lt b A b mod a 0 24 EX 5 5 Ecrivez une fonction my_insert qui prend une liste tri e sorted_ list
50. e le chronom tre a t arr t Une exception sera lev e s il est en train de tourner start qui relance le chronom tre qu il soit arr t ou non stop qui arr te le chronom tre get_elapsed_time qui renvoie le temps coul en secondes depuis le dernier lancement du chronom tre s il est en train de tourner ou le temps coul entre le dernier d part et le dernier arr t si le chronom tre a t arr t Contrainte utilisez le module time fourni par Python en particulier pour initialiser vos chronom tres utilisez la m thode time time Ex 12 2 Ecrivez une classe Monome Un mon me est un polyn me compos d un seul terme Par exemple 3r ou 7x ou encore 8 sont des mon mes Un mon me est caract ris par deux attributs son coefficient de type flaot et son degr de type naturel Votre classe devra donc comporter deux attributs une m thode d initialisation __init__ coefficient degre deux m thodes d acc s respectivement get_coefficient et get_degre qui renvoient les valeurs des attributs Enfin les m thodes __repr__et__str_ Votre classe devra donc comporter deux attributs une m thode d initialisation avec valeurs par d faut ainsi que deux m thodes d acc s getters qui renvoient les valeurs des attributs EX 12 3 D finissez les m thodes suivantes __add__ __ sub __ mul _ __truediv __ __floordiv_ le ler
51. es de caract res v et w On d finit l intersection de deux mots comme tant la plus grande partie commune ces deux mots Par exemple l intersection de programme et grammaire est gramm Ex 4 6 Ecrire une fonction trans text replaceA replaceB replaceA est un tuple oldA newA et replaceB est un tuple o1dB newB qui re oit trois param tres et renvoie le r sultat de la transformation suivante chaque occurrence du symbole o1dA dans la cha ne text est remplac e par la cha ne newA et chaque occurrence du symbole o1dB est remplac e par la cha ne newB Exemple gt gt gt print trans ABBAB A AB B BA gt gt gt ABBABAABBA EX 4 7 La m thode de chiffrement par d calage est une des premi res techniques utilis es pour chiffrer un message On appelle aussi cette technique le chiffre c sarien Dans cette m thode on d cale chaque lettre du message de k unit s Par exemple si k 3 la lettre A devient D par chiffrement De m me si l on consid re le mot BONJOUR nous obtenons avec un d calage de trois unit s le mot ERQMRXU Le d calage est circulaire un d calage de trois unit s sur la lettre X a par exemple pour r sultat la lettre Nous consid rons pour cet exercice que les messages ne sont compos s que de caract res alphab tiques majuscules et non accentu s Pour
52. eur du mot et r le nombre de tentatives restantes Pour le choix au hasard du mot nous vous demandons d utiliser la biblioth que randomet randint plus particuli rement Ex 13 4 Checksum mini projet Les donnes peuvent parfois tre perdu ou corrompu pen dant leur transmission On vous demande d impl menter un code d tecteur d erreur et un code correcteur d erreur Ces codes permettent de d tecter de de corriger les erreurs ventuelles de transmission Dans ce mini projet supposez que le fichier texte ne contient que des caract res 0 et des carac t res 1 et que tous les lignes ont la m me longueur 56 57 Code d tecteur L id e de ce code est d ajouter des informations redondantes dans le message Nous allons diviser le fichier en blocs et ajouter un bit chaque bloc pour que le nombre de bits 1 soit impaire Tous les nouveaux bits les bits de parit qu on calcule ainsi constituent un checksum 1 crivez une fonction addC hecksum filename qui lit le contenu d un fichier calcule le checksum et l ajoute la fin de fichier Prenez donc une ligne pour un bloc voir exemple 2 crivez une fonction veri fyChecksum filename qui lit un fichier avec le checksum et v rifie si le checksum est correcte renvoie True si c est le cas File 0 1 0001 0 0 Les bits de parit qu il faut ajouter O ligne 1 0 ligne 2 1 ligne 3 Apres l execution de addChecksum o OR
53. ez comment il serait possible de d chiffrer un message chiffr et quelle information devrait tre transmise entre l exp diteur et le destinataire pour que ce dernier comprenne bien le message Ex 4 8 Examen de janvier 2012 Le chiffre de Vigen re est une version am lior e du chiffre c sarien vu l exercice 4 7 Dans cet algorithme la clef n est plus un simple d calage dans l alphabet mais est un texte part enti re de longueur arbitraire A B CDE Z AJIA B C D E Z BIB C D E F A CIC D E F G B DID E F GH C E E FGH I D ZIZ A B CD Y TABLE 4 2 Extrait de la table de Vigen re Les lignes correspondent une lettre du texte clair les colonnes une lettre de la clef et les cases du tableau aux lettres correspondantes du texte chiffr Pour chiffrer un texte clair la main on utilise la table de Vigen re dont un extrait est donn dans la Table 4 2 Supposons que la clef choisie soit ABBA et que nous voulions chiffrer le texte clair ZED CAB Dans un premier temps nous tendons la clef en la concat nant elle m me jusqu ce qu elle ait la m me longueur que le texte clair en tronquant les ventuels caract res 20 Texte clair Z E D C A B Clef A B B A A BB Texte chiffr Z F E C B C FIGURE 4 1 Chiffrement par l algorithme de Vigen re superflus la clef ABBA devient donc ABBAABB car le texte clair est de longueur 7 Si la clef tait plus lon
54. g comment fonctionne l ins ruction break crire l quivalent des instructions suivantes sans instruction break i 0 while i lt 10 L 1 00 break print i i i 1 Ex 2 11 crire l quivalent des instructions suivantes sans instruction pass i 0 while i lt 10 if i pass elif i pass pass print i i i 1 Ex 2 12 Regarder dans le tutoriel Python sur le site python org comment fonctionne l ins ruction continue Ecrire l quivalent des instructions suivantes sans instruction continue for i in range 11 if i 2 print str i est pair continue print str i est impair Ex 2 13 crire l quivalent des instructions suivantes avec une boucle while a int input D int inout for i in range a b 1 print i Ex 2 14 Remplacez la boucle while une boucle for dans le code ci dessous a int input i 1 while i lt a Ex 2 15 Pour cet exercice vous ne pouvez pas utiliser d instruction i f crire un programme qui lit un nombre naturel n sur input et qui affiche successivement tous les nombres naturels l a entre 0 et n bornes non comprises de mani re croissante utilisez la boucle for 1 b idem 1 a mais utilisez la boucle while 2 a entre 0 et n compris de mani re croissante utilisez la boucle for 2 b idem 2 a mais utilisez la boucle while 3 a entre 0 et n compris de mani re d croissante utilisez la boucle for 3 b idem 3 a
55. gue que le texte clair de longueur n on la tronque pour ne garder que les n premiers caract res Ensuite pour chaque caract re du texte clair nous consultons la ligne correspondante dans la table dans la colonne du caract re de la clef la m me position et nous en tirons une lettre qui sera la lettre correspondante dans le chiffr La premi re lettre du texte clair Z restera donc Z dans le chiffr car chiffrer par la lettre A revient ne rien changer si nous consultons le tableau La seconde lettre du texte clair E se fera chiffrer par la lettre B la table nous indique que le caract re dans le chiffr correspondant sera donc F La Figure 4 T vous donne le chiffrement complet de ZED CAB par la clef ABBA Nous vous demandons d crire une fonction vigenere prenant deux param tres une cha ne de caract res plaintext ainsi qu une cha ne de caract res key Cette fonction de vra lire et chiffrer le texte clair donn par plaintext en utilisant la clef fournie et renvoyer le texte chiffr Vous pouvez supposer que le texte clair ne contient que des lettres majuscules ainsi que des symboles de ponctuation et des espaces Notez que si on rencontre autre chose que des lettres on laisse le caract re intact dans le chiffr voir comportement vis vis d un caract re espace en Figure T Vous pouvez utiliser les fonctions ord et chr vues l exercice 4 7 Nous vous encou
56. l n y a pas de solution r elle une liste avec une ou deux velaurs s il y a respectivement une ou deux solutions r elles EX 3 6 Dans le module random la fonction randint a b renvoie un nombre al a toire compris entre a et b inclus Ecrivez une fonction alea_dice qui g n re 3 nombres al atoires repr sentant 3 d s jouer six faces et qui renvoie True si les d s forment un 421 False sinon Ex 3 7 Consid rons les billets et pi ces de valeurs suivantes 20 10 5 2 1 Ecrivez une fonction rendreMonnaie qui prend en param tres un entier prix et un 5 uple 20 10 5 2 1 d entiers repr sentant le nombre de billets et de pi ces de chaque sorte que donne un client pour payer l objet dont le prix est mentionn La fonction doit renvoyer un S uple repr sentant la somme qu il faut rendre au client d compos e en billets et pi ces dans le m me ordre que pr c demment La d composition doit tre faite en utilisant le plus possible de billets et pi ces de grosses valeurs S il manque de l argent la fonction renverra None Ex 3 8 Ecrivez une fonction duree qui prend deux param tres debut et fin Ces derniers sont des couples dont la premi re composante repr sente une heure et la seconde composante repr sente les minutes Cette fonction doit calculer le nombre d heures et de minutes qu il faut pour passer de debut fin Exemple un appel duree 14 39 1
57. la condition sur le contenu de M pour que le code renvoie un r sultat vrai Donnez aussi la complexit au pire cas de l algorithme Justifiez vos r ponses def condition M MAX len M V False x MAX xMAX for i in range MAX for j in range MAX V M i j True n 0 while n lt MAX MAX and Vin n 1 return n MAX4xMAX 43 Ex 9 4 Examen de janvier 2010 Pour le code suivant sachant que les valeurs lues dans la matrice M de dimensions MAX x MAX sont toutes dans l intervalle 0 MAX x MAX 1 exprimez en logique du premier ordre la condition sur le contenu de M pour que le code renvoie un r sultat vrai Donnez aussi la complexit au pire cas de l algorithme Justifiez vos r ponses def condition M MAX len M found True k 0 while k lt MAX MAX and found found False i 0 while i lt MAX and not found j 0 while j lt MAX and not found found M i j k j 1 i 1 k 1 return found Ex 9 5 Examen de juin 2010 Soit une liste d entiers V n l ments n strictement posi tif Exprimez en logique du premier ordre que 1 V ne contient pas deux l ments de valeur gale 2 V est tel que ses l ments de valeur paire sont tri s par ordre croissant et ses l ments d indice impair sont tri s par ordre d croissant Ex 9 6 Examen de juin 2010 Pour le code suivant o n est une constante enti re stric tement positive et en ayant
58. lide mauvaises positions position d j compl te etc cette fonction renvoie explicitement None Cr ez une fonction finished morpion i j qui renvoie 1 si la partie n est pas ter min e 0 si la grille correspond une situation de match nul 1 si le joueur ayant plac le dernier pion a gagn la partie Un joueur emporte la partie s il y a une ligne une colonne ou une des deux diagonale qui ne contient que des jetons de ce joueur Cr ez une fonction play_morpion qui demande l utilisateur la taille de la grille et propose deux joueurs d effectuer une partie du Morpion Chapitre 7 Dictionnaires Exercices pr paratoires Mati re r viser syntaxe du dictionnaire d clef valeur fonctions len values keys items clear copy get op rateur in l exercice 4 7 p T8 Pr p 7 1 Parmi les instructions suivantes quelles sont celles qui engendrent une erreur Sans ces instructions erron es que contient le dictionnaire d la fin N I N D H i jis Nu lt o Il a n I Lo SO e I UW H 2 O O1 ND A Pr p 7 2 Devinez le r sultat de l op ration suivante sum set 1 1 1 2 1 1 2 3 5 8 Expliquez Exercices en s ance Ex 7 1 Dans un texte il nous arrive souvent de remplacer des mots par des abbr viations exemple bonjour par bjr
59. mult iple9 qui prend un param tre entier n 1 9 et qui renvoie le produit de n par 9 sous forme d une cha ne de caract res sans utiliser l op rateur de multiplication ni de boucles Ex 13 2 Ecrivez une fonction compress correspondante l exercice Ex 13 3 Pendu mini projet Nous vous demandons de d velopper un jeu du pendu Dans ce dernier le joueur essaie de deviner en un nombre limit de tentatives lettre par lettre un mot choisi par l ordinateur Ce dernier choisira au hasard un des mots contenu dans le fichier dictionary txt Le joueur n a droit qu dix tentatives infructueuses la 10 erreur le joueur a perdu chaque tape un r capitulatif de l tat du jeu c est dire le nombre restant de tentatives infructueuses les lettres d j jou es ainsi que le mot deviner dans lequel chaque lettre encore non trouv e est repr sent e par une ast risque doit tre affich avant le choix suivant de lettre du joueur chaque fois que le joueur entrera une lettre le programme v rifiera si ce dernier est dans le mot cach Si c est le cas il ajoute les nouvelles lettres d voil es sinon le nombre de tentatives restantes est d cr ment Si le nombre de tentatives restantes atteint 0 le joueur a perdu Si l enti ret du mot est d voil la partie est gagn e et le score est affich Ce dernier est calcul l aide de la formule suivante score f r o lest la longu
60. n change _ caracteres s i j t qui renvoie une cha ne de ca ract res identique s dans laquelle les caract res situ s entre la position i et bornes incluses ont t remplac s par la cha ne de caract res stock e dans t Si les bornes i et j sont invalides la fonction renvoie la cha ne vide Une fonction trouve_caractere s a qui parcourra la cha ne s lettre par lettre et renverra la position positive de la premi re lettre identique a rencontr e dans la cha ne S il n y aucune lettre a dans la cha ne de caract re la fonction renvoie 1 Ecrivez une fonction trouve _caractere_avec_find s a similaire mais qui utilise la m thode find ici a peut tre un string quelconque Ex 4 2 crivez les fonctions suivantes prenant toutes une cha ne de caract res en param tre sous la forme d un module appel userinput 1 convert_to_int qui si la cha ne de caract res repr sente un nombre entier effectue la conversion et renvoie l entier correspondant Si cette cha ne repr sente tout autre chose la fonction renverra None Conseil utilisation de la m thode isdigit appartenant au type cha ne de caract res 18 2 convert_to_float qui si la cha ne de caract res repr sente un nombre r el sans partie exposant renvoie le nombre r el Si cette cha ne repr sente tout autre chose la fonction renverra None Vous ne pouvez pas utiliser la fonction float Conseil Pour rappel un nomb
61. nglet Accessoires alternativement lancez l diteur dans le termi nal Sur une machine Mac utilisez TextWrangler Cr ez un fichier avec les commandes que vous avez tap es pour les exercices pr c dents dans le terminal Lancez encore un terminal et ex cutez le programme que vous venez d crire l aide de la commande python3 nom de _ fichier py positionnez vous d abord dans le bon dossier l aide des commandes cd et 1s Exemple d un tel fichier Mon fichier Python commandel commande2 commandeN Ex 1 4 valuez la main les expressions suivantes et essayez de deviner le type du r sultat Utilisez ensuite l interpr teur Python pour v rifier vos r ponses rappel type R solvez les exercices avec divisions en utilisant l op rateur puis l op rateur 1 14 14 1 6 9 1 0 2 0 18 7 1 3 2 x2 5 4 2 0 0 0 40 5 na um amp w D ICT 1 2 NI gt 3 Ex 1 5 Certaines des lignes de code suivantes contiennent des erreurs Il peut s agir d erreurs syntaxiques ou s mantiques et certaines lignes g n rent des exceptions Indiquez pour chacune d entre elles le type d erreur s il y en a ou le r sultat et expliquez bri vement V rifiez ensuite l aide de l interpr teur Le r sultat d sir par le programmeur est indiqu en gras 1 print Bonjour Bonjour 2 Dla x 340 blablabla 3 1 4 6 x 2 0 416666666
62. ntant des s quences ADN Une telle cha ne est dite compl mentaire d une autre si on obtient la deuxi me en rem pla ant chaque occurrence de la lettre par T T par G par C et C par G dans la premi re Par exemple les s quences ACCGAT et TGGCT A sont compl mentaires Ecrire une fonction qui re oit en param tre une liste de telles cha nes et renvoie une nouvelle liste dans laquelle les paires compl mentaires sont limin es Pour chaque paire compl mentaire pr sente dans la liste de d part seule la seconde cha ne de la paire sera conserv e dans la liste r sultat Par exemple la liste suivante ATCC ACGG TGCC ACC TAGG contient deux paires compl mentaires ACGG et TGCC d une part et ATCC et TAGG d autre part On doit liminer la premi re cha ne dans l ordre de la liste de chaque paire La liste renvoy e par la fonction sera donc TGCC ACC TAGG On supposera que toutes les cha nes de la liste de d part sont distinctes Ex 13 12 Examen Janvier 2013 On vous demande d impl menter la fonction alphaCount qui prend en argument une cha ne de caract res text Vous devez impl menter la fonction alphaCount de deux fa ons diff rentes 60 1 vous avez le droit d utiliser tous les outils fournis par Python 2 vous ne pouvez pas utiliser l operateur in les fonctions set list stri les m thodes s
63. nts sont indentiques Ex 3 19 intersection d1 d2 Entr e Deux droites d1 et d2 Sortie Un point d intersection de d1 et d2 s il existe None sinon Rappel Si les droites sont confondues choisir un point quelconque d une des droites Si elles ne sont pas confondues mais parall les alors il n y a pas d intersection Sinon l abscisse de b2 b Pintersection est donn e par n das t P ordonn e par yn azn b1 azz n b2 Ex 3 20 droite_normale d p Entr e Une droite d et un point p Sortie La droite perpendiculaire d passant par p Tp Rappel y y 2 a Ex 3 21 droite _ parallele d p Entr e Une droite d et un point p Sortie La droite parall le d passant par p Rappel y ax Yp at Ex 3 22 distance _ droite d p Entr e Une droite d et un point p Sortie La distance entre d et p Rappel distance euclidienne entre p et le point p qui est l intersection entre la droite d et la droite normale d passant par p Ex 3 23 symetrie_orthogonale d p Entr e Une droite d et un point p Sortie Le point qui est l image de p par la sym trie orthogonale d axe d Rappel Soit p l intersection entre la droite d et la droite perpendiculaire d passant par p Alors la sym trie orthogonale de p par d est le point p x 2 p p Yp 2 Yp Yp Ex 3 24 pour les f rus de maths Vous pouvez g
64. omes du Polyn me n ont jamais le m me degr et qu il y ai au moins un Mon me dans le polyn me cr _ repr_ qui donne pour un polyn me p une repr sentation normalis e de p dans le for mat Polynome Monome_1 Monome_2 o les Monome_ i sont les repr senta tions repr des mon mes de p par ordre croissant de degr _ str_ qui formate l affichage du polyn me en utilisant le formatage de l impression de Monome par ordre d croissant de degr gt gt gt p Polynome Monome 2 0 4 Monome 3 0 5 P Monome 9 0 0 Monome 11 0 1 gt gt gt print p 3 0 x 5 2 0 x 4 11 0 x 9 0 gt gt gt p Polynome Monome 9 0 0 Monome 11 0 1 Monome 2 0 4 Monome 3 0 5 gt gt gt q Polynome Monome 2 0 4 Monome 2 0 4 gt gt gt print q 0 0 gt gt gt q Polynome Monome 0 0 0 gt gt gt q Polynome Monome 2 0 4 Monome 2 0 4 Monome 35 0 1 gt gt gt print q 35 0 x 0 0 gt gt gt q Polynome Monome 0 0 0 Monome 35 0 1 gt gt gt r Polynome gt gt gt r Polynome Monome 0 0 0 gt gt gt Conseil Pour la d finition de la m thode __init__ un gather peut tre utile Ex 12 5 D finissez les m thodes __add__ et __mult sur la classe Polynome qui permettent de faire l addition et la multiplication entre deux polyn mes gt gt gt pl Polynome Monome 2 4 Monome 3 5 Monome 9 0 gt gt gt p2
65. on eval de Python Vous pouvez d finir d autres fonctions et crire du code en plus pour simplifier le code de la fonction evaluate Voici encore quelques exemples de liste expression Expression 1 1 1 il 1 Repr sentation sous forme d une liste r Mn Ra Meur Le mr LT NT WIT MAN R sultat 5 Expression C5 8 4 ER 2 4 8 Repr sentation sous forme d une liste SEM Mes EL JS LEE LEA wE MA 8 R sultat 24 FIGURE 13 5 Exemples Ex 13 14 Examen Janvier 2013 Le probl me de partition consiste d couper un ensemble d entiers L en deux partitions L et Lo tel que la somme des l ments du premier ensemble soit gale la somme des l ments du second Par exemple supposons que L vaut 10 4 9 5 3 7 Dans ce cas une solution au probl me de partition appliqu L est L qui vaut 10 9 et L qui vaut 4 5 3 7 En effet la somme des l ments de Z est la m me que la somme des l ments de Z2 Plus pr cis ment la somme est gale 19 dans les deux partitions On vous demande d crire une fonction partition qui r sout le probl me de partition Plus pr cis ment votre fonction prendra en entr e une liste d entiers L et renverra deux listes L1 et Lo l aide d un tuple L et Lo formeront une partition de L De plus la somme des l ments de L devra tre gale la somme des l ments de L Notez que chaque ensemble d
66. our chacune des 4 instructions d affichage print donner l ensemble des valeurs de a pour lesquelles celles ci seront ex cut es a int input L gt 0 if gt i if gt 2 print a 2 else print a 1 else print a else print Erreur Ex 2 5 crire le morceau de code qui si a est sup rieur 0 teste si a vaut 1 auquel cas il imprime a vaut 1 et qui si a n est pas sup rieur 0 imprime a est inf rieur ou gal 0 Ex 2 6 crire le programme qui lit en input trois entiers a b et c Si l entier c est gal 1 alors le programme affiche sur output la valeur de a b si c vaut 2 alors le programme affiche la valeur de a b si c est gal 3 alors l output sera la valeur de a x b Enfin si la valeur 4 est assign e c alors le programme affiche la valeur de a b x a Si c contient une autre valeur le programme affiche un message d erreur Ex 2 7 crire un programme qui imprime la moyenne arithm tique 2 de deux nombres lus sur input Ex 2 8 crire un programme qui imprime la moyenne g om trique V ab de deux nombres positifs de type float lus sur input Si un des deux nombres est n gatif imprime Erreur Ex 2 9 crire un programme qui lit deux nombres a et b sur input et qui calcule et affiche le nombre c tel que b soit la moyenne arithm tique de a et c Boucles simples Ex 2 10 Regarder dans le tutoriel Python sur le site python or
67. ous repr sentons une droite d dans le plan euclidien R par le tuple a b R de telle mani re ce que d y azr b De plus nous repr sentons un point du plan euclidien R par un couple de r els Impl mentez les fonctions suivantes en supposant que toutes les droites trait es sont telles que a 0 droites ni horizontales ni verticales Ex 3 13 daroite pl p2 Entr e Deux points distincts p1 et p2 Sortie Un tuple a b repr sentant la droite passant par p1 et p2 None si les deux points ont la m me abscisse Rappel a 2 et b y az y2 ax Ex 3 14 appartient d p Entr e Une droite d et un point p Sortie True si p d False sinon Rappel v rifier si yp a p b Ex 3 15 coefficient_angulaire d Entr e Une droite d Sortie Le coefficient angulaire de la droite d Rappel a est le coefficient angulaire d une droite y ax b Ex 3 16 intersection_abscisses d Entr e Une droite d Sortie Le point intersection de d avec l axe des abscisses Rappel 2 0 15 Ex 3 17 paralleles d1 d2 Entr e Deux droites d1 et d2 Sortie True si d1 et d2 sont parall les False sinon Rappel v rifier si les coefficients angulaires sont identiques Ex 3 18 confondues d1 d2 Entr e Deux droites d1 et d2 Sortie True si d1 et d2 sont confondues False sinon Rappel v rifier si les coefficients angulaires et les termes ind penda
68. ques Rappels de logique 1 i i Vi d i o est une formule logique fonction de i 2 a gt b gt c 4 aAb c 3 Priorit des op rateurs logiques A V gt 4 est associatif droite a b c est quivalent a b c Formes retenir 1 Vi 0 lt i lt n 2 M O lt Ki lt n A Propri t s respecter pour qu un invariant Inv d une boucle de condition C soit correct 1 Pre init gt Inv 2 Inv AC boucle gt Inv 3 Inv nC fin Post Preuve partielle prouver que l invariant d une boucle est correct Preuve de terminaison prouver qu avec les pr conditions et initialisations la boucle se ter mine toujours Preuve totale preuve partielle preuve de terminaison 41 42 Exercices en s ance Logique du premier ordre Ex 9 1 Exprimez en logique du premier ordre les affirmations suivantes vous supposerez que tous les vecteurs sont de taille n La variable v est positive ou nulle La variable v contient une valeur comprise entre 5 et 8 bornes incluses Si la variable v est positive alors la variable w est n gative ou nulle Le vecteur V ne contient que des valeurs positives ou nulles Au moins une case du vecteur V contient une valeur sup rieure ou gale 5 La variable v contient la somme des l ments du vecteur W La variable v contient la somme des i premiers l ments du vecteur W Les i premiers l ment
69. quisition de comp tences en algorithmique ii iii La pr paration individuelle des chapitres confronte l tudiant l interpr teur Python et lui permet de tester son comportement r el condition sine qua non pour la r alisation d exercices et la r ussite du cours Les s ances sont construites autant que possible pour que les exercices aient une difficult crois sante Les exercices d not s par une ast risque sont r put s de niveau examen tandis que ceux d not s par deux ast risques sont de difficult sup rieure ce qui serait demand un exa men Ces derniers exercices ont pour but de permettre aux tudiants le souhaitant de se d passer R gles du jeu L tudiant est tenu de pr parer chaque chapitre de ce syllabus de mani re individuelle en s ai dant du cours th orique Les exercices pr paratoires forment un pr requis n cessaire la com pr hension et la participation aux s ances d exercices Si l tudiant rencontre des difficult s qu il estime insurmontables dans le cadre des exercices pr paratoires il est invit contacter l assistant de son groupe par courrier lectronique au moins 24 heures avant la s ance compter un jour ouvrable Il est demand l tudiant de respecter le travail de ses condisciples aux s ances Les corrections d exercices ne seront pas syst matiquement fournies cela afin d viter que l tu diant vienne aux s ances uniquemen
70. r 2012 Donnez la complexit du code suivant o n est un param tre et mat une matrice de dimension n x n dont chaque l ment contient un string de taille n sum 0 for i in rangel n for j in range n if a in mat i j sum sum 1 Donnez la complexit du code suivant o n est un param tre i 2 while i lt n n i di i 39 Ex 8 10 Examen de juin 2012 Donnez la complexit au pire cas de l algorithme suivant en fonction de N def incseq V N len V i 0 k 0 maxseq 0 while i lt N 1 seq 1 j i done False while j lt N 1 and not done if V j gt V j 1 done True else seq 1 j 1 if seq gt maxseq maxseq seq k i i seq return k Ex 8 11 Examen de ao t 2015 Pour chacun des codes suivants en supposant que x et n sont des param tres de type entier naturel strictement positifs donnez les complexit s moyennes et maximales en terme de O des codes suivants en justifiant pr cis ment vos r ponses l t for i in range n n t tt i for i in t j 0 while j lt i print t j end j j print x 2 i i while i lt n print i i i 3 i 2 while i lt n print i i ixi 4 def power x n brecondition x gt 0 and n gt 0 postcondition renvoie x n result 1 40 while n 0 if n 5 2 0 result result x x n 1 xXx XxX n n 2 return result Sachant que
71. re entier est aussi un nombre r el dont la partie d cimale est gale 0 Les autres nombres r els qui ne sont pas entiers peuvent s crire sous la forme partie_enti re partie_d cimale pensez la m thode split sur les cha nes de caract res 3 is_one_word est une fonction qui prend un param tre si celui ci est une cha ne de caract res qui contient un seul mot renvoie True Sinon la fonction renvoie False 4 is_one_letter est une fonction prenant un param re si celui ci est une cha ne de caract res renvoie True si la cha ne de caract res repr sente une seule lettre Sinon la fonction renvoie False Ex 4 3 crivez une fonction plus_grand_bord w qui tant donn un mot w renvoie le plus grand bord de ce mot On dit qu un mot u est un bord de w si u est la fois un pr fixe strict c est dire non vide de w et un suffixe strict c est dire non vide de w Si w n a pas de bord la fonction renvoie la cha ne vide Exemple a et abda sont des bords de abdabda Le plus grand bord est abda Ex 4 4 crivez une fonction anagrammes v w qui renvoie True si et seulement si les mots v et w sont des anagrammes c est dire des mots qui comprennent les m mes lettres mais pas n cessairement dans le m me ordre Par exemple marion et romina sont des ana grammes Ex 4 5 crivez une fonction intersection v w qui calcule l intersection entre deux cha n
72. rictement positif n La fonction devra renvoyer une liste tri e tel qu utilis e par la fonc 34 tion histogramme et qui correspond n intervalles de m me taille telles que la borne inf rieure du premier intervalle est inf et que la borne sup rieure du dernier intervalle est sup Un exemple possible d ex cution en mode interactif serait le suivant gt gt gt L 1 0 3 10 0 5 9 8 12 gt gt gt I intervalles 7 9 5 4 gt gt gt histogramme L I p ALAT ZTS r 0 m A28 Sr L 25 7 3 TELs 2Sr orado t dy o S3 IDy Sepa 2 Vous ne pouvez pas utiliser la fonction sort pour vous aider Chapitre 8 Combplexit Exercices pr paratoires R visez le chapitre complexit du cours Pr p 8 1 Trouvez la complexit au pire cas du code suivant i 0 while i lt n tli 0 i 3 Pr p 8 2 Trouvez la complexit au pire cas de la fonction suivante a b et c sont des vecteurs de taille n n def somme c a b n for i in rangel n for j in range n c i j alillj b j i Pr p 8 3 Trouvez la complexit au pire cas du code suivant for j in range 4 for i in range n t i t i Pr p 8 4 Examen de janvier 2010 Donnez la complexit des op rations suivantes sur une liste Python en justifiant vos r ponses acc der un l ment d un indice donn x t i ajouter un l ment en fin de liste t append 3 ins rer un l ment
73. rigonom triques travaillent en radians et non en degr s Ex A 8 crivez une fonction permettant de dessiner des figures telles SES CE Ex A 9 crivez une fonction permettant de dessiner des figures telles Annexe B Python Imaging Library Exercices pr paratoires Mati re r viser les commandes en terminal 1s cd mkdir cp rm rmdir et autres Mode d emploi introductif pour les salles du NO4 et NO3 partie console Linux La biblioth que PIL ne supporte pas encore Python 3 on travaillera donc avec la version 2 de Py thon lancez python2 plut t que python3 dans le terminal Notez qu en Python 2 la syntaxe de la fonction print est l g rement diff rente on crit par exemple print Hello au lieu de print Hello Une autre diff rence est le mode de fonctionnement de la di vision en Python 3 l op rateur n existe pas le seul op rateur de division est Si les deux op randes num rateur et d nominateur sont de type int alors la division est enti re comme en Python 3 si au moins un des deux op randes est de type float alors l op rateur effectue une division r elle comme en Python 3 Pr p B 1 En utilisant l interpr teur python 2 faites l exercice 1 3 Pr p B 2 En utilisant l interpr teur python 2 faites l exercice 1 4 Pr p B 3 En utilisant l interpr teur python 2 faites l exercice 1 6l Pr p B 4 Pour cette s an
74. s du vecteur V sont inf rieurs 6 OO IN RER EME Tous les l ments du vecteur V sont inf rieurs ou gaux max gt max est la valeur maximale contenue dans le vecteur Le vecteur V contient toutes des valeurs diff rentes jani N Le vecteur V est tri de fa on croissante en es Les i premi res cases du vecteur V sont tri es de fa on decroissante P Les cases comprises entre les indices k et k2 du vecteur V sont tri es de fa on non decroissante n un Si la variable i est positive les i premi res cases du vecteur V sont tri es de fa on non decroissante sinon le vecteur V est initialis 0 16 La partie du vecteur V comprise entre les indices k et ko est tri e et il n existe pas de plus grande partie en terme de nombre de cases du vecteur qui soit tri e Ex 9 2 Examen d ao t 2010 Exprimez en logique du premier ordre que le vecteur V n composantes enti res d indices 0 1 n 1 1 est tel que toutes ses composantes except e celle d indice 0 ont une valeur qui est un multiple de la composante pr c dente 2 est tel que chacune de ses composantes a une valeur qui est un multiple de son indice correspondant Ex 9 3 Examen de janvier 2010 Pour le code suivant sachant que les valeurs lues dans la matrice M de dimensions MAX x MAX sont toutes dans l intervalle 0 MAX x MAX 1 exprimez en logique du premier ordre
75. se base sur l observation que si r est le reste de la division de x par y alors le pgcd de x et y est gal au pgcd de y et r Consid rez comme cas de base que le pgcd de x et 0 est x Ex 10 3 Une fonction factorielle n qui calcule et renvoie la factorielle de n not n Pour rappel nl 1x2x3 xn Ex 10 4 Une fonction puissance x n qui calcule et renvoie la n i me n N puis sance de x sans utiliser l op rateur x 47 48 Ex 10 5 Une fonction triangle_pascal i j qui tant donn deux entiers positifs i et j renvoie la valeur situ e la 1 ligne et la j colonne du triangle de Pascal Le triangle de Pascal voir Figure 10 1 est construit comme suit La valeur en 0 0 vaut 1 Pour toute case du triangle la valeur de cette case est la somme de la valeur situ e au dessus et de celle situ e au dessus gauche Pour toutes les autres cases consid rez une valeur nulle 0 1 2 3 4 5 OI 11 1 211211 31113131 411 416 1 5 FIGURE 10 1 Triangle de Pascal Ex 10 6 Une fonction contient n d qui renvoie True si et seulement si l entier positif repr sent par n contient le chiffre d 0 9 repr sent par d astuce utilisez la division enti re et le modulo Ex 10 7 Une fonction inverse n qui renvoie le miroir d un entier positif n Par exemple le miroir de 475 est 574 Ex 10 8 Une fonction est_multiple n
76. st bien accessible que fait le code suivant fd open test txt s fd readlines fd close for i in s print i strip Pr p 4 10 En supposant que le fichier test txt existe et est bien accessible que fait le code suivant fd S open test txt fd read while s print s strip S fd read fd close Pr p 4 11 Expliquez en termes de consommation de m moire quelles m thodes d acc s de fichier parmi celles montr es aux pr parations 4 8 sont efficaces et inefficaces Exercices en s ance Ex 4 1 crivez les fonctions suivantes sous la forme d un module appel stringmanip Dans tous les cas de figure vos fonctions doivent admettre des indices positifs et n gatifs 1 Une fonction caractere s i qui renvoie le i caract re de la cha ne de caract res s Si ce caract re n existe pas la fonction renvoie la cha ne vide Une fonction caracteres s i j quirenvoie une cha ne de caract res contenant les caract res compris entre la position i et la position j bornes incluses Si ces bornes sont invalides la fonction renvoie la cha ne vide Une fonction change _caractere s i a qui renvoie une cha ne de caract res identique s dans laquelle le i caract re a t remplac par le caract re stock dans a Si cette position est invalide ou que a contient plus d un caract re la fonction renvoie la cha ne vide Une fonctio
77. t avec la documentation et les diff rents filtres tudiez les modules ImageFont et ImageDraw essayez de les utiliser pour ajouter du texte dans une image
78. t pour recopier les solutions L tudiant aura sa disposi tion une plateforme interactive d apprentissage nomm e UpyLaB lui permettant de tester pour chaque exercice fourni son propre programme et d avoir une indication sur la validit de ce dernier La plateforme est accessible l adresse suivante http upylab ulb ac be UpyLaB permettra galement l quipe enseignante de suivre vos progr s et s il est insuffisant vous demander une remise niveau Notez qu UpyLaB ne renvoie pas a priori les r sulats de votre programme mais teste ce dernier par rapport une solution de r f rence Coordonn es des assistants L tudiant peut toujours contacter l assistant de son groupe en dehors des s ances d exercices en fixant un rendez vous pr alable par courriel Les coordonn es des assistants sont donn es par chacun d eux lors de la premi re s ance et sont galement disponibles sur l Universit Virtuelle http uv ulb ac be Des versions lectroniques du pr sent syllabus d exercices ainsi que des supports de cours et d anciens examens sont disponibles cette m me adresse Guidances Des guidances sont disposition de l tudiant partir du mois d octobre Toutes les informations relatives ce service sont disponibles l adresse suivante http www ulb ac be di quidances S ance introductive Contr le de flux 5 p on A es a pi pr on
79. t vaut 4 Pr p 5 8 Expliquez pourquoi le programme suivant affiche deux fois le m me r sultat L1 L2 L1 Li extend 1 2 L2 extend 3 4 print L1 L2 sep n Pr p 5 9 Quel r sultat affiche ce code Expliquez pourquoi L1 L2 L1 print L1 L2 print L1 is 12 Pr p 5 10 Quel r sultat affiche ce code Expliquez pourquoi L1 L2 print L1 12 print L1 is 12 Pr p 5 11 En supposant que L1 et L2 soient des listes vides distinctes quel est le r sultat des op rations suivantes Expliquez la diff rence entre les deux Ll append hello L2 extend hello Pr p 5 12 Que donne le code suivant Justifiez votre r ponse et d crivez la situation et son volution gr ce des diagrammes d tat 0 2 4 6 31 y 23 Pr p 5 13 Que donne le code suivant x Op 2 4 6 Pr p 5 14 Que donne le code suivant ex cutez le en mode interactif pour vous en assurer Expliquez leur comportement r rh rer dr r r rint s rint s 100 1000 x y z rint s 1005 100 0 A B print s print s 100 print s 100 uaua wanawa L ae i C3 Exercices en s ance Ex 5 1 Ecrivez une fonction bornes nombres qui re oit en param tre une liste de nombres et renvoie un tuple comprenant le maximum et le minimum des valeurs enti res pr sentes dans cette liste Votr
80. te v rifiez vos r ponses l aide de l interpr teur python3 Pr p 2 1 Qu crit sur output le programme suivant quand on lui fournit en input les valeurs 2et6 int input Pr p 2 2 Qu crit sur output le programme suivant quand on lui fournit en input les valeurs 2 6et47 int input int input b int input a print a b O p Pr p 2 3 Qu crit sur output le programme suivant quand on lui fournit en input les valeurs 2et6 b int input a int input a b 1 print a a b 1 print a a 1 print a a 1 Pr p 2 4 Qu crit sur output le programme suivant quand on lui fournit en input 1 les valeurs 2 et 6 2 les valeurs 8 et 3 3 les valeurs 3 et 3 a int input b int input if a gt b print a a b print a Pr p 2 5 Qu crit sur output le programme suivant quand on lui fournit en input 1 les valeurs 2 et 6 2 les valeurs 8 et 3 3 les valeurs 3 et 3 a int input b int input if gt Ds print a a b print a Pr p 2 6 Donnez la valeur des variables a b c arret test1 test2 et test3 apr s chacune des instructions ci dessous a 2 b 3 c 4 testl True test2 b gt a and c gt b test3 testl or test2 arret test3 and not test testl True b gt a and c gt b test3 testl or test2 arret or test2 c o u
81. tervalle 0 n utilisez la fonction randint 0 n Exemple d ex cution J ai choisi un nombre secret Quel est le secret 50 Non le secret est plus petit Quel est le secret 25 Non le secret est plus grand Quel est le secret 37 Bravo Le secret 37 est trouve en 3 essais Ex 2 18 On peut calculer approximativement le sinus de x en effectuant la sommation des n premiers termes de la s rie c est dire la somme infinie p g g R a a re o x est exprim en radians R crivez cette somme sous la forme sin x SFER i 0 On vous demande donc de trouver f i x crivez ensuite le code calculant de cette mani re la valeur de sin x o x est lu sur input Continuez l addition des termes successifs dans la s rie jusqu ce que la valeur d un terme devienne inf rieur en valeur absolue une constante par exemple 1075 not 1e 5 en Python Boucles imbriqu es Ex 2 19 crire un programme qui lit sur input une valeur naturelle n et qui affiche l cran un carr de n caract res X de c t comme suit pour n 6 X X X X X X X X X xK XK Xx xK XK x xK xK x xK x Xx xK xK x 10 EX 2 20 Variante de l exercice afficher le triangle sup rieur droit comme suit pour DH D D D K D PS K x D D autres variantes afficher uniquement le bord du carr afficher le triangle inf rieur gauche sup rieur gauch
82. tions de base introduit dans l dition 2011 2012 ont t inspir s par le syllabus du cours de Programmation anciennement Algorithmique et Program mation des ditions pr c dentes orient es vers le langage C auquel ont contribu Nadjet Benseba Emmanuel Dall Olio Martin De Wulf Gilles Geeraerts Jo l Goossens Christophe Macq Olivier Markowitch Thierry Massart et Patrick Meyer Cet ouvrage a galement servi de base principale pour les chapitres Complexit et Logique et invariants Informations importantes Les s ances d exercices de programmation servent plusieurs objectifs p dagogiques Ma triser les bases du langage de programmation Python dans des mises en situation D velopper l esprit logique et la capacit r aliser des algorithmes Mettre en pratique quelques bases d informatique th orique complexit logique et inva riants Inciter l tudiant travailler r guli rement Chaque chapitre du pr sent syllabus est s par en deux parties Pr paration Chaque chapitre exige l tude pr alable de pr requis typiquement de la ma ti re vue au cours ou ventuellement vue en secondaire ainsi que la r solution ventuelle d exercices pr paratoires Ceux ci forment une base pour la r alisation des exercices en s ance L objectif de la pr paration est de faire acqu rir l tudiant les l ments n cessaires de syntaxe et de s mantique du langage
83. tle left 90 turtle forward 100 V rifiez que ces commandes dessinent bien un angle droit Ex A 1 Modifier les commandes de sorte dessiner un carr Ex A 2 crivez une fonction square qui prend en param tre une tortue myTurt Le et qui lui fait dessiner un carr Appelez ensuite cette fonction en lui passant la tortue turtle en param tre 63 64 Ex A 3 Modifiez la fonction square en lui ajoutant un param tre length qui repr sentera la longueur des c t s du carr Testez votre fonction avec diff rentes longueurs Ex A4 Faites une copie de la fonction square et nommez la polygon Cette fonction prendra un param tre suppl mentaire n et devra dessiner un polyg ne r gulier n c t s Ex A 5 crivez une fonction circle qui prend en param tres une tortue myTurt le etun rayon r Cette fonction dessinera un cercle de mani re approximative l aide de la fonction polygon astuce faites en sorte que length x n circonf rence Ex A 6 crivez une version plus sp cifique de circle appel e arc qui prend un para m tre suppl mentaire angle exprim en degr s et d terminant la portion de cercle tracer Ex A 7 Examen de juin 2011 Il pourrait tre utile pour certaines applications de pouvoir utiliser la tortue en pr cisant plut t une liste de points dans le plan par laquelle elle doit passer Notamment une telle fonctionnalit permettrait de plus ais ment utiliser Turtle pour dessiner
84. tor 2 chaque l ment de la liste 1st en ins rant entre chaque l ment le deuxi me l ment de separator 3 le troisi me l ment de separator 25 Exemple gt gt gt my_print 1 2 3 4 gt affichera 1 gt 2 gt 33 5 gt 4 Ex 5 14 Ecrivez une fonction my_invert qui inverse en place l ordre des l ments dans une liste 1st qui lui est donn e en param tre sans utiliser une autre structure telle qu une autre liste Exemple my_invert 1 2 3 4 renverra 4 3 2 1 Ex 5 15 On se donne une liste qui encode une s quence t Chaque l ment de cette liste est un tuple de deux l ments le nombre de r p titions successives de l l ment x dans t et l l ment x lui m me Les l ments successifs r p t s forment la s quence t Ecrivez une fonction decompresse qui re oit une telle liste en param tre et renvoie la s quence sous forme d une nouvelle liste Exemple gt gt gt 11 4 1 2 2 2 test 3 3 1 b onJeur gt gt gt decompresse 11 LC CE he 2 002 Gest a TEESE A 3 S 35 bonjour 1 Chapitre 6 Matrices et tableaux Exercices pr paratoires Pr p 6 1 Qu affiche le code suivant L 0 0 0 M rbi L O 2 print M Pr p 6 2 Qu affiche le code suivant M 0 x3 3 M 0 0 2 print M Exercices en s ance Ex 6 1 crivez une fonction init _mat m n qui construit une m
85. uffit de faire gt gt gt picture size 2446 3720 Consultez de la m me mani re les attributs mode format format_description filename et d terminez quoi correspondent ces informations Ex B 3 Les images sont enregistr es avec la m thode save comme montr dans l exemple suivant gt gt gt picture save nom de _ fichier format _ du _ fichier On peut cr er ce qu on appelle des thumbnails c est dire des miniatures sur base d un tuple d terminant la taille de la miniature gt gt gt size 94 94 gt gt gt picture thumbnail size crivez une fonction traitement_par_lots liste_ noms directory qui prend en param tres une liste de noms de fichiers et un string contenant le chemin d un dossier La fonction devra ouvrir chaque fichier et en cr er un thumbnail de taille 128 x 128 qui sera sau vegard dans le dossier dont le chemin est fourni par directory B 2 Modifications et transformations g om triques Vous pouvez galement d couper une image partir d un rectangle d fini par les points su p rieurs gauches et inf rieurs droits Ce rectangle est d fini par un tuple contenant quatre va leurs x1 y1 x2 y2 et doit tre pass en param tre la m thode crop rectangle Vous pouvez redimensionner l image avec resize tuple et lui appliquer une rotation avec rotate degree Vous pouvez appliquer des sym tries orthogonales avec les appels la m thode transpose en
86. ur des strings sur des sets ou sur des listes La fonction alphaCount doit renvoyer un entier le nombre de lettres diff rentes uti lis es dans la cha ne text La fonction alphaCount ne doit pas compter les espaces les nombres ni les symboles de ponctuation Les majuscules et les minuscules sont consid r es comme la m me lettre e g les symboles b et B repr sentent la m me lettre Voir les exemples sur la Figure gt gt gt alphaCount bonjour gt gt gt 6 gt gt gt alphaCount acacia gt gt gt 3 gt gt gt alphaCount AaAaAa gt gt gt 1 gt gt gt alphaCount Buvez de ce whisky que le patron juge fameux gt gt gt 26 gt gt gt alphaCount Monsieur Jack vous dactylographiez bien mieux que votre ami Wol gt gt gt 26 gt gt gt alphaCount Python 3 alphaCount gt gt gt 10 FIGURE 13 3 Exemple les appels de la fonction alphaCount Notez qu il est possible d impl menter la fonction alphaCount avec une complexit en Of len text Vous pouvez supposer que tous les caract res sont en ASCII et que text ne contient pas de caract res accentu s Ex 13 13 Examen Janvier 2012 La notation polonaise est aussi connue sous le nom de notation pr fix e L id e de cette notation est simple on crit d abord l op rateur et ensuite les deux op randes par exemple 2 3 par opposition la notation classique

INFO-F101 : Programmation Syllabus d`exercices

Contents

Download Pdf Manuals

Related Search

Related Contents