Teste da razão e da raiz

Me justificando, se tá ali pronto e simples, não vejo porque eu ter que digitar as fórmulas no programinha de fórmulas. É muito chato e trabalhoso.

Testes da comparação

Teorema: Seja Σ a_n e Σ b_n séries de termos não negativos; Se Σ a_n é convergente e a_n > b_n para qualquer n, então Σ b_n também é convergente. Se Σ a_n é divergente e a_n < b_n , Σ b_n é divergente.
Exemplo do livro estou realmente preguiçosa hoje.

Ok, agora o próximo:

Série P

Série P é toda série cuja variável n tem uma potência fixa p, que é um número real. O "formato" da n-ésima variável é sempre ¹/n^p. A série P irá convergir se p > 1 e divergir se p <= 1. Um exemplo retirado do livro:

(eu ainda não peguei qual é a do fundo cinza)

Teste da integral

Teorema: Seja Σ^∞_{n = 0} a_n uma série de termos positivos, então se ∫₀^∞ f(x) dx existe e der um valor "fixo", a série é convergente. Se o resultado for ∞, a série é divergente.

A série de termos positivos só converge se e somente se as somas parciais de seus termos tiverem um limite superior.
Exemplos:

• Série harmônica:
  
  Observe que o limite dessa série dá 0, mas ela é divergente. Isso ocorre porque não há um limite superior para as somas dos seus elementos. Ou seja, citando o livro porque eu nem entendi isso muito bem, "a soma dos 2n termos terminados em 1/2n+1 é maior do que 2n/2n+1 = 1/2". 1/2 no caso é o limite superior das somas dos termos.
• Série convergente qualquer:
  

Só lembrando que o resultado da integral não é o resultado da soma!

Séries telescópicas

Série telescópica é engraçadinha, porque a soma é sempre 1. Normalmente são resolvidas com frações parciais (lembra de cálculo 1? Pois é, eu também não lembrava). Exemplim:

(não sei porque minhas imagens estão ficando com fundo cinza, que saco)

Teste do n-ésimo termo para convergência

• Se uma série é convergente, então a_n tende a 0. Se o limite de a_n não for 0 ou não existir, a série é divergente. Em notação matemática:
  
• Sejam  séries convergentes. 

Séries geométricas

 Considerações sobre séries geométricas:

1. elas sempre começam de n = 0
2. a é uma constante diferente de 0 e r é a base
3. fim

A soma de n termos da série geométrica é  . O limite (sempre com n -> ∞) dessa soma é previsível dependendo do módulo de r. Se |r| < 1, o limite será ^a/1-r, caracterizando uma série convergente. Caso |r| >= 1, o limite tenderá ao infinito, sendo assim, uma série divergente.
Exemplo:

Séries infinitas

Citando o senhor Thomas, "dada uma sequência de números {a_n}, uma expressão da forma a₁ + a₂ + a₃ + ... + a_n + ... é uma série infinita." Do próprio nome "série infinita" já dá pra tirar alguma coisa, né. Normalmente as séries são definidas por somatórios (é bem melhor do que escrever um monte de termos soltos).
Séries infinitas podem ser classificadas como convergentes ou divergentes.
Uma série convergente é aquela cuja soma resulta num número (calma, não julguem o sentido dessa frase ainda), por exemplo: 1 + 1/2 + 1/4 + 1/8 + ... + 1/2ⁿ = 2. Mas obviamente a gente não precisa somar infinitos termos pra chegar nesse resultado: quando se soma até o n-ésimo termo (a chamada n-ésima soma parcial) já dá pra ir percebendo mais ou menos onde a série vai dar. 
Já uma série divergente é aquela cuja soma tende ao infinito (infinito não é número).

Paradigmas de projeto de algoritmos

Um paradigma é um conjunto de práticas que definem os modos de fazer de uma disciplina científica durante um certo período de tempo. Um paradigma é definido por:
– o que é para ser observado e avaliado
– as questões que devem ser feitas acerca de um tema de pesquisa
– como essas questões são estruturadas
– como os resultados das investigações científicas devem ser analisados

Em computação, do ponto de vista estrutural existem paradigmas racionalistas (tem origem na teoria da computação), tecnocráticos (origem na engenharia de software) e científicos (origem na teoria de algoritmos).
Existem, também, paradigmas de linguagens: orientadas a objetos, procedurais, lógicas, etc.
Alguns paradigmas de projeto de algoritmos:
● Recursividade: chama a si mesmo, direta ou indiretamente
● Tentativa e erro – backtracking: decompor o processo em um número finito de subtarefas que devem ser exploradas exaustivamente. Backtracking: selecione um caminho que pode levar à solução; se a escolha não se mostrar adequada então os caminhos derivados daquela escolha são ignorados e a busca pela solução retorna a um estágio anterior (backtracking)
● Divisão e conquista: Consiste em dividir o problema em partes menores, encontrar
soluções para as partes, e combiná-las em uma solução global
● Balanceamento
● Programação dinâmica: Se o mesmo subproblema precisa ser resolvido muitas vezes, então a abordagem é resolvê-lo uma vez e armazenar sua solução para uso posterior
● Algoritmos gulosos: Fazem a escolha que parece ser a melhor no momento
● Algoritmos aproximados
● Programação paralela

Hashing

Hashing é uma técnica de busca para encontrar elementos a partir de uma chave em um grande conjunto previamente armazenado.
Essa técnica se baseia em criar tabelas e utilizar funções de transformações de chaves de forma a obter o índice do elemento na tabela. Podem ocorrer elementos com índice igual. Essas 'colisões' podem ser tratadas com listas encadeadas ou com encadeamento aberto, que será explicado mais adiante.

Como fazer uma tabela hash

a tabela tem um tamanho fixo M. Basta calcular, usando uma função hash, um índice para cada chave de forma a distribuí-los na tabela entre 0 e M-1.

Tratamento de colisões:
As colisões podem ser tratadas por meio de listas encadeadas, ou seja, caso um elemento tenha um índice onde já há outro elemento, ele é inserido logo após a raíz da lista e aponta para o elemento seguinte.
Podem, também, ser tratadas por endereçamento aberto:

• Hashing linear: caso o índice definido para um elemento já esteja ocupado, ele será inserido na primeira posição vazia disponível a partir daquele índice. Só que é perigoso a tabela encher e os registros começarem a se agrupar.
• Hashing quadrático: o elemento é inserido na posição correspondente ao quadrado do primeiro índice encontrado.
• Hashing duplo: caso haja colisão, é aplicada outra função hash para obter outro índice.

Função hash:

A função hash mais comum para chaves inteiras é chave % M. Lembrando que caracteres podem ser transformados em inteiros utilizando seu código ascii.

Outros métodos de ordenação

Além dos métodos de ordenação interna vistos anteriormente, ainda existem outros que devem ser ressaltados. Normalmente, são melhores para conjuntos específicos de dados.

Ordenação digital: é adequada para conjuntos específicos de dados, como por exemplo CEP, porque tem o mesmo número de dígitos e seguem uma distribuição uniforme. Numa central de correios, por exemplo, as cartas poderiam ser separadas primeiro pelo primeiro dígito do CEP, e dentro dessa separação, pelo segundo dígito e assim por diante. Alguns algoritmos: radixsort, bucketsort.

Counting sort: ordenar um conjunto de N letras:
 Contar as frequências de cada letra usando a chave como índice
 Calcular a frequência acumulada
 Ordenar no array temporário
 Copiar no array original
Esse eu nem entendi muito bem, admito.

Ordenação parcial: ordenar parcialmente é pegar apenas os k primeiros registros de um conjunto de tamanho n em ordem. Mas esses k primeiros são ordenados de acordo com o total, só que depois deles o resto pode ficar tudo desordenado que não tem problema, a gente só queria os primeiros k mesmo.

Ordenação externa: a ordenação externa é efetuada quando o conjunto a ser ordenado não cabe na memória interna. São muito difíceis e exigem cuidado, pois o acesso a dados na memória externa é extremamente custoso e é apenas sequencial. Portanto, a complexidade é analisada de acordo com o número de transferências de dados entre memória externa ou secundária e a interna. Isso faz com que os métodos de ordenação externa variem de acordo com a tecnologia atual.
O método mais eficiente é a ordenação por intercalação. O algoritmo pega blocos de dados na memória externa, os ordena na memória interna e intercala esses blocos, fazendo várias passadas pelo arquivo. Eles são cada vez maiores, até que todo o arquivo esteja ordenado. To com preguiça de descrever o método das fitas, porque exige um exemplo. Caso um dia alguém precise, basta perguntar.

