analise de algoritimo

Aula 2
ANÁLISE DE ALGORITMOS INTRODUÇÃO
PROF° MARCOS ALVES MARIANO
CENTRO UNIVERSITÁRIO DA GRANDE DOURADOS
FACULDADE DE CIÊNCIAS EXATAS E DA TERRA
CIÊNCIA DA COMPUTAÇÃO
Resolvendo Problemas:
Ir de casa ao trabalho
Conquistar um(a) namorado(a)
Analisar orçamento doméstico
Para resolver problemas temos receitas, procedimentos, descrição de processos – Algoritmos
ESCOPO DO CURSO
Algoritmo
A essência de um procedimento computacional, instrução passo-a-passo detalhadas
Programa
Implementação do algoritmo em uma linguagem de programação
Estrutura de dados
Organização dos dados necessários para resolver o problema
ESTRUTURA DE DADOS E ALGORITMOS
Computador na solução de problemas
Projetar
Escrever
Verificar
Questões Importantes na projeção de algoritmos
Corretude
Eficiência
Reusabilidade
Este curso não é sobre
Linguagem de programação, Arquitetura de computadores, Arquitetura de software, Processos de software e princípios de implementação
VISÃO GERAL
Entrada: sequência de n números
Saída: permutação de maneira que a’1≤ a’2…≤a’n
Exemplo:
Entrada: 8 2 4 9 3 6
Saída: 2 3 5 6 8 9
PROBLEMA DE ORDENAÇÃO
Número infinito de instâncias de input satisfazendo a especificação, por exemplo:
Sequência ordenada em ordem crescente
Sequência ordenada em ordem decrescente
Sequencia em ordem aleatória
PROBLEMA ALGORÍTIMICO
Algoritmo descreve ações no input
Podemos ter um número infinito de algoritmos corretos para o mesmo problema
SOLUÇÃO ALGORÍTMICA
Um algoritmo é uma sequência de instruções sem ambiguidade para solucionar um problema, isto é, para obter um output exigido para qualquer input válido em um intervalo de tempo finito.
Tipos de problemas
Projeto Genoma Humano
Busca/Roteamento na Internet
Distância entre pontos (google maps)
Multiplicação de matrizes
DEFINIÇÃO DE UM ALGORITMO
Estrutura de dados
Técnicas
Problemas Difíceis
Problemas NP-Completos
Aplicações Reais
Problema do