T.2 · Matemática discreta, probabilidade e métodos numéricos

Preparação de graduação para o GRE. Objetivos locais dentro do escopo revisado do ETS; este é ensino original, não um teste oficial ou preditor de nota.

Pré-requisitos: Contagem finita, probabilidade elementar, recorrências e derivadas.

• Usar contagem, recorrências, raciocínio gráfico e lógica
• Calcular probabilidades e propriedades de distribuição
• Aplicar aproximação numérica e avaliar erro

recorrência: Regra que liga um termo de sequência a termos anteriores.

mutually exclusive: Eventos que não podem ocorrer simultaneamente.

Escolha o modelo de contagem primeiro: seleções ordenadas de r objetos distintos usam n(n−1)⋯(n−r+1), enquanto subconjuntos não ordenados usam C(n,r). Um grafo simples completo com n vértices tem uma aresta por par não ordenado de vértices, resultando em n(n−1)/2 arestas; laços e arestas múltiplas alterariam o modelo. Para n retas em posição geral num plano, a k-ésima reta cruza as anteriores k−1 retas em pontos distintos e adiciona k regiões. O total é 1+n(n+1)/2; paralelas ou concorrência quádrupla invalidam essa contagem.

Use complementos para contar pelo menos uma ocorrência e condicione na população restante real após um sorteio sem reposição. Para r resultados i.i.d. escolhidos de n valores igualmente prováveis, a probabilidade de todos serem distintos é n(n−1)⋯(n−r+1)/n^r quando r≤n. Seu complemento conta resultados repetidos. Para uma contagem binomial com N ensaios independentes e probabilidade fixa de sucesso p, a média é Np e a variância Np(1−p). Probabilidades idênticas sozinhas não estabelecem independência.

Uma recorrência descreve valores posteriores a partir dos anteriores e precisa de dados iniciais suficientes para determinar uma sequência. Separe o índice do valor: a_n=2a_(n−1) com a_0=3 resulta em a_n=3·2^n. Argumentos gráficos e algorítmicos frequentemente estabelecem uma recorrência identificando o que um novo vértice ou passo adiciona. Uma fórmula fechada deve satisfazer tanto a recorrência quanto suas condições iniciais; ajustar alguns termos observados não prova que vale para todo índice.

Aproximação numérica exige um argumento de erro. A bisseção preserva um intervalo com mudança de sinal para uma função contínua e reduz sua largura à metade a cada etapa; uma raiz pode estar ausente se a continuidade falhar. A atualização de Newton é x_new=x−f(x)/f′(x), exigindo derivada não nula no ponto atual; a convergência não é automática a partir de qualquer valor inicial. O resíduo de uma aproximação e seu erro em x são diferentes. Declare as suposições do método e um critério de parada, em vez de tratar decimais extras exibidos como precisão.

Para f(x)=x²−2 e x₀=1, o passo de Newton resulta em 1−(1−2)/2=1.5. O próximo valor é 1.5−0.25/3=1.4167. Estes aproximam sqrt(2), mas f′(0)=0 torna zero um ponto inicial inválido.

Eventos com probabilidades positivas não podem ser simultaneamente independentes e mutuamente exclusivos.

Quatro sorteios rotulados são independentes e uniformes de cinco símbolos, com reposição. Encontre a probabilidade de que pelo menos dois sorteios concordem. Compare o número de seleções ordenadas e não ordenadas de quatro símbolos distintos.

Solução resolvida

Existem $5^4$ strings ordenadas de retirada igualmente prováveis. As strings sem repetição totalizam $5\cdot4\cdot3\cdot2=120$.

Seleções ordenadas distintas contam 120; subconjuntos não ordenados contam $\binom54=5$. Cada subconjunto ocorre em $4!=24$ ordens. Dividir por $4!$ é adequado apenas para a contagem não ordenada, não para o denominador da probabilidade de sorteio.

Aplique a bisseção em $f(x)=x^3-2$ no intervalo $[1,2]$. Dê os primeiros dois intervalos retidos e um limite para o erro do ponto médio após dez bisseções. Uma mudança de sinal sozinha justificaria a bisseção para $1/x$ no intervalo $[-1,1]$?

Verificar após tentar

O polinômio é contínuo; $f(1)<0<f(2)$. O primeiro ponto médio é $1.5$ com valor positivo, retendo $[1,1.5]$. O próximo é $1.25$ com valor negativo, retendo $[1.25,1.5]$. Após dez divisões pela metade, a largura é $2^{-10}$ e o ponto médio desse intervalo retido difere da raiz entre colchetes em no máximo $2^{-11}=1/2048$. O limite de erro usa o intervalo, não apenas um resíduo pequeno. Para $1/x$, zero é uma singularidade e não há raiz. A continuidade no intervalo falha; sinais opostos nas extremidades não justificam o método.