Fundamentos
FACULTAD DE INGENIERIA
DIVISIÓN DE INGENIERÍA ELÉCTRICA
COMPUTACIÓN PARA INGENIEROS
NOTA IMPORTANTE: Para complementar este tema
es necesario bajar e imprimir el artículo
Herramientas de Programación que se encuentra
en el apartado Artículos
PROF. ING. JAIME ALFONSO REYES CORTÉS
FUNDAMENTOS DE ALGORITMOS
Computabilidad: Término matemático paranombrar a los
estudios sobre teoría de la computación. Consiste en encontrar
la representación adecuada para la descripción de un
problema o un fenómeno.
Conocimiento transmisible: se da si se cierra el ciclo
Descripción
Representación
FUNDAMENTOS DE ALGORITMOS
Modelo: Especificación, generalmente en términos de un
lenguaje matemático, de los pasos necesarios para
reproducir, aquí yahora, un subconjunto determinado de
la realidad descrito previamente
Pregunta:
¿Todo aquello que es descriptible es representable?
¿Habrá una representación que simule completamente lo
descrito?
Cuanto más adecuada sea la descripción del proceso,
tanto mejor será el resultado que emula lo real
FUNDAMENTOS DE ALGORITMOS
Supongamos que se crea una máquina para
producir descripciones entérminos de cadenas de
símbolos.
Dada una descripción cualquiera, la analiza durante
un tiempo finito y después emite su dictámen (si o
no) con respecto al problema
Descripción
Procedimiento
De
decisión
Pregunta : ¿existirá una máquina así?
SI
NO
HAY
SOLUCIÓN
FUNDAMENTOS DE ALGORITMOS
Máquina de Turing: Es un modelo matemático para
especificar formalmente los pasos primitivos necesariospara representar una descripción en términos totalmente
explícitos y claros, sin hacer la menor referencia a
conceptos u operaciones ambiguos o sobreentendidos.
Elementos:
–
–
–
Una cinta de longitud infinita, dividida en celdas (cada
celda puede contener un símbolo
Un diccionario de símbolos predefinido (De aquí se
toman los símbolos para las celdas)
Un control finito, que posee un cojunto deestados y que
tiene la capacidad de examinar algún símbolo de alguna
celda y tomar una decisión (La decisión depende del
símbolo observado y del estado en el que se encuentre en
ese momento)
FUNDAMENTOS DE ALGORITMOS
Funcionamiento: Mediante un conjunto de funciones
matemáticas simples se indica el comportamiento completo
del proceso que está siendo representado, mostrando
detalladamente losestados por los que atraviesa para
lograrlo. Se parte de un estado inicial y se recorre un
conjunto de estados intermedios hasta llegar al estado
final, que marca entonces el final de la computación
S10
S0
CONTROL
FINITO
S7
S14
S4
S2
…
FUNDAMENTOS DE ALGORITMOS
Teoría de la computabilidad Encontrar formas de
representar descripciones de procesos, de manera tal
que siempre sepueda decir que la solución de un
problema existe o no
Un problema se dice que es Computable si existe una
máquina de decisión para él
Pregunta: ¿Todos los procesos son computables?
Un problema se dice que es No Computable si la
máquina de decisión para él llega a un estado en donde
no es capaz de decir que si o que no
FUNDAMENTOS DE ALGORITMOS
1. Definición o análisis del
problema: Descripciónespecífica y comprensible
del problema a resolver
2. Diseño del algoritmo:
Planteamiento de los
pasos a seguir para
resolver el problema
3. Transformación del
algoritmo en un programa
independientemente del
lenguaje de programación.
4. Ejecución y validación del
programa
5. Mejoras y correcciones al
programa
FUNDAMENTOS DE ALGORITMOS
Algoritmo: Conjunto ordenado y finito de pasos u
operacionesque permite hallar la solución de un
problema. Es un método formal y sistemático de
representar la descripción de un proceso.
CARACTERÍSTICAS:
–
–
–
Definido: debe indicar el orden de la realización de cada paso y
no debe tener ambigüedad
Preciso: Si se sigue dos veces o más se obtendrá e el mismo
resultado cada vez
Finito: Debe terminar en algún momento. Tiene un número
determinado de pasos...
Regístrate para leer el documento completo.