Informatica Basica: Capitulo 12 Teoria de la Computacion

TEORIA DE LA COMPUTACION

TEORIA DE FUNCIONES RECURSIVAS

— NADA MAS MOLESTA A LA NATURALEZA HUMANA QUE EL QUE NOS DIGAN QUE NOSE PUEDE HACER ALGO.

— UNA TECNICA MAS POTENTE PARA EL CALCULO DE FUNCIONES CONSISTE EN SEGUIR LAS DIRECTIVAS PROPORCIONALES POR UNA FORMULA ALGEBRAICA

MAQUINAS DE TURING

— EN UN INTENTO DE COMPRENDERLAS CAPACIDADES Y LIMITACIONES DE LAS MAQUINAS, MUCHOS INVESTIGADORES HAN PROSUPUESTOSY ESTUDIADO DIVERSOS DISPOSITIVOS COMPUTACINALES

ORIGENES DE LAS MAQUINAS DE TURING

— ALAN TURING DESARROLLO EL CONCEPTO DE MAQUINA DE TURING EN LA DECADA DE 1930, MUCHO ANTES DE QUE LA TECNOLOGIA FUERA CAPAZ DE PROPORCIONAR LAS TECNICAS QUE CONOCEMOS HOY EN DIA.

FUNDAMENTOS DE LA MAQUINA DE TURING

— UNA MAQUINA DE TURING ESTA COMPUESTA POR UNA UNIDAD DE CONTROL QUE PUEDE LEER Y ESCRIBIR SIMBOLOS EN UNA CINTA POR MEDIO DE UN CABEZAL DE LECTURA.

— LA COMPUTACION EFECTUADA POR UNA MAQUINA DE TURING CONSISTE EN UNA SECUENCIA DE PASOS EJECUTADOS POR UNA UNIDADSDE CONTROL DE LA MAQUINA.

LA TESIS DE CHURCH-TURING

— LA MAQUINA DE TURING DEL EJEMPLO ANTERIOR SE PUEDE UTILIZAR PARA CALCULAR LA FUNCION CONOCIDA CON EL NOMBRE DE FUNCION SUCESORA.

EL LENGUAJE DE BORE BONES

— COMENZAMOS NUESTRO PRESENTACION DE BARA BONES CONSIDERADO LAS SENTENCIAS DECLARATIVAS QUE PODEMOS ENCONTRAR EN OTROS LENGUAJES DE PROGRAMACION.

PROGRAMACION EN BARE BONES

— RECUERDE QUE NUESTRO OBJETIVO AL PRESENTAR EL LENGUAJE BARA BONES ES INVESTIGAR QUE COSAS SON POSIBLES.BARE BONES SERIA TERRIBLE DE UTILIZAR EN EL ENTORNO DE UNA APLICACIÓN REAL.

LA UNIVERSALIDAD DE BARE BONES

— APLIQUEMOS AHORA LA TESIS DE CHURCH-TURING PARA CONFIRMAR NUESTRA AFIRMACION DE UQE BARE BONES ES UN LENGUAJE DE PROGRAMACION UNIVERSAL.

— LA ENTRADA DE LA FUNCION ESTA COMPUESTO POR LOS VALORES ASINGNADOS A LAS VARIABLES ANTES DE LA EJECUCION DEL PROGRAMA

LA IRRESOLUBILIDAD DEL PROBLEMA DE LA DETENCION

— NUESTRO ENFOQUE CONSISTIRIA EN DEMOSTRAR QUE EL RESOLVER EL PROBLEMA REQUERIDO UN ALGORITMO PARA CALCULAR UNA FUNCION NO COMPUTABLE

COMPLEGIDAD ESPACIAL

— UNA ALTERNATIVA A MEDIR LA COMPLEJIDAD EN TERMINOS DEL TIEMPO ES LA DE MEDIR EN SU LUGAR LOS REQUISITOS DE ESPACIO DE ALMACENAMIENTO LO QUE DA CON RESULTADO UNA MEDIDA QUE SE CONOCE CON EL NOMBRE DE COMPLEJIDAD ESPACIAL

DETERMINISTA Y NO DETERMINISTA

— EN MUCHOS CASOS,EXISTE UNA LINEA MUY FINA ENTRE “ALGORITMO” DETERMINADA Y OTRO NO DETERMINADA SIN EMBARGO, LA DISTINCION ES BASTANTE CLARA E IMPORTANTE.

CRIPTOGRAFIA DE CLAVE PUBLICA RSA.

AHORA ESTAMOS PREPARADOS PARA CONSTRUIR Y ANALIZAR UN SISTEMA DESIFRADO DE CLAVE PUBLICA BASADO EN EL ALGORITMO RSA

LA ARQUITECTURA DE LA MAQUINA

— LA MAQUINA TIENE 16 REGISTROS DE PROPOSITO GENERAL NUMERADOS DE 0 A F CADA REGISTRO TIENE UNA LONGUITUD DE UN BYTE.

LENGUAJE DE LA MAQUINA

— CADA INSTRUCCIÓN DE LENGUAJE MAQUINA TIENE DOS BYTES DE LONGUITUD LOS PRIMEROS CUATROS PROPORCIONAN EL CODIGO DE OPERACIÓN

LENGUAJE S DE PROGRAMACION DE ALTO NIVEL

ADA

— EL LENGUAJE ADA FUE DESARROLLADO POR INICIATIVA DEL DEPARTAMENTO DE DEFENSA DE ESTADOS UNIDOS EN UN INTENTO DE OBTENER UN UNICO LENGUAJE DE PROPOSITO GENERAL QUE SATISFACIERA TODAS SUS NECESIDADES DE SOTFWARE.

— EL LENGUAJE C FUE DESARROLLADO PRO DENNIS A PRINCIPIOS DE LA DECADA DE 1970 DISEÑADO ORIGINALMENTE COMO UN LENGUAJE PARA EL DESARROLLO DEL SOTFWARE DE SISTEMAS.

C++

— EL LENGUAJE C++ FUE DESARROLLADO POR BJARME STROUSTRUP COMO UNA VERSION AMPLIA DEL ARTE. EL OBJETIVO ERA OBTENER UN LENGUAJE COMPATIBLE EN EL PARADIGMA DE LA ORIENTACION.

— EL LENGUAJE C# FUE DESARROLLADO POR MICROSOFT COMO UNA HERRAMIENTA PARA EL ENTORNO.

FORTRAN

— FORTRAN ES EL ACRONIMO DE FORMULA TRANSLATOR(TRADUCTOR DE FORMULAS) ESTE LENGUAJE FUE UNO DE LOS PRIMEROS LENGUAJES DE ALTO NIVEL QUE SE DESARROLLARON Y UNO DE LOS PRIMEROS LENGUAJES EN OBTENER UNA AMPLIA ACEPTACION DE LA COMUNIDAD DE LA COMPUTACION

JAVA

— JAVA ES UN LENGUAJE ORIENTADO A OBJETOS DESARROLLADOS POR SUN MICROSYSTEMS A PRINCIPIOS DE LA DECADA DDE 1990. JAVA PUEDE EJECUTARSE DE FORMA EFICIENTE EN UN AMPLIO RANGO DE MAQUINAS