Fundamentos Teóricos da Computação
Por: igorp19 • 20/10/2021 • Exam • 1.698 Palavras (7 Páginas) • 148 Visualizações
Fundamentos Teóricos da Computação
– Apresentação da Disciplina –
Zenilton Kleber Gonçalves do Patrocínio Jr.
Engenharia de Computação – PUC Minas
Belo Horizonte, Brasil
2021
Computabilidade e Decidibilidade Apresentação da Disciplina
Sumário
1 Computabilidade e Decidibilidade
Introdução
Histórico
2 Apresentação da Disciplina
Introdução
Conteúdo Programático
Bibliografia
Avaliações
Zenilton Patrocínio Jr. FTC – Apresentação da Disciplina 2021 2 / 15
Computabilidade e Decidibilidade Apresentação da Disciplina
Introdução Introdução
Computabilidade, Decidibilidade e Complexidade
O que é um computador?
Quais são suas capacidades e limitações?
Que classe de problemas são computáveis?
Como determinar a complexidade da solução?
Como obter um modelo geral para o conceito de
computabilidade?
Zenilton Patrocínio Jr. FTC – Apresentação da Disciplina 2021 3 / 15
Computabilidade e Decidibilidade Apresentação da Disciplina
Introdução Introdução
Computabilidade, Decidibilidade e Complexidade
O que é um computador?
Quais são suas capacidades e limitações?
Que classe de problemas são computáveis?
Como determinar a complexidade da solução?
Como obter um modelo geral para o conceito de
computabilidade?
Zenilton Patrocínio Jr. FTC – Apresentação da Disciplina 2021 3 / 15
Computabilidade e Decidibilidade Apresentação da Disciplina
Introdução Introdução
“Algoritmo”
Um processo finito de ações executar uma determinada tarefa
“Algoritmos” também possuem um papel importante na
matemática
Exemplo: algoritmo de Euclides para MDC
Zenilton Patrocínio Jr. FTC – Apresentação da Disciplina 2021 4 / 15
Computabilidade e Decidibilidade Apresentação da Disciplina
Histórico Histórico
A noção de algoritmo só foi definida, precisamente, no século
XX
Antes disso, os matemáticos baseavam-se na noção intuitiva
de “algoritmo”
Qual o problema de se usar uma noção intuitiva?
Zenilton Patrocínio Jr. FTC – Apresentação da Disciplina 2021 5 / 15
Computabilidade e Decidibilidade Apresentação da Disciplina
Histórico Histórico
A noção de algoritmo só foi definida, precisamente, no século
XX
Antes disso, os matemáticos baseavam-se na noção intuitiva
de “algoritmo”
Qual o problema de se usar uma noção intuitiva?
Zenilton Patrocínio Jr. FTC – Apresentação da Disciplina 2021 5 / 15
Computabilidade e Decidibilidade Apresentação da Disciplina
Histórico Histórico
Uma noção intuitiva não é suficiente para se obter provas
sobre propriedades de algoritmos!
Exemplo
Em 1900, Hilbert propôs uma série de problemas matemáticos:
10◦ Problema de Hilbert era o de encontrar um “algoritmo”
para determinar, dado um polinômio com coeficientes
inteiros, se o mesmo possuía raízes inteiras
Zenilton Patrocínio Jr. FTC – Apresentação da Disciplina 2021 6 / 15
Computabilidade e Decidibilidade Apresentação da Disciplina
Histórico Histórico
Uma noção intuitiva não é suficiente para se obter provas
sobre propriedades de algoritmos!
Exemplo
Em 1900, Hilbert propôs uma série de problemas matemáticos:
10◦ Problema de Hilbert era o de encontrar um “algoritmo”
para determinar, dado um polinômio com coeficientes
inteiros, se o mesmo possuía raízes inteiras
Zenilton Patrocínio Jr. FTC – Apresentação da Disciplina 2021 6 / 15
Computabilidade e Decidibilidade Apresentação da Disciplina
Histórico Histórico
Uma noção intuitiva não é suficiente para se obter provas
sobre propriedades de algoritmos!
Exemplo
Em 1900, Hilbert propôs uma série de problemas matemáticos:
10◦ Problema de Hilbert era o de encontrar um “algoritmo”
para determinar, dado um polinômio com coeficientes
inteiros,
...