Defina a operação de Separação por Tamanho.
Passo 1
O que o enunciado pede: definir o que é a operação chamada “Separação por Tamanho”.
Informações dadas: apenas o pedido de definição (não há dados numéricos ou figura no enunciado).
Informações dadas: apenas o pedido de definição (não há dados numéricos ou figura no enunciado).
Passo 2
Resumo intuitivo (em palavras simples e sem fórmulas ainda): a Separação por Tamanho é uma operação que pega um conjunto de objetos e os organiza em grupos (ou “baldes”) com base em uma medida de tamanho de cada objeto — por exemplo comprimento, peso, número de elementos, duração etc. Cada objeto vai para o grupo cujo intervalo de tamanhos contém o tamanho dele. É a ideia por trás de histogramas, bucket sort e de agrupar itens por faixas de tamanho.
Passo 3
Definição formal básica. Seja
um conjunto (ou lista) de objetos e seja
uma função que mede o “tamanho” de cada objeto:
Escolhe-se uma sequência crescente de limites (thresholds)
onde normalmente se toma
ou
e
para cobrir todos os tamanhos. A operação “Separação por Tamanho” produz uma família de grupos (baldes)
definida por
Explicação das partes:
é o conjunto de objetos,
é o tamanho do objeto
, os
são os limites das faixas, e cada
contém exatamente os objetos cujo tamanho está na faixa
.
Passo 4
Variações e detalhes importantes (exam-ready):
- Inclusão/exclusão nas fronteiras: pode-se usar
como acima, ou — o importante é definir e manter consistentemente a convenção (examinar casos em que ). - Faixas abertas/fechadas: escolha depende do contexto; para evitar ambiguidade faz-se uma faixa fechada à esquerda e aberta à direita, ou vice‑versa.
- Se os tamanhos são inteiros (por ex. contagens), costuma-se escolher
inteiros e as faixas ficam naturais (ex.: itens de tamanho , , , …).
Passo 5
Como aplicar passo a passo na prova (procedimento prático):
- Identificar o conjunto
e escrever a função tamanho . Diga com palavras o que mede . - Escolher os limites
que definem as faixas (ou usar as faixas pedidas no enunciado). Declare explicitamente a convenção de inclusões nas fronteiras. - Para cada
calcule e determine o índice tal que . Coloque em . - Ao final, apresente os grupos
ou contagens , dependendo do que a pergunta pedir.
Passo 6
Exemplo concreto e curto (para eu praticar mentalmente): seja
com tamanhos
,
,
,
. Tome limites
. Então
Esse exercício pequeno mostra exatamente como aplicar a definição.
Passo 7
Propriedades úteis e complexidade (quando for implementar ou justificar):
- Uma execução que calcula
para cada e faz uma comparação entre limites por item tem custo no pior caso se for procurar linearmente o balde, mas pode-se obter com técnica direta (por ex. calcular índice por fórmula ou usar mapeamento direto) — essa é a ideia por trás do bucket sort. - Memória: precisa de espaço para armazenar os
baldes mais os objetos: . - Conservação de ordem (estabilidade): se for importante manter a ordem relativa dentro de cada balde, insira os itens na ordem original (balde estável).
Passo 8
Erros comuns e dicas de prova:
- Não esqueça de declarar a convenção para pontos exatamente iguais a um limite
. - Sempre escreva explicitamente a função
(o examinador quer ver que você sabe o que mede). - Se a pergunta pede apenas contagens, calcule
em vez de listar objetos. - Em problemas algorítmicos, mencionar complexidade e estabilidade costuma somar pontos.
Resposta
A operação “Separação por Tamanho” é a operação que, dado um conjunto
, uma função tamanho
e uma sequência de limites
, produz a partição (ou família de baldes)
definida por
outra convenção possível sendo usar intervalos fechados/direitos nas fronteiras, desde que explicitada.