anprd

1.PRESENTACIN DE LA ASIGNATURA

2.CONTEXTUALIZACIN EN EL PLAN DE ESTUDIOS

3.REQUISITOS PREVIOS REQUERIDOS PARA CURSAR LA ASIGNATURA

ASIGNATURA DE GRADO:

PROGRAMACIN Y ESTRUCTURAS DE DATOS

AVANZADAS Curso 2013/2014

(Cdigo:71902019)

Esta asignatura permite al estudiante conocer una serie de estructuras de datos avanzadas, que se utilizan frecuentemente

en problemas prcticos de programacin. Tambin presenta diversos esquemas algortmicos (voraces, divide y vencers,

programacin dinmica, vuelta atrs y ramificacin y poda) en los que se enmarcan gran parte de los algoritmos ms

utilizados en la resolucin de problemas.

Esta asignatura es comn a los grados en Ingeniera Informtica y en Ingeniera de las

Tecnologas de la Informacin y se imparte en el primer semestre del segundo curso,

tiene carcter obligatorio, consta de 6 crditos ECTS y es parte de la materia de Metodologa de la Programacin y

Algoritmia.

Con esta asignatura se busca que el estudiante desarrolle las siguientes competencias generales:

Capacidad de anlisis de problemas; Aplicacin de los conocimientos a la prctica;

Resolucin de problemas en entornos nuevos; Competencia en la gestin y organizacin de la informacin.

Adems, durante el estudio de esta asignatura se pretende alcanzar competencias especficas que se engloban en las

siguientes competencias de la materia:

- Capacidad para comprender y dominar los conceptos bsicos de la algortmica, y su aplicacin para el tratamiento

automtico de la informacin por medio de sistemas computacionales y para la resolucin de problemas propios de la

ingeniera.

- Conocimiento y aplicacin de los procedimientos algortmicos bsicos de las tecnologas informticas para disear

soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.

- Conocimiento, diseo y utilizacin de forma eficiente de los tipos y estructuras de datos ms adecuados para la resolucin

de un problema.

- Capacidad para analizar y disear aplicaciones eligiendo la solucin ms adecuada.

Para cursar esta asignatura se requieren los siguientes conocimientos:

4.RESULTADOS DE APRENDIZAJE

5.CONTENIDOS DE LA ASIGNATURA

- conocimientos bsicos de programacin, impartidos en la asignatura de Fundamentos de Programacin.

- programacin orientada a objetos y Java, impartidos en la asignatura de Programacin Orientada a Objetos

- estructuras de datos, anlisis de algoritmos y recursividad, impartidos en la asignatura de Estrategias de Programacin y

Estructuras de Datos

Los resultados esperados del aprendizaje son:

- Saber utilizar entornos de desarrollo y prueba de programas.

- Implementar soluciones a problemas especficos mediante tcnicas y herramientas de programacin, planteando

correctamente las distintas fases para la construccin de un programa, desde el anlisis del problema hasta la programacin.

- Capacidad para usar estructuras de datos avanzadas para el manejo de informacin en los programas informticos.

- Conocer y aplicar diversos algoritmos, considerando la relacin entre coste computacional y sencillez de un determinado

algoritmo para resolver un problema.

Introduccin

Antecedentes

Nocin de Esquema Algortmico

Estructuras de datos avanzadas

Grafos

Definiciones bsicas

Tipos de grafos

Representacin de grafos

Recorrido de grafos

rboles de recubrimiento

Puntos de articulacin

Ordenacin topolgica de un grafo dirigido acclico

Camino ms corto desde la raz a cualquier otro nodo

Otros algoritmos sobre grafos

Montculos

Implementacin y operaciones sobre elementos del montculo

Eficiencia en la creacin de montculos a partir de un vector

Otros tipos de montculos

Tablas de dispersin (hash)

Funciones Hash

Resolucin de colisiones

Algoritmos voraces

Planteamiento General

Algoritmos voraces como procedimientos heursticos

Algoritmos voraces con grafos

rboles de recubrimiento mnimo: algoritmo de Prim

rboles de recubrimiento mnimo: algoritmo de Kruskal

Camino de coste mnimo: algoritmo de Dijkstra

Algoritmos voraces para planificacin

Minimizacin del tiempo en el sistema

Planificacin con plazos

6.EQUIPO DOCENTE

7.METODOLOGA Y ACTIVIDADES DE APRENDIZAJE

Almacenamiento ptimo en un soporte secuencial

Generalizacin a n soportes secuenciales

Problema de la mochila con objetos fraccionables

Mantenimiento de la conectividad

Problema de mensajera urgente

Problema del Robot desplazndose en un circuito

Divide y Vencers

Planteamiento y esquema General

El puzzle tromino

Ordenacin por fusin

Ordenacin rpida (Quicksort)

Clculo del elemento mayoritario en un vector

Liga de equipos

Skyline de una ciudad

Programacin Dinmica


Los Coeficientes Binomiales

Devolucin de cambio

El Viaje por el Ro

La Mochila

Multiplicacin Asociativa de Matrices

Camino de coste mnimo entre nodos de un grafo dirigido

Distancia de edicin

Vuelta Atrs


Coloreado de grafos

Ciclos Hamiltonianos

Subconjuntos de suma dada

Reparto equitativo de activos

El robot en busca del tornillo

Asignacin de cursos en una escuela

Ramificacin y Poda


Asignacin de Tareas: Pastelera

El viajante de comercio

Seleccin de tareas: Cursos de Formacin

Distancia de Edicin

