Projeto e Análise de Algoritmos

Professor: Saulo Henrique Cabral Silva

Instituto Federal de Minas Gerais Campus Ouro Branco

O que vamos abordar nesta disciplina

• Algoritmos;

• Funções assintóticas;

• Recorrências;

• Algoritmos de ordenação;

• Estruturas de dados;

• Programação Dinâmica;

• Algoritmos Gulosos;

• Algoritmo elementares de Grafos;

• Problemas NP-completos;

• Algoritmos de aproximação;

2

Introdução

• O que são os algoritmos?

• Qual foi a sua origem?

• Por que o estudo dos algoritmos vale a pena?

• Qual a função dos algoritmos em relação a outras tecnologias usadas em computadores?

3

Algoritmo

• Os algoritmos fazem parte do dia-a-dia

das pessoas. Exemplos: – instruções para o uso de medicamentos;

– indicações de como montar um aparelho;

– uma receita de culinária.

• Sequencia 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.

4

O papel dos algoritmos na 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 sequencia 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.

5

Algoritmo (Definição) • Dicionário Houaiss da Língua Portuguesa, 2014:

– [Informática] Conjunto de regras que fornecem uma sequência de operações capazes de resolver um problema específico.

• Dicionário Webster da Língua Inglesa: – An Algorithm is a procedure for solving a mathematical problem in a finite

number of steps that frequently involves a repetition of an operation .

• Introduction to Algorithms, ClRS, 2010: – Informally, an algorithm is any well-defined computational procedure that

takes some value, or set of values, as input and produces 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 problem

solving method suitable for implementation as a computer program 6

Algoritmo (Definição)

• Observações: – Regras são precisas

– Conjunto de regras é finito

– Tempo de execução é finito

– Regras executadas por um computador

7

Algoritmo (Consequências da Definição)

• Deve-se definir um repertório finito de regras – Linguagem de programação

• A maior parte dos algoritmos utiliza métodos de organização de dados envolvidos na computação – Estruturas de dados

• Tempo finito não é uma eternidade – A maior parte das pessoas não está interessada em algoritmos que levam

anos, décadas, séculos, milênios para executarem

• Existem diferentes “tipos de computadores” – Existem diferentes modelos computacionais

8

Algumas perguntas importantes Apresente as justificativas

• Um programa pode ser visto como um algoritmo codificado em uma linguagem de programação que pode ser executado por um computador. Qualquer computador pode executar qualquer programa?

• Todos os problemas ligados às ciências exatas possuem algoritmos?

• Todos os problemas computacionais têm a mesma dificuldade de resolução?

• Como algoritmos diferentes para um mesmo problema podem ser comparados/avaliados?

9

Algoritmo e Modelo Computacional

• Modelo: – Esquema que possibilita a representação de uma entidade

– Só se deve incluir o que for relevante para a modelagem do objeto em questão

• Um algoritmo não existe, ou seja, não é possível escrevê-lo, se antes não for definido o modelo associado ao mesmo.

• Questão: – Dado um problema qualquer, sempre existe um algoritmo que pode ser

projetado para um modelo computacional? • Não! Existem vários casos em que é possível mostrar que não existe um

algoritmo para resolver um determinado problema considerando um modelo computacional

10

Algoritmo e Modelo Computacional

• Quais modelos computacionais existem? – Dezenas

– Se não estiver satisfeito, invente o seu!

• O modelo computacional mais utilizado dentre os existentes: – RAM – Random Access Machine

– Modela o computador tradicional e outros elementos computacionais

• Elementos do modelo RAM – Único processador

– Memória para armazenamento

11

Algoritmo e Modelo Computacional

• Observações do modelo RAM – Pode-se ignorar os dispositivos de entrada e saída (teclado, monitor,

etc)

• Assumimos que os dados já estejam armazenados dentro da memória

– Em geral não é relevante para a modelagem do problema saber como o algoritmo e os dados foram armazenados na memória

• Característica da computação no modelo RAM – Processador busca instrução/dado da memória

– Uma única instrução é executada de cada vez.

– Cada instrução é executada sequencialmente.

12

Algoritmo e Modelo Computacional

• Cada operação executada pelo processador, incluindo cálculos aritméticos, lógicos e acesso a memória, implica num custo de tempo. – Função de complexidade de tempo.

• Número de vezes que determinada operação é executada

• Cada operação e dado armazenado na memória, implica num custo de espaço: – Função de complexidade de espaço.

• Quantidade de memória que é necessário para armazenar as estruturas de dados associados ao algoritmo.

