Cormem

Disponível somente no TrabalhosFeitos
  • Páginas : 66 (16414 palavras )
  • Download(s) : 0
  • Publicado : 6 de setembro de 2012
Ler documento completo
Amostra do texto
Projeto e Análise de Algoritmos Análise de Complexidade
Antonio Alfredo Ferreira Loureiro
loureiro@dcc.ufmg.br 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 receitade 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ídaum 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 Kitabal-jabr w’al muquabala. Esse livro foi traduzido para o latim e foi usado extensivamente. Seu livro sobre o uso dos numerais hindu descreve procedimentos para operações aritméticas usando esses numerais. Autores europeus usaram uma adaptação latina de seu nome, até finalmente chegar na palavra algoritmo para descrever a área da aritmética com numerais hindu.
UFMG/ICEx/DCC PAA

·

Analise deComplexidade ´

4

Algoritmo: Etimologia1
• Do antropônimo2 árabe al-Khuwarizmi (matemático árabe do século IX) formou-se o árabe al-Khuwarizmi ‘numeração decimal em arábicos’ que passou ao latim medieval algorismus com influência do grego arithmós ‘número’; forma histórica 1871 algorithmo.
1 Estudo da origem e da evolução das palavras. 2 Nome próprio de pessoa ou de ser personificadoReferência: Dicionário Houaiss da Língua Portuguesa, 2001, 1a edição.

UFMG/ICEx/DCC

PAA

·

Analise de Complexidade ´

5

Algoritmos: Definições
• Dicionário Houaiss da Língua Portuguesa, 2001, 1a edição: – Conjunto das regras e procedimentos lógicos perfeitamente definidos que levam à solução de um problema em um número de etapas. • Dicionário Webster da Língua Inglesa: – An Algorithm is aprocedure for solving a mathematical problem in a finite number of steps that frequently involves a repetition of an operation

UFMG/ICEx/DCC

PAA

·

Analise de Complexidade ´

6

Algoritmos: Definições
• Introduction to Algorithms, ClRS, 2001, 2nd edition: – Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input andproduces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input onto the output. • Algorithms in C, Sedgewick, 1998, 3rd edition: – The term algorithm is used in computer science to describe a problemsolving method suitable for implementation as a computer program.

UFMG/ICEx/DCC

PAA

·

Analise de Complexidade ´

7...
tracking img