Template MAPA Logica para computacao

Prévia do material em texto

��
�
Acadêmico: (Nome)	R.A.: (Registro Acadêmico)
Disciplina: Lógica para Computação
INSTRUÇÕES PARA REALIZAÇÃO DESTA ATIVIDADE
Todos os campos do cabeçalho (acima) deverão ser devidamente preenchidos;
O aluno deverá, obrigatoriamente, utilizar este formulário para realizar a atividade;
Esta é uma atividade INDIVIDUAL. Caso identificado plágio de colegas o trabalho de ambos será zerado.
Para realizar esta atividade acesse o ícone “Atividade de Estudos – MAPA”, siga as orientações e atente-se ao que está sendo solicitado. 
Utilizando este formulário, realize sua atividade, salve em seu computador e envie em forma de anexo;
Procure argumentar de forma clara e objetiva, de acordo com o conteúdo da disciplina. Ao utilizar quaisquer materiais de pesquisa referencie conforme as normas da ABNT e conforme exemplo citado no item REFERÊNCIAS;
Formatação exigida: documento Word, Fonte Arial ou Times New Roman tamanho 12, Espaçamento 1,5 entre linhas e texto com alinhamento justificado;
Critérios de avaliação: desenvolvimento, argumentação, conhecimento do tema, clareza e organização das ideias, linguagem adequada e correlação dos conteúdos estudados na disciplina. Normas de apresentação (ABNT - formatação exigida, ortografia, gramatical). Utilização do Modelo apresentado.
Em caso de solicitação do arquivo com o código fonte, deverá ser anexado junto com esse arquivo modelo (de forma compactada .zip).
VALOR DA ATIVIDADE: 1,0 PONTO
PRAZO PARA POSTAGEM: 25/07/17 a 22/08/17 (23h59 – horário de Brasília)
Em caso de dúvidas, entre em contato com seu Professor Mediador.
Bons estudos!!!�
Introdução:
Nesta etapa, o aluno irá descrever brevemente uma introdução sobre o trabalho a ser realizado no MAPA. Descrevendo brevemente o que foi solicitado e indicando os principais pontos a serem tratados no desenvolvimento.
O que deve ter em sua Introdução:
Descrever o assunto e um breve apanhado dos temas mencionados no trabalho;
Especificar quais os objetivos do trabalho;
Descrever como foi desenvolvido o trabalho;
Pode apagar o texto explicativo – substitua por sua introdução.�
Desenvolvimento:
Suponha que um caixeiro viajante tenha de visitar  cidades diferentes, iniciando e encerrando sua viagem na primeira cidade.
Suponha também que as cidades, aos pares, estão conectadas por rodovias; não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra.
O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.
O Problema do Caixeiro Viajante (PCV) é o nome que usualmente se dá a uma série de problemas reais importantes que podem ser modelados em termos de ciclos Hamiltonianos em grafos completos. O problema consiste em passar por todos os vértices de um grafo, não repetindo nenhum, a fim de encontrar um caminho ótimo.
Este problema pode ser modelado por um grafo G(V, E), sendo V o conjunto dos vértices e E o conjunto das arestas, onde:
 V = {c | c é uma cidade}
E = {( , ) | há uma estrada que conecta as cidades e , sendo que ela não passa por nenhuma outra cidade neste trajeto}.
Modelado desta forma, a solução deste problema passa por verificar se o grafo G é hamiltoniano.
PROBLEMA:
O Manoel é um caixeiro viajante que tem clientes instalados em seis cidades do Estado de São Paulo. Pretende-se determinar qual o percurso mais econômico tendo em atenção, exclusivamente, as distâncias em quilômetros entre as cidades. Ele deve iniciar e encerrar sua viagem na sua cidade de origem: São Paulo (capital).
Abaixo está representada a rede de cidades que o caixeiro deve visitar. 
Pesquise as distâncias (km) entre essas cidades e complete a tabela.
Em cada célula da tabela deve-se colocar as distâncias entre as cidades (Considere que as distâncias de ida e volta são iguais).
Exemplo: (linha 1coluna 2) = distância entre São Paulo e Taubaté.
	
	São Paulo
	Taubaté
	Assis
	Bauru
	Franca
	Campinas
	São Paulo
	---
	
	
	
	
	
	Taubaté
	
	---
	
	
	
	
	Assis
	
	
	---
	
	
	
	Bauru
	
	
	
	---
	
	
	Franca
	
	
	
	
	---
	
	Campinas
	
	
	
	
	
	---
Construir o grafo para representar as distâncias entre as cidades.
Quantos são os caminhos possíveis para fazer o percurso?
Aplique o Método do Vizinho Mais Próximo (ou método guloso, ou algoritmo dos mínimos sucessivos) para determinar um circuito possível para o Manoel:
Partindo da cidade de São Paulo, escolha a cidade mais próxima para iniciar o circuito.
A partir dessa cidade, visita-se a mais próxima e assim sucessivamente, até completar o circuito. 
Quando não for possível escolher a cidade mais próxima, quer por já ter sido visitada, quer por se fechar o circuito, então deve-se escolher a mais próxima ainda não visitada.
 Terminado o circuito somar os quilômetros percorridos.