13

Problema dos dois exércitos

• Na Grécia antiga, lugares maravilhosos podiam se transformar em cenários de guerra.

• É quando um filósofo propõe o “Problema dos dois exércitos”.

14

Problema dos dois exércitos • Exercito A está em maior número que o exercito B, mas está dividido entre

duas metades, cada uma numa lateral do vale.

• Cada metade do exército A está em menor número que o exército B.

• Objetivo do exército A: coordenar um ataque ao exército B para ganhar a guerra.

15

Problema dos dois exércitos • General do exercito A, do lado esquerdo do vale, chama o seu

melhor soldado para levar uma mensagem para o general do exército A do lado direito: – Vamos atacar juntos o exército B amanhã às 6:00?

– Única possibilidade de comunicação é através do mensageiro

– Os relógios são sincronizados pela posição do sol

16

Problema dos dois exércitos

• O soldado do exército A atravessa as linhas inimigas e leva a mensagem até o general do outro lado.

• O General do exército A do lado direito concorda em ataca o exército B no dia seguinte às 6:00

17

Problema dos dois exércitos

• O soldado do exército A atravessa novamente as linhas inimigas e confirma com o seu general o ataque para o dia seguinte.

18

Problema dos dois exércitos

• Vai haver ataque no dia seguinte???

19

Modelo computacional para sistemas distribuídos

• Mundo distribuído: – Normalmente os elementos computacionais seguem o modelo RAM

que são interconectados através de algum meio e só comunicam entre si através de troca de mensagens.

• Memória não compartilhada

• Elementos desse modelo – Nó computacional representado pelo modelo RAM.

– Canal normalmente representado pelo modelo FIFO.

20

Algoritmo - Problemas

• Informalmente podemos dizer que um algoritmo, é qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz um valor ou conjunto de valores como saída. – Ferramenta para resolver um problema computacional bem

especificado;

– O enunciado do problema especifica em termos gerais o relacionamento entre a entrada e a saída desejada.

• Exemplo: – <a1, a2, . . ., an>

– <a’1, a’2, . . .,a’n>

Tal que: a’1 < a’2 < . . . < a’n 21

Algoritmo - Problemas

• Dada uma sequencia de entrada como <31,41,59,26,41,58>, um algoritmo de ordenação retorna como saída a sequencia <26, 31, 41, 41, 58, 59>.

• Uma sequencia de entrada como essa é chamada uma instância do problema de ordenação. Em geral, uma instancia de um problema consiste na entrada.

• No caso da ordenação que é uma operação fundamental na computação, temos uma grande número de bons algoritmos de

ordenação que vem sendo desenvolvidos. – O melhor algoritmo para uma determinada aplicação

depende – entre outros fatores – do número de itens, da

extensão em que os itens já estejam ordenados, de

possíveis restrições sobre os valores de itens e ainda o

dispositivo utilizado (memória, disco, fita).

22

Exemplos de problemas

• Projeto Genoma Humano: Objetivo de identificar todos os 100000 genes do DNA humano, armazenar essas informações em bancos de dados e desenvolver ferramentas para análise de dados;

• Internet: Gerenciar grane volume de dados. Mecanismos de pesquisa para encontrar com rapidez páginas em que residem informações específicas;

• Comércio eletrônico: Troca de mercadorias e

serviços possam ser negociados e trocados

eletronicamente. A capacidade de manter

privativas informações como números de

cartão de crédito.

23

Exemplos de problemas

• Na indústria: alocação de recursos escassos de maneira mais benéfica. Uma empresa petrolífera talvez deseje saber onde localizar seus poços para tornar máximo o lucro esperado. – Provedor de internet que deseja definir onde instalar recursos

adicionais para servir de modo mais eficiente a seus clientes.

• Rotas: Como escolher qual a rota

mais curta? Qual a mais segura?

Qual possui o maior número de

espaços kids.

24

Problemas difíceis

• Trataremos em grande parte desta disciplina de algoritmos eficientes. – Eficiência velocidade (quanto tempo um algoritmo demora para

produzir o seu resultado).

• Existem problemas que não se conhece solução eficiente? – NP-completos;

– Embora não se tenha encontrado um algoritmo eficiente para esse fim. Ninguém provou ainda que não é possível existir um algoritmo.

– Se encontrar uma solução para um deles, automaticamente pode-se aplicar a solução para os demais.

– É importante conhece-los, pois se você em

algum momento se deparar com ele, não

perderá horas tentando a MELHOR solução.

