PRINCIPIOS, IMPLEMENTACIÓN Y RENDIMIENTO TEMA 1
1. CAPÍTULO 1
1.1 HISTORIA DE LA COMPUTACIÓN:
Punto de vista hardware Punto de vista software
PRIMERA GENERACIÓN Lenguaje máquina y lenguaje
Uso de válvulas en el vacío
(1951- 1958) ensamblador
Uso de transistores y se
SEGUNDA GENERACIÓN Desarrollo de lenguajes de
extiende el uso de
(1959-1964) alto nivel
microprogramación
- Inicia el uso de
multiprogramación y se
propone la programación
TERCERA GENERACIÓN estructurada.
Uso de circuitos integrados
(1965-1971) - Aparece UNIX
- Implementación de las
primeras redes de
computadores
- Memorias de estado sólido,
CUARTA primeros microprocesadores
–
ACTUALIDAD - Componentes de entrada- - Conectividad entre
(1972 -) salida dispositivos
1.2 EL COMPUTADOR COMO AUTÓMATA:
- Autómata: máquina de cálculo abstracta que salta de un estado a otro guiada por unas
entradas de control y unas pautas preestablecidas.
- La teoría de autómatas es la rama de las Ciencias de la Computación que estudia estas
máquinas y los problemas que son capaces de resolver.
- TIPOS:
o Autómata finito: Representas sistemas que pueden estar en un número finito
de estados y realizar transiciones entre ellos en respuesta de entradas
específicas.
o Autómata pila: Es un autómata finito, pero con una memoria auxiliar ordenada
como pila en la que puede leer y escribir.
o Máquina de Turing: Es un autómata finito, pero con una memoria auxiliar
infinita en la que se puede leer y escribir símbolos.
Teoría
Teoría de los Teoría de la
lenguajes de los
complejidad
formales Autómatas computacional
PRINCIPIOS, IMPLEMENTACIÓN Y RENDIMIENTO TEMA 1
1.3 MÁQUINA DE TURING:
- Conceptualmente: Es un autómata finito con una cinta infinita que se puede
desplazar a derecha e izquierda y en la que se pueden leer y escribir símbolos.
- Problemas indecidibles: Problemas que no se pueden resolver con un
computador. La máquina no pare nunca.
- FINAL CON ACEPTACIÓN: la máquina se para porque ha finalizado su tarea.
- FINAL CON NO ACEPTACIÓN: La máquina a alcanzado un estado en donde
ha entrado un símbolo no esperado.
1.3.1 EL PROBLEMA DE LA PARADA:
- Problema indecidible
- El problema de la parada busca determinar si se puede crear un programa que
sea capaz de decir a través del programa dado y la entrada si se detendrá o
seguirá infinitamente.
1.4 PROBLEMAS COMPUTACIONALES:
1.4.1 TIPOS DE PROBLEMAS:
- Decisión: La solución es un ‘sí’ o un ‘no’. Por ej. Determinar si “a” es
primo o no.
- Búsqueda: La solución debe cumplir un predicado lógico.
- Recuento: la solución es el número de soluciones que cumplen el predicado
lógico.
- Optimización: La solución debe ser la mejor entre todas las posibles.
1.4.2 TIPOS DE COMPLEJIDAD:
- Complejidad Constante O (1): significa que el tiempo o el espacio
requerido por el algoritmo no depende del tamaño de la entrada1. Es la forma más eficiente
de complejidad.
- Complejidad logarítmica O (log2 n): significa que el tiempo o el espacio
crece de manera logarítmica con respecto al tamaño de la entrada.
- Complejidad lineal O (n): significa que el tiempo y el espacio crecen de
manera proporcional al tamaño de la entrada. Eficiente y común en muchos algoritmos.
- Complejidad polinómica O (n^2): significa que el tiempo y el espacio
crecen de manera cuadrática en relación con el tamaño de la entrada.
- Complejidad exponencial O(2^n): significa que el tiempo y el espacio
crecen de manera exponencial con respecto al tamaño de la entrada. Menos eficiente.
(1) Cantidad de datos procesados o manipulados.
PRINCIPIOS, IMPLEMENTACIÓN Y RENDIMIENTO TEMA 1
1.4.3 CLASIFICACIONES EN LA TEORÍA DE LA COMPLEJIDAD
COMPUTACIONAL:
- DECIDIBLES: Para cualquier dato de entrada, siempre hay una respuesta.
- INDECIDIBLES: No existe un algoritmo por el cual se pueda decidir la
respuesta correcta en todos los casos posibles.
- P (Polinómico o inferior): Son problemas para los cuales existe un algoritmo
eficiente(polinómico) que puede encontrar solución en un tiempo razonable.
- NP (entre Polinómico y exponencial): Son problemas para los cuales si se
presenta una solución, se puede verificar rápidamente, pero no se ha demostrado
que exista un algoritmo eficiente para encontrar la solución.
- NP-completo (Exponencial o superior): son problemas para los cuales no se ha
encontrado un algoritmo eficiente (polinómico) para su resolución, se puede
verificar rápidamente su validez.
1.4.4 EL PROCESO DE COMPUTACIÓN:
- La resolución de un problema
computacional es un proceso integral en el
que el éxito depende de la adecuada
sintonización de las fases que lo componen.
- La figura ilustra esas fases desde la
inicial formulación abstracta hasta la
imagen binaria del programa ejecutable que
lo resuelve en un computador convencional
moderno.
- Asumiendo una correcta formulación de
un problema el siguiente paso es encontrar
un buen algoritmo que le dé solución.
^La algoritmia nos proporciona un
conjunto ordenado y finito de operaciones a
seguir. Además, nos revela la complejidad
intrínseca del problema respecto a los
recursos necesarios para resolverlo.
^A continuación se ha de escribir ese
algoritmo en algún lenguaje de programación cuidando que tanto las estructuras de datos
como la codificación y el propio lenguaje formal sean convenientes al tipo de problema.
^Durante el proceso de computación, el problema abstracto se convierte en un
problema concreto gracias a la formalización en código fuente de la relación entre los
conjuntos oportunamente estructurados de entrada y solución.
^Para un análisis más certero se debe tener en cuenta entradas no esperadas o vigilar la
existencia de trazas de ejecución (registro de lo que ocurre durante la ejecución de un
programa) imprevistas.
PRINCIPIOS, IMPLEMENTACIÓN Y RENDIMIENTO TEMA 1
^Otro aspecto a tener en cuenta es que su código fuente no aumente la complejidad
intrínseca del algoritmo que da solución al problema computacional original.
^ Una vez desarrollado el programa, éste aún no es ejecutable directamente sobre el
computador y ha de ser traducido a código binario y estructurado apropiadamente
utilizando otras herramientas tales como compiladores2, intérpretes3 o ensambladores4 .
- La única diferencia existente entre cada etapa del proceso es la forma de expresión.
1.5 ARQUITECTURA DE COMPUTADORES
