12258270
Description
Mind Map by Johan Roberto Rueda, updated more than 1 year ago
|
Created by Johan Roberto Rueda
almost 7 years ago
|
|
Autómatas y Lenguajes Formales
- Origenes
- Fue formalmente elaborado en los años 30 y 40 gracias a los descubrimientos de
lógicos matemáticos entre los que destacan:
- Precursores
- Gödel
- Turing
- Post
- Church
- Kleene
- Gödel
- D. Hilbert
- Formuló determinadas cuestiones en
1928, las cuales fueron el punto de
partida de muchos precursores
- ¿Son completas las matemáticas, en el
sentido de que pueda probarse
simultáneamente o no cada
aseveración matemática?
- ¿Son las matemáticas consistentes en el sentido de
que no pueda probarse simultáneamente una
aseveración y su negación?
- ¿Son las matemáticas decidibles, en el sentido de
que exista un método definido que se pueda aplicar
a cualquier aseveración matemática y que
determine si es cierta?
- ¿Son completas las matemáticas, en el
sentido de que pueda probarse
simultáneamente o no cada
aseveración matemática?
- Formuló determinadas cuestiones en
1928, las cuales fueron el punto de
partida de muchos precursores
- Precursores
- Fue formalmente elaborado en los años 30 y 40 gracias a los descubrimientos de
lógicos matemáticos entre los que destacan:
- Acontecimientos importantes
- 1928
- D. Hilbert
- Planteó las cuestiones tomadas de base por los precursores
- Planteó las cuestiones tomadas de base por los precursores
- 1931
- Gödel
- Presenta su teorema de incompletitud
- Todo sistema de primer orden consistente
que contenga los teoremas de la Aritmética
y cuyo conjunto de axiomas sea recursivo
no es completo.
- Todo sistema de primer orden consistente
que contenga los teoremas de la Aritmética
y cuyo conjunto de axiomas sea recursivo
no es completo.
- Presenta su teorema de incompletitud
- 1936
- Church
- Desarrolla el cálculo lambda,
basado en funciones recursivas.
- demuestra la existencia de problemas
indecidibles para el cálculo lambda.
- demuestra la existencia de problemas
indecidibles para el cálculo lambda.
- Desarrolla el cálculo lambda,
basado en funciones recursivas.
- Turing
- En 1936 probaron que el Entscheidungsproblem
(meta de Hilbert: crear un sistema matemático
formal "completo" y "consistente" en el que todas
las aserveraciones pudieran plantearse con
precisión) era un problema indecidible
- En 1936 probaron que el Entscheidungsproblem
(meta de Hilbert: crear un sistema matemático
formal "completo" y "consistente" en el que todas
las aserveraciones pudieran plantearse con
precisión) era un problema indecidible
- Gödel
- Define la clase de "Las funciones recursivas de
Herbrand-Gödel"
- Define la clase de "Las funciones recursivas de
Herbrand-Gödel"
- Kleene
- Demuestra formalmente la equivalencia entre funciones
λ-definible y funciones recursivas de Herbrand-Gödel
- Demuestra formalmente la equivalencia entre funciones
λ-definible y funciones recursivas de Herbrand-Gödel
- 1940
- 1938
- Claude Elwood Shannon
- publica A Symbolic Analysis of Relay and Switching Circuits.
Aplicación lógica matemática a los circuitos electrónicos.
- publica A Symbolic Analysis of Relay and Switching Circuits.
Aplicación lógica matemática a los circuitos electrónicos.
- 1948
- Claude Elwood Shannon
- publica Una Teoría Matemática de la Comunicación.
Nacimiento de la Teoría de la Información
- publica Una Teoría Matemática de la Comunicación.
Nacimiento de la Teoría de la Información
- 1950
- Se estudiaron los Autómatas Finitos
- inicia el estudio formal de las gramáticas
- inicia el estudio formal de las gramáticas
- 1955
- Noam Chomsky
- Doctorado en la Universidad de
Harvard con la tesis Estructura lógica
de la teoría lingüística. (1957) publica
Estructuras sintácticas en el que
aparece la clasificación de gramáticas
- Doctorado en la Universidad de
Harvard con la tesis Estructura lógica
de la teoría lingüística. (1957) publica
Estructuras sintácticas en el que
aparece la clasificación de gramáticas
- 1956
- Claude Elwood Shannon
- Edita, junto a McCarthy, Automata Studies,
sobre máquinas secuenciales y autómatas
finitos.
- Edita, junto a McCarthy, Automata Studies,
sobre máquinas secuenciales y autómatas
finitos.
- 1960
- Autómatas finitos y ciertas clases de
gramáticas formales son usadas en el
diseño y construcción de software.
- 1969
- Stephen Arthur Cook
- Extiende el estudio de Tuning. Cook separa aquellos
problemas que pueden ser solucionados de aquellos
que en principio pueden ser solucionados pero que en
la práctica toman demasiados recursos.
- Extiende el estudio de Tuning. Cook separa aquellos
problemas que pueden ser solucionados de aquellos
que en principio pueden ser solucionados pero que en
la práctica toman demasiados recursos.
- 1970
- Complejidad computacional
- 1971
- Stephen Arthur Cook
- En 1971 publica The Complexity of
Theorem Proving Procedures, donde
define las clases de problemas P, NP, y
NP completos.
- En 1971 publica The Complexity of
Theorem Proving Procedures, donde
define las clases de problemas P, NP, y
NP completos.
- 1990
- Se pueden tratar como elementos
simples, desde un punto de vista
computacional
- 1994
- Adleman
- Utilizó oligonucleótidos, es decir,
cadenas cortas de hasta 20
nucleótidos, para codificar los
vértices y la aristas de un grafo
dado.
- Utilizó oligonucleótidos, es decir,
cadenas cortas de hasta 20
nucleótidos, para codificar los
vértices y la aristas de un grafo
dado.
- 1998
- Chou y Reggia
- Usan bucles reproductores para resolver el
problema NP-completo de la satisfacibilidad
que consiste en ver si existe valores de
verdad que hacen verdadero un predicado
(literal).
- Usan bucles reproductores para resolver el
problema NP-completo de la satisfacibilidad
que consiste en ver si existe valores de
verdad que hacen verdadero un predicado
(literal).
- Chou y Reggia
- Adleman
- Se pueden tratar como elementos
simples, desde un punto de vista
computacional
- Stephen Arthur Cook
- Complejidad computacional
- Stephen Arthur Cook
- Autómatas finitos y ciertas clases de
gramáticas formales son usadas en el
diseño y construcción de software.
- Claude Elwood Shannon
- Noam Chomsky
- Se estudiaron los Autómatas Finitos
- Claude Elwood Shannon
- Claude Elwood Shannon
- Se estudiaron los Autómatas Finitos
- Desarrollo de la primera computadora digital
- Desarrollo de la primera computadora digital
- 1938
- Church
- Gödel
- D. Hilbert
- 1928
Want to create your own Mind Maps for free with GoConqr? Learn more.