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).

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 S um conjunto (ou lista) de objetos e seja s uma função que mede o “tamanho” de cada objeto:
s : S \to \mathbb{R}_{\ge 0}.
Escolhe-se uma sequência crescente de limites (thresholds)
T=\{t_0,t_1,\dots,t_k\}\quad\text{com}\quad t_0<t_1<\dots<t_k,
onde normalmente se toma t_0=-\infty ou t_0=0 e t_k=+\infty para cobrir todos os tamanhos. A operação “Separação por Tamanho” produz uma família de grupos (baldes) \{B_1,\dots,B_k\} definida por
B_i=\{x\in S \mid t_{i-1}\le s(x)<t_i\},\quad i=1,\dots,k.
Explicação das partes: \,S é o conjunto de objetos, \,s(x) é o tamanho do objeto x, os t_i são os limites das faixas, e cada B_i contém exatamente os objetos cujo tamanho está na faixa [t_{i-1},t_i).

Passo 4

Variações e detalhes importantes (exam-ready):
  • Inclusão/exclusão nas fronteiras: pode-se usar [t_{i-1},t_i) como acima, ou (t_{i-1},t_i] — o importante é definir e manter consistentemente a convenção (examinar casos em que s(x)=t_i).
  • 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 t_i inteiros e as faixas ficam naturais (ex.: itens de tamanho 0, 1, 2, …).

Passo 5

Como aplicar passo a passo na prova (procedimento prático):
  1. Identificar o conjunto S e escrever a função tamanho s. Diga com palavras o que mede s.
  2. Escolher os limites t_0<\dots<t_k que definem as faixas (ou usar as faixas pedidas no enunciado). Declare explicitamente a convenção de inclusões nas fronteiras.
  3. Para cada x\in S calcule s(x) e determine o índice i tal que t_{i-1}\le s(x)<t_i. Coloque x em B_i.
  4. Ao final, apresente os grupos B_1,\dots,B_k ou contagens |B_i|, dependendo do que a pergunta pedir.

Passo 6

Exemplo concreto e curto (para eu praticar mentalmente): seja S=\{a,b,c,d\} com tamanhos s(a)=2, s(b)=5, s\text{(c)}=3, s(d)=9. Tome limites T=\{0,4,8,+\infty\}. Então
B_1=\{x\in S\mid 0\le s(x)<4\}=\{a,c\},
B_2=\{x\in S\mid 4\le s(x)<8\}=\{b\},
B_3=\{x\in S\mid 8\le s(x)<+\infty\}=\{d\}.
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 s(x) para cada x e faz uma comparação entre limites por item tem custo O(nk) no pior caso se for procurar linearmente o balde, mas pode-se obter O(n + k) 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 k baldes mais os n objetos: O(n+k).
  • 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 t_i.
  • Sempre escreva explicitamente a função s (o examinador quer ver que você sabe o que mede).
  • Se a pergunta pede apenas contagens, calcule |B_i| 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 S, uma função tamanho s:S\to\mathbb{R}_{\ge 0} e uma sequência de limites T=\{t_0<\dots<t_k\}, produz a partição (ou família de baldes) \{B_1,\dots,B_k\} definida por
B_i=\{x\in S \mid t_{i-1}\le s(x)<t_i\},\quad i=1,\dots,k,
outra convenção possível sendo usar intervalos fechados/direitos nas fronteiras, desde que explicitada.

Exercícios relacionados