Algorithme au cycle 4 -Séquence 11 - Python, longueur et angle, le module turtle(1)

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.

Algorithme au cycle 4 -Séquence 3 - Python, longueur et angle, le module turtle(1)

Le module turtle est un ensemble d'outils permettant de dessiner à l'aide d'instructions simples.

Code Python traduit en HTML:

from turtle import *

forward(100)
right(90)
forward(100)
left(90)
forward(200)

tortue_1.0.0.py

Les principales fonctions du module turtle sont :

reset() On efface tout et on recommence
goto(x,y) Aller à l'endroit de coordonnées x et y
forward(distance) Avancer d'une distance donnée
backward(distance) Reculer
up() Relever le crayon (pour pouvoir avancer sans dessiner)
down() Abaisser le crayon (pour pouvoir recommencer à dessiner)
color(couleur) Couleur peut être une chaîne prédéfinie ('red', 'blue', 'green', etc.)
left(angle) Tourner à gauche d'un angle donné (exprimé en degré)
right(angle) Tourner à droite
width(épaisseur) Choisir l'épaisseur du tracé
fill(1) Remplir un contour fermé à l'aide de la couleur sélectionnée (on termine la construction par fill(0))
write(texte) texte doit être une chaîne de caractères délimitée avec des " ou des '

Vos missions : (faire des programmes séparés)

Construire un carré
Construire un triangle équilatéral
Construire un rectangle non carré
Construire un losange non carré
Construire un hexagone régulier
Construire un escalier à 3 marches
Construire un escalier à 10 marches, avec une boucle !
Construire le même escalier mais sans contre-marches
Construire le drapeau français
Ecrire un mot en dessinant les lettres.

Chaque mission est évaluée !

Pour les plus rapides :

Vous pouvez des recherches sur la toile sur le module Turtle de Python.

Utilisez correctement ces informations pour créer une oeuvre personnelle !

Exemples de travaux d'élèves

Officiel

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.

Liens

Téléchargemments

Le memo des séquences 1 et 2 en PDF
Les sources :
- Bonjour monde !
- conjugueur.py version 0.0.0
- conjugueur.py version 0.0.1 (correction fin de séquence 2)
- conjugueur.py version 0.1.0 (fin de séquence 3)
- conjugueur.py version 0.2.0 (départ séquence 5)
- L'exemple de la séquence 3
- L'exemple de la séquence 3 (version corrigée)
- Les fonctions -projet cesar- de la séquence 9

Tweets by wouf

Comment ???

NEWS

Page : https://site2wouf.fr/algorithme2022-2023_s3.php
Catégorie : Non définie

[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 blog