Análise de Algoritmos e Complexidade

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

03 de março de 2023
→ O que veremos nesta disciplina?
 - Como provar a "corretude" de um algortimo
 - Estimar a quantidade de recursos (tempo, memória) de um algoritmo = análise de complexidade
 - Técnicas e ideias gerais de projeto de algortimos: Indução, divisão e conquista, programação dinâmica, algoritmos gulosos...
 - A dificuldade intrínseca de vários problemas: inexistência de soluções eficientes
→ O que é um algoritmo?
 - Procedimento computaciona bem definido que:
 - Recebe conjunto de valores como entrada
 - Produz um conjunto de valores como saída
 - Através de uma sequência de passos em um modelo computacional
→ Dificuldade intrínseca de problemas
 - Problemas em que não se conhece algoritmos eficientes capazes de resolvê-los
 - Exemplo: NP-Completo
 - Observação: Se for encontrada a solução polinomial para um desses problemas, será válida para os demais problemas também (redutibilidade de problemas)
 - Exemplo de problema NP-difícil: Calcular as rotas dos caminhões de entrega de um distribuídora de bebidas em São Paulo
→ Algoritmos e tecnologia:
 - Condição ideal (irreal): Os computadores têm velocidade de procedimento e memória infinita. Neste caso qualquer algoritmo é igualmente bom (sem necessidade de pensar em algoritmos)
 - Condição real: Limite de processamente e memória
 - Exemplo: Ordenação de um vetor de n elementos
 A → 1G (10^9) instruções por s = 1 * 10^9 = 10^9 (100x mais rápido)
 B → 10M (10^6) instruções por s = 10 * 10^6 = 10^7
 
 Alg. 1 = 2n² | Ordenar: 
 Alg. 2 = 50 n log n | n = 10^6
 
 Alg. 1 → Máq. A → 2(10^6)² / 10^9 
 → 2(10^12) / 10^9
 → 2 * 10³ = 2000s
 
 Alg. 2 → Máq. B → 50(10^6) * log(10^6) / 10^7 
 → 50 * 10^6 * 6 / 10^7
 → 30 * 10 * 10⁶ / 10^7 = 30s
→ Uso de algortimos determinísticos: A entrada é sempre a mesma, logo a saída também
→ Máquinas RAM (Random Access Machine)
 - Simula máquinas convencionais de verdade
 - Possui um único processador e executa instruções sequencialmente
 - Tipos básicos são números inteiros e reais
 - Análise do pior caso 
→ Complexidade quick-sort n²
 - Linguagens de programação geralmente utilizam esse método, apesar deste não ser o melhor algoritmo de organização, porque no melhor caso sua complexidade é log n (caso médio), o que o faz convergir para ordenação rapidamente.
→ O que é importante analisar?
 - Verificar a finitude: Se o algortimo finaliza
 - Verificar a corretude: Se o algortimo faz o que promete
 - Verificar a complexidade
 
17 de março de 2023
Notação assintótica e indução matemática
→ Algoritmo: Método para resolver um problema computacional. É a ideia por trás de um programa e independe da linguagem de programação, máquina, etc.
 - Propriedades:
 - Correção: Deve resolver corretamente todas as instâncias do problema
 - Eficiência: Desempenho (tempo e memória) deve ser adequado
 OBS: Serão analisados algoritmos determinísticos, que dado uma entrada devolvem sempre a mesma saída 
→ Preocupações: Importância da análise do tempo de execução
 - Predição: Quanto tempo um algoritmo precisa para resolver um problema? Qual a escala? Podemos ter garantias sobre o tempo de funcionamento?
 - Comparação: Um algoritmo A é melhor que um algoritmo B? Qual é a melhor forma de resolvermos um determinado problema?
 - Exemplo: Um algoritmo n² vs. n log n para ordenação de cerca de 100 valores, o primeiro algoritmo tem um gasto computacional 20x maior que o segundo (10000 e 500 iterações, respectivamente)
→ Random Access Machine (RAM): Modelo genérico e independente de linguagem e de máquina
 - Cada operação simples (ex: +, -, ←, if) leva 1 passo
 - Cada acesso a memória leva também 1 passo
 - Tempo de execução pode ser medido contando o número de passos como uma função do tamanho de entrada T(n)
→ Tipo de análise de algoritmos:
 - Pior caso: T(n) = quantidade máxima de tempo para qualquer entrada de tamanho n
 - Caso médio: T(n) = tempo médio para qualquer entrada de tamanho n. Implica em conhecimento sobre a distribuição estatística das entradas