Algoritmia

Solo disponible en BuenasTareas
  • Páginas : 42 (10340 palabras )
  • Descarga(s) : 0
  • Publicado : 14 de marzo de 2011
Leer documento completo
Vista previa del texto
Algoritmos

Recursividad

Buscar y ordenar

Complejidad Computacional

Algoritmos y tecnolog´ ıa

´ FUNDAMENTOS DE COMPUTACION
Universidad de Cantabria
Depto. Matem´tica Aplicada y Ciencias de la Computaci´n a o

Algor´ ıtmica
Torrelavega 2011

Universidad de Cantabria ( c J. Guti´rrez ) e

´ FUNDAMENTOS DE COMPUTACION

Algor´ ıtmica Torrelavega 2011

1 / 62

AlgoritmosConcepto y representaci´n o

Recursividad

Buscar y ordenar

Complejidad Computacional

Algoritmos y tecnolog´ ıa

Un Algoritmo es una secuencia finita de instrucciones ordenadas y bien definidas. Por lo general utilizan un conjunto de datos de entrada y proporcionan unos datos de salida. Un algoritmo es una herramienta para resolver un problema computacional.
La palabra algoritmo tieneorigen en el nombre Abu Ja‘far Mohammed ibn Mˆsˆ Al-Khowˆrizm, u a a matem´tico persa del siglo IX, aunque el concepto es muy anterior. Euclides propuso en su a famoso tratado Elementos un m´todo genial para el c´lculo del m´ximo com´n divisor de e a a u dos n´meros. Tambi´n Gauss dise˜o varios e importantes algoritmos en su libro Disquisitiones u e n Arithmeticae, por ejemplo la Transformadar´pida de Fourier. Circunstancia por la que algunos a autores le consideran el primer inform´tico. a

¿ C´mo encontrar el n´mero mayor de una sucesi´n finita de n´meros ? o u o u Se trata de dise˜ar un algoritmo para resolver el siguiente problema: n
Encontrar el n´mero m´s grande u a

Entrada: Una sucesi´n de n n´meros L = [a1 , a2 , . . . , an ]. o u Salida: El n´mero m de la sucesi´n L tal quetodos los elementos ai no son u o m´s grandes que m, es decir, ai ≤ m. a Dada una entrada como L = [2, −5, 22, 6, 0, −10, 2, 22, 3], un algoritmo para resolverlo deber´ devolver el n´mero 22. ıa u
Universidad de Cantabria ( c J. Guti´rrez ) e ´ FUNDAMENTOS DE COMPUTACION Algor´ ıtmica Torrelavega 2011 2 / 62

Algoritmos Concepto y representaci´n o

Recursividad

Buscar y ordenarComplejidad Computacional

Algoritmos y tecnolog´ ıa

Diremos que un algoritmo es correcto si, para cada ”entrada concreta”=(instancia), proporciona una salida correcta. En este caso, diremos que el algoritmo resuelve el problema computacional.
Un algoritmo incorrecto puede no resolver el problema para algunas instancias. Contrario a lo que se puede pensar, los algoritmos incorrectos pueden ser utilesalgunas veces, si el margen ´ de error est´ controlado. Por ejemplo: los algoritmos probabilista (ej. tests de primalidad), y a los algoritmos heur´ ısticos (ej. Travelling Salesman Problem), etc.

Un algoritmo se puede ”detallar” mediante la utilizaci´n de un lenguaje de o programaci´n de alto nivel. Pero hay una torre de Babel de lenguajes de o programaci´n, por eso muchos libros prefierenutilizar: o ´ Pseudocodigo Conjunto de reglas informales para la representaci´n de algoritmos, utilizando o una combinaci´n de instrucciones escritas en un lenguaje natural y de ´rdenes o o de control estructuradas.

Universidad de Cantabria ( c J. Guti´rrez ) e

´ FUNDAMENTOS DE COMPUTACION

Algor´ ıtmica Torrelavega 2011

3 / 62

Algoritmos El n´mero m´s grande u a

RecursividadBuscar y ordenar

Complejidad Computacional

Algoritmos y tecnolog´ ıa

Encontrar el n´mero m´s grande u a

numero mas grande(lista) Hacer n =longitud(lista), i = 2 y m =lista(1) Mientras i < n + 1, Repetir Si lista(i) > m, Hacer m =lista(i) Hacer i = i + 1 Fin

Una implementaci´n del algoritmo en Python: o programa.py def numero_mas_grande(lista): n=len(lista) m=lista[0] i=1 while im:m=lista[i] i=i+1 return m
Universidad de Cantabria ( c J. Guti´rrez ) e ´ FUNDAMENTOS DE COMPUTACION Algor´ ıtmica Torrelavega 2011 4 / 62

Algoritmos Iteraci´n y recursi´n o o

Recursividad

Buscar y ordenar

Complejidad Computacional

Algoritmos y tecnolog´ ıa

El algoritmo anterior propuesto es iterativo pues hemos utilizado ciclos o bucles para indicar la repetici´n de una serie...
tracking img