Asistencia a incidencias

M. LOURDES ARAUJO SERNA

RAQUEL MARTINEZ UNANUE

MIGUEL RODRIGUEZ ARTACHO

LAURA PLAZA MORALES

El estudiante trabajar con contenidos terico-prcticos utilizando el texto base, la gua

de estudio y el material complementario. Adems se realizarn dos prcticas obligatorias bajo la supervisin del tutor, con

las herramientas y directrices preparadas por el equipo docente. Se requerir la asistencia, al menos, a dos de las sesiones

presenciales de prcticas organizadas por el tutor en el centro asociado.

8.EVALUACIN

9.BIBLIOGRAFA BSICA

10.BIBLIOGRAFA COMPLEMENTARIA

De manera orientativa, la distribucin porcentual del trabajo en cada una de las actividades formativas es la siguiente:

- Trabajo con contenidos tericos; consulta de materiales didcticos: 30 %

- Trabajo autnomo: estudio de contenidos tericos, realizacin de la prctica, preparacin de las pruebas presenciales,

consulta de dudas: 70 %

Se utilizarn dos formas de evaluacin:

Las prcticas (realizadas bajo la supervisin del tutor en el centro asociado) sern evaluadas por el tutor y

supondrn un 20% de la nota final. Es un requisito aprobarlas para poder superar la asignatura. Se requiere que

el alumno asista, al menos, a dos sesiones presenciales de tutoras relacionadas con las prcticas.

Una prueba presencial, de carcter terico-prctico, que ser evaluada por el equipo docente de la asignatura, y

supondr un 80% de la nota final. El examen podr incluir preguntas sobre la prctica realizada, y debe

aprobarse (mitad de la puntuacin del examen) para que se sume la nota de prcticas.

Adems, a efectos de autoevaluacin, el estudiante dispondr de cuestiones y problemas resueltos como parte del material

de estudio.

Comentarios y anexos:

PROGRAMACIN Y ESTRUCTURAS DE DATOS AVANZADAS,

Lourdes Araujo Serna, Raquel Martnez Unanue, Miguel Rodrguez Artacho

Ed Ramn Areces, 2011.

ISBN(13): 9788420538495 Ttulo: ESTRUCTURAS DE DATOS Y MTODOS ALGORTMICOS: EJERCICIOS RESUELTOS (1) Autor/es: Mart Oliet, Narciso ; Verdejo Lpez, Jos Alberto ; Ortega Malln, Yolanda ; Editorial: PEARSON ALHAMBRA

Buscarlo en libreria virtual UNED

Buscarlo en bibliotecas UNED

Buscarlo en la Biblioteca de Educacin

Buscarlo en Catlogo del Patrimonio Bibliogrfico

ISBN(13): 9788436236224 Ttulo: ESQUEMAS ALGORTMICOS. ENFOQUE METODOLGICO Y PROBLEMAS RESUELTOS (1) Autor/es: Gonzalo Arroyo, Julio ; Rodrguez Artacho, Miguel ; Editorial: UNED





11.RECURSOS DE APOYO

12.TUTORIZACIN

Comentarios y anexos:

Tcnicas de Diseo de Algoritmos.

GUEREQUETA, R. y VALLECILLO, A.:

Ed. Universidad de Mlaga (1998).

En estos libros pueden encontrarse ejemplos de uso de las estructuras de datos y los esquemas algoritmicos propuestos

distintos a los presentados en el texto base.

ISBN(13): 9788489660007 Ttulo: FUNDAMENTOS DE ALGORITMIA (1) Autor/es: Bratley, Paul ; Brassard, Gilles ; Editorial: PRENTICE-HALL





Adems de esta gua del curso y la gua de estudio (que detalla el plan de trabajo

propuesto para el alumno), el equipo docente proporcionar material adicional a travs del entorno de enseanza virtual de

la asignatura.

En los centros asociados los alumnos dispondrn de ordenadores en los que el entorno de desarrollo BlueJ (comn a varias

asignaturas del grado, y entre ellas la que nos ocupa) estar instalado. Adems, los alumnos que dispongan de ordenador

personal podrn instalarse ese entorno de desarrollo.

El alumno dispone de varios mecanismos para facilitar su aprendizaje:

- Tutores en los centros asociados. Sern los encargados de desarrollar las sesiones presenciales de seguimiento y control

de las prcticas. Para realizarlas, el alumno debe ponerse en contacto con su tutor al comienzo del semestre, para conocer

cuanto antes los horarios de las sesiones previstas.

- Tutoras presenciales o virtuales en el centro asociado correspondiente.

- Pgina web de la asignatura, en la que se ofrecer una visin general de la asignatura e informacin actualizada sobre los

contenidos y recursos. Puede encontrarse en www.lsi.uned.es.

- Entorno virtual de la asignatura (accesible desde el portal de la UNED, www.uned.es). Ese entorno ser el mecanismo

bsico de comunicacin del equipo docente con estudiantes y tutores. Dispone adems de foros donde los alumnos podrn

plantear sus dudas para que sean respondidas por los tutores o por el propio equipo docente.

- Tutoras con el equipo docente: Los jueves de 15 a 19 horas, el equipo docente atender dudas de carcter conceptual va

correo electrnico, telfono o presencialmente. El Equipo Docente no resolver problemas producidos a la hora de instalar,

compilar o depurar los programas que vayan generando para el estudio de la asignatura o la prctica. Las dudas al respecto

deben plantearse al tutor asignado por el centro asociado.

anprd

Documents