Algoritmos Computacionales

Algoritmos

En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo

(del griego y latín, dixit algorithmus y este a su vez del matemático persa Al-Juarismi) es un
conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite
llevar a cabo una actividad mediante pasos sucesivos que no generen dudas a quien deba
hacer dicha actividad.2 Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se
llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la
algoritmia.

En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas. Algunos

ejemplos son los manuales de usuario, que muestran algoritmos para usar un aparato, o las
instrucciones que recibe un trabajador de su patrón. Algunos ejemplos en matemática son el
algoritmo de multiplicación, para calcular el producto, el algoritmo de la división para calcular
el cociente de dos números, el algoritmo de Euclides para obtener el máximo común divisor
de dos enteros positivos, o el método de Gauss para resolver un sistema de ecuaciones
lineales.

En términos de programación, un algoritmo es una secuencia de pasos lógicos que permiten

solucionar un problema.

Tipos de algoitmos

Según el sistema de signos con el que describen los pasos a seguir, se reconocen:

 Algoritmos cualitativos: cuando se hace a través de palabras, es decir, las

instrucciones son verbales. Sucede, por ejemplo, con recetas de cocina.
 Algoritmos cuantitativos: cuando se hace a través de cálculos numéricos. Se puede
hacer un algoritmo, por ejemplo, para obtener la raíz cuadrada de un número.
Según su función, los algoritmos pueden ser:

 Algoritmos de ordenamiento: secuencian los elementos que ingresan a partir de un

cierto orden, en general, según un orden numérico o léxico.
 Algoritmos de búsqueda: al contrario de realizar operaciones o secuenciar elementos,
se dedica a encontrar dentro de una lista que ingresa, uno o varios elementos en
particular que cumplan con el conjunto de condiciones dadas.
 Algoritmos de encaminamiento: deciden de qué modo se deberá transmitir algo que
llega, y cómo seguirá un conjunto de pasos encadenados. Se dividen
fundamentalmente entre adaptativos y estáticos, los primeros con cierta capacidad de
aprendizaje y ajuste a la circunstancia, mientras que los segundos funcionan
mecánicamente, siempre del mismo modo. Es importante decir que los algoritmos de
encaminamiento cuentan con una propia subdivisión, según el camino que se toma
para que la transmisión llegue de manera efectiva (ejemplos de estos tipos son: por el
camino más corto, de manera óptima, basado en el flujo, etc.).

También los algoritmos han sido clasificados según la estrategia que se utiliza para llegar al
resultado. Veamos algunos ejemplos:

 Algoritmos probabilísticos: no se puede estar seguro de la exactitud de la respuesta

que darán. Se agrupan en distintos subtipos, pero con esa premisa: o bien presentan
soluciones aproximadas del problema, o bien presentan soluciones que pueden ser
correctas pero también erróneas.
 Algoritmo cotidiano: es el que se da en la vida común de las personas, no se aplica en
sistemas informáticos ni en nada ajeno al día a día. Muchas de las decisiones que se
toman desde que uno se despierta por la mañana pertenecen a este grupo.
 Algoritmo heurístico: abandona alguno de los objetivos como recurso para terminar
llegando a la solución. En general, son utilizados cuando no existe una solución
mediante las vías tradicionales.
 Algoritmo de escalada: se comienza con una solución insatisfactoria (que no cumple la
entrada y la salida), y se la va modificando aproximándose a lo que se busca. En algún
momento, estaremos cerca de (o llegaremos a) la solución correcta.
 Algoritmo voraz: Con la idea de llegar a una solución óptima definitiva, elige analizar
cada paso como único y elegir la solución óptima para ese paso.
  Algoritmo determinista: es completamente lineal (cada paso tiene un paso sucesor y
un paso predecesor) y por lo tanto predictivo, si se conocen sus entradas y su forma
de proceder. El algoritmo de Euclides, que permite averiguar el máximo común divisor
entre dos números, responde a este tipo. Se distinguen de los no deterministas, donde
el algoritmo tiene un comportamiento en forma de árbol.

Historia de los algoritmos

