Algoritmia
Páginas: 42 (10340 palabras)
Publicado: 14 de marzo de 2011
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...
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...
Leer documento completo
Regístrate para leer el documento completo.