PDF de programación - Introducción: historia de las Ciencias de la Computación

Imágen de pdf Introducción: historia de las Ciencias de la Computación

Introducción: historia de las Ciencias de la Computacióngráfica de visualizaciones

Publicado el 5 de Julio del 2019
205 visualizaciones desde el 5 de Julio del 2019
94,4 KB
11 paginas
Creado hace 2a (31/01/2017)
Introducción: historia de las Ciencias de

la Computación

Informática Teórica I:
Tema 1

Informática Teórica. Teoría de Lenguajes,

Gramáticas y Autómatas

Ciencias de la Computación:

.....
Teoría de Lenguajes,
Gramáticas,
Autómatas,
Redes de Neuronas,
Complejidad

...........

Informática

Teórica

2

Informática Teórica. Teoría de Lenguajes,

Gramáticas y Autómatas



Tres pilares sustentan la Teoría
de Lenguajes, Gramáticas y

Autómatas

AUTÓMATAS
(ingeniería)



• Leonardo Torres, 1915
• Shannon, 1938
• Mc Culloch-Pitts, 1943
• Moore, 1956

LENGUAJES y GRAMÁTICAS

(lingüística)

• Panini, entre el 400 y 200 AC
• Chomsky, 1967
• Backus, ≈1960
• Kleene, 1951
• Hirst, Tennant y Carbonell,
1981


COMPUTABILIDAD

(matemáticas)

• Hilbert, 1928
• Gödel, Kleene, Post y Turing,
≈1930
• Church, 1936
• Rabin, 1960
• Cobhan, 1964
• Cook, 1972
• Aho, Hopcroft, Ullman, 1974


6

Informática Teórica. Teoría de Lenguajes,

COMPUTABILIDAD

Gramáticas y Autómatas

(matemáticas)

• Hilbert, 1928
• Gödel, Kleene, Post y Turing,
≈1930
• Church, 1936
• Rabin, 1960
• Cobhan, 1964
• Cook, 1972
• Aho, Hopcroft, Ullman, 1974


• COMPUTABILIDAD:
Desarrollada aún antes de la existencia y desarrollo de las computadoras.

• ¿Qué problemas pueden

automáticos?



resolverse mediante procedimientos

• concepto de función calculable: función cuyos valores
pueden ser calculados de forma automática mediante una
sucesión bien determinada de pasos (un algoritmo) y construir
modelos teóricos (de computación) para ello.

• Teoría de la computabilidad: búsqueda de respuestas para las

siguientes preguntas:

• ¿Qué pueden hacer los ordenadores (sin restricciones de ningún
• ¿cuáles son las limitaciones inherentes a los métodos automáticos de

tipo)?
cálculo?

7

Informática Teórica. Teoría de Lenguajes,

Gramáticas y Autómatas

AUTÓMATAS
(ingeniería)

Leonardo Torres, 1915
Shannon, 1938
Mc Culloch-Pitts, 1943
Moore, 1956

AUTÓMATAS:

Concepto moderno de autómata: Leonardo Torres Quevedo, en 1915:

“Los antiguos autómatas... imitaban el aspecto y los movimientos de los
seres vivos, pero eso no tiene mucho interés en la práctica, y lo que
buscamos es un tipo de aparato que deje los meros gestos visibles del
hombre e intente conseguir los resultados que obtiene una persona,
para, de este modo, reemplazar a un hombre por una máquina”...

8

Informática Teórica. Teoría de Lenguajes,

Gramáticas y Autómatas

AUTÓMATAS
(ingeniería)

Leonardo Torres, 1915
Shannon, 1938
Mc Culloch-Pitts, 1943
Moore, 1956

• Teoría de Autómatas: aplicación en campos muy diversos que manejan
conceptos como “control”, “acción”, “memoria” y los objetos son controlados o
recordados con símbolos, palabras o frases de algún tipo.

• Teoría de la Comunicación
• Teoría del Control
• Lógica de los Circuitos Secuenciales
• Computadoras
• Redes Conmutadoras y Codificadoras,
• Lógica de los Sistemas Evolutivos y Autorreproductivos,
• Reconocimiento de Patrones
• Fisiología del Sistema Nervioso
• Estructura y Análisis de

Computadoras Digitales

los Lenguajes de Programación para

• Traducción Automática de Lenguajes y Teoría Algebraica de Lenguajes

9

Informática Teórica. Teoría de Lenguajes,

Gramáticas y Autómatas

LENGUAJES y GRAMÁTICAS

(lingüística)









Panini, entre el 400 y 200 AC
CChomsky, 1967
BBackus, ≈1960
KKleene, 1951
Hirst, Tennant y Carbonell, 1981