La palabra algoritmo proviene del nombre del matemático llamado Abu Abdullah Muhammad
bin Musa al-Khwarizmi que vivió entre los siglos VIII y IX. Su trabajo consistió en simplificar
las matemáticas a un nivel lo suficientemente bajo para que pudiera ser comprendido por un
amplio público. Y Aunque no haya sido él el inventor del primer algoritmo, merece que este
concepto esté asociado a su nombre. Al-Khorezmi fue sin duda el primer pensador algorítmico
pues explicó que, mediante una especificación clara y concisa de cómo calcular
sistemáticamente, se podrían definir algoritmos que fueran usados en dispositivos mecánicos
similares a un ábaco en vez de las manos. Ya en el siglo XIX, se produjo el primer algoritmo
escrito para un computador. La autora fue Ada Byron, en cuyos escritos se detallaban la
máquina analítica en 1842. Por ello que es considerada por muchos como la primera
programadora aunque, desde Charles Babbage, nadie completó su máquina, por lo que el
algoritmo nunca se implementó. Entonces podemos decir que estos bienes surgieron a
mediados del siglo IX por el matemático distinguido y astrónomo Mohammed Ibn Musa -
aljarizm: pero podemos ver que Al_yebr-mugabata es otro que desarrolló fórmulas para
posibilitar que con un número limitado de procesos fuese posible resolver ecuaciones de
primer y segundo grado.

Lenguajes algorítmicos

Es una serie de símbolos y reglas que se utilizan para describir de manera explícita un
proceso.

 Gráficos: Es la representación gráfica de las operaciones que realiza un algoritmo

(diagrama de flujo).
 No Gráficos: Representa en forma descriptiva las operaciones que debe realizar un
algoritmo (pseudocódigo).
Diagrama de flujo

Los diagramas de flujo son descripciones gráficas de algoritmos; usan símbolos conectados
con flechas para indicar la secuencia de instrucciones y están regidos por ISO.

Los diagramas de flujo son usados para representar algoritmos pequeños, ya que abarcan
mucho espacio y su construcción es laboriosa. Por su facilidad de lectura son usados como
introducción a los algoritmos, descripción de un lenguaje y descripción de procesos a
personas ajenas a la computación.

Pseudocódigo

El pseudocódigo (falso lenguaje, el prefijo pseudo significa falso) es una descripción de alto
nivel de un algoritmo que emplea una mezcla de lenguaje natural con algunas convenciones
sintácticas propias de lenguajes de programación, como asignaciones, ciclos y condicionales,
aunque no está regido por ningún estándar. Es utilizado para describir algoritmos en libros y
publicaciones científicas, y como producto intermedio durante el desarrollo de un algoritmo,
como los diagramas de flujo, aunque presentan una ventaja importante sobre estos, y es que
los algoritmos descritos en pseudocódigo requieren menos espacio para representar
instrucciones complejas.

El pseudocódigo está pensado para facilitar a las personas el entendimiento de un algoritmo, y

por lo tanto puede omitir detalles irrelevantes que son necesarios en una implementación.
Programadores diferentes suelen utilizar convenciones distintas, que pueden estar basadas en
la sintaxis de lenguajes de programación concretos. Sin embargo, el pseudocódigo, en general,
es comprensible sin necesidad de conocer o utilizar un entorno de programación específico, y
es a la vez suficientemente estructurado para que su implementación se pueda hacer
directamente a partir de él.

Así el pseudocódigo cumple con las funciones antes mencionadas para representar algo
abstracto los protocolos son los lenguajes para la programación. Busque fuentes más precisas
para tener mayor comprensión del tema.
Diagrama N-S

En programación de computadores un diagrama Nassi-Shneiderman (o NSD por sus siglas en

inglés), también conocido como diagrama de Chapin es una representación gráfica que
muestra el diseño de un programa estructurado.

Fue desarrollado en 1972 por Isaac Nassi y Ben Shneiderman. Este diagrama también es
conocido como estructograma, ya que sirve para representar la estructura de los programas.
Combina la descripción textual del pseudocódigo con la representación gráfica del diagrama
de flujo.

