Plano de Aula Teoria da Computação

PLANO DE ENSINO

Curso: CIÊNCIA DA COMPUTAÇÃO
Componente/Unidade Curricular: TEORIA DA COMPUTAÇÃO	Carga Horária: 80 horas
Modalidade:     Presencial ()                            Semipresencial (X)                                                 A distância ()
Período: 5°	Semestre Letivo: 2019.1
Professor (a): HILÁRIO TOMAZ ALVES DE OLIVEIRA

1. OBJETO DE ESTUDO - Ligação entre a ciência da computação e os modelos matemáticos e teóricos que permitem o desenvolvimento da computação moderna.

2. EMENTA - Conceitos preliminares (revisão): conjuntos, conjuntos finitos e infinitos, relações, funções; definição de procedimentos e algoritmos; introdução à computabilidade; programas e linguagens de programação; solubilidade; redutibilidade, decidibilidade e funções não computáveis; medidas de eficiência e introdução à Teoria da Complexidade de Algoritmos.

3. OBJETIVO(S)

3.1. Geral (is):  Introduzir os conceitos fundamentais sobre análise e projeto de algoritmos, análise de complexidade (Estudar os limites associados à computação de tarefas), técnicas para construção de algoritmos) e NP-Completude. Estudar a evolução dos modelos matemáticos aplicados à Teoria da Computação fornecendo embasamento teórico às diversas áreas da Ciência da Computação. Outros tópicos podem ser incluídos no programa para exemplificar a atividade de construção de algoritmos de acordo com o andamento do curso.

3.2.  Específico (s):  Compreender os conceitos associados ao processo de compilação e suas técnicas de construção, sendo capaz de aplicar tais abordagens no desenvolvimento de compiladores e em outros sistemas relacionados. Identificar todas as fases que compõem o processo de compilação das linguagens de programação. Especificar e desenvolver os módulos que compõem a etapa de Análise (Analisadores Léxicos, Sintáticos e Semânticos) do processo de compilação.

4. COMPETÊNCIAS

4.1. Conhecimentos(s): Competência 1 (C1) –Entender e analisar a essência da computação moderna. Competência 2 (C2) – Compreender o que é computação e função computável, função recursiva. Competência 3 (C3) – Formalizar a ideia de algoritmo computacional. Competência 4 (C4) – Analisar e decidir se um problema é computável ou não. Competência 5 (C5) - Entender os limites da computação e analisar a complexidade de algoritmos.

4.2.  Habilidade(s): Habilidade 1 (H1) – Conhecer os fundamentos teóricos da computação e das ciências e tecnologias relacionados à computação. Habilidade 2 (H2) – Especificar modelo computacionais usando a Máquina de Turing e suas derivações para resolução de problemas. Habilidade 3 (H3) - Comparar o desempenho dos algoritmos com base em sua Complexidade.

4.3 Atitude (s): Atitude 1 (A1) - Aplicar os conhecimentos sobre máquina, computação e função computada para desenvolver soluções algorítmicas mais eficientes. Atitude 2 (A2) – Adotar os conceitos de Máquinas Universais para compreender melhor o funcionamento de algoritmos complexos. Atitude 3 (A3) – Utilizar os conceitos de computabilidade, decidibilidade e complexidade para tomar decisões durante a resolução de um problema complexo. Atitude 4 (A4) -Ser proativo. Atitude 5 (A5) -Ser ético.

5. CONTEÚDO PROGRAMATICO:
Unid.	Conteúdos	Atividades	Conhecimentos	Habilidades	Atitudes	Nº Horas Aulas
I	Introdução a Teoria da computação O que é Teoria da Computação? Histórico. Conceitos e Propósitos Fundamentais da Teoria da Computação. Programas e funções computáveis. Programas, Máquinas, Computação e Funções computadas. Equivalência de Programas e Máquinas. Verificação de Equivalência Forte de Programas.	Exercícios de fixação. Resolução de exercícios em sala. Aplicação de questionários no ambiente virtual. Acompanhamento das atividades na sala de aula virtual. Criação de uma sala de aula virtual sobre o conteúdo do tópico 2.1. Criação de um fórum de discussão. Aplicação de lista de exercícios. Questionário de avaliação de aprendizagem.	Competência 1 (C1) –Entender e analisar a essência da computação moderna. Competência 2 (C2) – Compreender o que é computação e função computável, função recursiva;	Habilidade (H1) – Conhecer os fundamentos teóricos da computação e das ciências e tecnologias relacionados à computação.	Atitude 1 (A1) - Aplicar os conhecimentos sobre máquina, computação e função computada para desenvolver soluções algorítmicas mais eficientes. Atitude 4 (A4) -Ser proativo. Atitude 5 (A5) -Ser ético.	T 20	P	L	EAD 6
II	Máquinas Universais 3.1 Codificações de Conjuntos Estruturados 3.2 Máquina de Norma 3.3 Máquina de Turing 3.4 Variantes das Máquinas de Turing Hipótese de Church	Exercícios de fixação. Resolução de exercícios em sala. Aplicação de questionários no ambiente virtual. Adoção de simuladores online para melhor compreensão da execução das Maquinas Universais. 2.1 Simulador da Maquina de Turing e suas variantes. Acompanhamento das atividades na sala de aula virtual. Criação de uma sala de aula virtual sobre o conteúdo do tópico 3.4. Criação de um fórum de discussão. Aplicação de lista de exercícios. Questionário de avaliação de aprendizagem.	Competência 3 (C3) – Formalizar a ideia de algoritmo computacional;	Habilidade 2 (H2) – Especificar modelo computacionais usando a Máquina de Turing e suas derivações para resolução de problemas.	Atitude 2 (A2) – Adotar os conceitos de Máquinas Universais para compreender melhor o funcionamento de algoritmos complexos. Atitude 4 (A4) -Ser proativo. Atitude 5 (A5) -Ser ético.	20			7
III	Computabilidade, Decidibilidade Complexidade. Funções Recursivas Computabilidade parcial. Decidibilidade – Problemas de decisão. Tese de Church-Turing [O problema da parada]. Introdução a complexidade de problemas (P, NP e NPC)	Exercícios de fixação. Resolução de exercícios em sala. Aplicação de questionários no ambiente virtual. 2. Acompanhamento das atividades na sala de aula virtual. 2.1 Criação de uma sala de aula virtual sobre o conteúdo do tópico 4.5. 2.2 Criação de um fórum de discussão. 2.3 Aplicação de lista de exercícios. 2.4 Questionário de avaliação de aprendizagem.	Competência 4 (C4) – Analisar e decidir se um problema é computável ou não; Competência 5 (C5) - Entender os limites da computação e analisar a complexidade de algoritmos.	Habilidade 3 (H3) - Comparar o desempenho dos algoritmos com base em sua Complexidade.	Atitude 3 (A3) – Utilizar os conceitos de computabilidade, decidibilidade e complexidade para tomar decisões durante a resolução de um problema complexo. Atitude 4 (A4) -Ser proativo. Atitude 5 (A5) -Ser ético.	20			7
Subtotal da Carga Horária		60			20
	Total da Carga Horária                                                                                                               80

Legenda: T – Quantidade de aula(s) teórica(s) por unidade(s); P- quantidade de aula(s) práticas(s) por unidade(s); L - quantidade de aula(s) por unidade(s) de Prática Pedagógica (exclusivo para o Curso de Educação Física - Licenciatura); EAD - quantidade de aula(s) à distância.

...