Sorting, packing and network algorithms · Algoritmos de ordenação, empacotamento e redes
| English | Português |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algoritmo |
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.
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.
Which description correctly defines algorithm? · Qual descrição define corretamente algoritmo?
A finite set of ordered instructions that solves a defined class of problems. · Um conjunto finito de instruções ordenadas que resolve uma classe definida de problemas.
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.
Sorting, packing and network algorithms · Algoritmos de ordenação, empacotamento e redes
Trace the named algorithm exactly, including its tie rules · Rastreie o algoritmo nomeado exatamente, incluindo suas regras de empate
Compare the model with the worked case and explain one change. · Compare o modelo com o caso resolvido e explique uma mudança.
How many bins does the worked first-fit arrangement use? · Quantas caixas o arrangement de first-fit resolvido utiliza?
The first-fit arrangement fills two bins, each with total size 10. · O arrangement first-fit preenche duas caixas, cada uma com tamanho total 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.
Find the lower bound on bins for total size 20 and capacity 10. · Encontre o limite inferior em caixas para tamanho total 20 e capacidade 10.
Every bin holds at most 10, so at least ceiling(20/10)=2 bins are needed. · Cada caixa contém no máximo 10, portanto são necessárias pelo menos ceiling(20/10)=2 caixas.
A packing heuristic that works well on one example must always be optimal. · Uma heurística de empacotamento que funciona bem em um exemplo não precisa ser sempre ótima.
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. · Um exemplo de sucesso não prova que uma heurística é sempre ótima. Mantenha as listas intermediárias em um rastro de ordenação; não pule da entrada para uma lista final ordenada. Uma atualização de caminho mais curto deve manter informações do predecessor se uma rota for solicitada.
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.
Find space remaining in a bin containing items 5,3,2 with capacity 10. · Encontre o espaço restante em uma caixa contendo itens 5,3,2 com capacidade 10.
Unused capacity=10-(5+3+2)=0. · Capacidade não utilizada=10-(5+3+2)=0.
Match each part of a complete solution to its purpose. · Associe cada parte de uma solução completa ao seu propósito.
An assumption justifies the model; a check tests the result; interpretation connects it to the question. · Uma suposição justifica o modelo; uma verificação testa o resultado; a interpretação conecta-o à pergunta.
Use this in your course
- edexcel IAL 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.