Basado en un diseño top-down (de

lo complejo a lo simple), el problema
que se debe resolver se divide en
subproblemas cada vez más
pequeños - y simples - hasta que
solo queden instrucciones simples y
construcciones para el control de flujo. El diagrama Nassi-Shneiderman refleja la
descomposición del problema en una forma simple usando cajas anidadas para representar
cada uno de los subproblemas. Para mantener una consistencia con los fundamentos de la
programación estructurada, los diagramas Nassi-Shneiderman no tienen representación para
las instrucciones GOTO.

Los diagramas Nassi-Shneiderman se utilizan muy raramente en las tareas de programación

formal. Su nivel de abstracción es muy cercano al código de la programación estructurada y
ciertas modificaciones requieren que se redibuje todo el diagrama. .4

Los diagramas Nassi-Shneiderman son (la mayoría de las veces) isomórficos con los
diagramas de flujo. Todo lo que se puede representar con un diagrama Nassi-Shneiderman se
puede representar con un diagrama de flujo. Las únicas excepciones se dan en las
instrucciones GOTO, break y continue.
Estructura de datos

Variables

En programación, una variable está formada por un espacio en el sistema de almacenaje

(memoria principal de un ordenador) y un nombre simbólico (un identificador) que está
asociado a dicho espacio. Ese espacio contiene una cantidad de información conocida o
desconocida, es decir un valor. El nombre de la variable es la forma usual de referirse al valor
almacenado: esta separación entre nombre y contenido permite que el nombre sea usado
independientemente de la información exacta que representa. El identificador, en el código
fuente de la computadora puede estar ligado a un valor durante el tiempo de ejecución y el
valor de la variable puede por lo tanto cambiar durante el curso de la ejecución del programa.
El concepto de variables en computación puede no corresponder directamente al concepto de
variables en matemática. El valor de una variable en computación no es necesariamente parte
de una ecuación o fórmula como en matemáticas. En computación una variable puede ser
utilizada en un proceso repetitivo: puede asignársele un valor en un sitio, ser luego utilizada
en otro, más adelante reasignársele un nuevo valor para más tarde utilizarla de la misma
manera. Procedimientos de este tipo son conocidos con el nombre de iteración. En
programación de computadoras, a las variables, frecuentemente se le asignan nombres largos
para hacerlos relativamente descriptivas para su uso, mientras que las variables en
matemáticas a menudo tienen nombres escuetos, formados por uno o dos caracteres para
hacer breve en su transcripción y manipulación.

Constantes

En programación, una constante es un valor que no puede ser alterado/modificado durante la

ejecución de un programa, únicamente puede ser leído.

Una constante corresponde a una longitud fija de un área reservada en la memoria principal
del ordenador, donde el programa almacena valores fijos.

Por ejemplo:

El valor de PI = 3.1416
Por conveniencia, el nombre de las constantes suele escribirse en mayúsculas en la mayoría
de lenguajes.

Archivos

Registros

En informática, o concretamente en el contexto de una base de datos relacional, un registro

(también llamado fila o tupla) representa un objeto único de datos implícitamente
estructurados en una tabla. En términos simples, una tabla de una base de datos puede
imaginarse formada de filas y columnas o campos. Cada fila de una tabla representa un
conjunto de datos relacionados, y todas las filas de la misma tabla tienen la misma estructura.

Un registro es un conjunto de campos que contienen los datos que pertenecen a una misma
repetición de entidad. Se le asigna automáticamente un número consecutivo (número de
registro) que en ocasiones es usado como índice aunque lo normal y práctico es asignarle a
cada registro un campo clave para su búsqueda.

Campos

El término campo es incorrectamente intercambiado con el de columna, el término correcto a

usar es el de Columna

Ejemplo de tabla:

 Nombre (texto)
 Dirección 1 (texto)
 Dirección 2 (texto)
 Separada de ciudades, de la que cualquier información del estado o del país puede ser
tomada)
 Código postal (texto)
 Industria (identificador entero, Proviene de una tabla separada de industrias)
 etc.

