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

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?

Estruturas de Dados Lineares - Dinâmicas

EDs lineares dinâmicas são implementadas com listas encadeadas. Lista encadeada é aquela cujos elementos possuem apontadores para o próximo elemento (ou pode ter um pro anterior também... enfim, tem ponteiros). Essas listas são ótimas porque podem crescer ou diminuir em tempo de execução, porém a única maneira de acessar os itens é ir seguindo os links entre eles.
A definição de um nodo (célula da lista) é basicamente assim:
struct nodo {
   Item item; //pode ser qualquer coisa, meio que não interessa no momento
   struct nodo *prox; //note que a definição é recursiva

}
As listas podem ter nodos sentinela, que são células vazias opcionais colocadas no início e/ou fim da lista. Eles não contêm elementos válidos e são usados para simplificar as condições de limites. O nodo final sempre tem o valor null ou 0 ou aponta para um sentinela ou para o início da lista, tornando-a circular.

Implementação de uma lista linear simples com um nodo sentinela
● inicialização
lista = new nodo;
lista->prox = lista;

● testa lista vazia
(lista->prox == lista)

● insere t após x
t->prox = x->prox;
x->prox = t;

● remove nodo após x
t = x->prox;
x->prox = x->prox->prox;
delete t;

● loop para percorrer a lista:
t = lista->prox;
while (t!=lista) {
   t->item...; //operação
   t = t->prox;

}

Estruturas de Dados Lineares - Estáticas

Uma ED linear estática é implementada por um vetor. Fazem parte da ED: o vetor (dã) e as variáveis de controle (de inserções, retiradas, de quantos elementos tem) - números inteiros representando índices do vetor.
A definição de estrutura vazia pode ser feita via variáveis de controle, sem precisar inspecionar o vetor. Idem para estrutura cheia.
Testes de overflow (erro por tentar inserir elemento na estrutura cheia) e underflow (erro por tentar excluir elemento da estrutura vazia) são essenciais. As posições devem ser verificadas em cada caso de inserção e remoção de elementos.
Exemplo de implementação: pilha
int pilha[MAXTAM]; //a pilha :O
int topo; //a variável de controle, no caso sempre apontando para o topo da pilha

 inicializar a pilha:
topo = 0; //inicializa o controle, não o vetor

 definir a estrutura vazia
se topo = = 0 então a pilha está vazia

 comandos
return topo; //indica o número de elementos da pilha
return (topo = = 0); //indica se a pilha está vazia

 verificar se a estrutura está cheia

se (topo = = MAXTAM) então a pilha está cheia

 empilhar

se a pilha estiver cheia dá erro de overflow, senão adiciona o elemento no topo e incrementa ele

 desempilhar

se a pilha estiver vazia dá erro de underflow, senão decrementa o topo e retira o elemento dele

Tipos Abstratos de Dados

TADs são especificações de um certo conjunto de dados e das operações possíveis sobre eles, sendo esse conjunto de operações definido de acordo com a aplicação / contexto do problema a ser resolvido. O TAD não inclui a implementação, apenas especificações.
TADs servem para formalizar a definição do tipo de dados e operações. Ele é feito sem conexão com a implementação, permitindo diferentes implementações e que cada parte seja implementada independendo das outras. Um TAD bem implementado pode permitir que a implementação seja alterada mantendo a especificação.
Exemplo de TAD: fila
Modelo matemático: lista: seqüência de elementos
Operações: algoritmos que alteram o conjunto de dados
 inicializar a fila: criar uma fila vazia
 verificar se a fila está vazia
 inserir um elemento na fila
 enfileirar: sempre na última posição enqueue
 retirar um elemento da fila
 desenfileirar: retira o primeiro dequeue
 consultar o elemento do início da fila
 informar o tamanho da fila: retornar o número de elementos

 imprimir a fila

Estruturas de Dados lineares

Estruturas de dados são construções de dados que podem ser implementadas por uma linguagem de programação. Aprender a projetar EDs genéricas e eficientes é importante para saber escolher a certa para usar no programa: a escolha da ED afeta os algoritmos que podem ser utilizados, sendo mais ou menos eficientes, e para os mesmos dados, a ED pode ocupar mais ou menos espaço.
Nesse período serão estudadas EDs lineares: pilhas, filas e listas.
Definição formal de lista:
seqüência linear de 0 ou mais itens ou elementos cuja principal propriedade estrutural é a posição relativa dos elementos na seqüência:
 xi precede xi+1 para 1 <= i <= n - 1;
 xi sucede xi-1 para 2 <= i <= n;
 xi é o i-ésimo elemento da lista, x1 é o primeiro e xn é o último, sendo n o número de elementos (tamanho da lista).

Alguns tipos de listas:
 FIFO: First In First Out - o primeiro a entrar é o primeiro a sair
 LIFO: Last In First Out - o último a entrar é o primeiro a sair
 LRU: Least Recently Used - ordem dos menos utilizados recentemente
 MRU: Most Recently Used - ordem dos mais utilizados recentemente
 LFU: Least Frequently Used - ordem dos menos frequentemente utilizados
 MFU: Most Frequently Used -  ordem dos mais frequentemente utilizados

Pilhas e filas são variações de listas. Por exemplo, uma lista FIFO funciona como uma fila e uma LIFO, como uma pilha.

Alocação estática e dinâmica de memória:
Alocação estática de memória é gerenciada pelo compilador e alocada na stack memory. Quando você declara um vetor, por exemplo, ele tem o tamanho definido (no programa ou em tempo de execução, mas é sempre AQUELE tamanho) e já é alocado num espacinho contínuo quando seu programa compila. O acesso a cada elemento do vetor é aleatório e tem mesmo custo: basta ir ao vetor[indice] e pronto.
Alocação dinâmica de memória é gerenciada pelo programador e alocada na parte da memória denominada dynamic heap. Por exemplo: numa lista encadeada, não há um número fixo de elementos. O tamanho da lista é limitado apenas pela memória (heap e virtual), sendo, assim, uma estrutura muito versátil. Portanto, a criação E EXCLUSÃO deles deve ser pensada por você. Lembrando que é muito importante excluir elementos "inúteis" senão eles ficam ocupando memória e não são apagados quando seu programa é fechado. O acesso aos elementos da lista encadeada tem custo diferente para cada um, pois é sequencial. Então, se o elemento buscado for o último, a lista vai ter que ser percorrida inteira, cada elemento apontando para o próximo, até chegar no desejado.
Listas estáticas são implementadas com vetores (coleção fixa de elementos do mesmo tipo armazenados de forma contígua e acessíveis por um índice que têm correspondência direta e sequencial com a memória)
Listas dinâmicas, ligadas ou encadeadas são implementadas com ponteiros. Para entender isso basta ir ao resuminho de PC 1!

Capacitância

Um capacitor é um negocinho que armazena carga. É composto por duas placas (podem ser de qualquer formato, mas sempre serão chamadas placas) isolantes com cargas +q e -q. A capacitância é definida por q = CV, sendo q a carga e V a ddp entre as placas. A unidade é o Farad = 1 Coulomb / Volt.
Para calcular a capacitância, podemos

1. supor que uma carga q foi colocada nas placas
2. calcular, então, o campo E gerado por essa carga
3. depois, calcular a ddp V entre as placas
4. e por fim, jogando na definição q = CV para encontrar o valor.

Há alguns resultados particulares a serem considerados:

O capacitor de placas paralelas tem capacitância , sendo A a área das placas e d a distância entre elas.
O capacitor cilíndrico formado por dois cilindros coaxiais longos (comprimento L) e raios a e b tem capacitância .
O capacitor esférico formado por duas cascas esféricas concêntricas de raios a e b tem capacitância . Fazendo b = ∞ e a = R, temos a capacitância de uma esfera isolada de raio R: C = 4πɛ₀R.
Quando se tem capacitores em paralelo ou em série, é possível calcular a capacitância equivalente Ceq pelas seguintes expressões respectivamente: . Quando os capacitores estão em paralelo, todos estão sujeitos à mesma ddp. Em série, a soma das ddps resulta a total.
A energia potencial elétrica U de um capacitor carregado é igual ao trabalho necessário para carregar o capacitor e pode ser dada pelas seguintes fórmulas: . Essa energia pode ser associada ao campo E entre as placas e, por extensão, podemos associar a qualquer campo elétrico uma energia armazenada. No vácuo, a densidade de energia u (energia potencial por unidade de volume) associada a um campo de módulo E vale .

Agora dica amiga pra quem é aluno do infeliz do meu professor e vai fazer prova amanhã, tipo eu:
Fórmulas que não precisam de dedução:
V =-w/q

e = f/q  = kq/d²

q = cv

f = k.q1.q2 / d²

Potencial elétrico

A variação da energia potencial elétrica U de uma carga que se desloca de um ponto inicial i para um ponto final f é dada por ΔU = Ui - Uf = -W, onde W_∞ é o trabalho realizado pela força elétrica no deslocamento da carga de i para f. Se a energia potencial é definida como 0 no infinito, então a energia potencial elétrica U da carga pontual em qualquer ponto é dada por U = -W_∞ onde W_∞ é o trabalho da força elétrica para trazer a carga do infinito para o ponto em questão.
A diferença de potencial elétrico ΔV entre dois pontos i e f na presença de um campo elétrico é dada por ΔV = Vi - Vf = -W / q, onde q é a carga da partícula na qual é realizado o trabalho. O potencial em um ponto é dado por V = -W_∞ / q. A unidade é o Volt = 1 Joule / Coulomb. O potencial também pode ser dado em função da energia potencial U: V = U / q e  ΔV = ΔU / q.
Superfícies equipotenciais são pontos que possuem o mesmo potencial elétrico. O trabalho de deslocar uma carga de uma superfície equipotencial para outra não depende dos pontos de início e fim nem da trajetória entre os pontos. O campo elétrico é sempre perpendicular à superfície equipotencial correspondente.
A DDP calculada em função do campo E entre os pontos i e f é dada por  , sendo que a integral de linha é calculada ao longo do caminho de i até f.
O potencial produzido por uma carga pontual q, a uma distância r da carga, é dado por V = k q / r, e V tem o sinal de q. O potencial produzido por um conjunto de cargas é dado pela somatória dos potenciais de cada uma, ou seja, V = .
O potencial produzido por um dipolo elétrico a uma distância r do dipolo e com momento dipolar p = qd (sendo r >> d) é dado por , sendo θ o ângulo entre a reta que liga o ponto ao centro do dipolo e o eixo do dipolo.
O potencial produzido por uma distribuição contínua de cargas é dado por   onde a integral é calculada para toda a distribuição. Esse dq é distância vezes carga.
Para calcular o campo elétrico E a partir de V, considera-se que a componente de E em qualquer direção é o negativo da taxa de variação com a distância na tal direção. Ou seja, . As componentes de E são . Caso o campo seja uniforme, ele se reduz a , em que s é a direção perpendicular às superfícies equipotenciais. A componente paralela às superfícies é 0.
A energia potencial elétrica de um sistema de cargas pontuais é igual ao trabalho de montar esse sistema considerando que as cargas estavam no infinito em repouso. Para duas cargas separadas por uma distância r, a fórmula é a seguinte: . Para mais de duas cargas é só somar a energia dos pares de cargas, um de cada vez.
Em equilíbrio, toda carga em excesso de um condutor está na superfície externa dele. A carga se distribui de forma que o potencial de um condutor carregado é o mesmo em todos os pontos do condutor.

Lei de Gauss

Uma superfície gaussiana é uma superfície imaginária fechada que envolve a distribuição de cargas de um objeto. Ela pode ter qualquer forma, mas se possuir alguma simetria na distribuição de cargas os cálculos ficam mais fáceis.
A lei de Gauss relaciona os campos elétricos nos pontos de uma superfície gaussiana à carga total envolvida pela superfície. É expressa por .
O fluxo do campo elétrico através de uma superfície gaussiana é dado por . O vetor A representa a área que se está analisando. Ele tem o módulo da área e é perpendicular a ela. 
É possível demonstrar, usando a lei de Gauss, que:

1. Cargas em excesso de um condutor se concentram na superfície externa deste;
2. O campo elétrico externo nas proximidades da superfície de um condutor carregado é perpendicular à superfície e tem módulo , sendo sigma a densidade superficial de cargas. Dentro do condutor, o campo é 0;
3. O campo elétrico em qualquer ponto de uma linha de cargas infinita e com densidade linear de cargas uniforme lambda é perpendicular à linha e tem módulo , sendo r a distância entre a linha e o ponto em que se está analisando;
4. O campo elétrico produzido por uma placa não-condutora infinita com uma densidade superficial de cargas uniforme sigma é perpendicular ao plano da placa e tem módulo ;
5. O campo elétrico no exterior de uma casca esférica uniformemente carregada de raio R e carga q aponta na direção radial e tem módulo  , sendo r a distância entre o ponto analisado e a casca. A carga se comporta como se estivesse concentrada no centro da esfera. O campo dentro da casca é 0;
6. O campo elétrico no interior de uma esfera uniformemente carregada aponta na direção radial e tem módulo .