Algoritmos de ordenação eficientes

Algoritmos de ordenação eficientes são mais recomendados para arquivos muito grandes porque - adivinha - eles são eficientes. Tem 4 algoritmos eficientes: Quicksort, Shellsort, Heapsort e Mergesort.

Quicksort: o quicksort é baseado no bubble sort - ou seja, realiza trocas. Dado um conjunto inicial de dados, é escolhido aleatoriamente um índice cujo conteúdo será chamado pivô. Feita essa escolha, um contador i é iniciado do início para o fim, percorrendo os valores e comparando-os com o pivô. Ao achar um elemento maior ou igual ao pivô, o íncide i para e inicia-se um j, do fim para o início, percorrendo os valores e procurando um menor ou igual ao pivô. Quando esse elemento é encontrado, os valores das posições i e j são trocados e o processo recomeça. Quando os contadores i e j se cruzam (ou seja, i aponta para uma posição à direita de j), são definidas duas partições do vetor e são feitas duas chamadas recursivas do quicksort, uma para cada partição. Antes de prosseguir, note que ao formar partições, todos os elementos de uma delas serão menores ou iguais ao pivô e, da outra, maiores ou iguais ao mesmo.
O tempo de execução do algoritmo depende do bom balanceamento das partições, ou seja, se o número de elementos está bem distribuído dos dois lados do pivô. No caso de um bom balanceamento, o algoritmo é O(n logn). Porém, para o pior caso, o algoritmo é quadrático, o que o torna inviável devido às chamadas recursivas.

Shellsort: o shellsort é um melhoramento do insertion sort. Ele analisa o vetor como uma intercalação de conjuntos e ordena cada um desses conjuntos com o insertion sort. Uma vez ordenados, o processo se repete com conjuntos maiores e, para isso, menos espaçados. Explicando melhor, o shellsort faz passadas pelo vetor analisando elementos equidistantes entre si, com uma distância h dada por uma expressão no início do algoritmo. Ao ordenar os subconjuntos, que são formados por elementos com distância h entre si, o h diminui. Assim, os subconjuntos incluirão mais e diversificados elementos. O processo se repete até que h seja 1, ou seja, elementos adjacentes. O h=1 caracteriza o insertion sort, que é sensível à ordenação parcial do vetor e, portanto, muito eficiente.
Não existe análise de complexidade definida para o shellsort, porque o resultado depende da sequência h escolhida. Para algumas sequências, o algoritmo pode ser O(n^3/2), O(n^7/6), O(n^1,25) ou O(n*(log(n))2), como sugerem alguns experimentos.

Heapsort: o heapsort é um algoritmo baseado no selection sort. Ele organiza o vetor de forma que o elemento dos índices 2k e 2k+1 são sempre menores do que o do índice k. Fica mais fácil visualizar essa estrutura em forma de árvore, em que um elemento tem dois filhos e cada filho tem outros dois filhos e por aí vai. O pai sempre é maior que os filhos. Para montar o heap, inicia-se da metade do vetor (afinal, daí pra frente já não haverão mais filhos) e, para cada elemento, é selecionado o maior filho e comparado com o pai. Caso o maior filho seja maior do que o pai, os dois são trocados. Quando é analisado um elemento cujos filhos tem filhos e é feita uma troca, a análise segue a cadeia de filhos até o final para que o heap se mantenha correto. Quando ele estiver finalmente montado, o elemento da primeira posição é trocado com o da última e, como o atual topo é menor, o heap é corrigido. Ao final da correção, o mesmo é feito, porém com a penúltima posição e por aí vai, até sobrar apenas a posição do topo e aí o vetor estará o ordenado.
O algoritmo tem custo total da construção do heap e da ordenação, totalizando O(n log₂n).

