Mecanica

Fundamentos
¿Qué son las estructuras de datos?
Son maneras de organizar los datos para realizar operaciones sobre ellos (e.g. inserción, búsqueda y ordenación) de forma eficiente.
¿Qué es un algoritmo?
Puede ser visto como un récipe, método o procedimiento. Específicamente, es un conjunto de reglas finitas que establecen una secuencia de operaciones destinadas a resolver un problemaen particular.
Un algoritmo de tener las siguientes características:
* Debe ser finito: debe terminar luego de un número de pasos.
* Debe estar definido con precisión: cada paso de un algoritmo debe ser especificado claramente (para ello se definen lenguajes formales de programación).
* Puede tener 0 o más entradas de datos.
* Puede tener 0 o más salidas de datos.
*Debe ser efectivo:generalmente se espera que sea capaz de resolver el problema para el cual fue diseñado.
Nótese que los algoritmos son independientes de la implementación y del lenguaje de programación.
Análisis de algoritmos
Que un algoritmo sea finito no es suficiente en la práctica. Un algoritmo útil requiere no sólo un número finito de pasos, sino un número razonable de pasos (esdecir, que termine en un tiempo razonable).
Típicamente decimos que un algoritmo es bueno si es rápido. Con frecuencia nos encontramos con algoritmos que resuelven el mismo problema y debemos decidir cuál es el mejor o más apropiado; esto nos lleva al campo de Análisis de Algoritmos.
El análisis de algoritmos típicamente se concentra en estimar el tiempo de ejecución éstos. Analizar unalgoritmo antes de su codificación nos permite decidir si una solución particular es factible.
Entre los aspectos matémáticos requeridos con frecuencia en el análisis de algoritmos están:
1. Exponentes y logaritmos.
2. Series.
3. Aritmética modular.
4. Teoría de conjuntos.
5. Teoría combinatoria.
6. Análisis asíntótico (será tratado en el curso).
7. Análisisprobabilístico.
8. Pruebas matemáticas (inducción, contradicción y contra ejemplo).
Ejemplo de un algoritmo: Algoritmo de Euclides
Definición del problema: Se desea encontrar el máximo común divisor de 2 números enteros positivos ( y ). Es decir, el mayor entero positivo que divide a ambos.

El algoritmo de Euclides se basa en el siguiente hecho:si
.


Este hecho se verifica de la siguiente manera:


Sea
,
,
,
y ,


entonces
. En consecuencia, divide ay es el máximo común divisor de . Nótese que de no serlo,


entraría en contradicción con el supuesto de que
.
Si se procede de forma tal que y se sustituyen las variables de forma tal que siempre , llegará el momento en que y en ese momento
A continuación se presenta una implementación en Java de este algoritmo:/**
* Implementación básica del algoritmo de Euclides para determinar
* el máximo comun divisor de dos enteros positivos.
* @param u entero positivo.
* @param v entero positivo.
* @return el máximo comun divisor de <code>u</code> y <code>u</code>.* @throws IllegalArgumentException cuando alguno de los enteros
* no son positivos.
*/
public static int mcdSimple(int u, int v){
if ((u <= 0) || (v <= 0)){
throw new IllegalArgumentException("Los argumentos deben ser +...