PartageDeProjets:BacACompost

Espace de partage de projets.

Zone d'archive de «non-projets». Voici des idées intéressantes d'exercices ou d'activités permettant de développer des savoir-faire au delà des savoirs à transmettre en ISN, mais qui ne sont pas de fait des projets. Ces éléments sont issus du bac à sable et complètent les idées du bac à grains et du bac à fleurs car il est aussi utile de regarder des contre-exemples de projets.

---

Des idées qui en tant que telles se limitent à des exercides de programmation

Ces idées ne sont pas en soit des projets au sens développé ici mais des applications du cours, elles peuvent néanmoins servir d'engrais à de nouvelles idées de projet et montrent que les pistes ne manquent pas.

Algorithmes de plus court chemin

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : L'algorithme de parcours d'un graphe en largeur d'abord permet de déterminer s'il existe un chemin entre deux sommets d'un graphe et de calculer un plus court chemin, si ces deux sommets sont effectivement reliés. L'algorithme de Roy-Warshall-Floyd va plus loin en déterminant, une fois pour toutes, s'il existe un chemin entre toutes les paires de sommets d'un graphe et en calculant un plus court chemin pour chaque paire de sommets effectivement reliées. On programmera cet algorithme à partir de son decriptif et suggèrera des applications.

Programmer un générateur d'exercices de calcul mental

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Le programme choisit aléatoirement une opération et deux nombres, et vérifie la réponse de l'utilisateur. On peut ensuite poser une série de questions et compter le score total. On pourra enfin prévoir plusieurs niveaux de difficulté selon les opérations proposées ou la taille des nombres à calculer, et laisser l'utilisateur choisir son niveau de difficulté ou attribuer des scores variables aux réponses.

Mettre en place un Mastermind

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Écrire un programme qui lit deux tableaux de quatre éléments au clavier et indique le nombre d'éléments en commun dans ces deux tableaux. Écrire un programme qui joue au Mastermind : tire au hasard la la combinaison secrète et répond aux propositions de l'autre joueur.

Toucher à la bio-informatique

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Chercher sur le Web ce qu'est un brin d'ARN messager et comment il code pour une protéine. Écrire un programme qui détermine la protéine pour laquelle un brin d'ARN messager code.

Écrire un programme de bataille navale avec plusieurs bateaux.

• → source : Le «manuel ISN, Dowek etal 2012».

Poésie surréaliste.

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Chercher sur le Web, ou dans une bibliothèque, ce qu'est le recueil Cent mille milliards de poèmes de Raymond Queneau. Écrire un programme qui affiche ces cent mille milliards de poèmes.

Programmer le moteur d'un site de rencontres

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Programmer le moteur d'un site de rencontres, sur le principe suivant. Chaque personne inscrite sur le site répond à un questionnaire de personnalité dont les réponses sont des entiers entre 1 et 10. On stocke les réponses dans un tableau à double entrée : la case de la ligne i et de la colonne j contient la réponse de l'inscrit numéro i à la question numéro j. Pour mettre en relation un nouvel inscrit avec une personne déjà inscrite, on parcourt ce tableau en recherchant la ligne qui contient les réponses les plus proches de celles données par le nouvel inscrit. Pour déterminer si des réponses sont proches, on pourra par exemple compter le nombre de réponses identiques, calculer le total des différences, etc. On pourra enfin, à partir d'un tableau déjà rempli, chercher à former autant de couples que possible.

Toucher à la chimie numérique

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Programmer une boîte à outils pour automatiser les différents calculs que l'on a l'occasion de faire en chimie : durée d'une réaction, pH d'une solution, masses et concentrations, équilibre d'une équation-bilan simple, etc.

Calculs exacts sur des entiers ou des rationels

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : En représentant chaque nombre par un tableau qui contient la suite de ses chiffres, écrire une bibliothèque de fonctions permettant de faire du calcul sur des entiers de taille arbitraire, sans les dépassements de capacité que génère l'utilisation du type int. Proposer ensuite un type permettant de représenter une fraction en valeur exacte et écrire une bibliothèque de fonctions pour effectuer des calculs en valeur exacte sur des fractions. Rechercher sur le Web ce qu'est la méthode de Héron pour calculer une valeur approchée d'une racine carrée et la programmer en utilisant da bibliothèque de calcul sur les fractions.

Correcteur orthographique

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Réaliser un correcteur orthographique. Un tel programme prend en entrée un fichier texte, le découpe en mots, cherche chaque mot dans un dictionnaire et donne la liste des mots qui ne sont pas dans le dictionnaire.

