Source: https://www.scribd.com/doc/85565121/ALGORITMO
Timestamp: 2017-10-22 14:51:51+00:00

Document:
Uploaded by Salvador Perez Zamoran
ALGORITMO: 1.- Es una secuencia de pasos o procesos lógicamente relacionados entre sí a fin de obtener la solución a un problema planteado. 2.
- Es una lista de instrucciones para efectuar paso a paso un proceso. 3.- Conjunto “FINITO” de pasos o instrucciones, seguidas en un orden lógico, los cuales nos llevan a la solución de un problema específico. 4.- Una serie de instrucciones colocadas en cierta secuencia, necesarias para la descripción de las operaciones que llevan a la solución de un problema. 5.- Es un procedimiento completo para resolver un problema específico en un número “FINITO” de pasos. 6.- Es un método para resolver un problema mediante una serie de datos precisos, definidos y finitos. PASOS PARA PLANTEAR LA SOLUCIÓN A UN PROBLEMA: 1.- Análisis del problema. 2.- Identificar las entradas, procesos y salidas del problema, declaración de variables. 3.- Diseño del Algoritmo: Describe la secuencia ordenada de los pasos, sin ambigüedad, es decir, siendo preciso y veraz en la búsqueda de la solución al problema. 4.- Codificación del Algoritmo: Es la expresión en un lenguaje de programación de los pasos definidos en el algoritmo. 5.- Ejecución y validación del programa por el computador. CARACTERÍSTICAS DE ALGORITMOS: Las características fundamentales que debe cumplir todo algoritmo son: 1.- Un algoritmo debe ser preciso e indicar el orden de realización de cada paso. 2.- Un algoritmo debe estar bien definido, es decir, si se sigue la ejecución dos veces del mismo se debe obtener la misma secuencia lógica. El algoritmo debe definirse de forma precisa para cada paso, es decir, hay que evitar toda ambigüedad al definir cada paso. Puesto que el lenguaje humano es impreciso, los algoritmos se expresan mediante un lenguaje formal, ya sea matemático o de programación para un computador. 3.- Un algoritmo debe ser “FINITO”, Si se sigue un algoritmo se debe terminar en algún momento; o sea, debe tener un numero finito de pasos. 4.- Entrada: El algoritmo tendrá cero o más entradas, es decir, cantidades dadas antes de empezar el algoritmo. Estas cantidades pertenecen además a conjuntos especificados de objetos. Por ejemplo, pueden ser cadenas de caracteres, enteros, naturales, fraccionarios, etc. Se trata siempre de cantidades representativas del mundo real expresadas de tal forma que sean aptas para su interpretación por el computador. 5.- Salida: El algoritmo tiene una o más salidas, en relación con las entradas. CLASIFICACIÓN DE LOS ALGORITMOS:
Directos: Son aquellos que permiten encontrar la solución al problema de manera instántanea o directa, en un número determinado de pasos. Ejemplo: 23 = 2*2*2 = 8
 Se ignora el número de pasos.  Son aquellos donde se desconocen el número de pasos para lograr la solución de un problema. Estos a su vez, se clasifican en: Finito: El número de pasos a realizar son conocidos así como la factibilidad de solución al problema planteado, o sea, que va a ver una respuesta al proceso. Ejemplo: Medir distancia AB Es factible que algún día pueda saber la distancia entre la Sede antigua del IUTEPAL (Av. Constitución) y la Sede Nueva del IUTEPAL (Urb. Caña de Azúcar). Infinito: Se desconoce el número de pasos a realizar, así como la imposibilidad de encontrar la solución al problema planteado. Cuando realmente es imposible lograr la solución, por más vueltas que le demos al problema. Ejemplo: 20 ; +" ; -2 3 -" Ejemplos de Algoritmos: Podemos idear un algoritmo para un determinado proceso, así como también hacerlo en diferentes formas. Por ejemplo: Cómo podríamos encontrar el promedio de un conjunto de números?. Una posible solución sería: 1.- Sumar los números dados. 2.- Contar dichos números. 3.- Dividir el resultado obtenido en el punto 1 entre el resultado obtenido en el punto 2. Otra clase de ejemplo de Algoritmos, sería el de una llamada telefónica, o el proceso para efectuar un viaje en el Metro de Caracas, o la obtención de la licencia para conducir o el cambio de un caucho que esté bajo de aire, etc; en fin, hay muchas formas de aplicar los algoritmos en cuestiones cotidianas descomponiendo la acción en pasos lógicos, como es el caso de una llamada desde una cabina de un teléfono público: 1.- Inicio 2.- Descolgar el teléfono 3.- Esperar la señal digital. 4.- Preguntamos si está dañado. Si lo está: Vamos al paso 5. Si no lo está: Vamos al paso 8. 5.- Vociferar una palabra de mal gusto y fruncir el ceño. 6.- Colgar. 7.- Fin. 8.- Digitar los números. 9.- Verificamos si suena ocupado. Si suena ocupado: Vamos al paso 11.
.Preguntamos si se encuentra la persona.Verificamos si contestan.Si no lo está: Vamos al paso 13.. 18.Vociferamos ruidosamente algo. 11.. Si no lo está vamos al punto 4..Pensar algo malo. 3.Levantamos el carro por delante. dos versiones mas amplias del algoritmo anterior: Versión Nº 1 1. 3. 4.1. 6. aflojar tornillos antes de levantar el carro. Si contestan: Vamos al paso 14 Si no contestan: Vamos al paso 21. etc... Presentamos a continuación. junto al caucho dañado. podríamos agregar muchos más detalles como por ejemplo.. 19..-Insistir digitando los números.Verificamos si está dañado el caucho de repuesto. 5.. 12..2.. Si se encuentra: Vamos al paso 14. Nos vamos caminando a buscar ayuda ó telefoneamos alguien para que ayude. 2. 14.Apretar los tornillos. 15.. abrir la maleta. 10.Levantar el carro con el gato hidraúlico.. A los anteriores pasos. 13.Quitar el caucho dañado. 17..Sacar el caucho de repuesto y herramientas de la maletera. .3.Aflojamos los tornillos..Poner el caucho de repuesto. 4..Tomar un café y tranquilizarse.Quitamos la tapa del centro de la rueda delantera..Verificamos si el caucho bajo de aire es el caucho delantero. Vamos al punto 14. Si no se encuentra: Vamos al paso 17. 2.Colgar. 16. presentamos un ejemplo de algoritmo para el proceso de cambiar un caucho que está bajo de aire.Fin. Si lo está vamos al punto 3. 4.. 4. Si lo es: 4..Hablar lo deseado... A continuación.Ir al paso 8. 1.Ir al paso 15.Bajar el carro con el gato.Quitar los tornillos del rin..
8.Fin.4. 4. Versión Nº 2 1... Descripción de un algoritmo en forma gráfica: . 14. 7.1.Vamos al punto 5... 11. 11. 4..Observamos si el caucho de repuesto está vacío..Continuamos manejando. 12.. 3. 9.Verificamos si se han apretado todos los tornillos. Si no lo hemos quitado vamos al punto 4.. 5. 10..Apretamos un tornillo.Observamos si hemos quitado todos los tornillos.Quitamos los tornillos.4..Si lo hemos apretado.... 6. 2. Si no lo está vamos al punto 3.Bajamos el carro con el gato hidraúlico. 7. Si no lo es: 4.Llamamos a un taller..... 10.Quitamos un tornillo. el gato y las herramientas en la maletera.Levantamos el carro con el gato hidráulico..Guardamos el caucho dañado. 9.Colocamos los tornillos y las tapas.3.Levantamos el carro por detrás. 8.Aflojamos los tornillos.Ponemos el caucho de repuesto.Bajamos el carro con el gato hidráulico... Si lo está vamos al punto 2.Fin.Ponemos el caucho de repuesto.Quitamos el caucho dañado. 13..Nos limpiamos con estopa las manos. 4. junto al caucho dañado. Si lo hemos quitado vamos al punto 6. vamos al punto 11.Encendemos el vehículo. Si no lo hemos apretado vamos al punto 8.Quitamos la tapa del centro de la rueda trasera... Vamos al punto 12. 12. 6.Quitamos el caucho dañado... 5.2..
se desayuna y lee el periódico hasta que sean más de las 08:30 am. Algoritmos computacionales Es importante el estudio y conocimiento de lo que hoy conocemos como Algoritmos Computacionales. pensará nuevamente en la falta que le hace el reloj despertador. Es dudoso que quien lea por primera vez lo anterior esté en capacidad de seguir y mantener fielmente en su memoria la cantidad de actividades. Si se despierta entre las 06:30 am y las 07:30 am. después de esta hora se baña. y que no tenga decisiones lógicas ni alternativas a tomar. los lunes o los miércoles se baña. Los demás días de la semana. es decir que sólo implique seguir una serie de pasos. continúa durmiendo. si se despierta después de las 08:30 am realizará las mismas actividades que tendrían lugar si se levantara los lunes o los miércoles después de las 07:30 am. El conjunto de todas las operaciones a realizar y e orden en que se deben efectuarse. es muy fácil describirlo en palabras. La palabra algoritmo se deriva del nombre latinizado del gran Matemático Árabe Mohamed Ibn Al Kow Rizmi. se desayuna y se dedica a leer el periódico hasta que sean más de las 07:30 am. no entra a clase y se dedica a leer las carteleras y a esperar la próxima clase. secuencias. Pero si esta secuencia de actividades se hace más compleja será no sólo difícil describirlo en palabras sino también retener todas las alternativas. Los martes y los jueves. y seguirá siendo. luego toma el bus y llega a la Universidad. El lenguaje algorítmico es aquel por medio al cual se realiza un análisis previo del problema a resolver y encontrar un método que permita resolverlo. Entra a clase solamente si han transcurrido menos de 15 minutos desde su comienzo. . Marco Histórico Un algoritmo es un conjunto de operaciones y procedimientos que deben seguirse para resolver un problema. se baña. que desde su aparición hasta nuestros días es. uno después de otro. pero toma la decisión de no ir a clases en esa mañana. procura dormir hasta las 08:30 am. de otra manera. decisiones y alternativas que tiene el ejemplo. después de esta decisión. vital para el desarrollo de aplicaciones para computadoras y el manejo y dominio de la lógica de programación para resolver problemas. Su respuesta obvia para remediar lo anterior será dibujar un gráfico. se desayuna y se dedica a estudiar. luego realiza las mismas actividades que tienen lugar los lunes o lo miércoles cuando sale de su casa. donde se recogía el sistema de numeración hindú y el concepto del cero. procura levantarse entre las 07:30 am y las 08:30 am. sin embargo. Si llegara a despertarse después de la hora como frecuentemente ocurre. Los lunes y los miércoles. De otra forma se baña. se le denomina algoritmo. analicemos la secuencia de eventos que tienen lugar todas las mañanas para un estudiante de Universidad que tiene clase los lunes y los miércoles a las 08:00 am y los martes y jueves a las 09:00 am. Para ilustrar lo anterior. el que tradujo la obra al latín y el inicio con la palabra: Algoritmi Dicit.Cuando una secuencia de actividades que definen un problema es muy simple en su naturaleza. y aun sin conocer todas las técnicas de los diagramas de flujo será mucho más fácil para una persona seguir las actividades a través de un gráfico. procura levantarse entre las 06:30 am y las 07:30 am. Fue Fibinacci. se desayuna y se dedica a estudiar. Una vez que el estudiante se despierta mira el reloj y si no son aún las 06:30 am. el cual escribió sobre los años 800 y 825 su obra Quitad Al Mugabala.
que describe la secuencia ordenada de pasos que conducen a la solución de un problema dado. titulo uno de sus mas famosos libros. significándonos que solo se puede llegar a realizar un buen programa con el diseño de un algoritmo y una correcta estructura de datos. de modo que sin algoritmo no puede existir un programa. sin embargo.  Expresar el algoritmo como un programa de lenguaje de programación adecuado. Aunque la popularización del término ha llegado con el advenimiento de la era informática.Generalidades El programador de computadoras es ante que nada una persona que resuelve problemas. algoritmo proviene de Mohammed alKhowarizmi. por lo que para llegar a ser un programador eficaz se necesita aprender a resolver problemas de un modo riguroso y sistemático. por ejemplo. ingles o francés. pero cualquiera que sea el lenguaje. El eje central de esta metodología es el concepto. Un lenguaje de programación es tan solo un medio para expresar un algoritmo y una computadora es solo un procesador para ejecutarlo. En la ciencia de la computación y en la programación. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectúe el proceso correspondiente. ya tratado. Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que lo ejecuta. Euclides. multiplicar y dividir números decimales. un aspecto muy importante será el diseño de algoritmos. el algoritmo será siempre el mismo. El profesor Niklaus Wirth. inventor de Pascal. se considera con Al-Khowarizmi el otro gran padre de la algoritmia (ciencia que trata de los algoritmos). los pasos para la elaboración del plato se realizaran sin importar el idioma del cocinero. El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la técnica de la programación. (Fase de codificación. Modula-2 y Oberon. una receta de un plato de cocina se puede expresar en español. los algoritmos son más importantes que los lenguajes de programación o las computadoras. restar.)  Ejecución y validación del programa por la computadora. Algoritmos + Estructuras de Datos = Programas. Proceso y Salida. La resolución de un problema exige el diseño de un algoritmo que resuelva el problema propuesto. la solución de un problema se puede expresar mediante un algoritmo. (Análisis del problema y desarrollo del algoritmo). la traducción al latín del apellido de la palabra algorismus derivo posteriormente en algoritmo. Un algoritmo es un método para resolver un problema. Para llegar a la realización de un programa es necesario el diseño previo de algoritmo. Los pasos para la resolución de un problema son:  Diseño de algoritmo. Así. En esencia. En el algoritmo de receta de cocina citado anteriormente se tendrá: . La definición de un algoritmo debe definir tres partes: Entrada. A la metodología necesaria para resolver problemas mediante programas se denomina Metodología de la Programación. Esta ecuación será de una de las hipótesis fundamentales consideradas en esta obra. el gran matemático griego (del siglo IV antes de Cristo) que invento un método para encontrar el máximo común divisor de dos números. de algoritmo. matemático persa que vivió durante el siglo IX y alcanzo gran reputación por el enunciado de las reglas para sumar. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta. en una analogía con la vida diaria. Dada la importancia del algoritmo en la ciencia de la computación.
En la etapa de diseño se determina como hace el programa la tarea solicitada. El diseño del algoritmo es independiente del lenguaje de programación en el que se vaya a codificar posteriormente. El proceso implica la ejecución de los siguientes pasos hasta que el programa se termina:     Programar módulo. El proceso de romper el problema en cada etapa y expresar cada paso en forma más detallada se denomina refinamiento sucesivo. Esta examina en su banco de datos la ficha del cliente. la resolución de un problema complejo se realiza dividiendo el problema en sub problemas y a continuación dividir estos sub problemas en otros de nivel mas bajo. Comprobar el módulo. Los pasos del algoritmo son:  inicio  leer el pedido  examinar la ficha del cliente  si el cliente es solvente aceptar pedido. Salida: terminación del plato (por ejemplo. en caso contrario rechazara el pedido. comprobados y depurados independientemente (incluso por diferentes programadores) y a continuación combinarlos entre si. Proceso: elaboración de la receta en la cocina. Los programas estructurados de esta forma se dice que tienen un diseño modular y el método de romper el programa en módulos más pequeño se llama Programación Modular. Este método se conoce técnicamente como diseño descendente (Top Down) o modular. El proceso que convierte los resultados del análisis del problema en un diseño modular con refinamiento sucesivo que permitan una posterior traducción al lenguaje se denomina diseño de algoritmo. Cada sub programa es resuelto mediante un modulo (sub programa) que tiene un solo punto de entrada y un solo punto de salida. es decir. depurar el modulo. Los módulos pueden ser planeados. Si es necesario.Entrada: ingrediente y utensilios empleados. cordero). Cualquier programa bien diseñado consta de un programa principal (el modulo de nivel mas alto) que llama a sub programas (módulos de nivel mas bajo) que a su vez pueden llamar a otros sub programas. hasta que pueda ser implementada una solución en la computadora. rechazar pedido  fin Diseño del Algoritmo: En la etapa de análisis del proceso de programación se determina que hace el programa. en caso contrario. Los métodos mas eficaces para el proceso de diseño se basan en el conocido por Divide y Vencerás. Redactar el algoritmo correspondiente. Combinar el modulo con los módulos anteriores. Ejemplo de Algoritmo: Un cliente ejecuta un pedido a una fábrica. . si el cliente es solvente entonces la empresa acepta el pedido. codificados.
conviene conocer otros métodos de diseño de algoritmos que también resultan de utilidad práctica. Muchos problemas pueden resolverse buscando una solución fácil y directa pero. No obstante. El diseño de un algoritmo que resuelva un problema es. Aun así.Es necesario en este momento mencionar algo sobre como hacerlo. pero con un poco de análisis puede encontrarse algoritmos más eficientes. Este método. algunos resultan inmediatos de resolver. Si no nos importa la eficiencia del algoritmo. Una forma de facilitar esta labor consiste en recurrir a técnicas conocidas de diseño de algoritmos. la solución es dinámica. basado en la descomposición de un problema en subproblemas. siendo dicha solución finalmente adaptada al dominio original. hay problemas cuya solución no puede hallarse sino mediante un proceso de búsqueda. puede ser muy directo. llamado de fuerza bruta. se decir. si la decisión en una etapa. y el empleo de tablas como estructura auxiliar para la resolución eficiente de problemas donde se aplica programación dinámica). y a métodos basados en transformaciones del dominio para encontrar una solución mas fácilmente a un problema en un dominio transformado. Todo problema algorítmico es un reto para su diseñador. otros son bastante complejos. Consideraciones generales: Si el hábil programador dispone de un recetario de algoritmos de donde poder seleccionar el más adecuado para cada problema. y a pesar de que resulta mas adecuado en bastantes casos utilizar alguno de estos esquemas que realizar un diseño desde cero. El esquema mas sencillo quizás sea el llamado divide y vencerás. tenemos una solución voraz. Por ultimo. El acto de diseñar un algoritmo puede considerarse como una tarea que difícilmente podrá ser del todo automatizada. completa y consistente del problema a resolver y queremos obtener un algoritmo en el que. Otros esquemas requieren un análisis minucioso del problema de forma que la solución se vaya construyendo en etapas. Se programa un . a la vez bastante ineficiente.5. el uso de parámetros de acumulación al resolver problemas utilizando divide y vencerás. podríamos utilizar un algoritmo general llamado algoritmo del museo británico. La investigación en esta área ha permitido descubrir un conjunto de métodos o esquemas de diseño hacia los cuales puede orientarse la realización de muchos algoritmos. Técnica de diseño de algoritmos Diseño de Algoritmos: Hasta ahora se han realizado algunos comentarios respecto a la necesidad de diseñar algoritmos correctos y eficientes utilizando los elementos de un lenguaje de programación . su uso adecuado mediante el esquema de búsqueda con retroceso (o backtracking) permite ganar gran eficiencia respecto a soluciones de fuerza bruta. Supongamos que disponemos de una especificación precisa. a pesar de lo complejas que son las operaciones de búsqueda. se produzca cierto resultado. Si puede preverse que decisión conviene en cada etapa para producir cierto tipo de mejor resultado. Nos estamos refiriendo a métodos basados en la mejora de la eficiencia (por ejemplo. solo puede tomarse tras considerar varias soluciones de otras etapas mas simples. dados uno datos de entrada valido. en general. idear un algoritmo continua siendo una labor bastante creativa donde los conocimientos y la experiencia del propio diseñador tiene un papel fundamental. su tarea se simplifica. una tarea difícil. a esquemas muy generales que pueden adaptarse a un problema particular al detallar las partes generales del esquema.
El programa es más lento cuanto más crezca N. entre otras que requiere una serie de recursos. Se puede considerar como una gran constante.computador de manera que parta de un conjunto de axioma matemáticos y los que use para reducir aleatoriamente teoremas validos. y quizás el mejor. o un algoritmo muy complejo puede usar estructuras de datos muy simples. Obviamente. existen algoritmos para implementar dichas estructuras. esto es. El conocimiento de técnicas de diseño es solo un primer paso para el diseñador. pues logN no se duplica hasta que N llegue a N2. N. logN : Tiempo de ejecución logarítmico. . con la experiencia.C. sobre todo. puesto que existe un número reducido de esquema y técnicas de diseño. Significa que la mayoría de las instrucciones se ejecutan una vez o muy pocas. La base del logaritmo (en informática la más común es la base 2) cambia la constante. Este método de trabajo es practicable. . El término algoritmo proviene del matemático Muhammad ibn Musa al-Khwarizmi. A menudo los algoritmos requieren una organización bastante compleja de los datos. * Algoritmo no determinista: deben decidir en cada paso de la ejecución entre varias alternativas y agotarlas todas antes de encontrar la solución. De alKhwarizmi se obtuvo la derivación algoritmo. pero es inapreciable. La cantidad de recursos del algoritmo es tratada como una función de N. Todo algoritmo tiene una serie de características. El uso de estructuras de datos adecuadas pueden hacer trivial el diseño de un algoritmo. Dichas estructuras pueden implementarse de diferentes maneras. El mas entendido. · La memoria: la cantidad (la medida varía según la máquina) que necesita el algoritmo para su ejecución. pero no demasiado. la mayoría de los problemas tienen un parámetro de entrada que es el número de datos que hay que tratar. en la actual nación Iraní.Clasificación de algoritmos * Algoritmo determinista: en cada paso del algoritmo se determina de forma única el siguiente paso. Estos recursos son principalmente: · El tiempo: período transcurrido entre el inicio y la finalización del algoritmo. Aprender los principios básicos del diseño de algoritmos podemos preguntarnos por un método aceptable. De esta manera puede establecerse un tiempo de ejecución del algoritmo que suele ser proporcional a una de las siguientes funciones:   1 : Tiempo de ejecución constante. Uno de los algoritmos más antiguos conocidos es el algoritmo de Euclides. y es más. El describió la realización de operaciones elementales en el sistema de numeración decimal. algo que es fundamental considerar a la hora de implementarlos en una máquina. En general. que debe completarse con otros conocimientos y. la capacidad y el diseño de la máquina pueden afectar al diseño del algoritmo. y es por tanto necesario un estudio previo de las estructuras de datos fundamentales. es organizar el diseño sobre un esquema de algoritmo o una técnica de diseño que haya demostrado su utilidad para otros problemas. que vivió aproximadamente entre los años 780 y 850 d.
ignora si se hace una mejor o peor implementación del algoritmo. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. En este caso se diría que el algoritmo es del orden de N2. En general son infactibles salvo un tamaño de entrada muy reducido. Si N se duplica. * Algoritmos polinomiales: aquellos que son proporcionales a Nk. N·logN : El tiempo de ejecución es N·logN. el tiempo de ejecución es proporcional. Es por ello que se utiliza esta última expresión para este método de ordenación. multiplica por una constante a alguno de los tiempos de ejecución anteriormente propuestos. Suele ser habitual cuando se tratan pares de elementos de datos. siendo N el número de vértices de éste. Una definición rigurosa de esta notación es la siguiente: Una función g(N) pertenece a O(f(N)) si y sólo si existen las constantes c0 y N0 tales que: |g(N)| <= |c0·f(N)| . N3 : Tiempo de ejecución cúbico. El problema de la mochila resuelto por un algoritmo de fuerza bruta -simple vuelta atrás. Por ejemplo. Si N se duplica. que un problema sea decidible no implica que se pueda encontrar su solución. el peor caso. Si N se duplica. Como ejemplo se puede dar el de un bucle anidado triple. es decir. un algoritmo cuyo tiempo de ejecución sea T = 3N2 + 6N se puede considerar proporcional a N2. además de ser independiente de los datos de entrada del algoritmo. el tiempo de ejecución aumenta cuatro veces. como por ejemplo un bucle anidado doble.Notación O-grande En general. pues muchos problemas que disponen de algoritmos para su resolución son inabordables para un     . . Así. en la práctica este caso no se da casi nunca y la mayoría de los casos son proporcionales a N·logN. 2N : Tiempo de ejecución exponencial. Es decir. Si N se duplica. tardará el doble que otro en que N valga 20. esto es. el tiempo de ejecución es ligeramente mayor del doble. El peor caso de entrada del algoritmo Quick Sort se ejecuta en este tiempo. además de la suma de algunos términos más pequeños. Conviene diferenciar entre el peor caso y el esperado. Son en general factibles.es un ejemplo. la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución. es decir. el tiempo de ejecución del algoritmo Quick Sort es de O(N2). Un ejemplo sería un algoritmo que lee N números enteros y devuelve la media aritmética. y se escribe O(N2). para todo N >= N0. A veces ocurre que no hay que prestar demasiada atención a esto. Los grafos definidos por matriz de adyacencia ocupan un espacio O(N2). Sin embargo. el tiempo de ejecución se eleva al cuadrado. . * Problemas decidibles: aquellos que cuentan al menos con un algoritmo para su cómputo. el tiempo de ejecución se multiplica por ocho. N2 : Tiempo de ejecución cuadrático. * Algoritmos exponenciales: aquellos que son proporcionales a kN. Es común encontrarlo en algoritmos como Quick Sort y otros del estilo divide y vencerás. La notación O-grande ignora los factores constantes. Un caso en el que N valga 40. N : Tiempo de ejecución lineal.Clasificación de problemas Los problemas matemáticos se pueden dividir en primera instancia en dos grupos: * Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo. Sin embargo.
Importancia de los Diagramas de Flujo: Es importante ya que ayuda a designar cualquier representación gráfica de un procedimiento o parte de ese. Los algoritmos que los resuelven son deterministas. Para otros problemas..Es la representación gráfica de la solución a un problema utilizando símbolos predefinidos para su interpretación. Utilizan diversos símbolos para representar operaciones específicas.A nivel de programación es la representación gráfica de lo que se desea que la computadora realice. 2. Esta clase de problemas se denomina clase NP. economía y procesos industriales. que se realizan para entender mejor al mismo y son utilizados en programación. sus mejores algoritmos conocidos son no deterministas.Es la representación gráfica del algoritmo. 1. DIAGRAMAS DE FLUJO: Los diagramas de flujo son esquemas que representan gráficamente un algoritmo por medio de los pasos de un proceso. Aquellos problemas para los que se conoce un algoritmo polinómico que los resuelve se denominan clase P. Esto permite separar los problemas decidibles en dos: * intratables: aquellos para los que no es factible obtener su solución. Diagrama de Sistema: Representa la integración. como su nombre lo indica representa el flujo de información de un proceso. Por tanto. Es llamado diagramas de flujo porque los símbolos utilizados se conectan por medio de flechas para indicar la secuencia de una operación y son también llamados flujogramas. 4. los problemas de la clase P son un subconjunto de los de la clase NP. Diagrama de Procedimiento: Representa gráficamente una operación o flujo de datos dentro de un sistema.... Tipos de Diagramas: Diagrama de Programa: Representa gráficamente un método propuesto para la solución de un problema determinado. llega hacer fácil escribir el programa en cualquier idioma de alto nivel. 5. pues sólo cuentan con una alternativa en cada paso.. interacción lógicas de los elementos dentro de un sistema propuesto. * tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.computador por el elevado número de operaciones que hay que realizar para resolverlos. Utilizan una series de símbolos con significados especiales.Son representaciones graficas de un algoritmo el cual muestra los pasos o procesos a seguir para alcanzar la solución de un problema. 3. Un diagrama de flujo u organigrama es una representación diagramático que ilustra la secuencia de las operaciones que se realizan para conseguir la solución de un problema y son usados normalmente para seguir la secuencia lógicas de las acciones en el diseño de problemas de computadoras y se dibujan generalmente antes de comenzar a programar el código frente a la computadora y una que se dibuja el diagrama de flujo. Los problemas pueden clasificarse también atendiendo a su complejidad. .Lógica dibujada.
no es necesario usar un tipo especial de símbolos para crear un diagrama de flujo. los podía interpretar. las salidas. Se basan en la utilización de diversos símbolos para representar operaciones específicas. Definición Es un esquema para representar gráficamente un algoritmo. De acuerdo al estándar ISO. Se les llama diagramas de flujo porque los símbolos utilizados se conectan por medio de flechas para indicar la secuencia de operación. estandarizados según la norma ISO 5807:   Flecha. que se realiza para entenderlo mejor. Rectángulo.Diagrama de flujo sencillo con los pasos a seguir si una lámpara no funciona. Se utiliza para representar una condición. ya que. los símbolos e incluso las flechas deben tener ciertas características para permanecer dentro de sus lineamientos y ser considerados . Éste es controlado dentro del diagrama de flujo en que se encuentra.   DOCUMENTO DATOS ALMACENADOS CONECTOR TERMINADOR Existen además un sin fin de formas especiales para denotar las entradas. Se usa para representar un evento o proceso determinado. se hicieron símbolos casi universales. Círculo. Un diagrama de flujo es la forma más tradicional de especificar los detalles algorítmicos de un proceso. los símbolos se someten a una normalización. estos diagramas utilizan una serie de símbolos con significados especiales. en un principio cada usuario podría tener sus propios símbolos para representar sus procesos en forma de Diagrama de flujo. Rectángulo redondeado: Se usa para representar un evento que ocurre de forma automática del cuál generalmente se sigue una secuencia determinada. pero existen algunos ampliamente utilizados por lo que es adecuado conocerlos y utilizarlos. La mayoría de las veces se utilizan números en los mismos. Representa un punto de conexión entre procesos. Se utiliza principalmente en programación. En teoría. La simbología utilizada para la elaboración de diagramas de flujo es variable y debe ajustarse a un patrón definido previamente.    Rombo. Se utilizan los símbolos indicados a continuación. Son modelos tecnológicos utilizados para comprender los rudimentos de la programación lineal. etcétera. los almacenamientos. El rombo además especifica que hay una bifurcación. Se utiliza cuando es necesario dividir un diagrama de flujo en varias partes. por ejemplo por razones de espacio o simplicidad. Son la representación gráfica de los pasos de un proceso. economía y procesos industriales. Indica el sentido y trayectoria del proceso de información o tarea. Es el símbolo más comúnmente utilizado. ampliando así las posibilidades de crear un diagrama más claro y comprensible para crear un proceso lógico y con opciones múltiples adecuadas. Una referencia debe darse dentro para distinguirlo de otros. Normalmente el flujo de información entra por arriba y sale por un lado si la condición se cumple o sale por el lado opuesto si la condición no se cumple. Esto trajo como consecuencia que sólo aquel que conocía sus símbolos. Símbolos utilizados Para poder hacer comprensibles los diagramas a todas las personas. Se usa para representar un evento que ocurre de forma automática y del cual generalmente se sigue una secuencia determinada. es decir.
pero puede esconder un error aún más grave: a veces el analista no etiqueta un flujo o un proceso porque simplemente no se le ocurre algún nombre razonable. VARIABLE: Es un valor no fijo que permanece almacenado en la memoria del computador y que es identificado con un nombre único y irrepetible. que tienen salidas sin tener entradas. Físicamente. Evitar las burbujas de generación espontánea. Podemos definirlo como cualquier cantidad o valor al cual hacemos referencia asignándole un nombre. Recomendaciones A su vez. Existe un único punto de fin para el proceso de flujo (salvo del rombo que indica una comparación con dos caminos posibles). Características que debe cumplir un diagrama de flujo En los diagramas de flujo se presuponen los siguientes aspectos:    Existe siempre un camino que permite llegar a una solución (finalización del algoritmo). Esto suele ser un indicio de falta de esmero. es importante que al construir diagramas de flujo. números o la combinación de ambas. Existe un único inicio del proceso. Número de Cédula de Identidad. que asemejan a una "rectángulo oblicuo" y se utilizan para unir actividades que se encuentran en otra hoja. burbujas que tienen entradas pero no salidas. una variable es un espacio o dirección en la memoria del computador. se debe procurar usarlo sólo cuando se conecta con un proceso contenido dentro de la misma hoja. A COD COD01  Los nombres de las variables siempre deberán comenzar por una letra. Sueldo. Existen también conectores de página. En el caso del círculo de conexión. A= 0 A= B Sueldo= SDO Nombre= NOMBS CARACTERÍSTICAS DE LAS VARIABLES:  El nombre de una variable puede ir formado por una o más letras. porque son sumamente sospechosas y generalmente incorrectas. Debe ser memotécnica. FAC001 Nunca: 01COD COD01 Nunca: 001FAC   Los nombres de las variables no deberán ir separados por espacios en blanco. clave (casi siempre abreviada) y que tomará diferentes valores durante el proceso. Tener cuidado con los flujos y procesos no etiquetados. Ejemplo: Nombres y Apellidos.sintácticamente correctos. se observen las siguientes recomendaciones:    Evitar sumideros infinitos. Código Empleado = CODEMP .
%. éste incrementa en el valor de 1 y nos muestra el número de veces que el proceso ha detectado una ocurrencia determinada y siempre deberemos expresarlo en forma cuantitativa. .&&& FEC= (__/__/__)  Numéricas: Son aquellas que almacenan sólo números (Dígitos) de (0-9). números (0-9). un contador en términos constante es un valor fijo que se va a ir contando. según sea el caso. $. &. Es un campo en memoria. es decir cumpliendo una función cuantitativa.Cédula= CED Sueldo= SDO Impuesto sobre la Renta= ISLR Seguro Social Obligatorio= SS0 Monto= MTO TIPOS DE VARIABLES:  Alfanuméricas: Son aquellas que pueden almacenar cualquier carácter. /. Ejemplos: C= 5 Valor Fijo C= C+1 C= (5)+1 CONTADOR: Es un valor que se incrementa o decrementa. la cual puede aparecer en forma “LITERAL” y permanecerá invariable durante el proceso (Va a almacenar un valor inalterable). A= 0 SDO= CED= En números.&&&. definido con un nombre único y irrepetible que no va a cambiar durante todo el algoritmo (Programa). etc…) Ejemplos: ISLR= 10% CED$= V. + . TOT= MTO= CONSTANTE: Es un valor que no varía. o caracteres especiales (¡ . Es cualquier cantidad. letras (A-Z).&&. espacios en blanco. *. C= 0 Ejemplo: C= C + 1 C= Variable contador C + 1= Se incrementa cuantitativamente. el cual sirve (como su nombre lo indica) para contar.
Fin OPERADORES RELACIONALES: > = Mayor que (Q´) < = Menor que (Q´) " = Mayor o igual (Q´) " = Menor o igual (Q´) . sino que viene alterándose por la suma de un valor a dicho campo. posiblemente se puede utilizar sumatoria ".3...Entonces El Nº mayor es: N1 5.Primer número: N1 4. Es un campo en memoria.EL Nº mayor es:N2 6. N2= 0 3.Declarar: N1= 0. TNOT= Total Notas C= Cantidad de alumnos. pero que su incremento no es de 1.. un valor que se incrementa en forma no definida esto por la suma de otro valor a dicho campo.-Preguntar: SI N1 > N2 *Decisión* 5. C= 100 hasta C= 0 (Decrementa) 1 ó 2= Número de veces que se incrementa Número o decrementa el contador..Inicio 2. Ejemplo= TSDO= 0 TSDO= TSDO + SDO 0 + 14000 14000 + 20000 34000 + 2000 36000 Todos los totales implica Acumulador...-Segundo número: N2 5.PR= Promedio de Notas.1.. Ejemplo: Determinar cual de dos números es el mayor en forma de Algoritmo. 1. DECISIÓN: Es una evaluación o determinación que va arrojar un valor verdadero o falso.2. Incremento Decremento C=0 C=100 ACUMULADOR: Es un campo de memoria.De lo contrario mostrar 5.
TDED ISLR = SDO * 2% PROM = TNOTAS / Nº ALUMNOS 1..5% R= N * 13..a.Leer solvencia.Identificación de variables y análisis de proceso. . de tu solvencia de examen dice: “No puede presentar”.5% ó R= N*C 1. . donde: F= m.. .Identificación de variables y análisis de proceso... Imprimir el resultado con su respectivo mensaje.Algoritmo y Diagrama de Flujo para calcular el área de un círculo donde: a= ¶ * r2 . lo muestre por impresora.14 A. N= 0 C= 13. F= m * a m= f / a 1.Diagrama de Flujo que calcule el 13.= Resta * = Multiplicación / = División ^ = Exponente o potencia Ejemplos: TASG = TASG + ASD NETO = TASG .Algoritmo que describe el proceso de verificar el Por qué?.Inicio. 1..Algoritmo y Diagrama de Flujo para calcular la masa de un objeto que se mueve con una fuerza y una aceleración.Identificación de variables y análisis de proceso.5% de cualquier número.< > = Diferente ó desigual = Igual OPERADORES LÓGICOS: AND= NOT= OR= OPERADORES ARITMETICOS: + = Suma . 2. a= 0 r= 0 ¶= 3.
6.Error en el Departamento de Control de Estudios.Si el torniquete está DAÑADO. puedo presentar. puedo salir. fin...Entonces. 1.Verificar la causa del problema. 9...Si el importe del ticket es menor.. Para estas variables sólo existen dos estados posibles.. B.3.....Entonces. puedo salir.Entonces. no puedo presentar 9.. 5. 6. 7.. me dirijo al Operador. 3. 11.Cancelo la mensualidad. 10. 5. c.. 5.Soluciono el problema. a cada uno de estos estados se le asigna un valor.. 11..Verifico la causa del problema. 4. utilizo otro computador.. 8. 6.Entonces.. el CPU del computador que se te asignó en el Laboratorio no enciende.Fin...Entonces no puedo utilizar el computador.Si el problema es porque no está enchufado.Inicio 2. Variables Lógicas: Existe una clase de variables que solamente pueden tomar dos valores.Si el problema es de carácter técnico. 3..Fin.. 7.Si el problema es falta de energía eléctrica. fin. me impide salir..Si el problema es que el computador está Dañado..Fin..Algoritmo que ayude a verificar porqué el torniquete del Metro de Caracas. 4.. puedo presentar.Entonces.Si el ticket está deteriorado.Entonces.. 10..Si el problema es falta de nota 8. no puedo utilizar el computador.. 12.Entonces. voy a otro torniquete.. 4. ..Si el problema es falta de pago. 1.Inicio 2. 7.Entonces. 8. pago la diferencia.Algoritmo que descarte Por qué ¿..Enchufo el cable soluciono el problema.
Uno De los estados se representa con la letra mayúscula. Y. que solamente pueden alcanzar dos estados. Z se indica X+Y+Z Usándose el operador + para indicar la operación. Si bien se usan los valores cierto y falso para los dos estados de este tipo de variables. Para el estado cerrado se asigna a la variable X el valor de 1. W. 1 y 0. Z = 1. OPERACIONES LÓGICAS: Las operaciones que se encuentran definidas sobre las variables lógicas son las que siguen. Z. pudiendo haberlo hecho al contrario. Ejemplo: Sean las variables lógicas X. X. en caso contrario el resultado es cero.. También se usa con mucha frecuencia el operador ó (la letra o con acento). se presenta una llave de paso de agua que puede estar abierta o cerrada. En (a) aparece un contacto eléctrico. se presenta una sala que tiene dos puertas de entrada. cuando está abierto se le asigna el valor de 0. La suma lógica será: 1 + 0 +1 = 1 o1ó0ó1=1 o 1 or 0 or 1 =1 Ejemplo: En algunos recintos se puede encender una luz usando interruptores localizados en diferentes sitios. Y. y el otro con la misma letra con una barra encima: U. W. Y = 0. En (b).Se acostumbra representar a estas variables con letras mayúsculas: U. Por ejemplo. Y. que puede estar abierto o cerrado.2. Sobra decir que la asignación de valores a los dos estados es totalmente arbitraria. X. Z. El resultado de la suma lógica es 1 cuando al menos uno de los sumandos es 1. V. V. Abierto Abierta X0X Abierto Abierta X1X  (b) Ejemplo: En la figura se presentan diversos componentes. SUMA LÓGICA (Or) La suma lógica de las variables X. que en determinado momento tienen los valores siguientes: X = 1. y con mayor frecuencia aún se emplea el término inglés (or). para distinguir los dos estados posibles. Y. Z. en la figura 3. Al . lo más común es el uso de los dígitos del sistema binario.
si hay 5 puertas. Si alguna puerta no cierra. el problema valdrá o. V = 1 . con cinco interruptores denominados U. . COMPLEMENTO LÓGICO (Not) El complemento lógico de una variable X se indica como X. El complemento de 1 es o. Cuando se cierra. El resultado de un producto lógico vale 1 sólo cuando todas las variables valen 1. el respectivo interruptor queda abierto. Representa el otro estado de la variable. W = 0. que permite apagar o encender la luz. Si alguna de las variables tiene como valor 0. se colocan microinterruptores en cada una de dichas puertas. o su versión inglesa (And). es necesario que U * V * W * X * Z sea 1 para que se dé la condición de vuelo. en algunos textos se coloca un apóstrofe en lugar de la barra. al menos uno de ellos. que X+Y Dé como resultado 1. Es decir. sólo cuando todos se encuentren cerrados (todos en 1) recibirá el piloto el permiso para despegar. Y X Figura 3. aunque con más frecuencia se antepone la negación inglesa NOT. Z se indica así X*Y*Z Usándose el operador * para indicar la operación. Para facilidad de la escritura. W. el interruptor queda cerrado. la condición para que se encuentre la luz encendida es que. Es decir. Y.2 PRODUCTO LÓGICO (And) El producto lógico de varias variables X. Ejemplo: Considérense las variables U. así: NOT X. también se acostumbra anteponer la negación no. También se usa con mucha frecuencia el operador y. e Y indican el estado de esos interruptores. Z. como NO X. W cuyos valores son: U = 0. El producto lógico U * V * W es igual a U*V*W=0*1*0=0 El producto lógico U * V es igual a U*V=0*1=0 Ejemplo: Para asegurarse que todas las puertas de un Jumbo se encuentren convenientemente aseguradas y que no ocurrirá ninguna descomprensión cuando se encuentre volando. adoptándose 1 cuando están en On y 0 cuando en Off. Si las variables X. el de o es 1. Si se asigna el valor 1 a un interruptor cerrado. X. Además de la superbarra ( ) colocada sobre la variable. H`. V.lado de cada puerta existe un interruptor. Por ejemplo. se encuentre en On. y 0 a uno que esté abierto. V.
FUNCIONES LÓGICAS: La combinación de variables lógicas. B. se obtiene lo que se conoce como tabla de verdad de la función. TABLAS DE VERDAD . da lugar a expresiones más complejas. procurando que no exista confusión entre las letras asignadas a las variables y a las funciones. Las tablas de verdad son muy útiles para describir el comportamiento de los sistemas. A= 1 * 0 + 1 * (1 + 0) A= 0 + 1 * ( 1 + 1) A= 0 + 1 = 1 El resultado de la función A es 1. U= 1.Las anteriores son las operaciones lógicas básicas.5.. se reemplazan las variables por sus valores. Las funciones lógicas también se representan mediante letras mayúsculas: A. que pueden llamarse Funciones Lógicas. que pueden ser descritos mediante funciones lógicas. Ejemplo: Sea la función F= X + Y * X La tabla de verdad para esta función se encuentra en la figura 3. pueden alcanzar dos valores: cierto o falso. una manera gráfica de visualizar rápidamente el modo de ejecutarse las operaciones descritas es mediante el uso de contactos eléctricos. 1 ó 0. Estas. Y = 0. como las variables que la forman. Para cada combinación de X. tal como se hizo en el ejemplo anterior. En la tercera columna aparece el valor de F. Las dos primeras columnas corresponden a las 4 posibles combinaciones de las variables X e Y. se aplican las reglas de las operaciones lógicas y se obtiene el resultado. C. a partir de las cuales se pueden definir otras más complejas. TABLAS DE VERDAD: Si se tabulan todas las posibles combinaciones de los valores de las variables de una expresión. Z= 1. mediante el uso de los operadores lógicos. Y se reemplazan sus valores en la función y se obtiene el valor. junto con el valor resultante de la misma. W= 0 La evaluación de la función es muy simple. Efectuando esto se obtiene. D. Ejemplo Como ejemplos de funciones lógicas se pueden dar los siguientes: A = X * Y + Z * ( U + W) B = Z + Z * ( W * Y + U) Ejemplo: Sea la función A= X * Y + Z * ( U + W ) En la que los valores de las variables son los siguientes: X= 1. Para aclarar bien la forma de obtenerlas se van a resolver algunos ejemplos. etc.
En la figura 3. TABLAS DE VERDAD P 0 0 0 0 1 1 1 1 Fig 3. aparece la tabla de la verdad para esta función.6 PR= TNOT/C C= C-2 Fin R= N * 13.6.X 0 0 1 1 Fig 3.5 Ejemplo Y 0 1 0 1 F 0 1 1 1 Sea la función F= (P + Q) * R En este caso. Para cada trío de valores de las variables. se reemplazan en la expresión de la función y se obtiene el valor de F.5% R N N=0 R=0 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 F 0 0 0 1 0 1 0 1 . las posibles combinaciones de las tres variables son 8.
r Inicio Declarar variables Leer N Proceso / Calcular Imprimir Resultado Fin Inicio Inicio Inicio Declarar variables m=0 f= 0 a=0 r Leer N af f Fin Imprimir Resultado Proceso / Calcular “La masa es: ” Fin m= f / a Inicio Inicio Declarar variables a=0 Pi= 3.14 r=0 r Leer N r Fin Imprimir Resultado Proceso / Calcular “El área es: “ Fin a= ¶ * r2 X .
Guia08 c T WHILE Resuelta
Algoritmo (Revisado y Ampliado)
LABORATORIO_No5
04Algoritmos
Ejercicios y Prácticas de Fundamentos de Programación 2013B.pdf
More From Nvto Hit Stone
Normas Transparencia Resolución SBS N° 8181-2012
01 -Ley_26702_ LEY GENERAL DEL SISTEMA FINANCIERO.pdf
s2_conceptosdemodelado.pdf
ley 26702 EEFF.pdf

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución