Algoritmos De Banco De Dados

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 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,