Programa de teoría



Descargar 9,75 Kb.
Fecha de conversión15.02.2017
Tamaño9,75 Kb.

Programa de teoría

  • Parte I. Estructuras de Datos.
  • 1. Abstracciones y especificaciones.
  • 2. Conjuntos y diccionarios.
  • 3. Representación de conjuntos mediante árboles.
  • 4. Grafos.
  • Parte II. Algorítmica.
  • 1. Análisis de algoritmos.
  • 2. Divide y vencerás.
  • 3. Algoritmos voraces.
  • 4. Programación dinámica.
  • 5. Backtracking.
  • 6. Ramificación y poda.

Algoritmos y Estructuras de Datos

  • Tema 0. Introducción
  • PARTE II: ALGORÍTMICA (o ALGORITMIA)
  • 0.1. Definición y propiedades.
  • 0.2. Análisis de algoritmos.
  • 0.3. Diseño de algoritmos.

0.1. Definición y propiedades.

  • Algoritmo:
  • Conjunto de reglas para resolver un problema.
  • Propiedades
    • Definibilidad: El conjunto debe estar bien definido, sin dejar dudas en su interpretación.
    • Finitud: Debe tener un número finito de pasos que se ejecuten en un tiempo finito.
  • 1 ó más salidas
  • ALGORITMO

0.1. Definición y propiedades.

  • Algoritmos deterministas: Para los mismos datos de entrada se producen los mismos datos de salida.
  • Algoritmos no deterministas: Para los mismos datos de entrada pueden producirse diferentes de salida.
  • ALGORITMIA: Ciencia que estudia técnicas para construir algoritmos eficientes y técnicas para medir la eficacia de los algoritmos.
  • Objetivo: Dado un problema concreto encontrar la mejor forma de resolverlo.

Recordamos: Objetivo de la asignatura

  • 0.1. Definición y propiedades.
  • Pero ojo, los algoritmos no son el único componente en la resolución de un problema de programación.

Algoritmos + Estructuras de Datos = Programas

  • Algoritmos + Estructuras de Datos = Programas
  • Estructura de datos: Parte estática, almacenada.
  • Algoritmo: Parte dinámica, manipulador.
  • PROBLEMA
  • PROGRAMA
  • Algoritmos +
  • Estructuras de datos
  • 0.1. Definición y propiedades.

Observación.

  • Observación.
  • Hipótesis.
  • Experimentación.
  • Verificación.
  • MÉTODO CIENTÍFICO INFORMÁTICO
  • 2. Diseño del programa (alg. y estr.)
  • 3. Implementación (programación)
  • 4. Verificación y pruebas
  • 0.1. Definición y propiedades.

Otras ideas...

  • 0.1. Definición y propiedades.
  • Otras ideas...
  • Refinamiento por pasos sucesivos.
    • Escribir la estructura de la solución en pseudocódigo, de manera muy genérica.
    • Especificar los pasos de forma cada vez más detallada, y precisa.
    • Repetimos el refinamiento hasta llegar a una implementación.

Proceso de resolución propuesto por Aho.

  • 0.1. Definición y propiedades.
  • Proceso de resolución propuesto por Aho.
  • Modelo
  • matemático
  • Algoritmo
  • informal
  • Tipos de datos
  • abstractos
  • Programa en
  • pseudolenguaje
  • Estructuras
  • de datos
  • Programa
  • en Pascal
  • Más en las asignaturas de Ingeniería del Software...

0.2. Análisis de algoritmos.

  • ALGORITMIA = ANÁLISIS + DISEÑO
  • Análisis de algoritmos: Estudio de los recursos que necesita la ejecución de un algoritmo.
  • No confundir con análisis de un problema.
  • Diseño de algoritmos: Técnicas generales para la construcción de algoritmos.
  • Por ejemplo, divide y vencerás: dado un problema, divídelo, resuelve los subproblemas y luego junta las soluciones.

0.2. Análisis de algoritmos.

  • Análisis de algoritmos. Normalmente estamos interesados en el estudio del tiempo de ejecución.
  • Dado un algoritmo, usaremos las siguientes notaciones:
    • t(..): Tiempo de ejecución del algoritmo.
    • O(..): Orden de complejidad.
    • o(..): O pequeña del tiempo de ejecución.
    • (..): Cota inferior de complejidad.
    • (..): Orden exacto de complejidad.

0.2. Análisis de algoritmos.

  • Ejemplo. Analizar el tiempo de ejecución y el orden de complejidad del siguiente algoritmo.
  • Hanoi (N, A, B, C: integer)
  • if N=1 then
  • Mover (A, C)
  • else begin
  • Hanoi (N-1, A, C, B)
  • Mover (A, C)
  • Hanoi (N-1, B, A, C)
  • end
  • Mecanismos:
    • Conteo de instrucciones.
    • Uso de ecuaciones de recurrencia.
    • Medida del trabajo total realizado.

0.3. Diseño de algoritmos.

  • Diseño de Algoritmos. Técnicas generales, aplicables a muchas situaciones.
  • Esquemas algorítmicos. Ejemplo:
  • Insertar código AQUÍ
  • Insertar
  • tipos AQUÍ
  • ALGORITMO Voraz (C: ConjuntoCandidatos ; var S: ConjuntoSolución )
  • S:= Ø
  • mientras (C  Ø) Y NO SOLUCION(S) hacer
  • x:= SELECCIONAR(C)
  • C:= C - {x}
  • si FACTIBLE(S, x) entonces
  • INSERTAR(S, x)
  • finsi
  • finmientras

¿Qué clase de problemas?

  • 0.3. Diseño de algoritmos.

0.3. Diseño de algoritmos.

  • RESUELTO

Planificador de rutas

  • Calcular ruta
  • 0.3. Diseño de algoritmos.
  • RESUELTO

0.3. Diseño de algoritmos.

  • EL JUEGO DE LAS CIFRAS.
  • Dado un conjunto de 6 enteros, encontrar la forma de conseguir otro entero, utilizando las operaciones de suma, resta, producto y división entera (y sin usar cada número más de una vez).

0.3. Diseño de algoritmos.

0.3. Diseño de algoritmos.

  • cifras.exe

0.3. Diseño de algoritmos.

  • RETO. Implementar un programa para resolver el problema, más rápido que la versión del profesor, y que no pierda ninguna solución.
  • RECOMPENSA.
    • Un 10 en la tercera práctica de la asignatura (diseño de algoritmos).
    • Un 10 en el ejercicio correspondiente del examen.
    • Más 1 punto de notas de clase.

Jugador de Ajedrez

  • Situación Inicial
  • Movimien-tos de A
  • Movimien-tos de B
  • Movimien-tos de A
  • 0.3. Diseño de algoritmos.
  • PENDIENTE

Problema del viajante

  • 0.3. Diseño de algoritmos.
  • PENDIENTE

0.3. Diseño de algoritmos.

  • Técnicas de diseño de algoritmos:
    • 1. Divide y vencerás.
    • 2. Algoritmos voraces.
    • 3. Programación dinámica.
    • 4. Backtracking.
    • 5. Ramificación y poda.
  • Dado un problema: seleccionar la técnica, seguir el proceso/esquema algorítmico, obtener el algoritmo y comprobarlo.
  • Recordar: No empezar tecleando código como locos.


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal