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

Ordenação

Ordenar é arranjar um conjunto de elementos de acordo com determinada relação. É muito importante para pesquisar e apresentar dados e informação.
Alguns conceitos a serem conhecidos:
Arquivo: é um conjunto de n itens para ser ordenado;
cada Item é um objeto ou registro;
cada Registro contém uma Chave k que governa o processo de ordenação;
podem existir chaves iguais;

Os métodos de ordenação podem ser divididos assim:

Classificação de algoritmos quanto ao método de ordenação:

A ordenação por comparação é quando se observa duas chaves como valores e as compara. É adequada para qualquer tipo de dados e não tem restrições quanto às chaves. Existem quatro tipos de ordenação por comparação:

1) Ordenação por inserção: os itens são considerados um a um e cada novo item é inserido na posição correta relativa aos itens previamente ordenados

2) Ordenação por troca: se dois itens estão fora de ordem, eles são trocados; o processo é repetido até que não sejam necessárias mais trocas

3) Ordenação por seleção: o menor elemento é escolhido e separado dos demais; o processo se repete para os elementos restantes até que reste apenas um elemento

4) Ordenação por enumeração: cada item é comparado com todos os demais; a contagem do número de chaves menores determina a posição relativa do item no conjunto; método exige espaço adicional: não tem interesse prático

A ordenação digital observa os dígitos das chaves separadamente. É mais aconselhada para chaves com um mesmo número de dígitos, ou que seguem uma distribuição uniforme.

Classificação de algoritmos quanto ao espaço requerido pelos métodos:

A ordenação interna é aquela na qual a quantidade de dados cabe na memória principal. O acesso aos dados é mais fácil e pode ser aleatório, permitindo maior flexibilidade na estruturação dos dados.

As operações relevantes para algoritmos internos de comparação são o número de comparações entre chaves, o número de trocas dos elementos e o número de movimentações. O custo varia de acordo com o tamanho do arquivo e o arranjo inicial dos dados. São classificados em

• algoritmos simples (complexidade quadrática): são melhores pra arquivos pequenos. Alguns exemplos são o bubble, insertion, selection e enumeração.
• algoritmos eficientes (complexidade n logn ou n^(3/2)): são mais sofisticados e recomendados para arquivos grandes. Tipo quicksort, shellsort, heapsort, etc.

A ordenação externa é a que os dados não cabem na memória principal, requirindo uso de memória secundária. Há restrições para o acesso dos dados, tornando o acesso sequencial mais rápido do que o aleatório.

Classificação de algoritmos quanto à estabilidade:

Algoritmo estável é aquele que preserva a ordem relativa dos dados. Por exemplo, se pegamos uma lista de clientes de banco e ordenamos primeiro alfabeticamente depois por saldo, os clientes com mesmo saldo permanecem em ordem alfabética - são feitas duas ordenações com chaves diferentes.

A ordenação instável não mantém essa ordem relativa dos dados.

Comparação entre listas estáticas e dinâmicas

Estática

Vantagens
● acesso a qualquer elemento com custo O(1), porque os elementos já tem indexação direta
● melhor uso do espaço: só armazena os dados
● não usa apontadores
– implementação mais simples
– menos sujeita a erros

Desvantagens
● custo elevado para inserções e retiradas em qualquer posição: O(n) (porque para inserir numa posição que não seja a última, é preciso deslocar todos os elementos para liberá-la e para retirar, é preciso retornar todos os elementos uma posição)
● redimensionamento é difícil e caro, quando possível - a função realloc() é muito cara.

Dinâmica

Vantagens
● alterar o tamanho da lista é simples
● inserção e retirada têm custo O(1) quando é apontado o item a ser retirado
● não necessita deslocar elementos

Desvantagens 
● acesso aos elementos é apenas seqüencial
● ocupa mais espaço para armazenar o mesmo número de itens
● uso de apontadores

● implementação mais sujeita a erros

Critérios para a escolha da melhor estrutura
Acesso: como será o acesso aos elementos?
– sempre seqüencial, sempre aleatório?

Número de elementos a ser armazenado
– é conhecido? é previsível? ou não?

Inserções e retiradas
– há muitas inserções e retiradas?
– onde são: no início? no fim? posições variáveis?

Demais operações a serem realizadas
– quais são? busca? máximo ou mínimo?
– pesquisa conjugada com inserção? ordenação eventual ou freqüente?
– retornar o elemento de uma posição específica?
– o custo de todas as operações deve ser analisado em relação a sua freqüência

Espaço ocupado

– há restrições? são muitos dados? dados cabem na memória?