Linguagens Formais E Autômatos

ATIVIDADES PRÁTICAS SUPERVISIONADAS

Ciência da Computação

7ª Série

Linguagens Formais e Autômatos

A atividade prática supervisionada (ATPS) é um procedimento metodológico de ensino-aprendizagem desenvolvido por meio de um conjunto de etapas programadas e supervisionadas e que tem por objetivos:

 Favorecer a aprendizagem.

 Estimular a corresponsabilidade do aluno pelo aprendizado eficiente e eficaz.

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

 Desenvolver os estudos independentes, sistemáticos e o autoaprendizado.

 Oferecer diferentes ambientes de aprendizagem.

 Auxiliar no desenvolvimento das competências requeridas pelas Diretrizes Curriculares Nacionais dos Cursos de Graduação.

 Promover a aplicação da teoria e conceitos para a solução de problemas práticos relativos à profissão.

 Direcionar o estudante para a busca do raciocínio crítico e a emancipação intelectual.

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.

A sua participação nesta proposta é essencial para que adquira as competências e habilidades requeridas na sua atuação profissional.

Aproveite esta oportunidade de estudar e aprender com desafios da vida profissional.

AUTORIA:

Diego Daniel Duarte

Faculdade Anhanguera de Limeira

Ciência da Computação - 7ª Série - Linguagens Formais e Autômatos

Diego Daniel Duarte

Pág. 2 de 6

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.

 Capacidade para desenvolvimento de pesquisa científica e tecnológica.

 Profundo conhecimento dos aspectos teóricos, científicos e tecnológicos relacionados à computação.

 Competência para identificar, analisar, documentar e solucionar problemas e necessidades passíveis de solução via computação.

 Saber conciliar teoria e prática.

Produção Acadêmica

 Relatório contendo a apresentação e solução para validação do problema do Passeio do Cavalo.

Participação

Para a elaboração desta atividade, os alunos deverão previamente organizar-se em equipes de 3 a 4 participantes e entregar seus nomes, RAs e e-mails ao professor(a) da disciplina. Essas equipes serão mantidas durante todas as etapas.

Padronização

O material escrito solicitado nesta atividade deve ser produzido de acordo com as normas da ABNT1, com o seguinte padrão:

 em papel branco, formato A4;

 com margens esquerda e superior de 3cm, direita e inferior de 2cm;

 fonte Times New Roman tamanho 12, cor preta;

 espaçamento duplo entre linhas;

 se houver citações com mais de três linhas, devem ser em fonte tamanho 10, com um recuo de 4cm da margem esquerda e espaçamento simples entre linhas;

 com capa, contendo:

 nome de sua Unidade de Ensino, Curso e Disciplina;

 nome e RA de cada participante;

 título da atividade;

 nome do professor(a) da disciplina;

 cidade e data da entrega, apresentação ou publicação.

1 Consulte o Manual para Elaboração de Trabalhos Acadêmicos. Unianhanguera. Disponível em: <http://www.unianhanguera.edu.br/anhanguera/bibliotecas/normas_bibliograficas/index.html>.

Ciência da Computação - 7ª Série - Linguagens Formais e Autômatos

Diego Daniel Duarte

Pág. 3 de 6

DESAFIO

O Xadrez é um jogo estratégico de tabuleiro para dois jogadores. O jogo é disputado em um tabuleiro de 64 casas (8x8) alternadas entre claras e escuras. Cada jogador inicia a partida com 16 peças, sendo: 1 rei, 1 rainha, 2 bispos, 2 cavalos, 2 torres e 8 peões. O objetivo da partida é capturar o rei inimigo. Para isso, um dos jogadores deve posicionar suas peças no tabuleiro de forma que, na próxima jogada, ele consiga mover uma das peças para a casa ocupada pelo rei inimigo, considerando o movimento particular de cada peça.

Além do seu valor estratégico e lúdico, o xadrez também se mostra muito importante no ponto de vista matemático e computacional. Diversos problemas de natureza combinatória e topológica ligado ao xadrez são conhecidos, foram estudados nas últimas centenas de anos e, mais recentemente, suas soluções foram aplicadas para resolução de vários problemas computacionais. Esses problemas são chamados de composições.

Em uma composição o problema é apresentado por meio da definição de uma distribuição de peças no tabuleiro e a solução consiste em realizar uma ação determinada. É comum que a ação a ser realizada venha acompanhada de uma ou mais restrições.

Existem diversas composições clássicas no xadrez. Uma delas é conhecida como o passeio do cavalo. Nessa composição o desafio é fazer com que o cavalo passe por todas as casas do tabuleiro. Inicialmente o cavalo está em uma casa qualquer e ele deve ser movimentado obedecendo às regras de movimentação para essa peça.

Este desafio consiste em elaborar uma solução computacional, utilizando os conceitos de Linguagens Formais e Autômatos, para verificar se uma sequência de movimentações é uma solução para a composição do passeio do cavalo. Para tanto o aluno é