Mergesort: o mergesort é um algoritmo baseado em intercalação. Dado um vetor de tamanho n, ele vai separando em vetores menores cujo tamanho é metade do vetor anterior e por aí vai, até que cada vetor tenha tamanho 1. Em seguida, vai juntando pares de vetores intercalando-os de maneira ordenada. É um algoritmo recursivo. Como usa espaço extra, é aconselhado para situações de mesclar dois vetores já ordenados, por exemplo.
Tem custo O(nlogn) e usa espaço extra de tamanho proporcional a n para todos os casos (insensível a ordenação inicial do vetor).

Algoritmos de ordenação simples

Temos 4 algoritmos básicos de ordenação simples: Bubble Sort, Insertion Sort, Selection Sort e Enumeration Sort.

Bubble Sort: o bubble é um algoritmo baseado em trocas. Ele percorre o vetor do início ao final comparando pares de elementos e trocando-os caso seja necessário. Ele faz isso quantas vezes forem necessárias até que a ordenação esteja completa. A cada passada, o maior elemento analisado já fica no lugar.
O bubble sempre será O(n²) comparações. Para trocas, seu melhor caso é O(1), pois não faz trocas caso os elementos já estejam ordenados, e caso médio e pior caso são O(n²).
É um algoritmo amplamente utilizado didaticamente, porém é ineficiente.

Insertion Sort: o insertion analisa cada elemento e o insere na posição correta em relação aos elementos já ordenados. Ou seja, é um algoritmo que não realiza trocas, mas sim movimentações (cada troca é composta de 3 movimentações). Um bom exemplo: imagine que você está jogando cartas. Para organizá-las na sua mão, você pega a carta à direita e, a partir da esquerda, encontra seu lugar e a insere ali, não é mesmo? Isso é o insertion sort.
O algoritmo é sensível à ordenação inicial do arquivo: para o pior caso, é O(n²) comparações, mas para o melhor (arquivo ordenado) é O(n). Idem para o número de movimentações.
Caso se tenha um arquivo quase ordenado ou poucos registros para inserir num arquivo ordenado, o insertion sort é mais recomendado do que métodos sofisticados.

Selection Sort: o selection seleciona no conjunto de n elementos o maior (ou menor, dependendo da ordem desejada) e o troca com a primeira posição. A seguir, repete o processo para n-1 elementos. Assim, a cada passada um elemento estará na posição correta.
O número de comparações também é O(n²), porém para cada elemento é feita uma troca (a troca é realizada mesmo se ele já estiver na posição correta). Assim, é O(n) para trocas.

Enumeration Sort: ele percorre o vetor e armazena em outro vetor do mesmo tamanho a posição relativa daquele índice na ordenação. Por exemplo, se tem-se
|9|3|7|4|2|8|, o enumeration cria um outro vetor com os seguintes valores:
|5|1|3|2|0|4|, que correspondem à posição que o elemento de mesmo índice no vetor original ocuparia num vetor ordenado.
Além de não ordenar de fato, o algoritmo ainda ocupa um espaço adicional do tamanho do vetor original, tornando-se extremamente ineficiente.

Método de Lagrange

Sejam n+1 pontos (x0, y0), (x1, y1), ..., (xn, yn). Podemos encontrar polinômios interpoladores de modo que o erro seja minimizado. Dado Pi(xi) = 0 e Pj(xj) != 0, temos:

Como o polinômio interpolador não tem grau superior a n, então podemos escrevê-lo como combinação linear. Só que tem um monte de coisas aqui no meu caderno pra ficar escrevendo e substituindo e eu to com preguiça. Vou direto ao trem:

Interpolação

Dados valores empíricos de uma determinada tabela xi; yi, podemos estimar por um polinômio interpolador valores de xi de modo que tenhamos a variável de resposta yi com certa precisão. O desafio maior para esse caso é exatamente saber qual polinômio utilizar de modo que o erro obtido seja o menor possível.

Interpolação linear
Seja P(x) um polinômio interpolador de modo que P(x) = a0 + a1*x. Deste modo, P(x0) = a0 + a1*x0 = y0 ; P(x1) = a0 + a1*x1 = y1. P(xi) é um polinômio interpolador de grau 1. Para n+1 pontos sempre tem-se (pode-se ter) um polinômio de grau n.
|1  x0|  |a0|    |y0|
|1  x1| .|a1| = |y1|

