1

Algoritmos yEstructuras de Datos

Curso académico: 2007/2008

Titulación: Ingeniero en Informática

Ciclo: 1º; Curso: 2º

Carácter: Troncal

Créditos: 12 (6 teóricos + 6 prácticos)

Profesores: Ginés García Mateos (teoría y prácticas)

Joaquín Cervera López (teoría y seminarios)

Alberto Pérez Vela (prácticas)

2

Objetivos de la asignatura

Objetivo central

SER CAPAZ DE ANALIZAR, COMPRENDER Y RESOLVER UNA AMPLIA VARIEDAD DE

PROBLEMAS COMPUTACIONALES, DISEÑANDO E IMPLEMENTANDO SOLUCIONES EFICIENTES Y

DE CALIDAD, COMO RESULTADO DE LA APLICACIÓN DE UN PROCESO METÓDICO

1. Resolución de problemas

2. Eficiencia y calidad

3. Proceso metódico

3

Objetivos de la asignatura• Conocer y saber aplicar una amplia variedad de

técnicas de diseño de algoritmos y técnicas de representación de datos.

• Conocer y utilizar las técnicas de análisis de eficiencia, tomando conciencia de la importancia del factor eficiencia.

• Saber afrontar la resolución de problemas nuevos, utilizando las técnicas estudiadas como herramientas flexibles.

• Concienciarse de la importancia de seguir un proceso metódico y de lograr los factores de calidad del software.

4

Contexto curricular

Metodología yTecnología de

la Programación

Metodología yTecnología de

la Programación

Álgebra yMat. Discreta

Álgebra yMat. Discreta

Algoritmos yProg. Paralela

Algoritmos yProg. Paralela

1º1º 2º2º 3º, 4º, 5º3º, 4º, 5º

Algoritmos y Estructuras

de Datos

Algoritmos y Estructuras

de Datos

Bases deDatos

Bases deDatos

ProgramaciónOrientadaa Objetos

ProgramaciónOrientadaa Objetos

Fundamentosde Ingenieríadel Software

Fundamentosde Ingenieríadel Software

CálculoCálculo

EstadísticaEstadística Plan de IIde 2002

Plan de IIde 2002

SistemasOperativos

SistemasOperativos

5

Programa de teoríaParte I. Estructuras de Datos.

0. Introducción.

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.

Bloque IBloque I

Bloque IIBloque II

Bloque IIIBloque III

Bloque IVBloque IV

6

Programa de prácticas• Análisis, diseño, implementación y prueba de diversos

problemas de algoritmos y estructuras de datos.• Lenguajes C/C++, sobre Linux (Laboratorio 1/1).

• Seminario 1: Programación en C• Seminario 2: Programación en C++• Práctica 1: Implementación y manejo de estructuras

de datos• Práctica 2: Eficiencia, evaluación, comparación y

predicción• Práctica 3: Resolución de problemas SEMINARIOS:MARTES Y JUEVES POR LA MAÑANA EMPEZAMOS MARTES DE LA SEMANA QUE VIENE

APUNTARSE EN LA HOJA DE PRÁCTICAS

7

Evaluación• Nota Final = 0,65 Nota Total Examen + 0,35 Nota

Total Prácticas + Notas adicionales

• Nota Total Examen = 0,5 Nota Primer Parcial + 0,5 Nota Segundo Parcial– Primer Parcial: Bloque de estructuras de datos

– Segundo Parcial: Bloque de algorítmica

– Mínimo de 4 en cada parte para calcular el total

– Mínimo de 4,5 en el total para obtener el final

• Nota Total Prácticas = 2/4 Nota Práctica 1 + 1/4 Nota Práctica 2 + 1/4 Nota Práctica 3– Se deben aprobar todas las prácticas para calcular el total

– Obligatorio al menos una entrevista

8

El Problema con los ExámenesEspacio Europeo de Educación Superior (EEES)

• Modelo educativo actual

SemanaAntes de clase Clase Después de clase

AlumnoProfesor

Ded

icac

ión

