Cormem

Projeto e Análise de Algoritmos Análise de Complexidade
Antonio Alfredo Ferreira Loureiro [e-mail] http://www.dcc.ufmg.br/~loureiro

UFMG/ICEx/DCC

PAA

·

Analise de Complexidade ´

1

Algoritmos
• Os algoritmos fazem parte do dia-a-dia das pessoas. Exemplos de algoritmos: – instruções para o uso de medicamentos; – indicações de como montar um aparelho; – uma receita de culinária. • Seqüência de ações executáveis para a obtenção de uma solução para um determinado tipo de problema. • Segundo Dijkstra, um algoritmo corresponde a uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações. – Executando a operação a + b percebemos um padrão de comportamento, mesmo que a operação seja realizada para valores diferentes de a e b.

UFMG/ICEx/DCC

PAA

·

Analise de Complexidade ´

2

O papel de algoritmos em computação
• Definição: um algoritmo é um conjunto finito de instruções precisas para executar uma computação. § Um algoritmo pode ser visto como uma ferramenta para resolver um problema computacional bem especificado. • Um algoritmo pode receber como entrada um conjunto de valores e pode produzir como saída um outro conjunto de valores. § Um algoritmo descreve uma seqüência de passos computacionais que transforma a entrada numa saída, ou seja, uma relação entrada/saída. • O vocábulo algoritmo origina do nome al-Khowarizmi.

UFMG/ICEx/DCC

PAA

·

Analise de Complexidade ´

3

Origem do vocábulo algoritmo
Abu Ja’Far Mohammed Ibn Musa al-Khowarizmi (780–850), astrônomo e matemático árabe. Era membro da “Casa da Sabedoria”, uma academia de cientistas em Bagdá. O nome al-Khowarizmi significa da cidade de Khowarizmi, que agora é chamada Khiva e é parte do Uzbequistão. al-Khowarizmi escreveu livros de matemática, astronomia e geografia. A álgebra foi introduzida na Europa ocidental através de seus trabalhos. A palavra álgebra vem do árabe al-jabr, parte do título de seu livro Kitab al-jabr