Les conseils de Wouf
Beaucoup d’élèves entrant au lycée ont en effet des difficultés à manipuler les fractions, les racines carrées, les puissances, à factoriser des expressions… Ces notions, apprises au collège, sont mal assimilées, et le programme des classes de lycée ne prévoit pas de les retravailler en profondeur.
Cet ouvrage propose une remédiation pas à pas. Un code simple et mnémotechnique est associé à chacune des règles et rappelé dans toutes les corrections d’exercices. Il permet de se repérer et de comprendre ses erreurs.
Correction (et commentaire) de la séquence 1
Le plus beau compliment que je puisse faire à une femme est de lui dire : je suis aussi bien avec toi que si j'étais tout seul.
Jean Yanne
Vous pouvez relire cette séquence dans un nouvel onglet en cliquant ici
Pseudo-code :
Debut : La porte tq la porte est fermée dire toc toc toc si la porte s'ouvre entrer fin_si fin_tq fin
Logigramme
Si la porte n'est pas fermée...c'est qu'elle est ouverte !
Que pensez-vous de cette autre solution :
Logigramme
Oui cette variante est plus simple, et plus pertinente !
Ainsi la construction d'un logigramme aide à fixer les idées et à travailler une version simple et efficace d'un algorithme !
Maintenant, nous allons apprendre à un robot à faire des crêpes !
J'ai simplement cherché sur marmiton.org la recette d'une pate à crêpe :
- Etape 1 : Mettre la farine dans une terrine et former un puits.
- Etape 2 : Y déposer les oeufs entiers, le sucre, l'huile et le beurre.
- Etape 3 : Mélanger délicatement avec un fouet en ajoutant au fur et à mesure le lait. La pâte ainsi obtenue doit avoir une consistance d'un liquide légèrement épais.
- Etape 4 : Parfumer de rhum.
Logigramme
Votre pâte est maintenant prête. Il ne vous reste plus qu'à faire cuire vos crêpes
Etape 5 d'après marmiton
Faire chauffer une poêle antiadhésive et la huiler très légèrement. Y verser une louche de pâte, la répartir dans la poêle puis attendre qu'elle soit cuite d'un côté avant de la retourner. Cuire ainsi toutes les crêpes à feu doux.
Votre mission est de fabriquer, sur feuille blanche le logigramme de cette étape 5!
Les plus rapides d'entre-vous amélioreront le travail qui précède pour compter les crêpes, et annoncer le nombre de crêpes en fin de cuisson !
Les plus rapides des plus rapides réaliseront, après recherches, le logigramme symbolisant l'algorithme de conception d'une recette originale ! La recette la plus complète sera publiée sur la page dédiée aux travaux d'élèves et sur le Blog
Au cycle 4, les élèves s'initient à la programmation, en développant dans une démarche de projet quelques programmes simples, sans viser une connaissance experte et exhaustive d'un langage ou d'un logiciel particulier. En créant un programme, ils développent des méthodes de programmation, revisitent les notions de variables et de fonctions sous une forme différente, et s'entraînent au raisonnement.
Attendus de fin de cycle
- Écrire, mettre au point et exécuter un programme simple
Connaissances et compétences associées
Décomposer un problème en sous-problèmes afin de structurer un programme ; reconnaître des schémas. Écrire, mettre au point (tester, corriger) et exécuter un programme en réponse à un problème donné. Écrire un programme dans lequel des actions sont déclenchées par des événements extérieurs. Programmer des scripts se déroulant en parallèle. - Notions d'algorithme et de programme. - Notion de variable informatique. - Déclenchement d'une action par un événement, séquences d'instructions, boucles, instructions conditionnelles.
Exemples de situations, d'activités et de ressources pour l'élève
Jeux dans un labyrinthe, jeu de Pong, bataille navale, jeu de nim, tic tac toe. Réalisation de figure à l'aide d'un logiciel de programmation pour consolider les notions de longueur et d'angle. Initiation au chiffrement (Morse, chiffre de César, code ASCII...). Construction de tables de conjugaison, de pluriels, jeu du cadavre exquis... Calculs simples de calendrier. Calculs de répertoire (recherche, recherche inversée...). Calculs de fréquences d'apparition de chaque lettre dans un texte pour distinguer sa langue d'origine : français, anglais, italien, etc.
Repères de progressivité:
En 5e, les élèves s'initient à la programmation événementielle. Progressivement, ils développent de nouvelles compétences, en programmant des actions en parallèle, en utilisant la notion de variable informatique, en découvrant les boucles et les instructions conditionnelles qui complètent les structures de contrôle liées aux événements.
- python.org Le site officiel, pour télécharger Python !
- Apprenez à programmer en Python avec Openclassrooms
- Un programme Python pour publier du code Python sur une page web
- logigramme_svg, utilitaire de transcription de pseudo code en logigramme
- Wikibooks : Le module Turtle
- A la découverte de Turtle sur zestedesavoir.com
- snakify : La boucle for
- ARCHIVES
Travaux d'élèves :
La page dédiée
Robot Blue-Bot
Blue-Bot est un robot autonome spécialement conçu pour une utilisation scolaire. Le robot : 125,00 €Pack 6 robots + station d'accueil : 759,00 €
NEWS
- Page : https://site2wouf.fr/algorithme2019-2020_s2.php
- Catégorie : Informatique
[4/6] Pourquoi les graphes hamiltoniens sont-ils difficiles ?
Précédemment dans « Cultivons-nous… Hamilton »
Une ville traversée par un fleuve. Sept ponts. Et une promenade impossible.
Dans le prologue de cette série, l’héritage d’Euler nous avait appris qu’un problème de parcours pouvait parfois être résolu sans essayer le moindre itinéraire. Pour savoir s’il était possible de traverser chaque pont exactement une fois, il suffisait de regarder les degrés des sommets. Quelques nombres pairs ou impairs, et le verdict tombait.
Puis un nouveau personnage est entré en scène. Dans Hamilton et le jeu icosien, les arêtes ont cédé la vedette aux sommets. Il ne s’agissait plus d’emprunter chaque passage, mais de visiter chaque lieu une seule fois avant de revenir au point de départ. Le décor semblait familier. Les règles, elles, venaient de changer.
Le deuxième épisode, Euler contre Hamilton, révélait alors le véritable piège. Euler permet souvent de diagnostiquer un graphe en examinant ses degrés. Hamilton oblige à construire un parcours dont tous les choix doivent rester compatibles jusqu’au dernier sommet. Un déplacement parfaitement autorisé peut préparer une impasse qui ne se révélera que beaucoup plus tard.
Dans le troisième épisode, deux théorèmes semblaient enfin offrir une issue. Lorsque le graphe est suffisamment bien connecté, Dirac ou Ore peuvent garantir qu’un cycle hamiltonien existe avant même que nous ayons commencé à le chercher. À l’inverse, certains obstacles structurels permettent parfois d’affirmer immédiatement qu’aucun cycle n’est possible.
Mais entre ces deux certitudes subsiste une immense zone grise.
Le cycle existe peut-être.
Peut-être pas.
Et cette fois, les théorèmes ne diront rien de plus.
La théorie a parlé. Puis elle s’est tue.
Il ne reste plus qu’un graphe, une multitude d’embranchements et une question inquiétante : combien de parcours faudra-t-il examiner avant de connaître la vérité ?
Du silence des théorèmes à la forêt des choix
Un théorème comme celui de Dirac ou d’Ore ressemble à un raccourci spectaculaire. On lui présente un graphe, on vérifie quelques conditions sur les degrés, et la conclusion tombe : un cycle hamiltonien existe. Nul besoin de le construire, encore moins d’examiner tous les parcours possibles.
Mais lorsque ces conditions ne sont pas satisfaites, il ne faut surtout pas conclure trop vite. Le théorème ne dit pas que le cycle n’existe pas. Il dit seulement qu’il ne peut pas nous le garantir.
C’est une nuance logique essentielle.
Ne pas disposer d’une preuve d’existence n’est pas disposer d’une preuve d’impossibilité.
Imaginons un graphe dans lequel aucun sommet n’est isolé, aucune coupure évidente ne condamne le parcours et où les degrés restent pourtant insuffisants pour appliquer Dirac ou Ore. Le dessin semble prometteur. Plusieurs chemins s’offrent immédiatement à nous. Certains paraissent même presque dessiner un cycle.
Alors nous choisissons un sommet de départ.
Deux voisins sont accessibles. Nous en sélectionnons un. Depuis ce nouveau sommet, trois directions deviennent possibles. Puis deux autres. À chaque étape, il faut avancer sans revisiter un sommet déjà utilisé, tout en conservant l’espoir de rejoindre finalement le point de départ.
Le problème ne vient pas de la difficulté de chaque décision prise isolément. Choisir un voisin parmi deux ou trois possibilités paraît anodin. Ce sont les conséquences cumulées de ces choix qui deviennent redoutables.
Une branche peut sembler parfaitement viable pendant longtemps. Le parcours visite presque tous les sommets, contourne plusieurs obstacles et paraît toucher au but. Puis, à quelques étapes de la fin, un sommet reste prisonnier à l’écart du cycle. Il n’est plus possible de l’insérer sans repasser par un sommet déjà visité.
Il faut alors revenir en arrière.
Pas seulement d’un sommet, parfois. Le mauvais choix peut avoir été effectué beaucoup plus tôt, à un embranchement qui paraissait sans importance. On défait donc le dernier déplacement, puis le précédent, jusqu’à retrouver une décision encore modifiable. On emprunte une autre branche et l’exploration recommence.
C’est le principe du retour sur trace, ou backtracking, déjà rencontré dans l’épisode précédent. Cette méthode permet d’éviter de poursuivre un chemin dès qu’il est manifestement condamné. Elle est plus intelligente qu’une énumération aveugle de tous les ordres possibles.
Mais elle n’est pas magique.
Dans certains graphes, les impasses apparaissent très vite : l’exploration élimine alors de nombreuses branches presque immédiatement. Dans d’autres, les mauvais parcours ne révèlent leur faiblesse qu’après avoir visité une grande partie des sommets. Le programme peut alors consacrer beaucoup de temps à explorer des pistes qui semblaient toutes raisonnables.
Le dessin initial se transforme peu à peu en un arbre invisible. Son tronc représente le sommet de départ. Chaque embranchement correspond à un choix possible. Chaque nouvelle décision fait naître d’autres branches, qui se divisent à leur tour. Certaines s’interrompent rapidement. D’autres s’enfoncent très loin avant de finir en impasse.
Et quelque part, peut-être, une branche referme enfin le cycle.
La difficulté du problème hamiltonien se cache dans cette forêt des choix. Elle ne saute pas toujours aux yeux sur le dessin. Deux graphes presque semblables peuvent demander des efforts de recherche très différents. Une seule arête ajoutée ou retirée peut ouvrir un raccourci décisif, condamner une famille entière de parcours ou repousser très loin le moment où une erreur devient visible.
Nous voilà donc face à une question plus précise. Ce n’est plus seulement :
Existe-t-il un cycle hamiltonien ?
Mais aussi :
Combien de choix faudra-t-il explorer pour le trouver — ou pour comprendre qu’il n’existe pas ?
Pour mesurer l’ampleur du problème, il suffit maintenant d’ajouter quelques sommets.
Quelques sommets de plus, des millions de parcours
Au premier regard, ajouter un sommet à un graphe paraît être une modification modeste. Un point supplémentaire, quelques arêtes nouvelles, rien qui semble devoir bouleverser le problème.
Pourtant, dans une recherche hamiltonienne, ce sommet ne vient pas simplement s’ajouter à la fin d’un parcours. Il peut prendre place avant le deuxième sommet, après le troisième, entre deux sommets déjà choisis… Chaque nouvelle position possible se combine avec toutes les organisations précédentes.
L'explosion...
Le nombre de parcours envisageables ne grandit donc pas régulièrement. Il explose.
Prenons le cas volontairement extrême d’un graphe complet à n sommets : chaque sommet y est relié à tous les autres. Une fois le sommet de départ fixé, tous les ordres de visite sont possibles. Il faut cependant éviter de compter plusieurs fois le même cycle : commencer la lecture à un autre endroit ne crée pas un nouveau cycle, et parcourir celui-ci dans le sens inverse ne change pas davantage son tracé.
Le nombre de cycles hamiltoniens distincts est alors donné par :
\dfrac{(n-1)!}{2}Le point d’exclamation désigne ici une factorielle. Ainsi, la factorielle de 7 correspond au produit de tous les entiers de 1 à 7. Cette opération possède une redoutable particularité : sa croissance devient très rapidement vertigineuse.
| Nombre de sommets | Nombre de cycles hamiltoniens distincts |
|---|---|
| 8 | 2 520 |
| 10 | 181 440 |
| 12 | 19 958 400 |
| 15 | 43 589 145 600 |
| 20 | 60 822 550 204 416 000 |
Entre huit et dix sommets, le nombre de cycles est multiplié par 72. Avec seulement deux sommets supplémentaires, nous passons de quelques milliers de possibilités à près de deux cent mille.
- À douze sommets, il faut déjà compter près de vingt millions de cycles distincts.
- À quinze, plus de quarante-trois milliards.
- À vingt, le nombre dépasse soixante millions de milliards.
Travailler... pendant 2000 ans
Imaginons une machine capable d’examiner un million de parcours chaque seconde, sans jamais ralentir et sans commettre la moindre erreur. Pour parcourir la dernière ligne du tableau, elle devrait travailler pendant près de deux mille ans.
Le détective avait commencé son enquête avec quelques suspects. Il se retrouve désormais face à une foule plus nombreuse que tout ce qu’il pourrait interroger au cours d’une vie.
Dans les problèmes combinatoires, quelques éléments supplémentaires peuvent transformer une recherche raisonnable en exploration démesurée.
Il faut toutefois interpréter ce tableau avec prudence. Un graphe complet n’est pas un exemple difficile pour trouver un cycle hamiltonien : puisque toutes les arêtes existent, presque n’importe quel ordre de visite convient. Le tableau ne mesure donc pas directement le travail nécessaire pour résoudre ce cas particulier.
Révelation
Il révèle autre chose : la taille de l’univers dans lequel une recherche naïve pourrait être contrainte de se déplacer. Dans un graphe quelconque, une grande partie de ces ordres est éliminée parce que certaines arêtes manquent. Mais il reste parfois un nombre immense de parcours partiels qui semblent possibles avant de conduire à une impasse.
Supposons par exemple qu’un programme ait déjà visité dix sommets. Plusieurs prolongements restent disponibles. Il en choisit un, puis un autre, et poursuit jusqu’à ce qu’un sommet devienne inaccessible. Il revient alors au choix précédent, essaie une autre branche, avance de nouveau… Chaque échec élimine une possibilité, mais il peut rester derrière lui des milliers, des millions ou des milliards d’alternatives encore inexplorées.
C’est ici que l’apparence du graphe peut devenir trompeuse. Un dessin comportant vingt sommets tient facilement sur une feuille. L’œil humain les embrasse tous en une seconde. Pourtant, les ordres dans lesquels ils peuvent être visités forment un espace gigantesque, impossible à représenter sur cette même feuille.
Le graphe visible reste petit.
L’arbre des choix, lui, devient colossal.
Cette croissance explique pourquoi une méthode qui fonctionne parfaitement sur dix sommets peut devenir inutilisable ...
lien vers l'article sur wouf blogTIPS
