Atps Algoritmp

DESAFIO

Existem diversos problemas que são considerados clássicos em computação. Um deles é o problema do menor caminho e que consiste em encontrar um percurso de menor custo entre dois pontos dentro de um cenário especificado. Esse problema tem diversas aplicações práticas e muitos algoritmos que retornam a melhor solução para o problema.

Nesse desafio, propõe-se que esse problema seja estudado para uma aplicação prática e que seja elaborada pela equipe uma forma de solução que deverá ser apresentada num algoritmo.

Considerações importantes:

 cada ponto é chamado de nó e cada conexão entre os pontos (nós) é chamado de aresta;

 o valor associado ao nó é chamado de peso;

 graficamente um nó é representado por um círculo com sua identificação e uma aresta é uma linha que liga um nó ao outro, indicando que há uma conexão entre aqueles nós;

 a forma de solução apresentada pela equipe não precisa encontrar a melhor solução para o problema, apenas uma solução válida;

 a equipe poderá pesquisar algoritmos para a resolução do problema, mas deverá propor uma solução própria;

 a solução deverá ser apresentada em pseudo-linguagem, seguindo as especificações das etapas do desafio.

Problema Prático

A Figura 1 mostra as conexões de uma rede de computadores que está sendo proposta a uma Universidade. Cada nó é um computador e cada ligação é um cabo de fibra ótica. Os projetistas devem, agora, decidir como os e-mails serão roteados a partir do gateway da internet, que é o nó A, para/ou a partir de todos os outros nós.

Os números sobre os nós, indicados na figura, representam o tempo mínimo necessário para o computador correspondente transmitir ou receber um pacote de mensagem em centésimos de segundo.

O tempo pra enviar um pacote por meio de qualquer conexão da rede é o máximo dos tempos de recebimento e envio para o computador associado.

CST em Gestão da Tecnologia da Informação - 2ª. Série - Algoritmos e Estrutura de Dados

Jeanne Dobgenski

Pág. 3 de 10

Por exemplo, um e-mail para o nó H pode ser transmitido por meio do nó A para o nó B, então, repetido por meio do nó B para o nó E e, finalmente, repetido por meio do nó E para o nó H. O tempo total gasto nessa transmissão é 27 milissegundos = 6 (nó A transmite para nó B) + 4 (recebimento pelo nó B) + 4 (transmissão nó B para nó E) + 5 (recebimento pelo nó E) + 5 (transmissão de E para H) + 3 (recebimento por H).

Figura 1 – Grafo que representa a conexão entre computadores.

Fonte: desenvolvido pela autora.

O desafio proposto implica em estudar e propor uma solução para o problema, seguindo as especificações que são apresentadas nas etapas a seguir.

Objetivo do Desafio

Analisar e resolver uma aplicação prática do problema do menor caminho, apresentando um conjunto de relatórios sobre o estudo efetuado, com o propósito de compreender como desenvolver algoritmos e utilizar estruturas de dados.

Livro Texto da Disciplina

A produção desta ATPS é fundamentada no livro-texto da disciplina, que deverá ser utilizado para solução do desafio.

FORBELLONE, A. L. Lógica de Programação. 1ª ed. São Paulo: Pearson, 2008.

Participação

Esta atividade será, em parte, desenvolvida individualmente pelo aluno e, em parte, pelo grupo. Para tanto, os alunos deverão:

 organizar-se, previamente, em equipes cuja quantidade de participantes será definida pelo professor da disciplina;

 entregar seus nomes, RAs e e-mails ao professor da disciplina e

 observar, no decorrer das etapas, as indicações: Individual e Equipe.

A

C

B

E

D

F

G

6

5

4

5

4

4

6

I

H

J

4

2

3

CST em Gestão da Tecnologia da Informação - 2ª. Série - Algoritmos e Estrutura de Dados

Jeanne Dobgenski

Pág. 4 de 10

ETAPA 1 (tempo para realização: 10 horas)

 Aula-tema: Instruções e programas: pseudo-linguagem. Algoritmos. Dados e variáveis. Construções básicas: atribuição, leitura e escrita. Desenvolvimento de algoritmos: análise e resolução de problemas, técnicas top-down. Desenvolvimento de algoritmos: análise e resolução de problemas, técnicas top-down.

Esta atividade é importante para que você desenvolva a capacidade de compreender e solucionar problemas por meio do emprego de conceitos, técnicas e recursos computacionais, construindo algoritmos corretamente.

Para realizá-la, devem ser seguidos os passos descritos.

PASSOS

Passo 1 (Individual)

Fazer as atividades apresentadas a seguir.

1. Estudar na bibliografia recomendada ao final desse passo os capítulos que se referem aos conteúdos de Desenvolvimento de Algoritmos – técnica Top-Down, Lógica de Programação, Tópicos Preliminares e Estruturas de Controle.

2. Assistir ao vídeo: VisuALG - Aula 01 (Princípios Básicos). Disponível em: <http://www.youtube.com/watch?v=dZq7l9Oj-_c&list=PLE88CDBBDB041CC82&index=1>. Disponível também em: <https://drive.google.com/file/d/0ByrqRhRetWzENHA1enp2NlZKb00/edit?usp=sharing>.