Interpolação quadrática
Análogo à interpolação linear, temos que a interpolação quadrática é um polinômio interpolador de grau 2, de modo que P(x0) = a0 + a1*x0 + a2*x0² = y0 ; P(x2) = a0 + a1*x1 + a2*x1² = y1 ; P(x2) = a0 + a1*x2 + a2*x2² = y2. A matriz para a forma quadrática é conhecida como matriz de Vandermonde e seu determinante é não nulo. Isso nos garante que o sistema linear terá uma única solução e o polinômio será único. A matriz:
|1  x0  x0²|    |a0|    |y0|
|1  x1  x1²| .  |a1| = |y1|    => o nome disso é preguiça
|1  x2  x2²|    |a2|    |y2|

Método de Gauss-Seidel

Seja A uma matriz diagonal estritamente dominante e um valor inicial x0 = bi / aii. A partir do método de Jacobi podemos variar determinados valores de xk de modo que a convergência para os valores de xi ocorram com menor custo. Para isso, é só fazer as contas no mesmo esquema de Jacobi, mas utilizando numa iteração valores obtidos na mesma. Por exemplo, eu descobri o x1. Aí na hora de descobrir o x2, ao invés de usar o x1 da iteração anterior, eu uso o que eu acabei de descobrir. O x3 usa o x2 mais novo e por aí vai. Assim chega mais rapidinho nos resultados!
Novamente, um dia eu posto um exemplo, agora to correndo aqui.

Método de Jacobi

Para o método estacionário, devemos decompor A de modo que (D+E+F) = A. Assim, o sistema Ax = b é (D+E+F)x = b. Realizando as operações possíveis, temos Dx = -(E+F)x + b.
Escrevendo x em processo de recorrência (iterativo) temos: x^k+1 = -D^-1 (E+F)x + D^-1b, onde -D^-1(E+F)x é uma matriz jacobiana.
A representação em sistema linear matricial, já evidenciando o valor de xi para cada equação linear, é a seguinte:

Sendo x0 = bi / aii.

Um dia eu escrevo o exemplo, porque na verdade a prova disso já passou e eu só to atualizando mais ou menos os resumos. Favor me lembrar.

Métodos iterativos estacionários

Um sistema linear pode ser resolvido por um processo iterativo a partir de um valor inicial x0 e uma sequência de vetores {x1, x2, x3 ... xn}.

Critério de parada
Como os métodos são iterativos, eles precisam parar alguma hora, né. Para o critério de parada é definido um valor ɛ tal que 

Decomposição por LDLT

Seja A uma matriz simétrica. Podemos decompor A pelo produto de 3 outras matrizes a saber. L é uma matriz triangular inferior e unitária e D é uma matriz diagonal. A solução é: [Ly = b; Dt = y; L^Tx = t] para  .
Podemos ver que um termo usa o outro pra ser definido (l usa d e vice versa). Por isso tem uma ordem para fazer: d₁₁, l₂₁, l₃₁, d₂₂, l₃₂, d₃₃ (num exemplo de matriz de ordem 3). A ordem é essa porque fazendo o d₁₁ (esse é o primeiro em matriz de qualquer ordem) é possível descobrir todos os l da primeira coluna (ou seja, abaixo do índice 11, já que a matriz é triangular inferior e unitária). Após descobrir todos esses, com o d₂₂ dá pra descobrir todos os l abaixo de 22 e por aí vai.

Tudo que eu sei pra primeira prova de AOC I

Aritmética	add	add $s1, $s2, $s3	$s1 = $s2 + $s3
	sub	sub $s1, $s2, $s3	$s1 = $s2 - $s3
	addi	add $s1, $s2, 100	$s1 = $s2 + 100 (soma constante)
Transferência de dados	lw	lw $s1, 100($s2)	$s1 = $s2[100] //(Memória[$s2+100]
	sw	sw $s1, 100($s2)	$s2[100] /*(Memória[$s2+100]<)*/ = $s1

foda-se, eu não sei nada