Teoria da Computação - Aula 1: Apresentação da Disciplina

Teoria da Computação Aula 1 Apresentação da disciplina Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Apresentação da disciplina Objetivos Avaliações Bibliografia Introdução à Teoria da Computação Histórico Conceitos Iniciais Apresentação da disciplina Teoria da Computação Autômatos e linguagens Teoria da computabilidade Teoria da complexidade Objetivos Conhecer os principais conceitos que compõem a ciência da computação Conhecer os limites da computação e do desenvolvimento de soluções computacionais Desenvolver habilidades de análise de soluções computacionais Avaliações 5 ACs Avaliação oficial Avaliação substitutiva Bibliografia HOPCROFT JE MOTWANI R ULLMAN JD Introdução a Teoria de Autômatos Linguagens e Computação Rio de Janeiro Campus 2002 SIPSER M Introduction to the Theory of Computation 3rd Ed Boston Cengage 2013 GERSTING J L Fundamentos Matemáticos para a Ciência da Computação 7ed Rio de Janeiro LTC Livros Técnicos e Científicos 2016 Introdução à Teoria da Computação Quais problemas podem ser resolvidos por um computador Quais não podem Introdução à Teoria da Computação Quais problemas podem ser resolvidos por um computador Quais não podem Como comparar soluções computacionais diferentes para um mesmo problema Como saber se um problema é resolvível Introdução à Teoria da Computação Definir os limites da computação e dos computadores é uma questão abordada desde os anos 30 Definir os limites da computação e dos computadores é uma questão abordada desde os anos 30 Responder esta questão não é simples porém é necessário para a evolução da tecnologia Definir os limites da computação e dos computadores é uma questão abordada desde os anos 30 Responder esta questão não é simples porém é necessário para a evolução da tecnologia A resposta deve ser dada na dimensão conceitual os recursos para o desenvolvimento de uma solução podem surgir sem a necessidade de mudança de paradigma Exemplo Deep Learning teoria desenvolvida no final da década de 50 Exemplo Deep Learning teoria desenvolvida no final da década de 50 as aplicações tornaramse viáveis nos últimos anos com a implementação dos conceitos já existentes em GPUs Graphics Processing Units As sub áreas da Teoria da Computação Autônomos e linguagens Quais os fundamentos para a teoria da computação As sub áreas da Teoria da Computação Autônomos e linguagens Quais os fundamentos para a teoria da computação Teoria da computabilidade Para quais problemas é possível desenvolver um algoritmo capaz de solucionálos As sub áreas da Teoria da Computação A base da Teoria da Computação é a matemática em especial A base da Teoria da Computação é a matemática em especial Conjuntos Sequências Funções Conceitos Iniciais A base da Teoria da Computação é a matemática em especial Conjuntos Sequências Funções Grafos Strings Lógica Conceitos Iniciais Conjuntos c₁ 1 4 7 1 4 7 2 6 1 4 7 2 6 1 4 7 2 6 1 4 7 2 6 1 4 7 2 6 Conceitos Iniciais Sequências I 2 5 10 Conceitos Iniciais Sequências I 2 5 10 Conceitos Iniciais Sequências I 2 5 10 m 1 7 12 Conceitos Iniciais Sequências I 2 5 10 m 1 7 12 Conceitos Iniciais Sequências l 2 5 10 m 1 7 12 Conceitos Iniciais Funções y fx 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 Conceitos Iniciais Funções 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 1 2 5 10 17 26 37 50 65 0 1 2 3 4 5 6 7 8 1 2 5 10 17 26 37 50 65 0 1 2 3 4 5 6 7 8 1 2 5 10 17 26 37 50 65 Conceitos Iniciais Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si Conceitos Iniciais Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si V 1 2 3 4 5 Conceitos Iniciais Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si V 1 2 3 4 5 Conceitos Iniciais Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si V 1 2 3 4 5 Conceitos Iniciais Grafos Grafos são conjuntos de elementos com relações que conectam alguns deles entre si V 1 2 3 4 5 A 1 2 2 3 3 4 2 4 4 5 1 5 Conceitos Iniciais Strings strings são sequências de caracteres utilizadas na representação da informação textual dentro de sistemas computacionais Strings strings são sequências de caracteres utilizadas na representação da informação textual dentro de sistemas computacionais Strings strings são sequências de caracteres utilizadas na representação da informação textual dentro de sistemas computacionais Propriedades das strings comprimento alfanumérica numérica caixa alta caixa baixa etc Conceitos Iniciais Lógica A lógica que trataremos consiste na lógica Booleana Conceitos Iniciais Lógica A lógica que trataremos consiste na lógica Booleana A lógica Booleana por sua vez é trata de variáveis que podem assumir apenas dois valores portanto variáveis binárias o que pode ser interpretado como VERDADEIRO e FALSO Conceitos Iniciais Lógica A lógica que trataremos consiste na lógica Booleana A lógica Booleana por sua vez é trata de variáveis que podem assumir apenas dois valores portanto variáveis binárias o que pode ser interpretado como VERDADEIRO e FALSO Neste contexto temos as variáveis e as operações lógicas NOT AND OR XOR NAND NOR A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X₁ AND X₂ X1 X2 Y 0 0 0 0 1 0 1 0 0 1 1 1 X1 X2 Y F F F F V F V F F V V V Conceitos Iniciais Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X₁ OR X₂ X1 X2 Y 0 0 0 0 1 1 1 0 1 1 1 1 X1 X2 Y F F F F V V V F V V V V Conceitos Iniciais Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X₁ XOR X₂ X1 X2 Y 0 0 0 0 1 1 1 0 1 1 1 0 X1 X2 Y F F F F V V V F V V V F Conceitos Iniciais Lógica A forma mais usual de resolvermos equações lógicas consiste em definir a tabela verdade das equações Y X₁ OR NOT X₂ X1 X2 Y 0 0 1 0 1 0 1 0 1 1 1 1 X1 X2 Y F F V F V F V F V V V V X1 X2 Y 0 0 0 1 1 0 1 1 X1 X2 Y F F F V V F V V X1 X2 Y 0 0 0 1 1 0 1 1 X1 X2 Y F F F V V F V V