Ciencia_da_Computacao_Teoria_da_Computacao

ATIVIDADES PRTICAS

SUPERVISIONADAS

Cincia da Computao

6 Srie Teoria da Computao

A Atividade Prtica Supervisionada (ATPS) um procedimento metodolgico 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 convivncia e o trabalho em grupo.

Auxiliar no desenvolvimento das competncias requeridas para o

exerccio profissional.

Promover a aplicao da teoria na soluo de situaes que simulam a

realidade.

Oferecer diferenciados ambientes de aprendizagem.

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

serem percorridos ao longo do semestre para a sua soluo.

Aproveite esta oportunidade de estudar e aprender com desafios da vida

profissional.

AUTORIA:

Andr Ricardo Jovetta

Faculdade Anhanguera de Limeira

Walter Gima

Faculdade Anhanguera de Limeira .

Cincia da Computao - 6 Srie - Teoria da Computao

Andr Ricardo Jovetta, Walter Gima

Pg. 2 de 8

COMPETNCIAS E HABILIDADES

Ao concluir as etapas propostas neste desafio, voc ter desenvolvido as competncias e habilidades que constam, nas Diretrizes Curriculares Nacionais, descritas a seguir.

Compreender tecnologias relacionadas comunicao e processamento de dados e informaes.

Desenvolver sistemas informatizados desde a especificao de requisitos at os testes de implantao, bem como as tecnologias de comutao, transmisso, recepo de dados, podem constituir-se em especificidades desse eixo.

Abranger aes de concepo, desenvolvimento, implantao, operao, avaliao e manuteno de sistemas e tecnologias relacionadas informtica e telecomunicaes

Compreender o desenvolvimento de sistemas informatizados desde a especificao de requisitos at os testes de implantao, bem como as tecnologias de comutao, transmisso, recepo de dados, podem constituir-se em especificidades desse eixo.

DESAFIO

A administrao do sistema penitencirio brasileiro vem representando um dos maiores desafios para o Governo Federal, pois nos ltimos anos a populao carcerria vem crescendo de forma expressiva tornando a realizao de atividades cotidianas mais difceis. Como uma das medidas para melhorar a segurana, o Governo Federal pretende criar um modelo de segurana padro a ser implantado nos presdios. Esse modelo baseado em estudos lgicos e computacionais para desenvolver melhorias em diversos setores e procedimento de segurana dos presdios. Por meio de modelos lgicos computacionais o projeto visa mapear aes, traar um modelo de execuo e gerar diagramas para ilustrar e validar estes procedimentos. A empresa em que sua equipe trabalha foi selecionada por meio de licitao do Governo Federal para desenvolver o projeto de melhorias para os presdios. Sua equipe conta com seu professor para orientao no desenvolvimento projeto e aprovao do contedo produzido pela equipe de desenvolvimento.

Objetivo do Desafio

O objetivo deste desafio consiste na elaborao de relatrios com diversos modelos lgicos computacionais ilustrando solues de processos realizados nas unidades prisionais.

Livro Texto da Disciplina

A produo desta ATPS fundamentada no livro-texto da disciplina, que dever ser utilizado para soluo do desafio: LEWIS, Harry R; PAPADIMITRIOU, Christos H. Elementos de Teoria da Computao. 2 ed. Porto Alegre: Bookman, 2000.



Pg. 3 de 8

Participao

Esta atividade ser, em parte, desenvolvida individualmente pelo aluno e, em parte, pelo grupo. Para tanto, os alunos devero:

organizar-se, previamente, em equipes de 3 a 5 participantes; entregar seus nomes, RAs e e-mails ao professor da disciplina e observar, no decorrer das etapas, as indicaes: Individual e Equipe.

ETAPA 1 (tempo para realizao: 05 horas)

Aula-tema: Conceitos bsicos da teoria da computao. Programas, mquinas, computaes. Modelos computacionais e mquinas universais.

Esta atividade importante para que voc compreenda os conceitos bsicos da teoria da computao e juntamente aos alfabetos, palavras e autmato finito determinstico.

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

PASSOS

Passo 1 (Individual)

Realizar as atividades apresentadas a seguir: 1. Fazer a leitura individual do livro texto que retrata: Conjuntos, Relaes, Linguagens e

Autmatos Finitos. 2. Fazer a leitura individual do Material: e-book: Linguagens Formais e Autmatos.

Disponvel em: . Acesso em: 01 maio 2014.

Passo 2 (Equipe)

Analisar conceitos de autmato finito determinstico para atender ao seguinte contexto: 1. No presdio no ser permitido entrada do visitante com qualquer tipo de dispositivo

de comunicao, armas de fogo, materiais cortantes ou matrias de metais no geral. 2. O presdio ter um detector de metais juntamente a uma porta eletrnica para permitir

ou proibir a entrada dos visitantes. 3. Caso o visitante possui algum material de metal escondido ao passar pelo detector a