Agora você deve resolver este problema novamente pelo Método do Vizinho Mais Próximo, mas escolhendo sempre uma primeira cidade a ser visitada quando sair de São Paulo:
Partindo da cidade de São Paulo, escolha uma das cidades para iniciar o circuito (o que já está feito nos quadros abaixo).
A partir dessa cidade, visita-se a mais próxima e assim sucessivamente, até completar o circuito, como feito no item anterior. 
Terminado o circuito somar os quilômetros percorridos.
Repetir esse procedimento de forma a obter todos os caminhos possíveis, cada um dos quais com início numa das cidades.
Para isso, preencha os quadros indicando os ciclos pelo Método Guloso, iniciando pela cidade indicada. Utilize as distâncias entre as cidades determinadas no item (a).
(Por exemplo, no primeiro quadro, na frente de Assis deverão colocar a distância entre São Paulo (cidade anterior) e Assis).
	São Paulo
	Dist.
	Assis
	
	
	
	
	
	
	
	
	
	São Paulo
	
	Total
	
	São Paulo
	Dist. 
	Taubaté
	
	
	
	
	
	
	
	
	
	São Paulo
	
	Total
	
	São Paulo
	Dist.
	Bauru
	
	
	
	
	
	
	
	
	
	São Paulo
	
	Total
	
	São Paulo
	Dist.
	Franca
	
	
	
	
	
	
	
	
	
	São Paulo
	
	Total
	
	São Paulo
	Dist.
	Campinas
	
	
	
	
	
	
	
	
	
	São Paulo
	
	Total
	
Indicar o caminho a ser percorrido pelo Manoel, segundo esse método, informando a distância para esse percurso.
Comparando com o caminho obtido em (d), qual é o melhor?
Para realizar a atividade Mapa, é importante que você assista ao Estudo de Caso “Grafos e o Problema do Caixeiro Viajante”. O vídeo traz orientações e exemplos que poderão ajudar nesta atividade.
Atenção:
Para este MAPA você deve utilizar este TEMPLATE, no qual fará o desenvolvimento do seu trabalho. Este arquivo deverá ser anexado no momento do envio. Muita atenção para enviar o arquivo correto, visto que o envio pode ser feito uma única vez!
NÃO APAGUE O ENUNCIADO! – COLOQUE AQUI SUA RESPOSTA!!!
�
Conclusão:
Nesta etapa, o aluno irá realizar um breve comentário sobre o trabalho, dizendo as possíveis dificuldades na realização, se os objetivos foram alcançados, a importância que este trabalho teve para o seu conhecimento e indicando ao final um exemplo prático sobre o tema proposto do MAPA.
A sua Conclusão:
Fazer um breve resumo do trabalho;
Descrever qual foi a importância do trabalho para o seu aprendizado;
Indicar se os objetivos foram alcançados e mencionar possíveis dificuldades na execução do trabalho;
Pode apagar o texto explicativo! – substitua por sua conclusão.�
Referências:
Nesta etapa o aluno deverá colocar/mencionar TODAS as fontes/referências utilizadas na realização do trabalho. Lembrando que, caso for verificado cópias de textos (parciais ou totais) sejam de livros ou da internet sem suas respectivas fontes/referências será considerado plágio e passivel deaplicação de nota ZERO, ou nota parcial conforme descontos aplicados.
Exemplo de Referência:
LIVROS 
SOBRENOME, Nome . Título do livro: subtítulo. Local : Editora, ano 
Exemplo:
MAGNOLI, Demétrio. União Européia: História e Geopolítica. 5.ed. São Paulo: 1999
INTERNET
AUTOR/EDITOR. Titulo da obra. Disponível em: www.url.com.br/xxx. Acessado em dia, mês ano.
Exemplo:
MORAN, José Manuel. Guia do Saber. Disponível em: http://br.news.yahoo.com/020523/16/67pv.html. Acessado em 19 de jun. 2002
Pode apagar o texto explicativo! – substitua pelas referências utilizadas.
�
	CRITÉRIOS DE AVALIAÇÃO PARA A CORREÇÃO DA ATIVIDADE M.A.P.A. (Material de Avaliação Prática de Aprendizagem) (De uso dos Professores Mediadores)
	Itens
	Valor Máximo
	1. Conteúdo / Teoria / Prática
	0,6
	2. Correção gramatical e ortográfica
	0,1
	3. Normas (referência, formatação, utilização do MODELO, introdução, conclusão).
	0,3
	4. Plágio (o texto será zerado)
	0,0
	Total
	1,0
Disponível em: � HYPERLINK "http://goo.gl/Tq6HpH" �http://goo.gl/Tq6HpH