advertisement

Analisis de algoritmos - Introduccion

50 %
50 %
advertisement
Information about Analisis de algoritmos - Introduccion
Technology

Published on February 19, 2014

Author: parejajd

Source: slideshare.net

Description

Introducción al análisis básico de algoritmos.
Herramienta fundamental para el desarrollo de aplicaciones de calidad.
advertisement

Análisis de Algoritmos JUAN DAVID PAREJA SOTO @parejajd

Temario General (1)  Análisis de algoritmos   Análisis de algoritmos iterativos  Comportamiento asintótico de funciones   Conceptos básicos Análisis de algoritmos recursivos Técnicas de diseño de algoritmos   Método ávido  Backtrack   Dividir para vencer Programación dinámica Problemas NP  Algoritmos no determinísticos  Problemas P, NP duros y NP completos  Técnicas aproximativas @parejajd

Metodología (1)  Clases Presenciales   Sábados 10am Clases Virtuales  Grabadas durante la semana y seguidas el dia de clase normal  Vía Streaming y http://docencia.parejajd.co  4 Ejercicios de Práctica (Programación) 30%  2 Parciales 30% (15% Cada uno)  Asistencia y Participación 10%  Tareas, Talleres, Quiz, etc 30% @parejajd

Metodología (2)  Todo será usando Moodle http://docencia.parejajd.co  Los correos si se requieren serán enviados a docencia@parejajd.co @parejajd

Reglas básicas de Clase  Durante la explicación teórica y exposiciones los equipos de computo deben permanecer apagados (y con la tapa abajo)  Los Dispositivos Celulares y tabletas podrán usarse fuera del aula @parejajd

Copyright  Basado en la obra ubicada en http://docencia.izt.uam.mx/pece/pagina_academica/AA/indexa. html  Con aportes personales @parejajd

Análisis de Algoritmos UNIDAD 1

Objetivos  Al finalizar la asignatura el alumno será capaz de:  Discernir acerca de las mejores propuestas de solución a una problemática dada teniendo en cuenta las herramientas que el análisis de algoritmos ofrece.  Establecer el orden de complejidad, el tiempo promedio de ejecución y el conteo de instrucciones de un algoritmo.  Seleccionar una estrategia de solución para abordar situaciones particulares del quehacer profesional  Autoevaluar la funcionalidad de las propuestas de solución y plantear versiones mejoradas @parejajd

¿Qué es un algoritmo?  El termino algoritmo y lo que el significa han sido de gran importancia antiguamente en las matemáticas y durante mediados del siglo anterior y lo que vá del actual para las ciencias de la computación.  Surgio del matemático de Uzbequiztan Mohammed ibn-Musa alKhwarizmi , quien escribió un par de libros en su época el mas importante de ellos “el arte indio de contar” donde dio las nociones para realizar las operaciones matemáticas básicas siguiendo un proceso  la historia cuenta que se le atribuyo el método indio de conteo numérico y se le empezó a llamar método al-Khwarizmi , lo cual con los años y al llevarse “descuidadamente” termino llamándose algorismi , hoy dia Algoritmo @parejajd

¿Qué es un algoritmo?  En la actualidad podemos resumir su significado como conjuntos de reglas o procedimientos para realizar una o varias tareas. @parejajd

¿Todos los problemas son “solucionables”?  Será posible que todos los problemas existentes puedan representarse de manera algorítmica, es decir, mediante un conjunto de pasos o mediante un proceso  Si la respuesta es si, seguramente tendremos problemas que pueden solucionar mediante varios algoritmos.  Revisemos, los invito a jugar http://www.uterra.com/juegos/torre_hanoi.php  ¿Cuántas formas diferentes de solución encontramos?  ¿Cuál fue mas óptima es decir se llevó en menos tiempo? @parejajd

¿Todos los problemas son “solucionables”?  Revisemos otro http://www.sudoku-online.org/ o usemos el de la izquierda  @parejajd Por definición sudoku solo tiene una solución ¿la encontraste?

¿Todos los problemas son “solucionables”?  Como en ciertos problemas (Como las torres de hanoi) es posible encontrar mas de una solución, es necesario tener en cuenta algunas condiciones  tiempo de procesador y cantidad de memoria utilizados.  claridad, sencillez y facilidad de implantación, depuración y mantenimiento. @parejajd

Definición Formal de Algoritmo  Un algoritmo es un conjunto finito de instrucciones que indican cómo resolver un problema  no ambiguas  Efectivas  producen  reciben  y, al menos una salida cero o más entradas para ejecutarse, necesitan una cantidad finita de recursos. @parejajd

Ambiguedad  Hace referencia a que las instrucciones del Algoritmo deben estar expresadas de manera clara y directa y no son susceptibles a interpretaciones subjetivas @parejajd

Efectividad  Se refiera a que el algoritmo debe responder al problema de manera exacta @parejajd

..Al menos una salida  EL Algoritmo tiene que producir algo que haga entender que su trabajo a finalizado @parejajd

.. Recibir entradas  Aunque no es obligatorio el algoritmo debe ejecutarse con algunas entradas (parámetros)  Si el algoritmo no recibe entradas, esperaríamos siempre tener la misma salida @parejajd

Cantidad finita de Recursos  Debe tener una terminación  Debe usar los recursos de maquina produntemente @parejajd

Proceso computacional  Si una serie de instrucción cumple todas las condiciones anteriores excepto que posee una cantidad finita de tiempo de ejecución, es llamado PROCESO COMPUTACIONAL   Ej Sistemas Operativos Son “aplicaciones” que nunca detienen su funcionamiento @parejajd

Consideraciones Adicionales  Si un problema tiene una solución algorítmica, pero dicha solución lleva demasiado tiempo en su solución, se dice que el problema no tiene solución computacional  Muchos de los problemas que hace unos años se consideraban sin solución computacional, hoy en dia ya son solucionables gracias al poder de computo que se tiene @parejajd

Tarea 1  Consulte en Internet   ¿Cuál es el algoritmo de solución del problema de las torres de hanoi? Obtenga este algoritmo y ejecútelo contra el juego 3 veces (como soporte al trabajo indique cual es el tiempo que se tardó en cada ejecución) ?Si se necesita ordenar un conjunto de números enteros que algoritmos existen ya desarrollados para hacerlo? Obtenga al menos 3 algoritmos y ejecute la prueba con el siguiente conjunto de datos, cuente con un cronómetro cuando se demora haciendo el proceso y adjunto evidencias del proceso. @parejajd Lista Metodo 1 Metodo 2 Metodo 3 Tiemp 69 32 52 83 39 63 48 26 85 24 o

Complejidad Computacional

¿Qué es la Complejidad Computacional?  Es la medida que se utiliza para indicar la cantidad de recursos computacionales que un algoritmo utiliza o utilizará.  Se expresa mediante:  Donde n es el tamaño del programa  Es una función monótona creciente es decir. @parejajd

¿Como medir la Complejidad Computacional?  Medir la Memoria y la CPU usada es el principal objetivo y para esto se pueden usar dos enfoques.  Función complejidad espacial.   Expresado en términos de uso de la Memoria (Espacio en RAM) Función complejidad temporal  Expresado en términos de uso de la CPU (Tiempo de CPU) @parejajd

Función complejidad espacial.  Permite realizar una estimación de cuantos espacios de memoria (RAM) usa el programa, puede en la mayoría de los casos deducirse u obtenerse de la inspección del Código, así será necesario examinar dos elementos.  Celdas estáticas   Variables Estáticas, Constantes Celdas dinámicas  Variables de método, propiedades, atributos @parejajd

Función complejidad temporal  Dado que no es posible medir con exactitud cuanto tiempo de procesador utiliza un programa, vamos a suponer que cada instrucción del programa utiliza una cantidad constante y similar de tiempo, de allí que podremos utilizar pseudocódigo o código en cualquier lenguaje @parejajd

Revisemos un ejemplo   ¿Cuantas instrucciones se ejecutan si tamañoArreglo=10?  @parejajd Preguntas ¿Podemos generar una expresión matemática para esto’

Revisemos un ejemplo   10 Sumas  10 + 2 Asignaciones  10 + 1  10 + 1  10 + 1  @parejajd Si tamañoArreglo=10 10 + 1

Revisemos un ejemplo   10 Sumas  10 + 2 Asignaciones  10 + 1  10 + 1  10 + 1  10 + 1  @parejajd Si tamañoArreglo=10 ¿Cómo convertimos esto en una expresión matemática? Tarea

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Introduccion Al Diseno y Analisis de Algoritmos

Introduccion Al Diseno y Analisis de Algoritmos. by Michael Mendiola. 2,2K views. Embed. Download. Read on Scribd mobile: iPhone, iPad and Android.
Read more

Introducción al Análisis de Algoritmos - YouTube

Este video pretende mostrar los conceptos fundamentales del análisis de algoritmos
Read more

Introducción: El Rol de los Algoritmos en Computación

DR. JESÚS A. GONZÁLEZ BERNAL CIENCIAS COMPUTACIONALES INAOE Análisis y Diseño de Algoritmos Introducción: El Rol de los Algoritmos en Computación
Read more

Analisis de Algoritmos Introduccion - YouTube

Quiromancia “como leer la mano” la linea del amor, el matrimonio, los hijos | Linea del corazon | - Duration: 12:16. XXXthCENTURY 47,155 views
Read more

Introducción al diseño y análisis de los algoritmos ...

La presente monografía presenta en una primera parte una introducción al diseño de los algoritmos, mediante una variante de seudo código que permite ...
Read more

Introducción al Análisis de Algoritmos Notas de Clase

Introducción al Análisis de Algoritmos Notas de Clase Introducción al Análisis de Algoritmos ... latex2html analisis-algoritmos.tex -split 0 -nonavigation.
Read more

Introducción a los Algoritmos - upcAnalisisAlgoritmos - home

Introducción a los Algoritmos Andrés Becerra Sandoval 30 de julio de 2007 Resumen Haremos una introducción a los principales temas de todo el curso de
Read more

Introduccion Al Analisis de Algoritmos (Spanish Edition ...

Introduccion Al Analisis de Algoritmos (Spanish Edition) [Jesus Sanchez Velazquez] on Amazon.com. *FREE* shipping on qualifying offers.
Read more

Análisis de Algoritmos: Complejidad

Análisis de Algoritmos: Complejidad José A. Mañas Noviembre, 1997 1. Introducción 2. Tiempo de Ejecución 3. Asintotas 4. Reglas Practicas 5.
Read more