Cada fila proporcionaría un valor de los datos para cada columna y después sería entendida
como solo simple valor de datos estructurado, en este caso representando a una compañía.
Más formalmente, cada fila puede ser interpretada como una variable relacional, compuesta
por un conjunto de tuplas, con cada tupla consistiendo en los dos elementos: el nombre de la
columna relevante y el valor que esta fila proporciona para esa columna.

Base de datos

Tablas

Se refiere al tipo de modelado de datos, donde se guardan los datos recogidos por un
programa. Su estructura general se asemeja a la vista general de un programa de hoja de
cálculo.

Una tabla es utilizada para organizar y presentar información. Las tablas se componen de filas
y columnas de celdas que se pueden rellenar con textos y gráficos.

Técnica de diseño de algoritmos

En ciencias de la computación, el diseño de algoritmos es un método específico para poder
crear un modelo matemático ajustado a un problema específico para resolverlo. El diseño de
algoritmos o algorítmica es un área central de las ciencias de la computación, también muy
importante para la investigación de operaciones (también conocida como investigación
operativa), en ingeniería del software y en otras disciplinas afines.

Existen varias técnicas de diseño de algoritmos que permiten desarrollar la solución al

problema planteado, algunas de ellas son:

 Algoritmos voraces (greedy): seleccionan los elementos más prometedores del

conjunto de candidatos hasta encontrar una solución. En la mayoría de los casos la
solución no es óptima.
 Algoritmos paralelos: permiten la división de un problema en subproblemas de forma
que se puedan ejecutar de forma simultánea en varios procesadores.
 Algoritmos probabilísticos: algunos de los pasos de este tipo de algoritmos están en
función de valores pseudoaleatorios
  Algoritmos determinísticos: El comportamiento del algoritmo es lineal: cada paso del
algoritmo tiene únicamente un paso sucesor y otro antecesor.
 Algoritmos no determinísticos: El comportamiento del algoritmo tiene forma de árbol
y a cada paso del algoritmo puede bifurcarse a cualquier número de pasos
inmediatamente posteriores, además todas las ramas se ejecutan simultáneamente.
 Divide y vencerás: dividen el problema en subconjuntos disjuntos obteniendo una
solución de cada uno de ellos para después unirlas, logrando así la solución al
problema completo.
 Metaheurísticas: encuentran soluciones aproximadas (no óptimas) a problemas
basándose en un conocimiento anterior (a veces llamado experiencia) de los mismos.
 Programación dinámica: intenta resolver problemas disminuyendo su coste
computacional aumentando el coste espacial.
 Ramificación y acotación: se basa en la construcción de las soluciones al problema
mediante un árbol implícito que se recorre de forma controlada encontrando las
mejores soluciones.
 Vuelta Atrás (Backtracking): se construye el espacio de soluciones del problema en un
árbol que se examina completamente, almacenando las soluciones menos costosas.

Algoritmo voraz

Un algoritmo voraz (también conocido como ávido, devorador o greedy) es aquel que, para
resolver un determinado problema, sigue una heurística consistente en elegir la opción
óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este
esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su
funcionamiento. Normalmente se aplica a los problemas de optimización.

Elementos de los que consta la técnica

 El conjunto C de candidatos, entradas del problema.

 Función solución. Comprueba, en cada paso, si el subconjunto actual de candidatos
elegidos forma una solución (no importa si es óptima o no lo es).
 Función de selección. Informa cuál es el elemento más prometedor para completar la
solución. Éste no puede haber sido escogido con anterioridad. Cada elemento es
considerado una sola vez. Luego, puede ser rechazado o aceptado y pertenecerá a C /S.
  Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una
solución. Lo aplicaremos al conjunto de seleccionados unido con el elemento más
prometedor.
 Función objetivo. Es aquella que queremos maximizar o minimizar, el núcleo del
problema.

Ejemplos de algoritmos voraces

 Algoritmo de Kruskal
 Algoritmo de Prim
 Algoritmo de Dijkstra
 Algoritmo de triangulación voraz
 Algoritmo para la ubicación óptima

Algoritmo paralelo

En las ciencias de la computación, un algoritmo paralelo, en oposición a los algoritmos

clásicos o algoritmos secuenciales, es un algoritmo que puede ser ejecutado por partes en el
mismo instante de tiempo por varias unidades de procesamiento, para finalmente unir todas
las partes y obtener el resultado correcto.

Algunos algoritmos son fácilmente divisibles en partes; como por ejemplo, un algoritmo que
calcule todos los números primos entre 1 y 100, donde se podría dividir los números
originales en subconjuntos y calcular los primos para cada uno de los subconjuntos de los
números originales; al final, uniríamos todos los resultados y tendríamos la solución final del
algoritmo. Otro ejemplo, puede ser el cálculo de Pi en paralelo.

Por el contrario, a veces los problemas no son tan fácilmente paralelizables, de ahí que estos
problemas se conozcan como problemas inherentemente secuenciales. Como ejemplo de estos
métodos tendríamos los métodos numéricos iterativos como el método de Newton o el
problema de los tres cuerpos. Por otro lado, algunos problemas son difícilmente
paralelizables, aunque tengan una estructura recursiva. Como ejemplo de esto último
tendríamos la búsqueda primero en profundidad en un grafo.
Los algoritmos paralelos son importantes porque es más rápido tratar grandes tareas de
computación mediante la paralelización que mediante técnicas secuenciales. Esta es la forma
en que se trabaja en el desarrollo de los procesadores modernos, ya que es más difícil
incrementar la capacidad de procesamiento con un único procesador que aumentar su
capacidad de cómputo mediante la inclusión de unidades en paralelo, logrando así la
ejecución de varios flujos de instrucciones dentro del procesador. Pero hay que ser cauto con
la excesiva paralelización de los algoritmos ya que cada algoritmo paralelo tiene una parte
secuencial y debido a esto, los algoritmos paralelos puedes llegar a un punto de saturación
(ver Ley de Amdahl). Por todo esto, a partir de cierto nivel de paralelismo, añadir más
unidades de procesamiento puede sólo incrementar el coste y la disipación de calor.

El coste o complejidad de los algoritmos secuenciales se estima en términos del espacio

(memoria) y tiempo (ciclos de procesador) que requiera. Los algoritmos paralelos también
necesitan optimizar la comunicación entre diferentes unidades de procesamiento. Esto se
consigue mediante la aplicación de dos paradigmas de programación y diseño de
procesadores distintos: memoria compartida o paso de mensajes.

La técnica memoria compartida necesita del uso de cerrojos en los datos para impedir que se
modifique simultáneamente por dos procesadores, por lo que se produce un coste extra en
ciclos de CPU desperdiciados y ciclos de bus. También obliga a serializar alguna parte del
algoritmo.

La técnica paso de mensajes usa canales y mensajes pero esta comunicación añade un coste al
bus, memoria adicional para las colas y los mensajes y latencia en el mensaje. Los diseñadores
de procesadores paralelos usan buses especiales para que el coste de la comunicación sea
pequeño pero siendo el algoritmo paralelo el que decide el volumen del tráfico.

Finalmente, una subclase de los algoritmos paralelos, los algoritmos distribuidos son
algoritmos diseñados para trabajar en entornos tipo clusters y de computación distribuida,
donde se usan otras técnicas, fuera del alcance de los algoritmos paralelos clásicos.
Algoritmo probabilista

Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma

de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al
problema planteado para cualquier distribución de los datos de entrada. Es decir, al contrario
que un algoritmo determinista, a partir de unos mismos datos se puede obtener distintas
soluciones y, en algunos casos, soluciones erróneas.

Existen varios tipos de algoritmos probabilísticos dependiendo de su funcionamiento,

pudiéndose distinguir:

 Algoritmos numéricos, que proporcionan una solución aproximada del problema.

 Algoritmos de Montecarlo, que pueden dar la respuesta correcta o respuesta erróneas
(con probabilidad baja).
 Algoritmos de Las Vegas, que nunca dan una respuesta incorrecta: o bien no
