Definición matemática de algoritmo. Diferencias con el concepto de cálculo.

Formalizar mediante un método de cálculo el algoritmo de búsqueda binaria. La salida debe indicar si el elemento se encontró. En caso afirmativo, indicará la posición del elemento. Comprobar con ejemplos la corrección del método. Usar la definición :

Definir una máquina de Turing que obtenga el and lógico de dos números binarios separados por el símbolo x.

La ordenacion por inserción puede formularse de manera recursiva como : para ordenar el array A[1 .. n] , se ordena recursivamente el array A[1 .. n-1] y después se inserta A[n] ordenadamente.

Diseñar un algoritmo divide y vence que determine si dos árboles son isomorfos. (Dos árboles son isomorfos si ambos son NULL o sus subárboles tienen estructura isomorfa (Izquerda-Izquierda y Derecha-Deracha o bien Izquierda-Derecha y Derecha-Izquierda).

Desarrollar un método de cálculo para un algoritmo que devuelve el mínimo y el máximo de los elementos de una matriz, y las posiciones donde se encuentran.

Especificar una máquina de Turing que actúe sobre una cadena binaria en una cinta, con el bit más significativo a la izquierda, y que escriba un duplicado exacto de la misma a la derecha de la cadena original.

Escribir el pseudocódigo de la ordenación por inserción de un array A[1..n] y desarrollar detalladamente el análisis del número de comparaciones del bucle interno en el peor caso y en el caso medio.

Sea T un vector de n elementos, intercambiar los k primeros elementos del arrayy los n-k últimos sin utilizar un vector auxiliar. Ej :

Verificar la correción parcial de un fragmento de programa que efectúe una búsqueda lineal de un elemento x en un array T[1..n] comenzando el recorrido en la posición n.

Diseñar un algoritmo probabilista para comprobar si dos cadenas de caracteres son iguales. Explicar que tipo de algoritmo es y sus características fundamentales. Analizarlo y compararlo con la versión determinista, y decidir cuál es mejor.

Tenemos un grafo conexo no dirigido y valorado (positivo) G = {V, E}. Llamaremos P a uno cualquiera de sus caminos. Se define PesoMáximo(P) como el máximo de todos los pesos de los arcos de P. Desarrolar, demostrar la correción y analizar el tiempo de ejecución de un algoritmo en tiempo polinomial para el problema : dados dos vértices cualesquiera del grafo G, s y t, encontrar uno de los caminos entre ambos nodos que minimice la función PesoMáximo(P).

Tenemos um editor de textos con una función para transformar una cadena de caracteres fuente en otra destino. Internamente el editor sólo puede realizar :