![[hacker emblem]](/static/hacker-emblem.png "A glider in Conway's Game of Life")
Votre évaluation sera basée sur ce projet, et en mesure mineure sur votre participation et interaction pendant le cours. Le projet est obligatoire.
La date limite pour la soumission est le 20 novembre.
Le projet est individuel. Je n'accepterai aucune soumission en binôme ou en groupe.
Votre code doit marcher. Tout projet qui ne marche pas du tout parce qu'il contient des erreurs syntaxiques sera noté 0 (zéro). Ce n'est pas acceptable de soumettre du code qui n'a pas été testé.
Je vais évaluer votre style aussi, mais le style n'est pas prioritaire par rapport à la fonctionnalité.
Il y aura une soutenance orale le 26 novembre, également obligatoire. Quand même, la soutenance orale ne sert qu'à me convaincre que vous êtes vraiment les auteurs de votre code. Elle peut durer quelques secondes ou quelques minutes, jusqu'à quelques dizaines de minutes selon les cas. Vous n'avez pas besoin d'«étudier» pour la soutenance : vous devez juste connaître votre code, et savoir justifier vos choix.
Vous avez étés bien agréables et je n'ai aucune raison particulière pour douter de votre honnêteté, mais puisque j'ai eu des expériences très négatives autrefois je me permets d'énoncer explicitement ces règles ; ou bien, en substance, une seule règle : la triche ne sera pas tolérée.
Chacun doit être l'auteur du 100% du code qu'il envoie, avec une seule exception : vous avez le droit de réutiliser et modifier le code que j'ai écrit pendant le cours et publié sur la page web du cours.
Si vous soumettez du code écrit par n'importe qui sauf vous-mêmes et moi, votre note sera 0 (zéro) car vous n'aurez pas respecté cette spécification explicite. De plus, je vais aussi convoquer un conseil de discipline. Un mauvais étudiant et juste un mauvais étudiant, mais un tricheur essaye de gagner malhonnêtement un diplôme qu'il ne mérite pas (en réduisant aussi la valeur des diplômes mérités), et mérite donc une punition exemplaire. Je considère aussi la triche comme un insulte à mon intelligence.
Les étudiants peuvent bien sûr discuter entre eux et parler du projet ; on peut partager des idées, mais pas du code. N'essayez pas d'offusquer du code copié pour le faire sembler différent : je vais le voir.
Vous pouvez m'envoyer vos fichiers Python (le fichier ou les fichiers .py), et les autres fichiers dont j'aurais besoin pour exécuter vos programmes (probablement aucun pour la majorité des étudiants) par email. Je vais ignorer toute soumission en format non exécutable, par exemple sur papier ou en quelque format ridicule comme .pdf — oui, j'ai vu des étudiants qui ont essayé de faire ça pour cacher le fait que leur code ne marchait pas ou avait été copié.
Veuillez attacher vos fichiers à soumettre à votre email, en spécifiant aussi votre prénom et nom. Incluez le texte [Projet Intro Prog] dans le sujet.
Particulièrement si vous avez choisi une solution exotique et l'interface n'est pas évidente (ce qui ne devrait pas arriver), vous pouvez m'expliquer comment on exécute le programme dans votre email. Je dois le faire marcher sur mon ordinateur.
Si vous compressez les fichiers, s'il vous plaît utilisez le format .zip ou .tar.gz.
Je vais confirmer chaque réception par email.
Vous pouvez choisir un problème à résoudre entre :
Les deux sujets ne sont pas de la même difficulté.
Un étudiant qui va résoudre correctement le problème de la reconnaissance de la langue en utilisant la notion de distance que j'ai décrit, ou une solution également élaborée, peut obtenir 20/20. Une solution approximée (plusieurs étudiants ont proposé des idées) peut valoir jusqu'à 17/20 si très fiable — je vais tester votre solution en utilisant des textes que vous n'avez pas, écrits dans les mêmes langues. Une approximation raisonnable mais moins bonne peut valoir jusqu'à 15/20.
Le problème du code de sécurité sociale martien peut valoir jusqu'à 14/20 pour une solution parfaite, avec des tâches optionnelles. Une solution correcte sans des contrôles de correction optionnels ne vaut plus que 10/20.
J'ai publié sur la page du cours des fichiers Python que j'ai généré automatiquement, contenant chacun la définitions d'une liste de mots dans une langue, avec des répétitions. Chaque liste est en fait le texte complet d'un roman, sans espaces ni ponctuation, coupé en mots.
Le problème consiste à reconnaître, étant donnée une liste de mots similaire à un des échantillons donnés (mais pas nécessairement identique), la langue du texte.
Je souhaiterais avoir une fonction principale words_to_language qui accepte comme paramètre une liste de mots, et renvoie le nom de la langue comme résultat. Par exemple je pourrais essayer votre code dans l'interprète intéractif de la façon suivante :
>>> words_to_language (['Bonjour', 'le', 'monde']) 'French' >>> words_to_language (['Ich', 'möchte', 'Dich', 'zum', 'Abendessen', 'einladen']) 'German'
C'est acceptable si votre fonction donne un résultat plus fiable sur des textes de taille plus importante. Bien sûr je ne demande pas de reconnaître juste les mots de cet exemple : je vais utiliser des autres textes, typiquement beaucoup plus longs — par exemple, de la même taille d'un chapitre.
Vous avez le droit de modifier mes fichiers et copier leur contenu dans votre soumission ; par exemple, c'est plus facile de travailler avec une variable spanish_words, une autre variable english_words, une autre variable french_words etc., toutes définies dans un seul fichier. Vous pouvez faire ces changements si vous voulez.
La solution que j'ai proposé, et qu'a terrorisé tout le monde, consiste à utiliser mes listes de mots pour calculer une table de fréquence par langue, qui associe à chaque lettre la proportion des ses occurrences dans le texte. Par exemple, si dans le texte le 13.03% des caractères sont des e minuscules, la table associera e à 0.1303.
Une table de fréquence est facile à exprimer en Python en utilisant un dictionnaire. En fait vous n'avez rien de difficile à faire. J'ai déjà écrit le code pour générer une table à partir d'une liste de mots! Cherchez la fonction words_to_frequency_table dans le fichier seance6-letters.py. Dans ipython3 je peux faire:
In [1]: run seance6-letters.py
In [2]: run english.py
In [3]: words_to_frequency_table (words)
Out[3]:
{'D': 0.00016301349250137935,
't': 0.09142549029442745,
'B': 0.0004075337312534484,
'H': 0.0008652254601996288,
'o': 0.07552227015097557,
'e': 0.13033869187942018,
'Y': 5.642774740432362e-05,
'S': 0.0004921753523599338,
'd': 0.042254978181271004,
'M': 0.000347971108993329,
'G': 0.00030721773586798415,
'Q': 3.1348748557957567e-06,
'n': 0.06983560716256207,
'J': 0.0002821387370216181,
'R': 0.00021944123990570296,
'O': 0.00036364548327230776,
'm': 0.02379683503034559,
'u': 0.029467823644480112,
'f': 0.026082158800220696,
'k': 0.005529919245623714,
'C': 0.0004388824798114059,
's': 0.05894191703867182,
'V': 6.896724682750664e-05,
'c': 0.025875257059738175,
'z': 0.00044515222952299743,
'b': 0.015843657521191754,
'K': 4.702312283693635e-05,
'r': 0.05842152781260972,
'T': 0.002473416261222852,
'w': 0.024035085519386067,
'W': 0.0009467322064503185,
'A': 0.0015643025530420825,
'é': 3.1348748557957567e-06,
'q': 0.0008464162110648543,
'N': 0.00034170135928173747,
'/': 3.1348748557957567e-06,
'a': 0.07502695992375984,
'v': 0.010768295129658424,
'L': 0.0001880924913477454,
'P': 0.000811932587651101,
'i': 0.06415834879871596,
'g': 0.021931584491147113,
'l': 0.03784107438431058,
'x': 0.0021035010282389527,
'p': 0.018533380147464515,
'[': 3.1348748557957567e-06,
'h': 0.05877263379645885,
']': 3.1348748557957567e-06,
'U': 0.00015360886793399208,
'I': 0.0037931985755128655,
'F': 0.00022257611476149872,
'y': 0.01665245523398706,
'E': 0.0002633294878868436,
'j': 0.0007147514671214325}
La solution que j'ai décrit consiste à générer une table de fréquence par langue en utilisant mes fichiers. La fonction words_to_language générera une autre nouvelle table en utilisant son paramètre, et cherchera la table de fréquence plus proche de la nouvelle table parmi les tables des langues connues.
La seule difficulté est la définition d'une distance entre deux tables de fréquence, mais j'ai décrit informellement une solution : la distance entre la table t1 et la table t2 est donné par la racine carrée de la somme des carrés de chaque différence entre les deux fréquences des lettres correspondantes. En supposant que les lettres ne soient que a, b, c et d la distance serait sqrt (square (frequency_table_1['a'] - frequency_table_2['a']) + square(frequency_table_1['b'] - frequency_table_2['b']) + square(frequency_table_1['c'] - frequency_table_2['c']) + square(frequency_table_1['d'] - frequency_table_2['d'])).
C'est effectivement une distance Euclidéene en n dimensions, où chaque dimension est une lettre ; en le disant encore plus explicitement c'est une variante du théorème de Pythagoras où au lieu d'avoir une distance linéaire sur chacune de deux ou trois dimensions, on a une distance linéaire sur chaque lettre. Le concept de distance Euclidéene en n dimensions est bien expliqué ici : cherchez «Definition», jusqu'à «n dimensions». On peut calculer la distance entre deux tables de fréquences avec une fonction Python, qui fait une boucle sur toute lettre.
Je recommanderais de construire une seule liste all_letters contenant une seule copie de chaque lettre connue en toute langues. Calculer une distance devient facile comme ça, en faisant une seule boucle for sur all_letters.
Attention au cas où une table ne contient pas du tout une certaine lettre — c'est à dire, en Python, not (letter in frequency_table) : dans ce cas la fréquence de la lettre sera zéro. Il faut contrôler explicitement si letter in frequency_table est vrai ou faux : l'évaluation de frequency_table[letter] échouera avec une erreur si letter n'est pas une clé de frequency_table.
On peut utiliser la même technique des tables de fréquence au niveau des mots, au lieu des lettres. Dans ce cas par exemple le mot the aurait une fréquence élevée en anglais, mais zéro ou très faible dans les autres langues. Dans ce cas aussi j'ai déjà fait la majorité du travail, en vous donnant le fichier seance6-words.py.
Plus brutalement, on peut ignorer les listes de mots que j'ai donné et simplement essayer de conter dans la liste reçu par words_to_language certaines mots qui sont très communes dans une langue mais pas dans les autres — certains articles et prépositions sont des bons candidats. Plusieurs étudiants travaillent déjà sur des variantes similaires qu'ils ont proposé. Ces solutions ne mériteront pas 20/20, mais on peut quand même obtenir des bonnes notes de cette façon : jusqu'à 17/20 pour une bonne solution.
[Novembre 2018: ce sujet est aussi accepté pour la dernière édition du cours de 2018]
Tout citoyen de la planète Mars a un code de sécurité sociale qui contient des information vaguement similaires à celles des codes de sécurité sociale français, encodées d'une façon différente.
Le problème consiste à écrire un programme qui, dans une boucle infinie :
Si un code saisi contient des erreurs un programme bien fait devrait informer l'utilisateur en expliquant exactement le problème.
Chaque martien a un nombre de tentacules variable de 2 à 9 et un nombre d'antennes variables de 0 à 2.
La majorité des martiens ont un des quatre sexes biologiques principales : Foo, Bar, Qux et Norf. Il existe aussi des individus intersexuels de plusieurs types dits collectivement Xiq, et des individus déclarant publiquement que le gouvernement ne devrait pas s'occuper de leur sexualité, qui se font enregistrer comme Wuf.
Chaque individu a exactement trois parents biologiques, tous de sexe différent (Xiq ici est considéré comme un sexe). Toute combinaison de trois sexes différentes parmi les quatre principaux plus Xiq sont possibles et fertiles (on ne peut avoir plus qu'un Xiq parmi les trois parents). C'est aussi possible que parmi les trois parents d'un individu il y ait un, deux ou trois parents biologique Wuf, car on ne connaît pas le sexe biologique associé à ce genre.
Un individu peut être marié avec un nombre d'épouxs variable de 0 à 5, sans aucune restriction de sexe biologique ou de genre. Le mariage est encodé dans le code de sécurité sociale, qui change après chaque mariage ou divorce.
Mars est divisé en 97 divisions administratives dits secteurs, numérotées de 0 à 96.
Les prénoms martiens sont composés en n'utilisant que les six voyelles a, e, i, o, u et y. Les martiens ont tous un prénom, mais les noms n'existent pas.
Par convention un an martien dure exactement 1.8808 fois un an terrestre non bissextile. On compte les ans martiens à partir de 0, et on les écrit typiquement en trois chiffres : par exemple, 086. Le début de l'an martien 0 corresponde à la date terrestre 1 Janvier 1952.
Le code est une chaîne de caractère de taille fixe composées par des lettres majuscules ASCII (sans accents) et des chiffres décimaux.
Le code a toujours exactement 45 caractères. Dans l'ordre on a :
Les données sur les épouxs sont toujours alignées à gauche : s'il y a des champs ZZZZ, ces champs sont toujours les derniers.
Vous devez écrire une boucle infinie qui demande à l'utilisateur de saisir un code de sécurité sociale martien, analyse ce code et affiche les informations contenues. Vous devez vérifier la correction de la taille du code saisi, et ne pas accepter des lettres où le format demande des chiffres, ou le contraire.
Essayez de vérifier la correction du format plus en profondeur.
Je l'ai toujours dit au cours et montré, mais il faut répéter cette suggesion : divisez votre programme en fonctions, et testez-les indépendemment. Par exemple, on pourra avoir une fonction qui prend comme paramètre le champ prénom (une chaîne de 5 caractères). On a aussi plusieurs champs ayant la même structure (parents, époux) : bien sûr on devrait partager le code.
Un programme où la logique est toute dans la boucle principale sans aucune fonction auxiliaire devient rapidement impossible à gérer. Même corriger des simples erreurs de distractions, qui arrivent toujours, vous coûterait très cher.
Vous avez des conditions d'erreur à vérifier ? Testez-les dans des fonctions auxiliaires renvoyant des résultats booléens.
Pour chaque champ écrivez une fonction qui, étant donné comme paramètre le code complet, renvoie le champ (une sous-chaîne). Une façon simple de calculer une sous-chaîne est utiliser l'opérateur crochets sur les chaînes (Par exemple s[10]) pour sélectionner des caractères, et l'opérateur + pour concaténer plusieurs chaînes d'un seul caractère.
Ce projet est très très simple, mais il faut bien structurer le code. Il y a essentiellement une seule boucle, mais plein de tests. Qu'est-ce qu'on fait en cas d'erreurs ? Si on utilise des fonctions auxiliaires on peut facilement utiliser return pour sortir par avance de la fonction qui affiche les données décodées. On peut aussi renvoyer des résultat booléens pour représenter une condition de succès/échec. Quelques étudiants plus ambitieux peuvent aussi essayer d'apprendre les exceptions en Python, et les utiliser.
Revenir à la page principale du cours.
Luca Saiu — IUT de Villetaneuse, Département Réseaux et Télécommunications
Mis à jour le 27 novembre 2018.