Cryptage de César

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Écrire un programme qui déchiffre automatiquement un message codé selon la méthode de César sans connaître la valeur du décalage a priori. Rechercher ce qu'est le chiffre de Vigenère, et écrire un programme qui code un message selon ce principe. Rechercher une méthode pour décoder un message codé selon ce principe sans connaître la clé utilisée, et écrire un programme qui effectue ce décodage.

Simuler des circuits électroniques

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Pour construire et simuler des circuits, on peut utiliser logiciel Logisim disponible à l'adresse : http://ozark.hendrix.edu/~burch/logisim. Ce logiciel libre fonctionne sur la plupart des ordinateurs. Il n'est pas encore traduit en français, mais il est très bien documenté : on peut commencer sa lecture par le tutoriel. En utilisant ce logiciel, on peut par exemple construire le multiplexeur et les circuits de décalage définis au chapitre 13 et le compteur huit bits défini dans ce chapitre.

Simuler une unité centrale de calcul

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Écrire un programme permettant de simuler le comportement du processeur avec un programme écrit dans le langage machine décrit dans ce chapitre. Ce programme lira dans un fichier le contenu de la mémoire, qui contient également le programme à exécuter. Il affichera l'état de la mémoire et des registres au fur et à mesure de l'exécution du programme.

Observation du réseau

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Utilisation du logiciel Wireshark. Installer et lancer le logiciel. Capturer des paquets ethernet ou wifi depuis la carte réseau et afficher leur contenu à l'écran. Quelles sont les adresses MAC utilisées pour la destination et la source de chaque paquet? Quels ordinateurs sont identifiés par ces adresses ? Quelle est la taille de chaque paquet ?

Prouver la correction d'un algorithmee

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : On considère un algorithme qui calcule le successeur d'un nombre entier naturel n, c'est-àdire le nombre n + 1. Cet algorithme est similaire à celui de l'addition, mais il s'applique à un unique nombre : il procède de la droite vers la gauche en posant un chiffre et en propageant une retenue à chaque étape. Identifier les fonctions booléennes qui à un chiffre binaire et une retenue associent le chiffre à poser et la retenue à propager. Programmer cet algorithme et démontrer sa correction en suivant les lignes de la démonstration de correction de l'algorithme de l'addition, disponible dans un manuel ISN. Pour aller plus loin : dessiner un circuit booléen qui ajoute 1 à un nombre binaire de quatre bits.

Expérimenter un automate programmable : le jeu de la vie

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Projet. Le jeu de la vie. Sur un damier carré, on dispose des créatures de manière aléatoire. La population évolue d'un état au suivant selon les règles suivantes; – une créature survit si elle a 2 ou 3 voisines dans les 8 cases adjacentes et elle meurt à cause de son isolement ou de la surpopulation sinon, – une créature naît dans une case vide s'il y a exactement 3 créatures dans les 8 cases voisines, et rien ne se passe dans cette case sinon. Proposer une simulation d'un tel sytème dynamique et en s'aidant du Web, programmer des vaiseaux, des navires et des clignotants. Donner un panorama de l'étude de tels systèmes en sciences numériaque.

Etudier le jeu de TicTacToe

• → source : Le «manuel ISN, Dowek etal 2012».
• → descriptif : Un joueur de Tic-tac-toe. Le Tic-tac-toe est un jeu où deux joueurs placent à tour de rôle l'un des ronds O et l'autre des croix X sur un plateau de trois cases sur trois cases, jusqu'à ce que l'un des joueurs ait aligné trois symboles ou que les neuf cases soient remplies. C'est le joueur O qui commence. Décrire ce jeu sous forme d'un ensemble d'états et d'un ensemble de transitions. Combien y a-t-il d'états possibles ? Un état du jeu peut être gagnant pour O, gagnant pour X, match nul ou en cours de jeu. Exprimer chacun des 39 états à l'aide d'un nombre entier. Construire un tableau qui pour chacun de ces états indique s'il est gagnant pour l'un des joueurs, nul ou en cours de jeu et, dans ce cas, les transitions possibles pour chacun des joueurs. Calculer ensuite, de proche en proche, les états dans lesquels – le joueur O est certain de gagner, – le joueur X est certain de gagner, – le joueur O est certain de gagner ou de faire match nul, – le joueur X est certain de gagner ou de faire match nul. Écrire un programme qui joue contre un joueur humain et montrer finalement que ce jeu n'a aucun intérêt.