porta no abrir, mas se ele no possuir nenhum material de metal ao passar pelo detector a porta abrir permitindo a sua passagem para dentro do presdio.

4. Ao passar pela porta de entrada do presdio o visitante pra em uma sala onde possui um leitor de carto magntico.

5. O visitante dever passar o seu carto magntico que recebeu do policial recepcionista no leitor magntico para poder abrir uma das portas que d acesso a um dos setores onde possui uma sala de visitas que os presidirios daquele setor estaro para receber a visita juntamente aos policiais responsveis.

6. Os presdios tero no mnimo cinco setores. 7. Cada carto magntico possui a gravao da permisso de qual porta abrir.



Pg. 4 de 8

Passo 3 (Equipe)

Realizar as atividades apresentadas a seguir: 1. Fazer um diagrama do autmato finito determinstico que represente o sistema de

autorizao ou proibio da entrada de um visitante no presdio. 2. Adicionar no diagrama do autmato finito determinstico que representa o sistema de

autorizao ou proibio da entrada de um visitante no presdio, a representao do mecanismo do reconhecimento da leitura do carto magntico de qual porta dever abrir quando o visitante passar o carto magntico.

Passo 4 (Equipe)

Elaborar e entregar ao professor da disciplina: um relatrio com o nome Relatrio 1: Diagrama do autmato finito determinstico do mecanismo de segurana da porta de entrada e das portas de acesso aos setores. Entregar o projeto criado nos Passos 2 e 3 desta etapa da seguinte forma:

Documento de texto contendo os registros de execuo das mquinas. Os resultados da execuo das mquinas e devem conter comentrios e a concluso da equipe.

Consultar o professor sobre o tipo de mdia (CD, e-mail etc.) para a entrega do relatrio.


Aula-tema: Mquinas universais.

Esta atividade importante para que voc aprenda os conceitos e desenvolver os diagramas do autmato finito no determinstico e o autmato finito no determinstico com pilha.


PASSOS


Realizar as atividades apresentadas a seguir: 1. Fazer a leitura individual do Captulo do livro texto que retrata: Linguagens Livres

De Contexto. 2. Fazer a leitura individual do Material: Coutinho, S.C. Autmatos e Linguagens

Formais. Disponvel em: . Acesso em: 01 maio 2014. Focar a leitura no captulo 12: Autmatos de Pilha.

Passo 2 (Equipe)

Analisar conceitos de autmato finito no determinstico e autmato finito no determinstico com pilha para atender ao seguinte contexto:



Pg. 5 de 8

1. As portas que do acesso aos setores para as salas de visitas, tambm, so as portas de sadas dos setores.

2. Cada porta possui um controle para permitir sada dos visitantes mesma quantidade de vezes que entrou.

Passo 3 (Equipe)

Realizar as atividades apresentadas a seguir: 1. Elaborar um diagrama de um autmato finito no determinstico dos conceitos obtidos

do passo 2 dessa etapa. 2. Elaborar um autmato no determinstico com pilha dos conceitos obtidos do passo 2

dessa etapa.

Passo 4 (Equipe)

Elaborar e entregar ao professor da disciplina: um relatrio com o nome Relatrio 2: Diagrama do autmato finito no determinstico e autmato finito no determinstico com Pilha do controle de abrir e fechar as portas de acesso aos setores. Entregar o projeto criado nos Passos 2 e 3 desta etapa da seguinte forma:

Documento de texto contendo os registros de execuo das mquinas. Os resultados da execuo das mquinas e devem conter comentrios e a concluso da equipe.



Aula-tema: Funes Recursivas, Computabilidade.

Esta atividade importante para que voc criar um modelo para verificar os cdigos de segurana dos cartes dos agentes de segurana utilizando conceitos de mquina de Turing.


PASSOS


Realizar as atividades apresentadas a seguir: 1. Fazer a leitura individual do Captulo do livro texto que retrata: Mquinas De Turing. 2. Fazer a leitura individual do Material: Coutinho, S.C. Autmatos e Linguagens

Formais. Disponvel em: . Acesso em: 01 maio 2014. Focar a leitura no captulo 15: Mquinas de Turing e Linguagens.

Passo 2 (Equipe) Analisar conceitos de Mquinas de Turing para atender ao seguinte contexto:

Os agentes de segurana iro receber diariamente cartes com uma sequncia de caracteres que sero lidos por dispositivos instalados na entrada de locais restritos dentro das prises. Esses caracteres so cdigos que sero analisados e caso



Pg. 6 de 8

reconhecidos vo liberar acesso a blocos e locais dos presdios, conforme nvel de acesso.

Para os agentes prisionais h dois nveis de acesso. Os cartes recebem ento, dois tipos de cdigos, conforme seu nvel.

Criar uma Linguagem para o nvel 1 de acesso que contenha pelo menos dois elementos diferentes (exemplo: a e b). Por meio desta linguagem, criar cinco entradas vlidas e duas invlidas para serem analisadas por uma mquina de Turing (a anlise ser realizada no prximo passo).

Criar uma Linguagem para o nvel 2 de acesso que contenha pelo menos trs elementos diferentes (exemplo: a e b e c). Por meio desta linguagem, criar cinco entradas vlidas e duas invlidas para serem analisadas por uma mquina de Turing (a anlise ser realizada no prximo passo).

Passo 3 (Equipe) Realizar as atividades apresentadas a seguir: 1. Criar uma mquina de Turing que ir verificar se os cdigos dos cartes dos agentes

penitencirios so vlidos para o nvel 1. Caso a codificao do carto seja vlida o agente ter acesso a locais restritos liberados para o nvel 1.

2. Criar uma mquina de Turing que ir verificar se os cdigos dos cartes dos agentes penitencirios so vlidos para o nvel 1 e 2. Caso a codificao do carto seja vlida o agente ter acesso a locais restritos liberados para o nvel 2.

Passo 4 (Equipe)

Elaborar e entregar ao professor da disciplina um relatrio com o nome Relatrio 03 Verificao de acesso dos agentes Prisionais. Entregar o projeto criado nos Passos 2 e 3 desta etapa da seguinte forma: Documentar os textos contendo as linguagens, as entradas, as mquinas e a execuo da mquina de Turing para cada entrada. Os resultados da execuo do sistema devem conter comentrios e a concluso da equipe.


Aula-tema: Android: Computabilidade, Computabilidade.

Esta atividade importante para que voc criar modelos para verificao de tornozeleiras dos prisioneiros utilizando os recursos das mquinas de Moore e Mealey. Para realiz-la, devem ser seguidos os passos descritos.

PASSOS


Realizar as atividades apresentadas a seguir: 1. Fazer a leitura individual do Material: Menezes, P. Autmato Finito com Sada.

Disponvel em: . Acesso em: 01 maio 2014.



Pg. 7 de 8

2. Fazer a leitura individual do Material: Autmatos Finitos. Disponvel em: . Acesso em: 01 maio 2014. Focando a leitura no Captulo 2.9: Mquinas Transdutoras.

Passo 2 (Equipe)

Analisar conceitos de mquina de Mealey e Moore para atender ao seguinte contexto:

1. Os presos das unidades prisionais vo receber tornozeleiras que emitem sinais de sua localizao, esses sinais enviam o cdigo dos blocos e reas internas dos presdios. Em caso de fugas as tornozeleiras enviam o cdigo das reas externas da priso. H uma central de controle que ir receber esses sinais.

Figura Exemplo de uma planta da unidade prisional com seus blocos e reas internas e externas.

2. Criar uma Linguagem para representar o percurso dos prisioneiros mudando de blocos,

de reas internas e reas externas. Por meio desta linguagem, criar cinco percursos dos presos entre os blocos e reas internas e dois percursos entre blocos reas internas e externas (rea externa caracteriza fuga do prisioneiro).

Passo 3 (Equipe)

Realizar as atividades apresentadas a seguir: 1. Criar uma mquina de Mealey que ir verificar os percursos dos prisioneiros criados no

Passo Anterior. As reas da priso sero as sadas da mquina de Mealy, caso a mquina retornar uma rea externa a central ir soar os alarmes caracterizando assim uma fuga.

2. Criar uma mquina de Moore que ir verificar os percursos dos prisioneiros criados no Passo Anterior. As reas da priso sero as sadas da maquina de Moore, caso a mquina retornar uma rea externa a central ir soar os alarmes caracterizando assim uma fuga.



Pg. 8 de 8

Passo 4 (Equipe)

Elaborar e entregar ao professor da disciplina um relatrio com o nome Relatrio 04 Registro de atividades dos prisioneiros e Alarme para Fugas. Entregar o projeto criado nos Passos 2 e 3 desta etapa da seguinte forma:

Documentar o texto contendo os registros de execuo das mquinas. Os resultados da execuo das mquinas e devem conter comentrios e a concluso da equipe.


Padronizao O material escrito solicitado nesta atividade deve ser produzido de acordo com as normas da ABNT, com o seguinte padro (exceto para produes finais no textuais):

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; espaamento de 1,5 entre linhas; se houver citaes com mais de trs linhas, devem ser em fonte tamanho

10, com um recuo de 4cm da margem esquerda e espaamento simples entre linhas;

com capa, contendo: nome de sua Unidade de Ensino, Curso e Disciplina; nome e RA de cada participante; ttulo da atividade; nome do professor da disciplina; cidade e data da entrega, apresentao ou publicao.

Para consulta completa das normas ABNT, acesse a Normalizao de Trabalhos Acadmicos Anhanguera. Disponvel em: . Acesso em: 13 maio 2014.

Documents

Ciencia_da_Computacao_Teoria_da_Computacao