encuentran la respuesta correcta e informan del fallo.

Algoritmo determinista

En ciencias de la computación, un algoritmo determinista es un algoritmo que, en términos

informales, es completamente predictivo si se conocen sus entradas. Dicho de otra forma, si se
conocen las entradas del algoritmo siempre producirá la misma salida, y la máquina interna
pasará por la misma secuencia de estados. Este tipo de algoritmos ha sido el más estudiado
durante la historia y por lo tanto resulta ser el tipo más familiar de los algoritmos, así como el
más práctico ya que puede ejecutarse en las máquinas eficientemente.

Un modelo simple de algoritmo determinista es la función matemática, pues esta extrae

siempre la misma salida para una entrada dada. No obstante un algoritmo describe
explícitamente cómo la salida se obtiene de la entrada, mientras que las funciones definen
implícitamente su salida.

Definición formal

Formalmente los algoritmos deterministas se pueden definir en términos de una máquina de

estado; un «estado» describe qué está haciendo la máquina en un instante particular de
tiempo. Justo cuando se produce la entrada, la máquina comienza en su «estado inicial» y,
posteriormente, si la máquina es determinista, comenzará la ejecución de la secuencia de
estados predeterminados. Una máquina puede ser determinista y no tener límite temporal
para la ejecución o quedarse en un bucle de estados cíclicos eternamente.

Ejemplos de máquinas abstractas deterministas son las máquinas de Turing deterministas y

los autómatas finitos deterministas.

Algoritmo no determinista

En ciencias de la computación, un algoritmo no determinista es un algoritmo que con la

misma entrada ofrece muchos posible resultado, y por tanto no ofrece una solución única. No
se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no
determinista.

Uso

En la teoría estándar de la computación la definición de algoritmo deja en claro que de por sí

un algoritmo es determinista.

Sin embargo, los algoritmos no deterministas emplean modelos de computación tales como la
Máquina de Turing probabilística, que no son deterministas. Se considera entonces que los
algoritmos no deterministas son un caso especial.

Metaheurística

Una metaheurística es un método heurístico para resolver un tipo de problema computacional

general, usando los parámetros dados por el usuario sobre unos procedimientos genéricos y
abstractos de una manera que se espera eficiente. Normalmente, estos procedimientos son
heurísticos. El nombre combina el prefijo griego "meta" ("más allá", aquí con el sentido de
"nivel superior") y "heurístico" (de ευρισκειν, heuriskein, "encontrar").

Las metaheurísticas generalmente se aplican a problemas que no tienen un algoritmo o

heurística específica que dé una solución satisfactoria; o bien cuando no es posible
implementar ese método óptimo. La mayoría de las metaheurísticas tienen como objetivo los
problemas de optimización combinatoria, pero por supuesto, se pueden aplicar a cualquier
problema que se pueda reformular en términos heurísticos, por ejemplo en resolución de
ecuaciones booleanas.

Las metaheurísticas no son la panacea y suelen ser menos eficientes que las heurísticas
específicas, en varios órdenes de magnitud, en problemas que aceptan este tipo de heurísticas
puras.

Programación dinámica

En informática, la programación dinámica es un método para reducir el tiempo de ejecución

de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras
óptimas, como se describe a continuación.

El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para
optimizar problemas complejos que pueden ser discretizados y secuencializados.

Ramificación y poda

El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y

Acotación) es una variante del Backtracking mejorado sustancialmente. El término (del inglés,
Branch and Bound) se aplica mayoritariamente para resolver cuestiones o problemas de
optimización.

La técnica de Ramificación y poda se suele interpretar como un árbol de soluciones, donde

cada rama nos lleva a una posible solución posterior a la actual. La característica de esta
técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se
encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para
«podar» esa rama del árbol y no continuar malgastando recursos y procesos en casos que se
alejan de la solución óptima.

Vuelta atrás

Vuelta atrás (Backtracking) es una estrategia para encontrar soluciones a problemas que
satisfacen restricciones. El término "backtrack" fue acuñado por primera vez por el
matemático estadounidense D. H. Lehmer en la década de 1950.
Diseño e implementación

