Equações lineares de 1ª ordem

São equações do tipo , onde:
- y e dy/dx são multiplicados por funções de x, somente;
- y e dy/dx estão elevados a 1

Método de resolução:

1. resolva a ED na forma descrita acima para a forma padrão   dividindo a equação por a₁(x)
2. procurar um fator de integração μ(x) multiplicando a ED na forma padrão por μ(x):
    , implicando que 
   SENDO QUE μ(x) é obtido de 
   
   

Muito confuso, né? Pois é. Sóoo que eu tenho exemplo!

Resolva 

1. Colocar no formato padrão (dividindo por x): 
2. Obter um μ(x): 
3. Multiplicar a ED por μ(x):
4. Encontrando y: 
   

Somatórios e exemplos

Conceito de OPERAÇÃO RELEVANTE: A op. relevante é a operação básica mais importante do código que representa seu custo. Numa inicialização de vetor, por exemplo, a operação relevante é a atribuição. Em geral, a op. relevante tem a ver com a semântica (significado; função) do código.
A complexidade do algoritmo muitas vezes é representada pela op. relevante pelo fato dessa representação muitas vezes ser da mesma ordem de complexidade do total de operações.

Somatórios simples:

1. soma de uma constante: 
   
   
2. soma dos nºs naturais até n: 

Exemplos:

1. análise da função fatorial

   int fatorial (int N) {       int fat = 1;       for (in i=2; i<=N; i++)          fat = fat * i;       return fat;    }

   Operação relevante: multiplicação f(n) = nº de repetições da OP. relevante

   
   
2. soma de matrizes
   
   

   for(int i=1; i<=N; i++)       for(int j=1; i<=N; j++)          C[i][j] = A[i][j] + B[i][j]

   Operação relevante: soma f(n) = nº de repetições da OP. relevante

   
   
3. multiplicação de matrizes
   
   

   for(int i=1; i<=N; i++)       for(int j=1; i<=N; j++){          C[i][j] = 0;          for(int k=1; k<=N; k++)             C[i][j] = C[i][j] + A[i][k] * B[k][j];       }

   Operação relevante: multiplicação f(n) = nº de repetições da OP. relevante

   
   
4. dois laços em sequência
   

   int soma = 0;    for(int i=1; i<=N; i++)       scanf("%d", &a[i]);    for(int j=1; i<=N; j++)       soma = soma + a[j];

   f(n) = nº de instruções

Análises de casos

Temos 3 casos possíveis ao executar um algoritmo: melhor caso, pior caso e caso médio ou esperado.

O melhor caso é a execução com o menor número possível de instruções (ou seja, a mais eficiente).

O pior caso é a execução com o maior número possível de instruções (menos eficiente). Fornece um 'teto' para o número de instruções.

O caso médio é a média ponderada de todas as entradas e suas chances de ocorrer.

Os casos são causados por comandos condicionais, porque estes direcionam a caminhos diferentes de execução e esses caminhos podem ter mais ou menos comandos. Alguns exemplos pra entender direitinho:

Busca pelo maior elemento (entrada:vetor; saída: índice do maior elemento):

- num vetor de n elementos, são executadas n-1 comparações. Afinal, nunca saberemos se um número é o maior se não testarmos todos.

- num vetor de n elementos, podem ser executadas entre 1 e n atribuições (do índice do maior elemento pra variável que for retornar). Considerando o nº de atribuições:

• melhor caso: o elemento está na primeira posição
• pior caso: o elemento está na última posição
• caso médio: o elemento está no meio

Busca pelo maior E menor elementos (entrada:vetor; saída: índices do maior e menor elementos):

1. utilizando o seguinte método:
   if (a[i] > max) max = i;
   if (a[i] < min) min = i;
   - num vetor de n elementos, são executadas 2n-2 comparações. Afinal, nunca saberemos se um número é o maior ou menor se não testarmos todos.
2. utilizando o seguinte método, que faz muito mais sentido porque se um elemento é maior, ele não pode ser o menor, nem precisa conferir:if (a[i] > max) max = i;else if (a[i] < min) min = i;

• melhor caso: n-1 comparações com o maior elemento na primeira posição
• pior caso: 2n-2 comparações com o maior elemento na última
• caso médio: supondo 50% de chance de o elemento ser maior que o anterior e não entrar no else e 50% de chance dele não ser maior que o anterior e entrar, temos o seguinte: f(n) = ((n-1) + (2n-2)) / 2 = 3/2 (n-1) comparações em média

Algoritmo de busca sequencial de um elemento no vetor:

- o elemento pode existir ou não, e a análise de complexidade é feita separadamente para essas duas hipóteses.

- a busca é sequencial, ou seja, vai procurando no vetor até achar ou chegar no fim, indicando que não achou o elemento procurado.

• pesquisa sem sucesso: são feitas n comparações para constatar que o elemento não esta lá.
• pesquisa com sucesso:
• melhor caso: o elemento está na primeira posição (1 comparação)
• pior caso: o elemento está na última (n comparações)
• caso médio: média ponderada dos casos e suas probabilidades. Como não sabemos probabilidades específicas, podemos considerar todas iguais (p = 1/n). Assim, temos f(n) = 1/n (1 + 2 + 3 + ... + n), resultando em (n+1)/2

Análise de espaço e tempo

