Responsable: | (-) |
Otros: | (-) |
Créditos | Dept. | Tipo | Requisitos |
---|---|---|---|
7.5 (6.0 ECTS) | CS |
|
PRAP
- Prerequisito para la EI , ETIG PRED - Prerequisito para la EI , ETIG PS - Prerequisito para la ETIS |
Responsable: | (-) |
Otros: | (-) |
Proveer al estudiante de las técnicas básicas de algorítmica que permiten abordar el desarrollo de programas correctos y eficientes para resolver problemas no triviales. Dichas técnicas básicas incluyen conocimientos teóricos y prácticos, habilidades, experiencias y sentido crítico, todas ellas fundamentadas en teorías y técnicas sólidas, comprobadas y bien establecidas.
Horas estimadas de:
T | P | L | Alt | L Ext. | Est | O. Ext. |
Teoria | Problemas | Laboratorio | Otras actividades | Laboratorio externo | Estudio | Otras horas fuera del horario fijado |
|
T | P | L | Alt | L Ext. | Est | O. Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
3,0 | 2,0 | 0 | 0 | 0 | 5,0 | 0 | 10,0 | |||
MergesortQuicksort
Karatsuba Strassen Otros ejemplos |
|
T | P | L | Alt | L Ext. | Est | O. Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
7,0 | 8,0 | 0 | 0 | 0 | 15,0 | 0 | 30,0 | |||
Heaps
Heapsort Colas de prioridad ampliadas Tablas de dispersión Árboles binarios de búsqueda Árboles binarios de búsqueda equilibrados |
|
T | P | L | Alt | L Ext. | Est | O. Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
3,0 | 2,0 | 0 | 0 | 0 | 7,0 | 0 | 12,0 | |||
RepresentacionesRecorridos
Algoritmos básicos |
|
T | P | L | Alt | L Ext. | Est | O. Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
5,0 | 5,0 | 0 | 0 | 0 | 12,0 | 0 | 22,0 | |||
Principios de los algoritmos voraces
Árboles de expansión mínimos: Kruskal, Prim Caminos mínimos: Dijkstra Códigos prefijos óptimos: Huffman Otros ejemplos |
|
T | P | L | Alt | L Ext. | Est | O. Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
5,0 | 5,0 | 0 | 0 | 0 | 12,0 | 0 | 22,0 | |||
Principios de los algoritmos de búsqueda exhaustivaMarcha atrás (backtracking) y Ramificación y Poda (branch and bound)
Ejemplos Nociones de complejidad |
|
T | P | L | Alt | L Ext. | Est | O. Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
5,0 | 5,0 | 0 | 0 | 0 | 12,0 | 0 | 22,0 | |||
Principios de los algoritmos de programación dinámica
Principio de optimalidad Soluciones recursivas, con memoización e iterativas Caminos mínimos: Floyd Distancia de edición Otros ejemplos |
Total por tipo | T | P | L | Alt | L Ext. | Est | O. Ext. | Total |
33,0 | 32,0 | 0 | 0 | 0 | 73,0 | 0 | 138,0 | |
Horas adicionales dedicadas a la evaluación | 9,0 | |||||||
Total horas de trabajo para el estudiante | 147,0 |
El temario se expone de forma muy práctica, a través de la presentación de muchos ejemplos.
La teoría y los ejemplos de aplicación se hirán presentando de forma más o menos paralela a lo largo del curso.
Las cinco horas semanales en promedio de la asignatura se organizan en dos bloques de horas cada semana y un bloque de dos horas en semanas alternas.
La evaluación constará de un examen parcial, un
examen ante ordenador, un examen final y un
trabajo práctico voluntario.
El examen parcial (P) es una prueba escrita donde entra
la materia de los temas 1 a 4.
El examen ante ordenador (M) es una prueba
consistente en resolver dos problemas sobre la
materia de los temas 2, 4, 5 y 6 ante
el ordenador y utilizando el sistema del Juez.
El examen final (F) es una prueba escrita donde entra
toda la materia de la asignatura.
El trabajo práctico voluntario (V) consiste en la
implementación de un jugador para un juego.
La nota de la asignatura se calcula así:
NOTA = min (10, max (25% P + 25% M + 50% F, 100% F) + 20% V)
La temporización es la siguiente:
El examen parcial se hace a mediados de curso, el examen
ante ordenador a finales de curso y el examen
final una vez terminado el curso. El trabajo voluntario
debe entregarse a finales de curso.
El mecanismo del examen ante máquina es el
siguiente:
Delante del ordenador, los estudiantes reciben dos
problemas. Un problema se define con un
enunciado, uno o más juegos de pruebas públicos y,
quizá, cierto código ya implementado. Cuando un estudio
quiera entregar su solución para alguno de los
problemas, lo envía a un juez automático que, en
poco segundos, le devolverá el veredicto sobre el
comportamiento de su programa. El estudiante puede
reenviar hasta 10 soluciones para el mismo
problema. Los profesores corregirán el último
envío realizado por cada problema.
El mecanismo del trabajo práctico voluntario es el
siguiente:
Después del parcial, se entregará el enunciado del
trabajo práctico voluntario, que consistirá en la
descripción de un juego. Los estudiantes que quieran
llevar a cabo el trabajo práctico voluntario deberán
de programar un jugador para este juego (es decir,
implementar una estrategia para intentar ganar el
juego). Junto con el enunciado, los profesores
también entregarán el código de un jugador muy sencillo:
el tonto.
A finales de curso, habrá un enfrentamiento público
a través de un sistema de rondas que incluirá todos
los jugadores entregados por los estudiantes y el tonto.
De este enfrentamiento se deducirá una clasificación
y se nombrará un campeón.
La nota del trabajo práctico voluntario se calcula
automáticamente a partir de la posición en la
clasificación, de forma lineal y garantizando que el
campeón tenga un 10 y que todos los participantes
que ganen al tonto tengan una nota mínima de 5.
Los jugadores que no ganen al tonto tendrán una
nota de 0.
La entrega del trabajo práctico voluntario
implica aceptar que, si se comprueba que ha
habido fraude en su realización, se restarán
sus puntos (en lugar de sumarlos) a los de
la asignatura.
Dominio de las técnicas de programación imperativa basada en objetos:
- paso de parámetros,
- clases,
- objetos,
- métodos,
- punteros,
- memoria dinámica,
- genericidad,
- uso de clases estándar.
Conocer bien al menos un lenguaje imperativo orientado a objetos, preferentemente C++.
Recursividad.
Concepto de TAD.
TAD secuenciales:
- pilas,
- colas,
- listas con punto de interés,
- listas con iteradores.
Uso e implementación interna de los TAD secuenciales.
TAD arbóreos:
- árbol binario,
- árbol n-ario,
- árbol general,
- recorridos.
Uso e implementación interna de los TAD arbóreos.
Conocimientos matemáticos sobre grafos, sumatorios, límites. Matemática discreta. Capacidad para seguir y proponer razonamientos matemáticos.
Algunos conocimientos rudimentarios de estadística y probabilidades: espacio de probabilidad, acontecimientos, funciones de distribución, variable aleatoria, esperanza.