Esencialmente, la idea es encontrar la mejor combinación posible en un momento

determinado, por eso, se dice que este tipo de algoritmo es una búsqueda en profundidad.
Durante la búsqueda, si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta
el paso anterior y toma la siguiente alternativa. Cuando se han terminado las posibilidades, se
vuelve a la elección anterior y se toma la siguiente opción (hijo [si nos referimos a un árbol]).
Si no hay más alternativas la búsqueda falla. De esta manera, se crea un árbol implícito, en el
que cada nodo es un estado de la solución (solución parcial en el caso de nodos interiores o
solución total en el caso de los nodos hoja).

Normalmente, se suele implementar este tipo de algoritmos como un procedimiento

recursivo. Así, en cada llamada al procedimiento se toma una variable y se le asignan todos los
valores posibles, llamando a su vez al procedimiento para cada uno de los nuevos estados. La
diferencia con la búsqueda en profundidad es que se suelen diseñar funciones de cota, de
forma que no se generen algunos estados si no van a conducir a ninguna solución, o a una
solución peor de la que ya se tiene. De esta forma se ahorra espacio en memoria y tiempo de
ejecución.

Algoritmos heurísticos

Abandona alguno de los objetivos como recurso para terminar llegando a la solución. En
general, son utilizados cuando no existe una solución mediante las vías tradicionales.

A menudo, pueden encontrarse instancias concretas del problema donde la heurística

producirá resultados muy malos o se ejecutará muy lentamente. Aun así, estas instancias
concretas pueden ser ignoradas porque no deberían ocurrir nunca en la práctica por ser de
origen teórico. Por tanto, el uso de heurísticas es muy común en el mundo real.
Verificación y derivación de programas

Conceptos básicos

En el software, la verificación formal de programas, consiste en justificar que un programa

cumpla una especificación formal de su comportamiento. Esta verificación formal incluye la
verificación deductiva, la interpretación abstracta, la demostración automática de teoremas,
etc. La característica principal es que la verificación se escribe de manera dependiente al tipo
de programación, es decir, las propias funciones incluyen sus especificaciones y el mismo
código establece la corrección frente a esas especificaciones. Incluso, el propio lenguaje
admite la verificación deductiva.

Otro enfoque complementario es la llamada derivación del programa, en la que un código

eficiente se deriva, gracias a una serie de pasos de corrección, a partir de especificaciones
funcionales.

Algunas características de las técnicas usadas en la verificación de programas son:

Las mismas propiedades, se pueden deducir lógicamente de la semántica.

También es posible obtener un único resultado a partir de todo el espacio de posibilidades,

por ejemplo, buscar la solución únicamente en los números enteros y hasta un cierto número.

Y por último, estas técnicas tienen la característica de ser tanto decibles, es decir, sus
algoritmos están implementados para poner fin a una respuesta, como indecidibles (que
nunca podrán terminar).

Semántica axiomática

Semántica axiomática es un enfoque basado en la lógica matemática para demostrar la

correctitud de un algoritmo. Está estrechamente relacionado con la lógica de Hoare.

La semántica axiomática define el significado de un comando dentro de un programa,

mediante la descripción de su efecto sobre las aserciones acerca del estado del programa.

El primer aporte significativo en esta aproximación, fue realizado por Hoare y Wirth en 1980.
Más precisamente para proveer la semántica del lenguaje Pascal.
Diseño interactivo

El diseño interactivo es el arreglo de gráficos, texto, videos, fotos, ilustraciones, sonidos,

animación, imágenes tridimensionales (3D), realidad virtual y otros medios en un documento
interactivo. Un documento interactivo puede ser una página web con texto y enlaces a otras
páginas web, o una aplicación autónoma más compleja que use tipografía, gráficos, sonido y
video con controles interactivos como pueden ser botones, enlaces, etc. Ya sean simple o
complejos, los mejores diseños interactivos, presentan el mensaje de manera clara y tienen
una interfaz fácil de navegar, y que funciona adecuadamente con la tecnología que utilice el
usuario para desplegar el documento interactivo.

El diseño interactivo es un conjunto de disciplinas que engloba términos como el diseño de

software, de interfaz de usuario, diseño centrado en el usuario, diseño de productos, diseño
web, etc. Según Terry Winograd e Yvone Rogers, se refiere al diseño de espacios interactivos
para apoyar la forma en que la gente se comunica e interactúa con su vida y quehacer diario.
Es fundamental para todas las disciplinas, campos y afines preocupados por investigar y
diseñar sistemas basados en computadora para el ser humano.

El diseño interactivo es una derivación histórica de la multimedia interactiva con la diferencia

de que ‘Multimedia Interactiva’ es un término que históricamente se relaciona con medios
obsoletos como el CD-ROM y tiene connotaciones caducas, el término Diseño Interactivo por
otro lado tiene una connotación más contemporánea y sus plataformas son tan variadas como
lo pueden ser la Web, los teléfonos inteligentes (como el iPhone), las tabletas (como el iPad),
etc.

El diseñador interactivo diseña para Medios Interactivos a diferencia del diseñador de

Interacción que diseña los comportamientos de los puntos de contacto del usuario con los
productos que no necesariamente son digitales, Diseño Interactivo es una derivación del
Diseño Gráfico y el Diseño de Interacción es una derivación del Diseño Industrial. A diferencia
del Diseño de Interacción, el Diseño Interactivo se centra en el ‘cómo’ y el ‘qué’ mientras el
primero se centra en el ‘porqué’.

Diseño Interactivo es un área de estudio enfocada a comprender como nos relacionamos con
la tecnología y como desarrollamos nuevas metodologías de diseño para crear productos y
servicios que combinan estética, cultura, tecnología y las humanidades.
El diseño interactivo o ID, por sus siglas en inglés, Interaction Design, se encuentra expuesto
en todo y forma parte de la vida de cualquier persona. Las disciplinas y campos
interdisciplinarios que contribuyen con el diseño interactivo y que se mencionan en el libro
Interaction Design. Beyond Human-Computer Interaction, son la psicología, las ciencias
sociales, las ciencias computacionales, la informática, la interacción humano-computadora, la
ingeniería cognitiva, el trabajo cooperativo y soportado por computadora, los sistemas de
información, etc. Las disciplinas y los campos interdisciplinarios anteriormente mencionados
sobresalen en la vida de cada persona, por lo que el diseño interactivo se encuentra implícito a
nuestro alrededor.

El diseñador interactivo diseña fundamentalmente para la pantalla y en sus raíces está el

Diseño Gráfico pero centrado en la interactividad. Así pues el Diseño Interactivo utiliza
herramientas como pueden ser HTML, CSS, Javascript, Actionscript, PHP, Content
Management Systems (CMS=Sistemas manejadores de contenidos), programas de edición de
imágenes de pixel como Photoshop, editores de HTML tipo WYSIWYG como Dreamweaver, y
en menor medida otros programas como Flash, Illustrator, InDesign, etc. Para crear proyectos
completos y funcionales, siendo el Diseño y la Programación habilidades fundamentales del
diseñador interactivo, a diferencia del Diseño de Interacción que su fin último es diseñar las
interacciones para la pantalla en prototipos en papel.

Formas utilizadas en los diagramas de flujo

Forma Nombre Utilidad

Inicio/Final El símbolo de terminación
marca el punto inicial o final
del sistema. Por lo general
contiene la palabra “inicio” o
“fin”
Entrada Representa el material o la
información que entra o sale
del sistema, como una orden
 del cliente (entrada) o un
producto (salida).
Acción o proceso Representa un paso dentro
del proceso

Documento impreso Representa un documento o

informe impreso

Multidoumento Representa un
multidocumento en proceso

Decisión o ramificación Representa una decisión en

el proceso.

Entrada manual Representa un paso en el

que se le pide al usuario que
introduzca la información
manualmente
Preparación Representa un ajuste a otro
paso en el proceso

Conector Significa que el flujo

continúa donde se ha
colocado un símbolo
idéntico (que contiene la
misma letra)