Respuestas
6. ¿Qué es algoritmo?
Es un conjunto de instrucciones definida, no ambiguas, ordenadas, y finitas
que permiten realizar un cómputo, procesar datos y llevar a cabo otras
tareas o actividades.
7. ¿Qué es un lenguaje formal?
Es una forma de comunicación artificial con reglas precisas y precisas,
del cual se compone por: un conjunto de sı́mbolos llamado alfabeto, un
conjunto de reglas llamado gramática o sintaxis, y cadenas de sı́mbolos
formadas de acuerdo a la gramática.
8. ¿Cuáles son las diferencias entre lenguaje formal y lenguaje natural?
El lenguaje natural cuenta con reglas, pero éstas van cambiando a lo largo
del tiempo, evolucionando e incluso formando nuevos lenguajes, diferente
a las reglas del lenguaje formal, las cuales estan formalmente especifica-
das; Un Lenguaje Natural no surge de la misma manera que un lenguaje
formal, ya que éste puede surgir a partir de otro lenguaje humano, o inclu-
so puede ser creado de forma natural, como la comunicación que tienen los
animales, a diferencia de los lenguajes formales, los cuales son formados
artificialmente.
11. En a lo más 15 lı́neas, escribe una pequeña biografı́a de Kurt Gödel inclu-
yendo sus aportaciones más importantes. Inserta una imagen de él al lado
derecho del texto, de tal manera que la imagen ocupe la mayor cantidad
de lı́neas posibles. Consulta tres fuentes y cı́talas.
Kurt Gödek nación el 28 de abril de 1906
en Brün, Austria-Hungrı́a (hoy Brno, Reúbli-
ca Checa) y murió el 14 de enero de 1978 en
Princeton, Nueva Jersey, USA. Gödel es mejor
conocido por su demostración de los “Teore-
mas de Incompletitud de Gödel”. En particu-
lar, probó que la consistencia de los axiomas
no puede probarse, y acabó con cien años de
intentos de establecer axiomas que pudieran
poner a todas las matemáticas sobre una base
axiomática. Lo cual también implica que es
imposible programar una computadora para
que responda todas las preguntas matemáti-
cas. Después de establecerse en los Estados
Unidos, Gödel produjo su obra maestra “Con-
sistencia del axioma de elección y de la hipóte-
sis del continuo generalizada con los axiomas
de la teorı́a de conjuntos”, donde probó que si
1
un sistema axiomático de la teorı́a de conjuntos como los propuestos por Russell
y Whitehead es consistente, entonces permanece consistente al agrega al sistema
el axioma de elección y la hipótesis del continuo generalizada.
Referencias:
[Link]
204-goedel-kurt
[Link]
[Link]
12. En a lo más 15 lı́neas, escribe una pequeña biografı́a de Claude Shannon
incluyendo sus aportaciones más importantes. Inserta una imagen de él
al lado derecho del texto, de tal manera que la imagen ocupe la mayor
cantidad de lı́neas posibles. Consulta tres fuentes distintas y cı́talas.
Claude Elwood Shannon (30 de abril de
1916 - 24 de febrero de 2001) fue un matemáti-
co, ingeniero eléctrico y criptógrafo estadou-
nidense recordado como el padre de la teorı́a
de la información. Fundó este campo con la
publicación de Una teorı́a matemática de la
comunicación. También es conocido por haber
sentado las bases de la teorı́a del diseño de cir-
cuitos digitales en 1937. Contribuyó, también,
al campo del criptoanálisis para la defensa de
Estados Unidos durante la Segunda Guerra
Mundial con trabajos sobre el descifrado de
códigos y la seguridad en las telecomunica-
ciones. En su tesis de maestrı́a en el MIT,
demostró cómo el álgebra booleana se podı́a
utilizar en el análisis y la sı́ntesis de la con-
mutación y de los circuitos digitales. En 1940
le fue concedido el Premio a ingenieros ame-
ricanos del Instituto Americano Alfred Nobel
de Estados Unidos. Por lo general, su biografı́a está llena de frutos de su ingenio,
con numerosas aplicaciones en el campo de las máquinas automáticas, desde un
ratón electrónico, hasta diversos juegos electrónicos de ajedrez, calculadoras,
instrumentos musicales, juguetes mecánicos, relojes, entre muchos otros.
Referencias:
[Link]
[Link]
[Link]
2
19. Inserta la función de Haskell que calcula la reversa de una lista. El formato
de inserción debe ser el siguiente: debes primero insertar el pseudocódigo
de la función y después la función tal y como la escribirı́as en Haskell para
que la compile. No es válido tomar capturas de pantalla al código de algún
editor de texto.
Proceso reversa
Establecemos que, cuando rev sea una lista vacı́a, devuelva [] como resul-
tado.
Establecer la función que separa el primer elemento de la lista del resto
sea igual a la concatenación de la función del resto de la lista con el primer
elemento de la lista.
Repetir el proceso hasta que la función del resto de la lista sea []
código en Haskell
rev [] = []
rev (x : xs) = revxs + +[x]
20. Escribe la función de Haskell que reciba una lista de números enteros y
devuelva la lista de números después de sumarles los n-1 números anterio-
res a cada uno. No es necesario que entregues el archivo .hs, sin embargo
debes justificar tu respuesta e insertar el código de la función como en el
ejercicio anterior.
Establecemos que la composición addn1 (m([])) cuando m tenga un valor
arbitrario devuelva [] como resultado.
Definimos como m = 0 como valor inicial
Establecemos la composición addn1 de la función m que separa el primer
elemento de la lista con el resto, sea igual a la concatenación de la suma
de m más el primer de la lista, con la composición addn1 de la función m
más el primer elemento de la lista con el resto de la lista.
Repetir el proceso hasta que addn1 m[] = []
código en Haskell
addn1 [] = []
addn1 m(x : xs) = (m + x) : addn1(m + x)xs
Al ejecutar
addn1 0 [a]
Ej. addn1 0 [1, 2, 3]
32. Investiga sobre la gramática de cualquier lenguaje de programación de tu
preferencia.
Java:
3
• Identifica las reglas de producción.
exp ::=< const > | < ident > | < op − unario >< exp > |
< exp >< op − bin >< exp > | < exp >
op − bin ::= +| − | ∗ |/| %| == |! = | >= | <= | > | < |&&|(||)
op − unario ::= −| + |!
const ::= 0|1|2|3|4|5|6|7|8|9
ident ::= a|b|c|d|...|x|y|z
• Identifica los sı́mbolos terminales y no terminales.
No terminales: {< const >, < ident >, < op − bin >,
< op − unario >}
Terminales: {+, −, ∗, /, %, ==, ! =, >=, <=, >, <, &&, ||, !,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, ..., z}
• Da una cadena bien formada del lenguaje y realiza su derivación.
−a + 3
exp →< exp >< op − bin >< exp >→
< op − unario >< exp >< op − bin >< exp >→
− < exp >< op − bin >< exp >→
− < ident >< op − bin >< exp >→
− a < op − bin >< exp >
− a+ < exp >→
− a+ < const >
−a+3
36. Cierto o falso (justifica brevemente): Existe un algoritmo tal que pa-
ra cualquier lenguaje determine el conjunto de expresiones mı́nimas que
genere dicho lenguaje.
Falso.
[Link]