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²