Antes de clase Clase Después de clase

AlumnoProfesor

Ded

icac

ión

Semana

• Nuevo modelo educativo

9

El Problema con los ExámenesEspacio Europeo de Educación Superior (EEES)

• Modelo educativo actual

AlumnoProfesor

Ded

icac

ión

AlumnoProfesor

Ded

icac

ión

• Nuevo modelo educativo

10

El Problema con los ExámenesEspacio Europeo de Educación Superior (EEES)

• Modelo educativo actual

CuatrimestreExamen

Profesor

Ded

icac

ión

AlumnoProfesor

Ded

icac

ión

• Nuevo modelo educativo

Alumno

CuatrimestreExamen

11

EvaluaciónPrincipios:

• Evaluación continua del trabajo a lo largo de todo el curso, no atracón de última hora.

• Para cada tema, ejercicios, tests, y otras actividades. Si se superan, el tema queda convalidado.

• La asistencia a clase es obligatoria (mínimo del 80%).

• Evaluación alternativa: mediante examen final.– Examen exigente. Una pregunta por tema. TODAS LAS

PREGUNTAS DEBEN APROBARSE POR SEPARADO (1/3).

– No se requiere asistencia a clase ni otras actividades.

– Si alguien convalida sólo algunos temas, puede recuperar los que queden en el examen, pero siempre con la asistencia a clase.

12

EvaluaciónActividades:

• Asistencia a clase: se pasará lista de asistencia.

• Resúmenes: leer temas del texto guía, entregar resúmenes: una sola hoja escrita a mano.

• Examen de tipo test: ejecutar algoritmos, relacionar cosas, aspectos esenciales.

• Y por supuesto…

• ¡¡El juez on-line!!

13

Evaluación

14

Evaluación

15

Evaluación

16

Evaluación

17

Evaluación

18

Mooshak

19

MOSS (Measure of Software Similarity)

20

Actividades de teoría

Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones.

2. Conjuntos y diccionarios.

3. Repr. de conjuntos mediante árboles.

4. Grafos.

Ejercicios de Maude (gr.2)

Examen test

Ejercicios de programación

(indiv.)

~24/oct

~30/nov

~25/ene

Asistencia a clase y entrega de resúmenes

21

Actividades de prácticas

Práctica 1: Implementación y manejo de estructuras de datos.

• Ejercicios básicos.

• Implementación de tabla de dispersión.

• Diccionarios mediante árboles.

• Buscador de contenido en texto.

~9/nov

~30/nov

~14/dic

~14/ene

22

Otras actividades...

• Notas adicionales:

– +0,5 puntos sobre la nota final, siempre que esté aprobada la asignatura.

– Superación de retos propuestos.

– Concurso de programación ACM Contest.

– Participación en el curso de preparación.

– Otros...

23

Tutorías• Lunes y miércoles, de 10:30 – 13:30

• Despacho 2.34 (2ª planta Fac. Informática)

• E-mail: ginesgm@um.es• Web asignatura:

http://dis.um.es/~ginesgm/aed.html

24

Bibliografía• Algoritmos y Estructuras de Datos (texto guía)

Volumen I y II

G. García Mateos, D. Giménez Cánovas,

J. Cervera López, N. Marín Pérez

Ed. Diego Marín, 2003

• Estructuras de datos y algoritmosA.C. Aho, J.E. Hopcroft, J.D. UllmanAddison-Wesley Iberoamericana, 1988

• Fundamentos de AlgoritmiaBrassard, BratleyPrentice-Hall, 1998

• Estructuras de datos y algoritmosMark Allen WeissAddison-Wesley Iberoamericana, 1995 (más en la web de la asignatura)

25

Ejercicios para casa• Leer el capítulo 1, y las secciones

2.1 y 2.2 del texto guía.• Preparar un resumen en un folio por

las dos caras (una cap. 1 y otra para 2.1 y 2.2), ESCRITO A MANO.

• Entregar el lunes de la semana que viene, en clase.

Nombre del alumno, AED Cap.1, Fecha (horas estim.)