Post on 24-Jul-2020
MODELOS DE COMPUTACION YCOMPLEJIDAD
Grado en Ingenierıa Informatica. Tecnologıas Informaticas
Mario de J. Perez Jimenez
Grupo de investigacion en Computacion NaturalDpto. Ciencias de la Computacion e Inteligencia Artificial
E.T.S. Ingenierıa InformaticaUniversidad de Sevilla
Curso 2018-2019
Problemas, problemas, problemas ...
Una eterna aspiracion del hombre ...
∗ Mejorar la calidad de Vida.
Para ello, necesita resolver problemas.
∗ A ser posible usando procedimientos mecanicos.
2 / 24
Problemas abstractos vs problemas concretos
1. Determinar si el numero 4730099 es primo.
2. Calcular el producto de dos numeros naturales.
3. Hallar el maximo comun divisor de 314 y 4524.
4. Determinar si la suma de los angulos de un triangulo es 127o.
5. Para cada numero natural n hallar un numero primo y mayor que n.
6. Hallar la suma de los numeros 1234567 y 9876543.
7. Determinar si un numero natural n es primo.
8. Hace unas horas, una empresa de reparto ha recibido 75 electrodomesticosde un hipermecado a fin de que los entregue a sus compradores esta mis-tarde. Si esos electrodomesticos tienen cabida en un camion, ¿que rutadebe seguir el conductor para consumir la menor cantidad de gasolina?
3 / 24
Problema concreto (I)
∗ Dadas 42 ciudades, tiempos tij entre dos ciudades, hallar un circuito querecorra las 42 ciudades en el menor tiempo posible.
4 / 24
Problema concreto (II)
∗ Dadas 3150 ciudades, tiempos t′ij entre dos ciudades, hallar un circuitoque recorra las 3150 ciudades en el menor tiempo posible.
5 / 24
Problema abstracto (III)
Dadas n ciudades y unos valores tij que representan los tiempos para ir de laciudad i a la ciudad j. Determinar un circuito que permita recorrer todas lasciudades en el menor tiempo posible.
Problema del viajante de comercio (TSP).
6 / 24
Problemas concretos vs Problemas abstractos
Problema abstracto: conjunto de problemas concretos.
∗ Tamano de un problema concreto.
¿Que significa resolver mecanicamente un problema abstracto?
∗ Algoritmos/programas.
Modelo de computacion: definicion formal de procedimiento mecanico.
∗ Sintaxis.
∗ Semantica.
7 / 24
Maquinas, maquinas, maquinas...
Ventajas de la resolucion mecanica de problemas abstractos
? Las maquinas: asistentes del hombre.
• Realizacion de tareas tediosas...
• ... y otras tareas inteligentes.
8 / 24
Maquinas de proposito especıficoEl abaco (aprox. ano 1000 a.C.): sumar, restar y multiplicar.
La anticitera: Antikytera (aprox. ano 87 a.C.): determinar la posicion de los astros.
9 / 24
Las tablas de Neper (1617): multiplicar sin saberse la tabla.
La regla de calculo (1620–1630): multiplicar, dividir y calcular logaritmos.
10 / 24
La maquina de Pascal (1642-1645): pionera en realizar calculos de forma autonoma (mecanica).
La maquina de Leibniz (1670-1694): la primera capaz de realizar las 4 operaciones aritmeticas.
11 / 24
El telar de Jacquard (1801-1805): la primera maquina “programable”.
El aritmometro de Colmar (1820): la primera maquina comercial construida en serie.
12 / 24
La maquina de diferencias de Babbage (1821): funciones polinomicas (solo con sumas)
La maquina tabuladora de Hollerith (1886): maquina censadora que usa tarjetas perforadas.
13 / 24
Maquinas de proposito general
El sueno de la maquina analıtica: Charles Babbage (1847-1849).
14 / 24
Aparicion del primer ordenador electromecanico: Mark I, H. Aiken, 1944.(760.000 ruedas + 800 kms. de cable + 5.000 Kgs. de peso + Superficie de mas de 17 m2 )
Primer ordenador electronico: Eniac, J.W. Mauchcly y J.P. Eckert, 1945.(17.468 valvulas + 6.000 interruptores manuales + 27.000 Kgs. de peso + Superficie de mas de 160 m2 )
15 / 24
Mas ordenadores ...
? Ordenadores basados en los transistores (1954 - 1962).
• Lenguajes de alto nivel.
? Ordenadores basados en circuitos integrados (1963 - 1972).
• Multiprocesadores.
? Ordenadores basados en microprocesadores (1972 - 1984).
? Ordenadores que incorporan paralelismo (1984 - 1990).
• Familias de ordenadores compatibles.
? Ordenadores con arquitecturas masivamente paralelas (1990 - ...).
• Supercomputadores, computacion de altas prestaciones (HPC), sistemasde realidad virtual, ....
16 / 24
Como resolver problemas de la vida real
Problemas de la vida real: problemas concretos.
¿Como se puede resolver un problema de la vida real?
∗ Se modeliza/representa a traves de un problema abstracto.
∗ Se disena una solucion mecanica del problema abstracto (algoritmo).
∗ Se escribe dicha solucion en un lenguaje especıfico (programa).
∗ Se ejecuta el programa sobre una “maquina” que entienda ese lenguaje,introduciendo los parametros especıficos del problema concreto.
∗ Al final de dicha ejecucion, se obtiene la solucion del problema concreto
17 / 24
Programa + Dato entrada
Maquina
Solucion
18 / 24
Computabilidad ...
? ¿Como saber si un problema abstracto se puede resolver mecanicamente?
∗ Asimetrıa entre la respuesta afirmativa o negativa a esta cuestion.
? Necesidad de formalizar la idea intuitiva de procedimiento mecanico.
• Modelo de computacion.
? Dispositivos computacionales del modelo: maquinas.
• Maquina virtual (teorica).
• Maquina real (construida con soporte fısico).
19 / 24
Complejidad ...
? Analisis “a priori” de la cantidad de recursos (espacio/tiempo) quenecesita una solucion mecanica para resolver un problema abstracto.
• Complejidad Computacional.
? Maquinas reales: dispositivos finitos.
? Limitaciones de las maquinas reales convencionales (electronicas).
• R. Churchhouse, 1983.
? Necesidad de disenar nuevos paradigmas de computacion.
20 / 24
Objetivos generales del curso
∗ Formalizar la idea intuitiva de resolucion mecanica de un problemaabstracto.
∗ Presentar dos modelos de computacion.
∗ Estudiar las limitaciones y potencia de los modelos de computacion.
∗ Analizar la complejidad computacional de problemas abstractos.
∗ Estudiar el problema P versus NP.
∗ Presentar modelos no convencionales inspirados en la Naturaleza Viva.
21 / 24
Contenidos del curso
PARTE I: Teorıa de la Computabilidad.
∗ Modelos de computacion.
∗ Funciones computables.
∗ Programas universales.
∗ Recursividad enumerable e indecidibilidad.
PARTE II: Teorıa de la Complejidad Computacional.
∗ Medidas de complejidad computacional.
∗ Complejidad en tiempo. El problema P versus NP.
∗ Problemas NP-completos.
∗ Modelos de computacion no convencionales.
22 / 24
Evaluacion de la asignatura y Tutorıas
A. Evaluacion alternativa
? Ejercicios propuestos en clase.
? Examenes escritos.
Condicion necesaria: haber asistido, al menos, a 20 sesiones.
B. Examen de evaluacion final
? Examen escrito relativo a los contenidos impartidos en clase.
? Convocatoria oficial: 10 de junio de 2019.
TUTORIAS: Martes, Miercoles y Viernes: de 8:30 h. a 10:30 h.
(Modulo H, despacho H1.41)
23 / 24
Pagina web de la asignatura
http://www.cs.us.es/cursos/mcc/
24 / 24