25

Caixeiro Viajante

• Imagine uma empresa de transporte com um armazém central. A cada dia, ela carrega o caminhão no armazém e o envia a diversos locais para efetuar entregas. No final do dia, o caminhão tem de estar de volta ao armazém, a fim de ser preparado para receber a carga do dia seguinte.

• Para reduzir custos, a empresa deve selecionar uma ordem de paradas de entrega que represente a menor distância total a ser percorrida pelo caminhão.

• Este problema não possui algoritmo

eficiente conhecido. Em certas

hipóteses, há algoritmos eficientes

que fornecem uma distância total não

muito acima da menor possível.

26

Para refletir...

• Pense em um exemplo do mundo real no qual apareça o problema de ordenação.

• Além do tempo de execução, que outras medidas de eficiência poderiam ser usadas?

• Selecione uma estrutura de dados que você já tenha visto antes e discuta seus pontos fortes e suas limitações.

• Mostre um problema real no qual apenas a melhor

solução servirá. Em seguida, apresente um

problema em que baste uma solução

que seja “aproximadamente” a melhor.

27

Algoritmos como uma tecnologia

• Suponhamos que os computadores fossem infimamente rápidos e que a memória do computador fosse livre. – Utilizaríamos a forma mais simples de resolver ?

– Precisaríamos estudar para ter um algoritmo com uma boa prática de Engenharia de Software ?

• Computadores podem ser rápidos, mas não são infinitamente rápidos. – A memória pode ser de baixa custo, mas

não é gratuita.

– O tempo de computação é um recurso

limitado, bem como o espaço na

memória.

– Precisamos construir um algoritmo

eficiente em termos de tempo ou espaço. 28

Eficiência

• Os algoritmos podem diferir de forma drástica em sua eficiência. – Hardware;

– Software;

• Ex: – Ordenação por inserção: c1.n² (c1 não depende de n)

– Ordenação por intercalação: c2.n.lg(n)

• Veremos que os fatores constantes

podem ser muito menos significativos

do que o tamanho da entrada.

29

Análise de desempenho

• Geralmente para pequenas entradas

o algoritmo de ordenação por inserção é mais rápido do que o algoritmo por intercalação. – Quando o tamanho da entrada se torna grande o suficiente, a

vantagem de lg(n) contra n compensará com sobras.

– Independente do quanto c1 seja menor que c2;

• Vamos analisar o exemplo com dois computadores (A e B) – A (mais rápido 1 Bilhão de inst.) – executa ordenação por inserção

– B (lento – 10 Milhões de inst.) – executa ordenação por intercalação

– A – algoritmo otimizado por um prog. NINJA (código de máquina)

• Fator 2

– B – algoritmo prog. Médio (linguagem de alto nível)

• Fator 50 30

Análise de desempenho

• Vamos supor uma instância com um milhão de números:

• Calcule para 10 milhões (diferença bem mais pronunciada)

31

Tecnologias que podem influenciar

• O desempenho total do sistema depende da escolha de algoritmos eficientes tanto quanto da escolha de hardware rápido.

• Será que os algoritmos são verdadeiramente tão importantes quanto: – Hardware com altas taxas de clock, pipeline e arquiteturas superescalares;

– Sistemas O.O.

– Redes locais e Remotas.

• Com o aumento da capacidade dos computadores passamos a resolver problemas com instâncias cada vez maiores: – Big Data;

– Projetar componentes mais otimizados

– Traçar melhores rotas. Tudo isso depende de

algoritmos.

32

Exercícios

1. Forneça um exemplo de aplicação que exige conteúdo algorítmico no nível da aplicação e discuta a função do algoritmo envolvido.

2. Suponha que uma comparação entre ordenação por inserção e ordenação por intercalação na mesma máquina. Para entradas de tamanho n, a ordenação por inserção é executada em 8n² etapas, enquanto a ordenação por intercalação é executada em 64.n.lg(n) etapas. Para que valores de n a ordenação por inserção supera a ordenação por intercalação.

3. Qual é o menor valor de n tal que um algoritmo cujo tempo é 100.n² funciona mais rápido que um algoritmo cujo tempo de execução é na mesma máquina?

33

Exercícios

4. Para cada função f(n) e cada tamanho de entrada n, determine o tempo de execução para o algoritmo. Considere que o computador em questão executa 1000000 de instruções por segundo

34

10 20 30 40 50 60

log(n)

n

n.log(n)

n²

n³

n5

2n

3n

Dúvidas

36