LENGUAJES Y GRAMÁTICAS
• Tiene su origen en un campo alejado de la Informática: la lingüística. Los
lingüistas distinguen, tradicionalmente, entre gramática particular (propiedades
de lenguajes concretos, como frecuencia de vocablos, reglas sintácticas, etc.) y
gramática universal (propiedades generales que pueden aplicarse a cualquier
lenguaje humano), tal y como fue descrito por Chomsky en 1967.





• Lingüistas escuela estructuralista americana: elaboraron en los 50 algunas
ideas informales acerca de la gramática universal. Por ejemplo, si un lenguaje
(natural) es un conjunto innumerable de frases, para describirlo debería
establecerse una gramática generativa o conjunto de reglas que subyacen en la
composición de frases correctas y una descripción estructural para cada frase
que permitiese explicar cómo puede componerse tal frase a partir de la
gramática.

13

Informática Teórica. Teoría de Lenguajes,

Gramáticas y Autómatas

LENGUAJES y GRAMÁTICAS

(lingüística)











Panini, entre el 400 y 200 AC
CChomsky, 1967
BBackus, ≈1960
KKleene, 1951
Hirst, Tennant y Carbonell, 1981



la

lingüística moderna,

• La formalización de estos conceptos fue obra de Chomsky en 1956, figura
más destacada de
tanto por desarrollar sus
fundamentos matemáticos como por su teoría sobre el origen y la naturaleza
de los lenguajes naturales. Por ejemplo, las gramáticas generativas
formalizadas permiten explicar el “carácter creativo” de los lenguajes
naturales, es decir, el hecho de que dispongan de mecanismos recursivos
que les permiten expresar un número potencialmente infinito de ideas,
sentimientos, etc. La falta de un formalismo para estudiar estos mecanismos
había inclinado previamente a ciertos lingüistas de la escuela conductista a
negar tal propiedad, y a otros, como Saussure, a considerarla como algo
ajeno al campo de la lingüística.

14

Informática Teórica. Teoría de Lenguajes,

Gramáticas y Autómatas

LENGUAJES y GRAMÁTICAS

(lingüística)













Panini, entre el 400 y 200 AC
CChomsky, 1967
BBackus, ≈1960
KKleene, 1951
Hirst, Tennant y Carbonell,
1981



lenguajes de programación surgió de

•La utilización de gramáticas para especificar la sintaxis de
los
forma
independiente. Mientras trabajaba en un borrador de
ALGOL60, John Backus adaptó las producciones de
Post. La notación resultante fue una variante de las
gramáticas independientes del contexto.

• El lingüista Panini diseñó una notación sintáctica equivalente para especificar las

reglas de la gramática del sánscrito entre el 400 a.C. y el 200 a.C.

• Un avance en la descripción de los lenguajes regulares fueron las expresiones
regulares propuestas por Kleene en 1951 a partir de los trabajos de McCulloch-
Pitts sobre la neurona artificial. Dichas neuronas utilizan una notación para las
cadenas de entrada y salida que fueron la base para el desarrollo de expresiones
regulares. En el trabajo de Kleene se demuestra la equivalencia entre lo que él
llama “dos formas de definir una misma cosa”, que son los conjuntos regulares,
es decir, las expresiones regulares y los conjuntos especificados por un
autómata finito.

15

Informática Teórica en la Ingeniería Informática

Lenguajes

Problemas

• Dado un Lenguaje, L, generar
cadenas que pertenezcan a L.


• Dada una cadena, x,

reconocer si pertenece a un
determinado L.

Abstracciones

• L finito: solución sencilla:
enumeración de todas las
cadenas que lo forman


• L infinito: descripción finita para

resolver generación y
reconocimiento. → Metalenguaje



Generar

escribir, programar

Reconocer

diccionario, explorador

sintáctico

Gramáticas
descripción

metalingüística para
poder desarrollar un
algoritmo enumerativo

de generación de

cadenas del Lenguaje

Autómatas

Permiten, dado un L y
una cadena x, determinar
si x pertenece o no a L.

Descripción formal de Lenguaje

17

Jerarquía de Chomsky



Informática
Teórica I

G. Regulares

G3

G. Indep Contexto

G2

Autómatas

Finitos

G. Dependientes
del Contexto G1

Autómatas Pila

G. sin restricciones

G0

Lenguajes
Regulares

Autómatas
Linealmente
Acotados

Lenguajes Indep.

Contexto

Máquinas de Turing

Lenguajes

Dependientes

Contexto

Lenguajes sin
restricciones

18
  • Links de descarga
http://lwp-l.com/pdf16231

Comentarios de: Introducción: historia de las Ciencias de la Computación (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad