Sorting, packing and network algorithms · Tri, conditionnement et algorithmes de réseau
| English | Français |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algorithme |
Is a fast packing method always optimal?
- A packing method quickly fills boxes, but a fast valid arrangement need not use the smallest number of boxes.
- This lesson studies algorithm 算法: A finite set of ordered instructions that solves a defined class of problems.
Une méthode d'emballage rapide est-elle toujours optimale ?
- Une méthode d'emballage remplit rapidement les boîtes, mais un arrangement valide rapide n'utilise pas nécessairement le moins de boîtes.
- Cette leçon étudie algorithme : Un ensemble fini d'instructions ordonnées qui résout une classe définie de problèmes.
Choose the mathematical structure
- Trace the named algorithm exactly, including its tie rules. In first-fit packing, place each item in the first available bin that can hold it. First-fit decreasing sorts before applying first-fit. A heuristic may be valid without being optimal.
- State the allowed inputs and units before calculating. An equation should express the relationship, not just record a calculator entry.
Choisissez la structure mathématique
- Suivez l'algorithme nommé exactement, y compris ses règles de rupture d'ex æquo. Dans l'emballage premier-disponible (first-fit), placez chaque objet dans le premier conteneur disponible capable de le contenir. Premier-disponible décroissant trie avant d'appliquer premier-disponible. Une heuristique peut être valide sans être optimale.
- Énoncez les entrées autorisées et les unités avant de calculer. Une équation doit exprimer la relation, et non simplement enregistrer une saisie de calculatrice.
Which description correctly defines algorithm? · Quelle description définit correctement un algorithme ?
A finite set of ordered instructions that solves a defined class of problems. · Un ensemble fini d'instructions ordonnées qui résout une classe définie de problèmes.
Work through a checked case
- Check the result against the starting quantities. Substitute into the original relation, or compare the graph and numerical answer where appropriate.
With bin capacity 10 and items 6,5,4,3,2 in that order, first-fit places 6 and 4 in bin 1, then 5,3,2 in bin 2. It uses 2 bins. The total size is 20, so the lower bound is ceil(20/10)=2; this arrangement is optimal for this instance.
Travaillez à travers un cas vérifié
- Vérifiez le résultat par rapport aux quantités de départ. Substituez dans la relation originale, ou comparez le graphique et la réponse numérique là où c'est approprié.
Avec une capacité de conteneur 10 et des objets 6,5,4,3,2 dans cet ordre, premier-disponible place 6 et 4 dans le conteneur 1, puis 5,3,2 dans le conteneur 2. Il utilise 2 conteneurs. La taille totale est 20, donc la borne inférieure est ceil(20/10)=2 ; cet arrangement est optimal pour cette instance.
Sorting, packing and network algorithms · Tri, conditionnement et algorithmes de réseau
Trace the named algorithm exactly, including its tie rules · Tracez l'algorithme nommé exactement, y compris ses règles de départages
Compare the model with the worked case and explain one change. · Compare le modèle avec l'exemple résolu et explique un changement.
How many bins does the worked first-fit arrangement use? · Combien de conteneurs l'exemple résolu avec premier ajustement utilise-t-il ?
The first-fit arrangement fills two bins, each with total size 10. · L'arrangement premier ajustement remplit deux conteneurs, chacun ayant une taille totale de 10.
Test a tempting shortcut
- An example of success does not prove a heuristic is always optimal. Keep intermediate lists in a sorting trace; do not jump from input to a sorted final list. A shortest-path update must retain predecessor information if a route is requested.
- When a shortcut fails, identify the assumption it breaks. Keep an exact value until the requested final rounding.
A packing heuristic that works well on one example must always be optimal. This claim is false. Explain which definition or assumption it violates.
Testez un raccourci tentant
- Un exemple de succès ne prouve pas qu'une heuristique soit toujours optimale. Gardez les listes intermédiaires dans une trace de tri ; ne sautez pas directement de l'entrée à une liste finale triée. Une mise à jour de chemin le plus court doit conserver l'information du prédécesseur si un itinéraire est demandé.
- Lorsqu'un raccourci échoue, identifiez l'hypothèse qu'il viole. Conservez une valeur exacte jusqu'au dernier arrondi demandé.
Une heuristique d'emballage qui fonctionne bien sur un exemple doit toujours être optimale. Cette affirmation est fausse. Expliquez quelle définition ou hypothèse elle viole.
Find the lower bound on bins for total size 20 and capacity 10. · Trouvez la borne inférieure en nombre de conteneurs pour une taille totale de 20 et une capacité de 10.
Every bin holds at most 10, so at least ceiling(20/10)=2 bins are needed. · Chaque conteneur contient au maximum 10, donc au moins ceiling(20/10)=2 conteneurs sont nécessaires.
A packing heuristic that works well on one example must always be optimal. · Une heuristique de conditionnement qui fonctionne bien sur un exemple doit toujours être optimale.
An example of success does not prove a heuristic is always optimal. Keep intermediate lists in a sorting trace; do not jump from input to a sorted final list. A shortest-path update must retain predecessor information if a route is requested. · Un exemple de succès ne prouve pas qu'une heuristique est toujours optimale. Conservez les listes intermédiaires dans un tracé de tri ; ne sautez pas directement de l'entrée à une liste finale triée. Une mise à jour de chemin le plus court doit conserver l'information du prédécesseur si un itinéraire est demandé.
Interpret a new situation
- For Dijkstra, choose the smallest unsettled tentative label and update its neighbours. For route-inspection problems, distinguish a closed route from an open one and identify odd vertices before pairing them.
- A complete solution gives the mathematical result and explains what it means. Check that it is possible in the stated context.
Interprétez une nouvelle situation
- Pour Dijkstra, choisir la plus petite étiquette provisoire non définitive et mettre à jour ses voisins. Pour les problèmes d'inspection de route, distinguer une boucle fermée d'une boucle ouverte et identifier les sommets impairs avant de les appairer.
- Une solution complète fournit le résultat mathématique et explique sa signification. Vérifiez qu'elle est réalisable dans le contexte indiqué.
Find space remaining in a bin containing items 5,3,2 with capacity 10. · Trouvez l'espace restant dans un conteneur contenant les éléments 5,3,2 avec une capacité de 10.
Unused capacity=10-(5+3+2)=0. · Capacité inutilisée=10-(5+3+2)=0.
Match each part of a complete solution to its purpose. · Associer chaque partie d'une solution complète à son but.
An assumption justifies the model; a check tests the result; interpretation connects it to the question. · Une hypothèse justifie le modèle ; une vérification teste le résultat ; l'interprétation le relie à la question.
Use this in your course
- edexcel IAL further mathematics; official unit D1. Other-unit enrichment is identified in the scope review; it is not an extra cash-in requirement.
- Give the method before the final answer, and use the paper's calculator and formula rules. Review a wrong answer by locating the first invalid step.
A finite set of ordered instructions that solves a defined class of problems. Choose the relationship, show the method, check its assumptions and interpret the result.
Utilisez ceci dans votre cursus
- edexcel IAL mathématiques avancées ; unité officielle D1. L'enrichissement par d'autres unités est identifié dans l'examen de portée ; ce n'est pas une exigence supplémentaire de paiement.
- Présentez la méthode avant la réponse finale, et respectez les règles de calculatrice et de formules du sujet. Revoir une réponse erronée consiste à localiser la première étape invalide.
Un ensemble fini d'instructions ordonnées qui résout une classe définie de problèmes. Choisir la relation, exposer la méthode, vérifier ses hypothèses et interpréter le résultat.