Estruturas de controle: Iteração. Estruturas de dados compostas: vetores. Estruturas de dados compostas

Estruturas de controle: Iteração. Estruturas de dados compostas:

vetores. Estruturas de dados compostas:

ATIVIDADES PRÁTICAS

SUPERVISIONADAS

CST em Gestão da Tecnologia da Informação

2ª. Série

Algoritmos e Estrutura de Dados

A Atividade Prática Supervisionada (ATPS) é um procedimento metodológico

de ensino-aprendizagem desenvolvido por meio de etapas acompanhadas pelo

professor, e que tem por objetivos:

 Favorecer a autoaprendizagem do aluno.

 Estimular a corresponsabilidade do aluno pelo seu aprendizado.

 Promover o estudo, a convivência e o trabalho em grupo.

 Auxiliar no desenvolvimento das competências requeridas para o

exercício profissional.

 Promover a aplicação da teoria na solução de situações que simulam a

realidade.

 Oferecer diferenciados ambientes de aprendizagem

Para atingir estes objetivos, a ATPS propõe um desafio e indica os passos a

serem percorridos ao longo do semestre para a sua solução.

Aproveite esta oportunidade de estudar e aprender com desafios da vida

profissional.

AUTORIA:

Jeanne Dobgenski

Anhanguera Educacional

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

Jeanne Dobgenski

Pág. 2 de 10

.

COMPETÊNCIAS E HABILIDADES

Ao concluir as etapas propostas neste desafio, você terá desenvolvido as competências e

habilidades que constam, nas Diretrizes Curriculares Nacionais, descritas a seguir.

 Compreender tecnologias relacionadas à comunicação e processamento de dados e

informações.

 Desenvolver sistemas informatizados desde a especificação de requisitos até os

testes de implantação, bem como as tecnologias de comutação, transmissão,

recepção de dados podem constituir-se em especificidades desse eixo.

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