Introdução de Algoritmos

Há muitas classes gerais de problemas que aparecem na matemática discreta. Por exemplo:

·         Dada uma sequência de números inteiros, encontre o maior;

·         Dado um conjunto, liste todos os seus elementos;

·         Dado um conjunto de números inteiros, coloquei-os em ordem crescente;

·         Dada uma rede de transmissão, encontre o caminho mais curto entre dois vértices;

Quando apresentamos problemas como esses, a primeira coisa a fazer é construir um modelo que traduza o problema em um contexto matemático. As estruturas discretas usadas em tais modelos incluem conjuntos, sequências e funções, assim como outras estruturas como permutações, relações, grafos, árvores, redes e máquinas de estado finito.

Construir o modelo matemático apropriado é apenas parte da solução. Para completa-la, é necessário um método que resolva o problema geral usando esse modelo. Em condições ideais, o que é preciso é um procedimento que siga uma sequência de passos para chegar à resposta desejada. Tal sequência de passos é chama de algoritmo.

DEFINIÇÃO

Um algoritmo é um conjunto finito de instruções precisas para realizar uma operação computacional ou para resolver um problema.

O termo algoritmo é a simplificação do nome al-Khowarizmi, um matemático do século IX, cujo livro sobre numerais hindus é a base da notação decimal moderna. Originariamente, a palavra algorismoera usada nas regras para realizar aritmética usando a notação decimal. Algorismopassou a algoritmo no século XVIII. Com o crescimento do interesse em máquinas computacionais, o conceito de algoritmo teve seu significado expandido para incluir todos os procedimentos definidos para resolver problemas, não apenas os procedimentos de aritmética.

Mesmo que o problema de encontrar o maior elemento de uma sequência seja trivial, ele fornece uma boa ilustração do conceito de um algoritmo. Há também muitos casos em que o maior número inteiro em uma sequência finita de inteiros é solicitado. Por exemplo, uma universidade pode precisar descobrir a maior nota em uma prova competitiva aplicada a milhares de estudantes. Ou uma organização esportiva pode querer identificar o membro com maior pontuação em um determinado mês.

Há muitas propriedades que os algoritmos normalmente compartilham. É útil lembrar-se delas quando os algoritmos são descritos. Essas propriedades são:

·         Entrada: um algoritmo tem um valor de entrada, ou inicial, de um determinado conjunto.

·         Saída: para cada conjunto de valores de entrada, um algoritmo produz valores de saída de um determinado conjunto. Os valores de saída, ou finais, são as soluções para o problema.

·         Certeza: os passos de um algoritmo devem ser definidos precisamente.

·         Exatidão: um algoritmo deverá produzir os valores finais corretos para cada conjunto de valores iniciais.

·         Finitude: um algoritmo deverá produzir o valor final desejado depois de um número de passos finitos (possivelmente grande) para as entradas em um conjunto.

·         Efetividade: deve ser possível realizar cada passo de um algoritmo de modo exato e em uma quantidade finita de tempo.

·         Generalidade: o procedimento deverá ter aplicabilidade para todos os problemas da forma desejada, não apenas para um determinado conjunto de valores iniciais.

ABU JÁ’FAR MOHAMMED IBN MUSA AL-KHOWARIZMI (780-850)

Al-Khowarizmi, astrônomo e matemático, era um membro da Casa da Sabedoria, uma academia de cientistas em Bagdá. O nome al-Khowarizmi significa “da cidade de Kowazizm”, que era então parte da Pérsia, mas agora é chamada de Khivae faz parte do território do Uzbequistão. Al-Khowarizmi escreveu livros sobre matemática, astronomia e geografia. Os europeus aprenderam álgebra pela primeira vez com seus trabalhos. A palavra álgebra vem de al-jabr, parte do título de seu livro Kitabal-jabw’almuquabala. Este livro foi traduzido para o latim e foi amplamente usado. Seu livro sobre o uso dos numerais hindus descreve procedimentos para operações aritméticas que usam esses numerais. Autores europeus usaram uma variante em latim de seu nome, o qual foi mais tarde transformado na palavra algoritmo, para descrever assuntos de aritmética com numerais hindus.