A análise de complexidade dos algoritmos é importante para definir o custo inerente a eles. Desta forma, dado um problema pode-se definir qual é a melhor solução para ele. Todo tipo de custo é calculado, mas os principais são o tempo de execução (uso de CPU) - relacionado ao nº de operações que o programa executa - e o espaço ocupado (uso de memória) - relacionado à quantidade de dados.
A análise do espaço é feita de forma muito simples: avaliando a quantidade de variáveis e o espaço ocupado por cada uma delas. O uso eficiente do espaço se dá quando o algoritmo utiliza o espaço da entrada mais uma fração desse valor. O uso pouco eficiente se dá quando o algoritmo utiliza o espaço dos dados da entrada mais uma vez ou mais esse valor.

A análise do tempo pode ser feita de duas formas:

• Medição empírica: mede o tempo do mesmo algoritmo para entradas diferentes. É uma medição muito particular, porque vai depender da capacidade de processamento do computador, do hardware, do sistema operacional, enfim. Muitas coisas. Por ser uma medida tão particular, ela só é válida para o ambiente em que foi feita, apesar de dar o tempo real da execução.
• Medida analítica: determina a quantidade de trabalho para resolver o problema baseando-se na entrada de dados, no algoritmo utilizado e na natureza do problema. O tempo é proporcional à quantidade de instruções executadas (dentre atribuições, operações lógicas, aritméticas, leitura e escrita de dados, condicionais, loops, chamadas a outras funções e combinações de todos esses procedimentos), portanto, conta-se o número de instruções e o custo é dado por uma expressão matemática que tem n (nº de entradas) como parâmetro e resulta no nº de instruções em função de n. Para medir certinho o tempo, basta calcular o tempo médio por instrução e multiplicar pelo nº de instruções.
  
  Exemplo: seja o comando for(i=0; i<N; i++) a[i] = 0; O laço é executado N vezes. Portanto, há 1 atribuição de valor a i (em i=0), N incrementos de i, N+1 comparações para ver se i<N e N atribuições do valor 0 a cada posição do vetor a. Portanto, a inicialização de um vetor é dada por f(n) = 3n + 2; sendo f(n) o número de instruções executadas.

DADO: um computador de 1GHz executa aproximadamente 10^9 instruções por segundo, cada uma com custo médio de 1ns.

Algoritmo ótimo é aquele que cujo custo equivale ao custo mínimo da classe de problemas que ele resolve.

AEDS - Primeiros conceitos

Algoritmo é um conjunto finito (preferencialmente pequeno) de instruções destinadas a solucionar determinado problema. Há uma definição formal de algoritmos chamada Máquia de Turing. Todo algoritmo pode ser expresso por uma MT que, em resumo, é uma máquina que interpreta uma sequência de bits - uma abstração do computador.
Características desejáveis em algoritmos:

• Correção: o algoritmo apresenta a saída correta para qualquer entrada válida
• Eficiência: uso eficiente dos recursos computacionais
• Elegância: ser simples e claro, de fácil interpretação
• Robustez: ser capaz de lidar com qualquer entrada de dados
• Generalidade: ser adaptável a dados e sistemas diferentes

Estrutura de dados é a abstração de um conjunto de dados, sua representação. A escolha da estrutura de dados correta é importantíssima, pois ela limita ou define quais algoritmos usar. Algoritmos e estruturas de dados são interdependentes, e juntos compõem programas.

O problema que o algoritmo visa solucionar é o que fazer com uma entrada para que ela gere a saída desejada; é a relação entre entrada e saída. O algoritmo especifica como fazer isso com a entrada.

Computabilidade é a existência de uma solução algorítmica para um problema. Por exemplo, achar o enésimo termo da sequência de Fibonacci é um problema computável, mas achar o segredo da felicidade não (profundo, hein). Toda função computável pode ser expressa por uma MT.

Teoria de algoritmos é uma área que trata da eficiência dos algoritmos. As soluções para problemas computáveis são uma fração de todos os problemas, e soluções eficientes são uma fração destas. 

Equações Diferenciais Exatas

RELEMBRANDO: diferencial total (dF) de uma função  
Por exemplo: f(x, y) = x² + 3xy nos dá df = (2x + 3y) dx + 3x dy.
Agora voltando.
Definição: uma EDO escrita na forma M(x, y) dx + N(x, y) dy é exata se o formato mostrado (em vermelho) for o diferencial total de uma função f(x, y).

Exemplo: a equação x²y³ dx + x³y² dy = 0 é exata pois é a diferencial total da função f(x, y) = ⅓ x³y³

Critério para determinar se uma função é exata: considere uma EDO na forma M(x, y) dx + N(x, y) dy = 0. Se a ED é exata, temos . Teremos também  , logo   porque as derivadas parciais mistas são iguais.

Exemplo: verifique se 2xy dx + (x² - 1)dy = 0 é exata.
Temos:   M = 2xy   e   N = x²-1. Derivando parcialmente como mostrado acima, temos ambas as derivadas parciais mistas iguais a 2x. Portanto, a ED é exata.

Formato da solução numa ED exata: temos M(x, y) dx + N(x, y) dy = 0. Se a ED for exata, podemos descrevê-la como df = 0, portanto f(x, y) = C é a solução da ED.

1. Verificar se a ED é exata ✓
2. 
   o termo g(y) aparece na função porque sabemos apenas a parte originária da derivada parcial de x
3. 
4. x²-g'(y) = x²-1   =>   g'(y) = -1   =>   g(y) = -y
5. f(x, y) = x²y - y. Solução: x¹y - y = C

Tabela de Integrais

Segue a "breve" tabela de integrais do livro de cálculo do Thomas, vol. 2: