[[{"text":"devoir"}],[{"quiz":888}]]
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1573
[[{"visi":false,"text":"Vous allez répondre à un QCM sur le web du programme de Snt.
Quelle est la signification de l'acronyme Http?
"},{"radio":[{"label":"Hypertext Transfer Protocol","sol":true},{"label":"Hide Transition Transfert Production","sol":false},{"label":"HyperTransfert Text Protocole","sol":false},{"label":"Hide Text Transition Protocole","sol":false}]}],[{"chrono":90},{"text":"Quelle est la signification de l'acronyme Url?
"},{"radio":[{"label":"Uniform Resource Locator","sol":true},{"label":"Uniform Resource Link","sol":false},{"label":"Union Revision Link","sol":false},{"label":"Unification Ressource Link","sol":false}]}],[{"chrono":90},{"text":"
"},{"radio":[{"label":"image","sol":true},{"label":"texte","sol":false},{"label":"page web","sol":false},{"label":"video","sol":false}]}],[{"chrono":90},{"text":"Pour qu'un site web soit sécurisé. Quelles sont les informations affichées dans le navigateur?"},{"chekbox":[{"label":"l'adresse web est en https","sol":true},{"label":"Il y a un cadena à gauche de la barre d'adresse","sol":true},{"label":"Il y a une clé à gauche de la barre d'adresse","sol":false},{"label":"l'adresse est en http","sol":false}]}],[{"chrono":90},{"text":"
"},{"radio":[{"label":"<input type=\"radio\">","sol":true},{"label":"<input type=\"checkbox\" >","sol":false},{"label":"<input type=\"button\">","sol":false},{"label":"<input type=\"password\">","sol":false}]}],[{"chrono":90},{"text":"Je souhaite mettre l'élément ci-dessous dans mon formulaire.
"},{"radio":[{"label":"<input type=\"radio\">","sol":false},{"label":"<input type=\"checkbox\" >","sol":true},{"label":"<input type=\"button\">","sol":false},{"label":"<input type=\"password\">","sol":false}]}],[{"chrono":90},{"text":"Je souhaite mettre l'élément ci-dessous dans mon formulaire.
"},{"radio":[{"label":"<input type=\"radio\">","sol":false},{"label":"<input type=\"checkbox\" >","sol":false},{"label":"<input type=\"button\">","sol":false},{"label":"<input type=\"password\">","sol":true}]}],[{"chrono":90},{"text":"Je souhaite mettre l'élément ci-dessous dans mon formulaire.
"},{"radio":[{"label":"<input type=\"text\">","sol":true},{"label":"<input type=\"texte\" >","sol":false},{"label":"<input type=\"label\">","sol":false},{"label":"<input type=\"word\">","sol":false}]}],[{"chrono":90},{"text":"Je souhaite mettre l'élément ci-dessous dans mon formulaire.
"},{"radio":[{"label":"<select>
"},{"radio":[{"label":"<input type=\"textarea\">","sol":true},{"label":"<input type=\"button\" >","sol":false},{"label":"<input type=\"label\">","sol":false},{"label":"<input type=\"paragraphe\">","sol":false}]}]]
Consignes :
- 1 seul onglet ouvert sur sciencesappliquees.com dans le navigateur chrome;
- Aucun autre logiciel doit être exécuté pendant le test.
Si vous enfreignez une de ces consignes, vous aurez 0 avec 2 heures de colles pour tentative de triche!
","posi":15}],[{"chrono":90},{"text":""},{"radio":[{"label":"Hypertext Transfer Protocol","sol":true},{"label":"Hide Transition Transfert Production","sol":false},{"label":"HyperTransfert Text Protocole","sol":false},{"label":"Hide Text Transition Protocole","sol":false}]}],[{"chrono":90},{"text":"Quelle est la signification de l'acronyme Url?
"},{"radio":[{"label":"Uniform Resource Locator","sol":true},{"label":"Uniform Resource Link","sol":false},{"label":"Union Revision Link","sol":false},{"label":"Unification Ressource Link","sol":false}]}],[{"chrono":90},{"text":"
Nous avons l'adresse web suivante :
http://www.sciencesappliquees.com/images/texte.png
Quel est le protocole utilisé?
"},{"radio":[{"label":"http","sol":true},{"label":"www","sol":false},{"label":"com","sol":false},{"label":"png","sol":false}]}],[{"chrono":90},{"text":"Nous avons l'adresse web suivante :
http://www.sciencesappliquees.com/images/texte.png
Quel est le type de ressource?
C’est quoi un cookie dans un navigateur?
"},{"chekbox":[{"label":"Un fichier texte","sol":true},{"label":"Il permet de me suivre sur le web.","sol":true},{"label":"Une page web","sol":false},{"label":"Un gateau","sol":false}]}],[{"chrono":90},{"text":"Je suis sur la page web index.html
De quel type est cette page?"},{"radio":[{"label":"C'est une page statique.","sol":true},{"label":"C'est une page dynamique.","sol":false},{"label":"C'est une page simple.","sol":false},{"label":"C'est une page de texte..","sol":false}]}],[{"chrono":90},{"text":"Je suis sur la page web index.php
De quel type est cette page?"},{"radio":[{"label":"C'est une page statique.","sol":false},{"label":"C'est une page dynamique.","sol":true},{"label":"C'est une page simple.","sol":false},{"label":"C'est une page de texte..","sol":false}]}],[{"chrono":90},{"text":"Qu'est-ce qu'un client web?
"},{"radio":[{"label":"Un navigateur","sol":true},{"label":"Un serveur"},{"label":"Un acheteur","sol":false},{"label":"Un ordinateur","sol":false}]}],[{"chrono":90},{"text":"Où sont stockés les sites web?"},{"radio":[{"label":"Dans un serveur","sol":true},{"label":"Dans la stratosphère","sol":false},{"label":"Dans mon ordinateur","sol":false},{"label":"Dans le web","sol":false}]}],[{"chrono":90},{"text":"Comment appelle-t-on le faite de demander une informaton à un serveur?"},{"radio":[{"label":"Une requête ","sol":true},{"label":"Un appel","sol":false},{"label":"Un signal","sol":false},{"label":"Une commande","sol":false}]}],[{"chrono":90},{"text":"Nous souhaitons réaliser un formulaire?
Quelle balise allez vous utiliser?
"},{"radio":[{"label":"form","sol":true},{"label":"formulary"},{"label":"formulaire","sol":false},{"label":"formule","sol":false}]}],[{"chrono":90},{"text":"Je souhaite envoyer mon formulaire.Quellle balise vais-je utiliser?
"},{"radio":[{"label":"<input type=\"submit\" value=\"Envoyer\">","sol":true},{"label":"<input type=\"send\" value=\"Envoyer\">","sol":false},{"label":"<input type=\"envoyer\" value=\"Envoyer\">","sol":false},{"label":"<input type=\"requet\" value=\"Envoyer\">","sol":false}]}],[{"chrono":90},{"text":"Quelles sont les 2 méthodes pour envoyer un formulaire?"},{"chekbox":[{"label":"Post","sol":true},{"label":"Get","sol":true},{"label":"Send","sol":false},{"label":"Http","sol":false}]}],[{"chrono":90},{"text":"Je souhaite mettre l'élément ci-dessous dans mon formulaire.Quellle balise vais-je utiliser?
Quellle balise vais-je utiliser?
Quellle balise vais-je utiliser?
Quellle balise vais-je utiliser?
Quellle balise vais-je utiliser?
<option selected>Maths</option>
<option>Nsi</option>
<option>Physique</option>
</select>
","sol":true},{"label":"<list> <option selected>Maths</option>
<option>Nsi</option>
<option>Physique</option>
</list>
","sol":false},{"label":"<input type=\"list\">","sol":false},{"label":"<input type=\"select\">","sol":false}]}],[{"chrono":90},{"text":"Je souhaite mettre l'élément ci-dessous dans mon formulaire.Quellle balise vais-je utiliser?
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1360
[[{"text":"","title":"Le web : Client<->Serveur : formulaire "},{"htm":"","css":"","js":""}],[{"text":"
","title":"Case à cocher"},{"htm":"","css":""},{"edit":" "}],[{"text":"
","title":"D'autres types de formulaires de liste"},{"htm":"","css":""},{"edit":" "}],[{"text":"
"},{"htm":"","css":""},{"edit":" "}],[{"text":"
","title":"Formulaire d'Upload"},{"htm":"","css":""},{"edit":" "}],[{"text":"
","title":"Zones de Texte, commentaires"},{"htm":"","css":""},{"edit":" "}],[{"text":"
![\"Le](\"https://mdn.mozillademos.org/files/15999/0006.png\")
"},{"htm":"","css":""},{"edit":" "}],[{"text":"
","title":"Mise en page élémentaire du formulaire"},{"htm":"","css":""},{"edit":" "}],[{"text":"
","title":"Envoyer les données au serveur Web"},{"htm":"","css":""},{"edit":" "}],[{"text":"
","title":"Félicitations"},{"htm":"","css":""},{"edit":" "}],[{"text":"Sources
"},{"edit":" "}]]
Les formulaires sont parmi les outils les plus importants utilisés par un webmaster pour récolter d'importantes informations sur un utilisateur internet, de l'information tel qu'un e-mail, nom, adresse, téléphone ou n'importe quelle autre sorte d'information.
En cas de besoin l'information peut même être stockée dans un fichier, vous pouvez faire des statistiques, formulaires d'inscription ou de souscription à l'information présentée dans votre page internet, et pleins d'autres
"},{"htm":"","css":"","js":""}],[{"text":"Avant de rentrer dans les détails, nous devons exposer un peu les bases d'un formulaire. Les champs de texte ont quelques attributs qui doivent être mentionnés pour commencer:
type - établit le type de champ de texte. Par exemple: texte, envoi, ou mot de passe.
name - donne un nom au champ pour référence ultérieure.
size - définit la taille du champ.
maxlenght - la valeur maximale des caractères qui peuvent être tapés.
HTML
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\">
\tName: <input type=\"text\" size=\"10\" maxlength=\"40\" name=\"name\" /><br />
\tPassword: <input type=\"password\" size=\"10\" maxlength=\"10\" name=\"password\" />
</form>
Copier et exécuter le code ci-dessous.
N'UTILISEZ PAS ce code. Les données du formulaire ne seront pas encryptées et ne seront pas sûres en terme de sécurité
","title":"Champs de texte"},{"htm":"","css":""}],[{"text":"Ajoutons le bouton d'envoi à présent. Généralement, le bouton d'envoi doit être le dernier et avoir l'attribut nommé 'Send', 'Submit', ou quelque chose comme ça.
Nous devons aussi spécifier une destination pour les données entrées dans le formulaire, tout comme le mode de transfert. Cela peut être fait en ajoutant les attributs de formulaires suivants:
method - Nous utiliserons le \"post\" method. Cela envoie le formulaire avec l'information insérée sans afficher les données de l'utilisateur.
action - Cela sera utilisé pour spécifier l'URL ou l'information sera envoyée.
HTML
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\">
\tName: <input type=\"text\" size=\"10\" maxlength=\"40\" name=\"name\" /><br />
\tPassword: <input type=\"password\" size=\"10\" maxlength=\"10\" name=\"password\" /><br />
\t
\t<input type=\"submit\" value=\"Send\" />
\t
</form>
Ecrire et tester le code.
Changez simplement ladresse e-mail en une existante pour que cela fonctionne!
","title":"Email formulaires"},{"htm":"","css":""}],[{"text":"Les boutons radio sont très populaires, utiles et faciles à utiliser. L'exemple le plus utilisé serait une question avec plus d'un choix de réponses. Les attributs que vous devez connaitre sont les suivants:
value - spécifie ce qui sera envoyé si l'utilisateur sélectionne un certain bouton. Seulement une valeur sera envoyée.
name - décide à quel ensemble de boutons appartient le bouton sélectionné.
HTML :
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\">
\t<p>Quel type de chaussures vous portez ?</p>
\t
\t<label>Color:</label> <br />
\t<input type=\"radio\" name=\"color\" value=\"sombre\" /> Sombres <br />
\t<input type=\"radio\" name=\"color\" value=\"clair\" /> Claires <br />
\t
\t<label>Size:</label> <br />
\t<input type=\"radio\" name=\"size\" value=\"petite\" /> Petites <br />
\t<input type=\"radio\" name=\"size\" value=\"moyenne\" /> Moyennes <br />
\t<input type=\"radio\" name=\"size\" value=\"grande\" /> Grandes <br />
\t
\t<input type=\"submit\" value=\"M'envoyer un Email\" />
</form>
Ecrire et tester le code.
Si vous remplacez l'adresse email par la votre vous recevrez un email avec: 'size=(choisir) color=(choisir)'.
","title":"Boutons Radio"},{"htm":"","css":"","js":""}],[{"text":"En utilisant les cases à cocher l'utilisateur à la possibilité de choisir une, deux ou plus, variantes de réponses. Les attributs name et value sont utilisés de la même maniere que pour le bouton radio.
HTML
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\">
\t<p>Quelle couleur de chaussures vous préférez?</p>
\t<input type=\"checkbox\" name=\"shoes\" value=\"noires\" /> Simple Noires <br/>
\t<input type=\"checkbox\" name=\"shoes\" value=\"blanches\" /> Simple Blanches <br/>
\t<input type=\"checkbox\" name=\"shoes\" value=\"grises\" /> Nuances de gris <br/>
\t<input type=\"checkbox\" name=\"shoes\" value=\"noires&blanches\" /> Noires et blanches<br/>
\t
\t<input type=\"submit\" value=\"M'envoyer un Email\" />
</form>
Ecrire et tester le code
Un autre modèle de formulaire de liste est le suivant, dans lequel cas l'utilisateur sélectionne une certaine ligne qui sera envoyée comme l'option choisie.
HTML
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\">
\t<p>Préférences musicales</p>
\t
\t<select multiple name=\"musique\" size=\"4\">
\t\t<option value=\"emo\" selected>Emo</option>
\t\t<option value=\"metal/rock\" >Metal/Rock</option>
\t\t<option value=\"hiphop\" >Hip Hop</option>
\t\t<option value=\"ska\" >Ska</option>
\t\t<option value=\"jazz\" >Jazz</option>
\t\t<option value=\"country\" >Country</option>
\t\t<option value=\"classique\" >Classique</option>
\t\t<option value=\"alternative\" >Alternative</option>
\t\t<option value=\"retro\" >Retro</option>
\t\t<option value=\"techno\" >Techno</option>
\t</select><br />
\t
\t<input type=\"submit\" value=\"M'envoyer un Email\" />
</form>
Ecrire et tester le code.
Un autre modèle de formulaire est le menu 'déroulant'. Cela sera affiché comme un champ, qui montrera ensuite une liste lorsqu'un clic aura été effectué dessus.
HTML
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\">
\t<p>Niveau d'éducation?</p>
\t
\t<select name=\"education\">
\t\t<option>Choisir</option>
\t\t<option>Lycée </option>
\t\t<option>College</option>
\t\t<option>Doctorat</option>
\t</select><br />
\t
\t<input type=\"submit\" value=\"M'envoyer un Email\" />
</form>
Ecrire et tester le code.
Premièrement il doit être mentionné que ce formulaire est seulement l'interface, la partie visible avec lequel l'utilisateur sera capable de travailler. Pour créer un formulaire d'upload complet des connaissances et compétences en PHP et PERL, sans mentionner javascript, sont requises.
Un formulaire d'upload est composé de plusieurs parties. Nous commencerons par établir la taille du fichier qui sera uploadé. Cela est fait en utilisant un champ caché. Après cela, nous créérons le champ dans lequel l'utilisateur sera capable d'écrire l'adresse du fichier ou sera capable de le rechercher dans une fenêtre 'explorateur'.
HTML
<input type=\"hidden\" name=\"MAX_FILE_SIZE\" value=\"100\" /> <input name=\"file\" type=\"file\" />
Ecrire et tester le code.
Généralement, les zones de texte sont utilisées pour envoyer des commentaires. Les blogs et forums sont les pages internet principales qui utilisent ce genre d'options. Néanmoins, il y a beaucoup de sites qui utilisent ces zones de texte pour découvrir l'opinion de leur utilisateur sur un certain sujet.
Pour créer une zone de texte nous spécifierons tout d'abord les attributs rows et cols à l'intérieur de la balise <textarea> . 'Rows' définira la hauteur du champ, et 'cols' sa longueur, en terme de caractères. Dans l'exemple suivant il y a 5 lignes de 20 caractères chacun. Aussi, nous devons spécifier les attributs de la balise warp, ceux-ci étant:
wrap=
\"off\"
\"virtuel\"
\"physique\"
HTML
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\">
\t<textarea rows=\"5\" cols=\"20\" wrap=\"physique\" name=\"commentaires\">Ecrivez un commentaire</textarea><br />
\t<input type=\"submit\" value=\"M'envoyer un Email\" />
\t
</form>
Ecrire et tester le code.
Avant de passer au code, il est souhaitable de prendre un peu de recul et accorder quelques instants de réflexion à votre formulaire. Dessiner un rapide croquis vous permettra de définir les informations que vous souhaitez demander à l'utilisateur. Du point de vue de l'expérience utilisateur, il est important de garder à l'esprit que plus vous demandez d'informations, plus vous risquez que votre utilisateur s'en aille. Restez simple et ne perdez pas votre objectif de vue : ne demandez que ce dont vous avez absolument besoin. La conception de formulaires est une phase importante de la construction d'un site internet ou d'une application. L'approche de l'expérience utilisateur de ces formulaires ne fait pas partie des objectifs de ce guide, mais si vous souhaitez approfondir ce sujet, vous pouvez lire les articles suivants :
Smashing Magazine a de très bons articles à propos de l'expérience utilisateur dans les formulaires, mais le plus intéressant est certainement leur « Guide complet pour des formulaires web facilement utilisables ».
UXMatters est une ressource bien pensée avec de très bons conseils allant des meilleures pratiques de base jusqu'à des sujets plus complexes tels que les formulaires sur plusieurs pages.
Dans ce guide, nous allons concevoir un formulaire de contact simple. Posons les premières pierres.
Le croquis du formulaire que l'on veut créer
Notre formulaire contiendra trois champs de texte et un bouton. Nous demandons simplement à notre utilisateur son nom, son adresse électronique et le message qu'il souhaite envoyer. En appuyant sur le bouton, le message sera envoyé au serveur web.
","title":"Concevoir votre formulaire"},{"htm":"","css":""},{"edit":" "}],[{"text":"Très bien, nous sommes maintenant prêts à passer au HTML et à coder notre formulaire. Pour construire notre formulaire, nous aurons besoin des éléments HTML suivants : <form>, <label>, <input>, <textarea> et <button>.
Avant de poursuivre, faites une copie locale de notre simple modèle HTML — vous y incorporerez votre formulaire.
L'élément <form>
Tous les formulaires HTML débutent par un élément <form> comme celui-ci :
HTML
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\">
Le formulaire sera ici.
</form>
Cet élément définit un formulaire. C'est un élément conteneur au même titre que les éléments <div> ou <p>, mais il accepte aussi quelques attributs spécifiques afin de contrôler la manière dont il se comporte. Tous ses attributs sont optionnels mais définir au moins les attributs action et method est considéré comme de bonne pratique.
L'attribut action définit l'emplacement (une URL) où doivent être envoyées les données collectées par le formulaire.
L'attribut method définit la méthode HTTP utilisée pour envoyer les données (cela peut être « get » ou « post »).
Note : Si vous souhaitez en savoir plus sur le fonctionnement de ces attributs, cela est détaillé dans l'article « Envoi des données de formulaire ».
Ecrire et tester le code.
","title":"Apprentissage actif : mise en œuvre de notre formulaire HTML"},{"htm":"","css":""},{"edit":" "}],[{"text":"Pour le moment, ajoutez l'élément <form> ci dessus dans le corps de votre HTML.
Les éléments <label>, <input> et <textarea>
Notre formulaire de contact est très simple et ne contient que trois champs de texte, chacun ayant une étiquette. Le champ d'entrée pour le nom est un champ de texte sur une seule ligne, le champ pour l'adresse électronique est un champ de texte sur une ligne qui n'accepte que des adresses électroniques et enfin le champ pour le message est un champ de texte sur plusieurs lignes.
En terme de code HTML, nous avons besoin de quelque chose qui ressemble à ceci pour mettre en œuvre nos widgets de formulaire.
HTML
<form action=\"/ma-page-de-traitement\" method=\"post\">
<div>
<label for=\"name\">Nom :</label>
<input type=\"text\" id=\"name\" name=\"user_name\">
</div>
<div>
<label for=\"mail\">e-mail :</label>
<input type=\"email\" id=\"mail\" name=\"user_mail\">
</div>
<div>
<label for=\"msg\">Message :</label>
<textarea id=\"msg\" name=\"user_message\"></textarea>
</div>
</form>
Les éléments <div> sont ici pour structurer notre code et rendre la mise en page plus facile (voir ci-dessous). Veuillez noter l'utilisation de l'attribut for sur tous les éléments <label>. C'est une manière formelle de lier un libellé à un élément du formulaire. Cet attribut fait référence à l'id de l'élément correspondant. Il y a plusieurs avantages à faire ainsi. Le plus évident de permettre à l'utilisateur de cliquer sur l'étiquette pour activer le bloc correspondant. Si vous souhaitez mieux comprendre les bénéfices de cet attribut, tout est détaillé dans cet article : Comment structurer un formulaire HTML.
Concernant l'élément <input>, l'attribut le plus important est l'attribut type. Ce dernier est extrêmement important puisqu'il définit le comportement de l'élément <input>. Il peut radicalement changer le sens de l'élément, faites-y attention. Si vous voulez en savoir plus à ce propos, vous pouvez lire l'article au sujet des widgets natifs pour formulaire.
Dans notre exemple nous n'utilisons que la valeur text — qui est la valeur par défaut de cet attribut et représente un champ de texte basique sur une seule ligne acceptant n'importe quel type de texte.
Pour le deuxième entrée, nous utilisons la valeur email qui définit un champ de texte sur une seule ligne n'acceptant que des adresses électroniques valides. Cette dernière valeur transforme un champ basique en une sorte de champ « intelligent » qui réalise des vérifications sur les données fournies par l'utilisateur. Vous trouverez plus de détails sur la validation des formulaires dans l'article Validation des données de formulaire.
Ecrire et tester le code.
Last but not least, remarquez la syntaxe de <input> vs <textarea></textarea>. C'est une des bizarreries du HTML. La balise <input> est un élément vide, ce qui signifie qu'il n'a pas besoin de balise fermante. Au contraire, <textarea> n'est pas un élément vide, il faut donc le fermer avec la balise fermante appropriée. Cela a un effet sur une caractéristique spécifique des formulaires HTML : la manière dont vous définissez la valeur par défaut. Pour définir une valeur par défaut d'un élément <input> vous devez utiliser l'attribut value de la manière suivante :
<input type=\"text\" value=\"par défaut cet élément sera renseigné avec ce texte\">
A contrario, si vous souhaitez définir la valeur par défaut d'un élément <textarea>, il suffit simplement de mettre la valeur par défaut entre les balises ouvrantes et fermantes de l'élément <textarea> de la manière suivante :
<textarea>par défaut cet élément sera renseigné avec ce texte</textarea>
L'élément <button>
Notre formulaire est presque terminé. Il nous suffit seulement d'ajouter un bouton pour permettre à l'utilisateur de nous envoyer les données renseignées dans le formulaire. Ceci se fait simplement en ajoutant d'un élément <button> ; ajoutez‑le juste avant la balise fermante </form> :
<div class=\"button\">
<button type=\"submit\">Envoyer le message</button>
</div>
Comme vous le voyez l'élément <button> accepte aussi un attribut de type — il peut prendre une des trois valeurs : submit, reset ou button.
Un clic sur un bouton submit (valeur par défaut) envoie les données du formulaire vers la page définie par l'attribut action de l'élément <form>.
Un clic sur un bouton reset réinitialise tous les widgets du formulaire à leurs valeurs par défaut immédiatement. Du point de vue de l'expérience utilisateur, utiliser un tel bouton est une mauvaise pratique.
Un clic sur un bouton button ne fait... rien ! Cela peut paraître stupide mais c'est en réalité très pratique pour concevoir des boutons personnalisés avec JavaScript.
Note : Vous pouvez aussi utiliser l'élément <input> avec le type approprié pour produire un bouton, par exemple <input type=\"submit\">. Le principal avantage de <button> par rapport à l'élément <input> est que ce dernier ne permet d'utiliser que du texte comme étiquette tandis que l'élément <button> permet d'utiliser n'importe quel contenu HTML, autorisant ainsi des textes de bouton plus complexes et créatifs.
Ecrire et tester le code.
"},{"htm":"","css":""},{"edit":" "}],[{"text":"Nous avons désormais notre formulaire HTML, et si vous le regardez dans votre navigateur préféré, vous verrez qu'il est plutôt laid.
Note : Si vous pensez que vous n'avez pas écrit un code HTML correct, faites la comparaison avec celui de notre exemple terminé — voyez first-form.html ( ou également directement).
Les formulaires sont notoirement embêtants à présenter joliment. Apprendre la mise en page ou la décoration des formulaires sort du cadre de cet article, donc pour le moment nous allons simplement ajouter quelques indications au CSS pour lui donner un air convenable.
Tout d'abord, ajoutons un élément <style> à notre page, dans l'en‑tête HTML. Comme ceci :
<style>
</style>
Entre les balises style, ajoutons le CSS suivant, juste comme indiqué :
CSS
form {
/* Uniquement centrer le formulaire sur la page */
margin: 0 auto;
width: 400px;
/* Encadré pour voir les limites du formulaire */
padding: 1em;
border: 1px solid #CCC;
border-radius: 1em;
}
form div + div {
margin-top: 1em;
}
label {
/* Pour être sûrs que toutes les étiquettes ont même taille et sont correctement alignées */
display: inline-block;
width: 90px;
text-align: right;
}
input, textarea {
/* Pour s'assurer que tous les champs texte ont la même police.
Par défaut, les textarea ont une police monospace */
font: 1em sans-serif;
/* Pour que tous les champs texte aient la même dimension */
width: 300px;
box-sizing: border-box;
/* Pour harmoniser le look & feel des bordures des champs texte */
border: 1px solid #999;
}
input:focus, textarea:focus {
/* Pour souligner légèrement les éléments actifs */
border-color: #000;
}
textarea {
/* Pour aligner les champs texte multi‑ligne avec leur étiquette */
vertical-align: top;
/* Pour donner assez de place pour écrire du texte */
height: 5em;
}
.button {
/* Pour placer le bouton à la même position que les champs texte */
padding-left: 90px; /* même taille que les étiquettes */
}
button {
/* Cette marge supplémentaire représente grosso modo le même espace que celui
entre les étiquettes et les champs texte */
margin-left: .5em;
}
Mettre le code html de la page précédente dans html.
Ecrire le code ci-dessus dans le css et tester.
Désormais notre formulaire a une bien meilleure allure.
Note : Il est sur GitHub dans first-form-styled.html (à voir aussi directement).
Finalement, gérer les données du formulaire côté serveur web est peut être le plus compliqué. Comme dit auparavant, un formulaire HTML est une manière pratique de demander de l'information à un utilisateur et de les adresser à un serveur web.
L'élément <form> définit où et comment les données sont envoyées, merci aux attributs action et method.
Mais ce n'est pas tout. Nous avons aussi besoin de donner un nom à nos données. Ces noms sont importants pour deux raisons. Du côté du navigateur, cela sert à définir le nom de chaque élément de donnée. Du côté du serveur, chaque information doit avoir un nom pour être manipulée correctement.
Pour nommer vos données vous devez utiliser l'attribut name pour identifier bien précisément l'élément d'information collecté par chacun des widgets. Regardons à nouveau le code de notre formulaire :
HTML
<form method=\"post\" action=\"https://www.sciencesappliquees.com/serveur.php\"> <div>
<label for=\"name\">Nom :</label>
<input type=\"text\" id=\"name\" name=\"user_name\" />
<div>
<div>
<label for=\"mail\">E-mail :</label>
<input type=\"email\" id=\"mail\" name=\"user_email\" />
</div>
<div>
<label for=\"msg\">Message:</label>
<textarea id=\"msg\" name=\"user_message\"></textarea>
</div>
....
</form>
...
Dans notre exemple, le formulaire enverra trois informations nommées respectivement « user_name », « user_email » et « user_message ». Ces informations seront envoyées à l'URL « /my-handling-form-page » avec la méthode HTTP POST.
Du côté du serveur, le script à l'URL action=\"https://www.sciencesappliquees.com/serveur.php\" recevra les données sous forme d'une liste de trois éléments clé/valeur intégrés à la requête HTTP. Vous vérez en Nsi comment ce script manipulera les données. Chacun des langages serveurs (PHP, Python, Ruby, Java, C#, etc.) a son propre mécanisme pour traiter ces données.
Ecrire et tester le code.
Copier les codes css et html précédents dans html et css ci-dessous.
Exécuter et tester le code.
Félicitations ! Vous avez construit votre premier formulaire HTML. Il ressemble à ceci :
Toutefois, ce n'est qu'un début — il est désormais temps de regarder plus en détail. Les formulaires HTML sont bien plus puissants que ce que vous avez pu voir ici et les autres articles de ce guide vous aiderons à maîtriser le reste.
Pour aller plus loin.
https://developer.mozilla.org/fr/docs/Web/Guide/HTML/Formulaires/Mon_premier_formulaire_HTML
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1503
[[{"text":"","title":"Algorithmes gloutons"}],[{"text":"
","title":"Problème d'optimisation : le voyageur"},{"edit":" "}],[{"text":"
"},{"edit":" "}],[{"text":"
","title":"Problemes difficiles"},{"edit":" "}],[{"text":"
","title":"Résolution approchée du problème du voyageur"},{"edit":"
"}],[{"text":"
","title":"Mise en oeuvre Le programme 17 propose une realisation en Python de l'algorithme du voyageur glouton. Les n villes a visiter sont numerotees de 0 a n - 1 et les distances entre villes sont stockees dans un tableau dist A deux dimensions tel que dist [i] [j] donne la distance de la ville numero I a la ville numero j. La fonction principale voyageur prend en parametres la liste des villes, la table des distances et le numero de la ville de depart. Elle utilise un tableau visi-tees de booleens indignant pour chaque ville (donnee par son numero) si elle a Mà ete visitee ou non, ainsi qu'une variable courante memorisant le numero de la vine actuelle. La fonction est ensulte constituee d'une boucle Metz Programme 17 — voyageur glouton del plus_proche(ville, dist , visitees) : \"Renvoie le numero de la ville non encore visitee la plus proche de la ville courante, en supposant qu'il en existe au moms une.\"\"\" pp = None for I in range(len(visitees)): if visitees [i] : continue if pp == None or dist [ville] [i] < dist [ville] [pp] : PP ' return pp del voyageur(villes, dist, depart): \"Affsche les etapes du parcours glouton depuss La vslle de depart.' n = len(villes) visitees = [False] * n courante = depart for _ in range(n-1): visitees [courante] = True suivante = plus_proche(courante, dist , visitees) print (\"on va de\", vines [courante] , \\ \"a\", villes [suivante] , \\ \"en\", dist [courante] [suivante] , \"km\") courante = suivante print (\"on revient de\", vines [courante] , \\ \"a\", vines [depart] , \\ \"en\", dist [courante] [depart] , \"km\") qui, n - 1 fois, marque comme visit& la ville courante puis selectionne la suivante. La fonction voyageur delegue le choix de la ville suivante a une fonction auxiliaire plus_proche, qui prend en parametres la table des distances, le numero de la ville courante et le tableau des villes déjà visitees pour selectionner la ville la plus proche de la ville courante parmi les villes non encore visitees. Cette fonction est constituee d'une boucle examinant les villes tour a, tour en ecartant les villes déjà visitees et en memorisant dans une variable pp le numero de la ville non visitee la plus proche vue jusque la. Cette variable est initialisee avec la valeur speciale None puisqu'on ne connait pas a .\t. ,\t•11\t,1. •11 Ii faut noter que la fonction plus_proche depend d'une precondition : elle ne peut fonctionner correctement que s'il existe au moms une ville non visitee, et renvoie None sinon. Aucun test specifique n'est fait car il est certain que l'utilisation de plus_proche par voyageur respectera toufours cette precondition. En effet, chacun des n - 1 tours de boucle marque exactement une des n villes comme visit& et il en restera donc touj ours au moms une qui ne soit pas encore marquee. Quake de l'approximation. La. solution dorm& par iii algorithme glouton ii 'est pas necessairement optirnale. Pent-on nearimoins s'attendre A un certain niveau de qualite? Si oui, cc niveau de quake attendu est-il garanti, c'est-a-dire respecte meme dens le pire des scenarios? 01.1 bien est-il seulement hautement probable, c'est-h-dire genera-lenient respecte mais avec des exceptions? Les reponses a ees questions dependent fortement du probleme considere. Pour notre probleme du voyageur, ii a ete demontre que lorsque Ic nombre de villes devient grand, le rapport entre la. solution gloutontw et la solution optimale est dans le pire des cas proportiormel au logarithme du nombre de villes."},{"edit":"
"}],[{"text":"
","title":"Qualité de l'approximation"},{"edit":" "}],[{"text":"
","title":"Problème : rendu de monnaie"},{"edit":""}],[{"text":"
","title":"Rendu de monnaie glouton"},{"edit":"
"}],[{"text":"
","title":"Optimalité du rendu de monnaie glouton en euros"},{"edit":" "}],[{"text":"
"},{"edit":" "}],[{"text":"
","title":"Savoir si un systeme est canonique"},{"edit":" "}],[{"text":"
","title":"Exercice"},{"edit":" "}],[{"text":"
","title":"Exercice"},{"edit":" "}],[{"text":"
","title":"Exercice"},{"edit":" "}],[{"text":"
","title":"Exercice"},{"edit":" "}],[{"text":"
","title":"Exercice"},{"edit":" "}],[{"text":"
","title":"Exercice"},{"edit":" "}],[{"text":"
","title":"Exercice"},{"edit":" "}]]
Supposons que l'on ait déterminé une certaine liste de villes dans lesquelles nous devons nous rendre et que l'on cherche un itinéraire minimisant la distance totale parcourue.
On s'autorisera à visiter les villes dans n'importe quel ordre, mais aucune ne doit être négligée, et il faudra à la fin revenir à la ville de départ.
Voici une situation concrète. Nous partons de Carhaix et devons nous rendre à Brest, à Rennes, à Nantes et à Vannes avant de retourner à Carhaix.
Le tableau des distances routières kilométriques entre ces différentes villes est le suivant :
| Carhaix | Brest | Rennes | Nantes | Vannes | |
| Carhaix | 80 | 154 | 227 | 111 | |
| Brest | 80 | 239 | 298 | 112 | |
| Rennes | 154 | 239 | 106 | 95 | |
| Nantes | 227 | 298 | 106 | 114 | |
| Vannes | 111 | 112 | 95 | 114 |
Ces données sont issues de https://www.geoportail.gouv.fr, arrondies à 1 unité la plus proche.
Le problème se ramène à trouver un ordre de visite des quatre villes Brest, Rennes, Nantes et Vannes pour lequel la somme des distances données par ce tableau pour chaque étape est aussi petite que possible.
Une manière simple d'aborder ce problème consiste à énumérer tous les ordres possibles, calculer pour chacun la distance correspondante, pour sélectionner ensuite la plus petite.
On a ici vingt-quatre itinéraires possibles, dont douze sont détaillés dans le tableau ci-dessous, où le départ et l'arrivée à Carhaix sont sous-entendus.
Cependant, cette technique ne passe pas à l'échelle. En se fixant une liste plus longue de villes à visiter, le nombre de circuits différents à analyser devient vite beaucoup trop important, et ce même pour les capacités de calcul d'un ordinateur.
Nous avons ainsi 24 circuits pour 4 villes (hors ville de depart), presque 2 millions pour 10 villes, plus de 3 milliards pour 13 villes, et plus d'un milliards de milliards pour 20 villes (la valeur exacte est la moitié de la factorielle du nombre de villes).
| Circuit | Kilomètrage |
| Carrhaix - Brest - Rennes - Nantes - Vannes - Carhaix | 80 + 239 + 106 + 114 + 111 = 650 |
| Carrhaix - Brest - Rennes - Vannes - Nantes - Carhaix | 80 + 239 + 95 + 114 + 227 = 755 |
| Carrhaix - Brest - Nantes - Rennes - Vannes - Carhaix | 80 + 298 + 106 + 95 + 111 = 690 |
| Carrhaix - Brest - Nantes - Vannes - Rennes - Carhaix | 80 + 298 + 114 + 95 + 154 = 741 |
| Carrhaix - Brest - Vannes - Rennes - Nantes - Carhaix | 80 + 112 + 95 + 106 + 227 = 620 |
| Carrhaix - Brest - Vannes - Nantes - Rennes - Carhaix | 80 + 112 + 114 + 106 + 154 = 566 |
| Carrhaix - Rennes - Brest - Nantes - Vannes - Carhaix | 154 + 239 + 298 + 114 + 111 = 916 |
| Carrhaix - Rennes - Brest - Vannes - Nantes - Carhaix | 154 + 239 + 112 + 114 + 227 = 846 |
| Carrhaix - Rennes - Nantes - Brest - Vannes - Carhaix | 154 + 106 + 298 + 112 + 111 = 781 |
| Carrhaix - Rennes - Nantes - Vannes - Brest - Carhaix | 154 + 106 + 114 + 112 + 80 = 566 |
| Carrhaix - Rennes - Vannes - Brest - Nantes - Carhaix | 154 + 95 + 112 + 298 + 227 = 886 |
| Carrhaix - Rennes - Vannes - Nantes - Brest - Carhaix | 154 + 95 + 114 + 298 + 80 = 741 |
| Carrhaix - Nantes - Brest - Rennes - Vannes - Carhaix | 227 + 298 + 239 + 95 + 111 = 970 |
| Carrhaix - Nantes - Brest - Vannes - Rennes - Carhaix | 227 + 298 + 112 + 95 + 154 = 886 |
| Carrhaix - Nantes - Rennes - Brest - Vannes - Carhaix | 227 + 106 + 239 + 112 + 111 = 795 |
| Carrhaix - Nantes - Rennes - Vannes - Brest - Carhaix | 227 + 106 + 95 + 112 + 80 = 620 |
| Carrhaix - Nantes - Vannes - Brest - Rennes - Carhaix | 227 + 114 + 112 + 239 + 154 = 846 |
| Carrhaix - Nantes - Vannes - Rennes - Brest - Carhaix | 227 + 114 + 95 + 239 + 80 = 755 |
| Carrhaix - Vannes - Brest - Rennes - Nantes - Carhaix | 111 + 112 + 239 + 106 + 227 = 795 |
| Carrhaix - Vannes - Brest - Nantes - Rennes - Carhaix | 111 + 112 + 298 + 106 + 154 = 781 |
| Carrhaix - Vannes - Rennes - Brest - Nantes - Carhaix | 111 + 95 + 239 + 298 + 227 = 970 |
| Carrhaix - Vannes - Rennes - Nantes - Brest - Carhaix | 111 + 95 + 106 + 298 + 80 = 690 |
| Carrhaix - Vannes - Nantes - Brest - Rennes - Carhaix | 111 + 114 + 298 + 239 + 154 = 916 |
| Carrhaix - Vannes - Nantes - Rennes - Brest - Carhaix | 111 + 114 + 106 + 239 + 80 = 650 |
Face à de tels problèmes d'optimisation impossibles à explorer dans un temps raisonnable, il peut être utile de connaitre des algorithmes donnant rapidement une réponse qui, sans être nécessairement optimale, resterait bonne. La méthode gloutonne présentée dans cette séquence donne une approche simple pour concevoir de tels algorithmes souvent approximatifs mais rapides.
Les différents algorithmes s'appliquant à un tableau de longueur n peuvent impliquer des nombres d'opérations très différents. proportionnels par exemple à n. (parcours d'un tableau) ou au carré de n (tri par sélection). Pour mesurer l'importance de cette différence, voici un petit tableau de taille n donnant un nombre d'opérations proche du milliard, c'est-à-dire un nombre d'opération qu'il est envisageable de faire exécuter à un programme.
Nombre op.\tn maximal
log(n) 10300 000 000
√ n 1018
n 1 000 000 000
n2 31 600
n3 1000
2n 30
n! 12
On observe qu'un algorithme avec un nombre d'opérations proportionnel à une petite puissance ne pourra être appliqué à un tableau grand voire très grand. Si le nombre d'opérations est en revanche exponentiel ou pire alors l'algorithme ne pourra être appliqué\tqu'à de tout petits tableaux.
","title":"Ordres de grandeur de la complexité des algorithmes"},{"edit":" "}],[{"text":"Les algorithmes gloutons sont utilises pour répondre à des problèmes d'optimisation, c'est-à-dire des problèmes algorithmiques dans lesquels l'objectif est de trouver une solution \"la meilleure possible\" selon un certain critère, parmi un ensemble de solutions également valides mais potentiellement moins avantageuses.
Le contexte général d'un tel problème d'optimisation est donc le suivant :
• on considère un problème possédant un très grand nombre de solutions,
• on dispose d'une fonction mathématique évaluant la qualité de chaque solution,
• on cherche une solution qui soit bonne, voire la meilleure.
Les algorithmes gloutons s'appliquent lorsque de plus :
• la recherche d'une solution peut se ramener à une succession de choix, qui produisent et précisent petit à petit une solution partielle,
• on dispose d'une fonction mathématique évaluant la qualité de chaque solution partielle (dont on attend en général qu'elle soit cohérente avec la fonction d'évaluation des solutions complètes).
L'approche gloutonne consiste alors à construire une solution complète par une succession de choix en prenant systématiquement l'option donnant la meilleure solution partielle.
","title":"Algorithmes gloutons"},{"edit":" "}],[{"text":"Certains problèmes algorithmiques sont difficiles, au point que l'on peut parfois aller jusqu'à, démontrer que leur résolution demande un nombre d'opérations exponentiel.
Par exemple, pour déterminer s'il est possible de gagner à coup sur à une partie du jeu de dames à partir d'une certaine configuration sur un plateau de coté n peut requérir un nombre d'opérations proportionnel à l'exponentielle de n. (cela vaut également pour le go et les échecs).
Une famille do problèmes célèbre dans le domaine est celle des problèmes NP-cormplets, à laquelle appartient le problème du voyageur.
Ces problèmes répondent à une question de la forme \"Existe-t-il une solution telle quo...\t? \"
et sont caractérisées par deux conditions :
• Il est facile de vérifier la validité ou l'invalidité d'une prétendue solution (un itinéraire étant donné, ii est: facile de vérifier qu'il passe par toutes les villes et de calculer sa distance totale).
• L'ensemble des solutions potentielles est vaste et nous ne savons pas l'explorer efficacement à la recherche d'une solution valide.
Par exemple pour notre problème d'itinéraire, il faut se poser la question : Existe-t-il un itinéraire passant par toutes
les villes en moins de 750kilomètres?
Personne ne sait, résoudre ces problèmes à coup sur en un temps qui soit meilleur qu'exponentiel. En pratique on ne peut donc les résoudre parfaitement que sur des instances de taille modeste. Une majorité des algorithmiciens tendent même à supposer qu'il soit effectivement impossible de résoudre ces problème en un temps raisonnable. Cependant, personne n'a encore réussi. à démontrer cette conjecture et un prix d'un million de dollars est d'ores et déjà promis à quiconque trancherait définitivement Ia. question.
.Ainsi, un problème NP-complet ne peut probablement pas être résolu parfaitement en un temps raisonnable pour des instances de grande taille. On se tourne alors le plus souvent vers des algorithmes donnant des solutions approchées.
Appliquons l'approche gloutonne à notre problème du voyageur. Le problème considéré est une visite de l'ensemble des villes, depuis une ville de départ déterminée et avec retour à cette ville. Une solution est donc n'importe quelle séquence passant par toutes les villes intermédiaires demandées, qu'on peut ramener à une succession de choix :
\"quelle sera ma prochaine étape ?\"
Une solution partielle est donc n'importe quel début de séquence.
La qualité d'une solution est inversement proportionnelle à la distance totale parcourue et on peut appliquer ce critère autant aux solutions partielles qu'aux solutions complètes.
Ces éléments mis en place, il ne reste plus qu'a appliquer la méthode gloutonne :
- partant de la ville de départ, aller à la ville la plus proche, puis à la ville la plus proche de cette dernière parmi les villes non encore visitées, et ainsi de suite.
| Carhaix | Brest | Rennes | Nantes | Vannes | |
| Carhaix | 80 | 154 | 227 | 111 | |
| Brest | 80 | 239 | 298 | 112 | |
| Rennes | 154 | 239 | 106 | 95 | |
| Nantes | 227 | 298 | 106 | 114 | |
| Vannes | 111 | 112 | 95 | 114 |
Compléter le texte ci-dessous pour appliquer l'algorithme glouton à notre voyage.
Partant de .............., nous irons donc en premier lieu à ......... , distante de ........ kilomètres.
Ensuite à ................ en ........ kilomètres,
puis à .............. en ........ kilomètres,
et enfin à .......... en ....... kilomètres,
avec ultime retour à ................ en ......... kilomètres.
Notre voyage fera donc ......... kilomètres.
L'itinéraire ainsi obtenu est plus long que le circuit minimal de ......... kilomètres vu en introduction, mais reste loin des assez nombreuses mauvaises solution qui demandaient plus de mille kilomètres. Et surtout, nous n'avons analyse qu'un unique itinéraire !
Le programme suivant propose une réalisation en Python de l'algorithme du voyageur glouton. Les n villes à visiter sont numérotées de 0 à n-1 et les distances entre villes sont stockées dans un tableau dist à deux dimensions tel que dist[i][j] donne la distance de la ville numéro i à la ville numéro j.
#tableau des villes
tabvilles = [\"Carhaix\",\"Brest\",\"Rennes\",\"Nantes\",\"Vannes\"]
#tableau des distances entre les villes
tabdist = [[ 0 , 80 , 154 , 227 , 111 ],
[ 80 , 0 , 239 , 298 , 112 ],
[ 154 , 239 , 0 , 106 , 95 ],
[ 227 , 298 , 106 , 0 , 114 ],
[ 111 , 112 , 95 , 114 , 0 ] ]
#ville de départ Carhaix
depart = 0
def plus_proche(ville, dist , visitees) :
\"\"\"Renvoie le numéro de la ville non encore visitée la plus proche
de la ville courante, en supposant qu'il en existe au moins une.\"\"\"
pp = None
for i in range(len(visitees)):
if visitees[i] : continue
if pp == None or dist[ville][i] < dist[ville][pp] :
pp = i
return pp
def voyageur(villes, dist, depart):
\"\"\"Affsche les etapes du parcours glouton depuis
la ville de depart.\"\"\"
n = len(villes)
visitees = [False] * n
courante = depart
for _ in range(n-1):
visitees[courante] = True
suivante = plus_proche(courante, dist , visitees)
print (\"on va de\", villes[courante] , \\
\"a\", villes[suivante] , \\
\"en\", dist[courante][suivante] , \"km\")
courante = suivante
print(\"on revient de\", villes[courante] , \\
\"a\", villes[depart] , \\
\"en\", dist[courante][depart] , \"km\")
voyageur(tabvilles, tabdist, depart)
La fonction principale voyageur prend en paramètres la liste des villes, la table des distances et le numéro de la ville de départ. Elle utilise un tableau visitees de booléens indiqnant pour chaque ville (donnée par son numéro) si elle a été visitée ou non, ainsi qu'une variable courante mémorisant le numéro de la ville actuelle.
La fonction est ensulte constituée d'une boucle qui, n-1 fois, marque comme visité la ville courante puis sélectionne la suivante.
La fonction voyageur délègue le choix de la ville suivante à une fonction auxiliaire plus_proche, qui prend en paramètres la table des distances, le numéro de la ville courante et le tableau des villes déjà visitées pour sélectionner la ville la plus proche de la ville courante parmi les villes non encore visitées.
Cette fonction est constituée d'une boucle examinant les villes tour à, tour en écartant les villes déjà visitées et en mémorisant dans une variable pp le numéro de la ville non visitée la plus proche vue jusque là. Cette variable est initialisée avec la valeur spéciale None.
Il faut noter que la fonction plus_proche dépend d'une pré-condition : elle ne peut fonctionner correctement que s'il existe au moins une ville non visitée, et renvoie None sinon.
Aucun test spécifique n'est fait car il est certain que l'utilisation de plus_proche par voyageur respectera toujours cette condition. En effet, chacun des n-1 tours de boucle marque exactement une des n villes comme visité et il en restera donc toujours au moins une qui ne soit pas encore marquée.
Ecrire et tester le code.
Mettre le résultat ici.
La solution donnée par i'algorithme glouton n'est pas nécessairement optimale. Peut-on néanmoins s'attendre à un certain niveau de qualité?
Si oui, ce niveau de qualité attendu est-il garanti, c'est-à-dire respecte même dans le pire des scénarios?
Ou bien est-il seulement hautement probable, c'est-à-dire généralement respecté mais avec des exceptions?
Les réponses à ces questions dépendent fortement du problème considéré.
Pour notre problème du voyageur, ii a été démontré que lorsque Ie nombre de villes devient grand, le rapport entre la. solution gloutonne et la solution optimale est dans le pire des cas proportionnel au logarithme du nombre de villes.
Dans certains cas la stratégie gloutonne donne toujours une solution optimale.
Considérons le problème d'un commerçant devant rendre de la monnaie à l'un de ses clients. Il souhaite le faire en utilisant le moins de pièces et de billets possibles.
On suppose que l'on manipule les coupures et pièces habituelles des euros (oublions les centimes) et que le commerçant dispose d'une réserve suffisamment importante de chaque espèce.
Si la somme qui doit être rendue est 9, les différentes combinaisons possibles sont les suivantes, qui utilisent entre 3 et 9 pièces.
| Combinaison | Pieces |
| 9 x 1€ | 9 |
| 7x1€ + 1x2€ | 8 |
| 5x1€ + 2x2€ | 7 |
| 3x1€+ 3x2€ | 6 |
| 1x1€ + 4x2€ | 5 |
| 4x1€ + 1x5€ | 5 |
| 2x1€ + 1x2€ + 1x5€ | 4 |
| 2x2€ + 1x5€ | 2 |
Une seule combinaison, que votre boulanger connait bien, permet d'atteindre la somme de 9 euros avec seulement trois éléments : 2 pieces de deux euros plus 1 billet de cinq euros.
Pour aborder le problème de rendu de monnaie avec une stratégie gloutonne, on va donc sélectionner les pièces et billets à rendre un à un, et faire décroitre progressivement la somme restant à rendre.
Chaque choix doit être celui qui parait être le meilleur au vu de la situation présente, c'est-à-dire de la somme restant à rendre. Pour limiter le nombre de devises rendues, on choisit de faire décroitre cette somme aussi vite que possible, c'est-à-dire de sélectionner à chaque fois la plus grande valeur disponible qui ne soit pas strictement supérieure à la somme à rendre.
Ainsi, dans notre exemple précédent, pour atteindre la somme de 9 on sélectionne d'abord un billet de 5 euros. Il reste alors 4 euros à rendre et on choisit une pièce de 2 euros.
Enfin, les 2 euros restant après cette étape sont atteints avec une unique pièce. On obtient alors la combinaison 2x2€+1x5€ dont on a vu qu'elle était optimale.
Le programme ci-dessous définit une fonction Python calculant le nombre de pièces ou billets qui doivent être utilises pour une somme à rendre donnée, en utilisant la stratégie gloutonne. Jusqu'à ce que la somme totale ait été rendue, cette fonction considère tour à tour les différentes coupures de la plus grosse à la plus petite, identifiées par un indice i dans le tableau euros.
euros = [1, 2, 5, 10, 20, 50, 100, 200]
def monnaie(s):
\"\"\"combien de pieces faut-il pour
obtenir la somme\"\"\"
i = len(euros) - 1
p = 0
while s > 0:
if s >= euros[i] :
s -= euros[i]
p += 1
else:
i -= 1
return p
print(\"nb pièce(s)\",monnaie(9))
Tant que la somme à rendre est supérieure à la coupure courante, on choisit de l'utiliser. Des que la somme à rendre devient inférieure à la valeur de la coupure en euros, on poursuit avec la coupure immédiatement inférieure.
On remarque que, la somme à rendre ne faisant que décroitre, une coupure écartée à cette étape ne sera effectivement plus jamais utile.
D'autres expériences permettent d'observer que cet algorithme glouton fournit toujours une réponse optimale. C'est quelque chose qui peut même être démontre.
Mettre les résultats ici.
. Les euros forment ce qu'on appelle un systèrne canonique, c'est-à-dire un système pour lequel l'algorithme glouton donne un rendu optimal.
Pour démontrer cela„ on peut. commencer par analyser quelques combinaisons de pièces pouvant on non apparaitre dans un rendu optimal.
•\t.Les pieces de 1 euro et les billets de 5, 10, 50 et 100 euros ne peuvent chactm etre utilises qu'une seule fois dans un rendu optimal. En eFfet, un rendu qui utiliserait deux pieces de 1 euro pent etre ameliore en remplaca.nt ces deux pieces par line, unique piece de 2 cures. De mettle pour 5/10, 10/20, 50/100 et 100/200.
•\tLes pieces de 2 cures et, les billets de 20 euros ne peuvent chacun etre utilises que deux fois dans un rendu optimal. En effet, un rendu qui utiliserait trois pieces de 2 cures pent etre ameliore en remplaca.nt ces trois pieces par line piece de 1 ewe et 1.111 billet de 5 euros. Dc meme pour 20/10/50.
•\tUn rendu optimal ne pent. contenir a la fois deux pieces de 2 cures et. lute piece de 1 euros (ou deux billets de 20 et. un de 10). En effet, un rendu avec c.:ette combinaison pent etre ameliore en utilisant è. la. place un billet de 5 cures (ou 50:).
On en deduit que, da.ns un rendu optimal, la somme totale des pieces et billet de 100 cures ou mains ne pent depa.sser 199 cures (avec la combinaison 2 x 2+1 x 5+2.x 20+1 x 50+1 x.1.00). Si la somme é. rendre est, superieure a 200 cures, le rendu optimal contient done necessairement tin billet de 200 cures, que l'algorithme glouton a. alors raison de choisir. On pent. poursuivre le raisonnement avec les coupures de 50 euros 01.1 moins (maximum 99) pour valider le choix d'un billet de 1.00, et ainsi dc suite pour valider l'integralite du systeme,.
Rendu de monnaie glouton dans d'autres systemes monetaires
Avec les euros, l'algorithme de rendu de monnaie glouton donne toujours la reponse optimale. Cependant ii n'en est pas toujours de meme dans tout systeme monetaire.
Considerons comme premier contre-exemple un systeme dans lequel les coupures out les valetas 1, 6 et 10. On souhaite rendre la somme 12. L'algorithme glouton selectionne d'abord la coupure 10, puis deux fois la coupure 1 pour un total de trois coupures. Ii etait cependant possible de faire mieux avec deux fois 6. Dans cc cas, l'algorithme glouton a donne une solution de rendu de monnaie correcte, mais pas optimale.
On peut construire un deuxieme contre-exemple plus grave avec le systerne dont les coupures out les valeurs 2 et 3, en tentant de rendre la somme 4. L'algorithme glouton selectionne alors en premier la coupure 3, apres quoi ii ne reste plus que 1 a rendre, cc que l'on ne sait pas faire avec les coupures disponibles. Et pourtant, une solution pour rendre 4 existait, il suffisait de selectionner deux fois 2! Dans cc cas, l'algorithme glouton echoue atrouver une solution de rendu alors qu'il en existait une.
On ne connait pas de critère simple caractérisant les systèmes canoniques. On salt en revanche qu'il suffit de tester l'algorithme pour chaque valeur inférieure à la somme des deux plus grandes pièces d'un système donné pour savoir si ce dernier est canonique.
Ainsi, la démonstration de canonicité des euros pourrait être remplacée par une vérification de l'optimalité de tous les rendus gloutons pour les sommes allant de 1 à 299 euros, vérification que l'on peut faire manuellement ou confiée à un programme.
Le processus est cependant susceptible d'être assez couteux, puisqu'il nécessite de faire une recherche exacte du rendu optimal pour toutes ces valeurs.
Problème du sac à dos.
Arsène L. à devant lui un ensemble d'objets de valeurs et de poids variés. II dispose d'un sac à dos dans lequel il ne peut prendre qu'une partie des objets, en essayant de maximiser la valeur totale emportée.
Cependant, il ne pourra emporter le sac que si le poids total ne dépasse pas 10 kilogrammes. Dans chacune des situations suivantes, indiquer les différentes combinaisons qui peuvent être formées et les valeurs correspondantes.
| Objet | Poids (kg) | Prix (€) | Objet | Poids (kg) | Prix (€) | |
| A | 8 | 4800 | A | 6 | 4800 | |
| B | 5 | 4000 | B | 5 | 3500 | |
| C | 4 | 3000 | C | 4 | 3000 | |
| D | 1 | 500 | D | 1 | 500 |
Algorithmes gloutons pour le problème du sac à dos. Arsene L. ne voulant pas arriyer en retard à son rendez-vous avec la comtesse C. Il va devoir choisir très rapidement les objets a emporter.
Appliquer chacune des trois stratégies gloutonnes suivantes aux situations de l'exercice précédent.
1. Choisir les objets par ordre de valeur décroissante parmi ceux qui ne dépassent pas la capacité restante.
2. Choisir les objets par ordre de poids croissant.
3. Choisir les objets par ordre de rapport valeur/poids décroissant parmi ceux qui ne depassent pas la capacité restante.
","title":"Exercice"},{"edit":" "}],[{"text":"Problème du sac à dos :
Pour chacune des stratégies gloutonnes de l'exercice précédent, trouver des situations dans lesquelles la valeur emportée est aussi éloignée que possible de la valeur optimale (Cas le plus défavorable).\tSolution page 466 0
Bin packing. Arsene L. à une nouvelle strategie. Ii enyerra aujourd'hui plusieurs complices avec l'objectif de tout emporter sans se soucier de la valeur de chaque objet, mais toujours dans la limite de 10 kilogrammes chacun. II faut cette fois essayer de repartir les objets parmi les personnes presentes.
1. Supposons qu'Arsene ait envoye trois personnes, et qu'il y a parmi les objets a emporter : un objet de lkg, deux objets de 2kg, deux objets de 3kg, deux objets de 4kg, un objet de 5kg et un objet de 6kg. Trouver une maniere de repartir les objets.
2. Combien de personnes faut-il pour recuperer un objet de 3kg, un objet de 5kg et deux objets de 6kg ?
4. kg €
A 7 9100
Exercice 162 Bin packing : strategic gloutonne. Une strategie gloutonne consiste a considerer les objets dans l'ordre, et pour chacun decider d'une personne a qui le confier. Pour cela, les personnes ont elles-memes un ordre, et on confie l'objet a la premiere ayant encore la capacite de le prendre. Si personne ne peut prendre l'objet on dira que la strategie a echoue.
Appliquer cette strategic a la situation de l'exercice 161 avec les deux ordres suivants pour les objets.
1.\t[6,\t3,\t4,\t2,\t4,\t3,\t1,\t5, 2]
2.\t[6,\t3,\t4,\t2,\t3,\t4, \t1,\t5, 2]
Exercice 163 Bin packing : programmation. On veut ecrire un programme qui, etant dorm& un tableau tab donnant les poids de chaque objet et un nombre n de conteneurs de capacite c, chercher a repartir l'ensemble des objets dans les conteneurs. Ecrire un programme qui indique s'il a reussi a repartir tous les objets en utilisant la premiere strategie proposee a
Exercice 164 Supposons avoir une liste d'activites, chacune associee a un creneau horaire defini par une heure de debut et une heure de fin. Deux activites sont compatibles si leurs creneaux horaires ne se recouvrent pas. On souhaite selectionner un nombre maximal d'activites toutes compatibles entre elles.
1. On se donne des activites avec les creneaux suivants : 8h-13h, 12h-17h, 9h-11h, 14h-16h, 11h-12h. Combien de ces activites peuvent-elles etre conciliees sur une seule journee ?
2. On propose une strategie gloutonne pour selectionner des activites en commencant par le debut de la journee : choisir l'activite dont l'heure de fin arrive le plus tot (parmi les activites dont l'heure de debut est bien posterieure aux creneaux des activites déjà choisies). Appliquer cette strategie a la situation precedente.
Remarque : cette strategie gloutonne donne toujours un nombre d'activites
optimal.\t
Exercice 165 On reprend le probleme de l'exercice precedent et on suppose avoir n activites numerotees de 0 a n - 1, et deux tableaux debut et fin de taille n tels que debut [i] et fin [i] contiennent respectivement l'heure de debut et l'heure de fin de l'activite numero i.
1. Ecrire une fonction prochaine (debut , fin, h) qui selectionne, parmi les activites dont l'heure de debut n'est pas anterieure a h, une s'arretant le plus tot. On demandera A la fonction de renvoyer None
1,1'17- 9 911,1711 ,TZ11-19911 0(11,11,9n1-11A9
2. En deduire une fonction selection(debut , fin) qui, en supposant que toutes les heures sont positives, selectionne autant d'activites que possible en suivant la strategie gloutonne. On demandera a la fonction d'afficher les numeros des activites selectionnees.
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 2238