30178521-Practicas S2

PREDA - UNED
Prácticas de curso – 2019/20

Histórico
Curso Nº práctica Esquema Tema
1 DyV Skyline
2011/12
2 RyP Viajante de comercio
1 DyV Organización calendario liga deportiva
2012/13
2 VA Problema del caballo
1 Voraz Mensajería urgente
2013/14
2 PD Devolución de cambio en monedas
1 PD Multiplicación asociativa de matrices
2014/15
2 VA Coloreado de grafos
1 Voraz Minimización del tiempo en el sistema
2015/16
2 PD Coeficientes binomiales
1 DyV Multiplicación de grandes números
2016/17
2 VA N reinas
1 Voraz Robot en un circuito
2017/18
2 PD Mochila no fraccionable
1 VA Subconjuntos de suma dada
2018/19
2 PD Distancia de edición
2019-20
• Práctica 1:
• Cálculo del elemento mayoritario de un vector (DyV)
• Práctica 2:
• Reparto equitativo de activos (VA)
Normas
• Los estudiantes que tengan aprobadas ambas
prácticas en el curso anterior (sólo el anterior) no es
necesario que vuelvan a realizarlas en este curso.
• Para que el examen sea calificado el alumno deberá:
• haber asistido a las sesiones presenciales de prácticas
• haber entregado y aprobado las prácticas obligatorias
• Si se entregan y aprueban las prácticas en septiembre, hay que
presentarse necesariamente al examen de septiembre
Entrega
• Fechas
• Convocatoria de Febrero: 1 semana para corregir
• Domingo 19 de enero de 2020 (27/ene: Exámenes)
• Convocatoria de Septiembre:
• Domingo 23 de agosto de 2020
• Doble entrega necesaria

• Por email: [email protected]
• En la plataforma ALF
• A través del enlace habilitado en el apartado
“Entrega de trabajos”
Entrega
• ¿Todos inscritos al grupo de prácticas del centro
asociado de Sevilla?
• Plataforma ALF
• Entrega de trabajos -> Apuntarse a grupo de prácticas
Fernando Enríquez de Salamanca
• Comprobar que tenéis activadas las dos entregas

Evaluación de las prácticas
• Para que se evalúe la práctica es imprescindible que el
programa completo compile y funcione
• Su dificultad no será alta, por lo que sólo se calificarán con
sobresaliente aquellas prácticas con una excelente
documentación y calidad del código, que además cumplan los
requisitos imprescindibles de correcto funcionamiento y
aplicación de la estructura de datos o esquema adecuados
• En la evaluación que realiza el tutor se tendrán en cuenta los
siguientes aspectos:
Material a entregar (formato ZIP)
• Archivo .pdf con la siguiente información:
• Datos de la asignatura
• Nombre y Código
• Título de la práctica
• Centro Asociado
• Datos del alumno
• Nombre, apellidos, NIF, teléfono y correo electrónico
• Respuestas a los apartados:
• Descripción del esquema utilizado y su adecuación al problema
(Seguir las directrices del libro)
• Análisis del coste computacional
• Estudio de otras alternativas y comparativa
• Descripción de los casos de prueba realizados y sus resultados
• Código fuente Java (diseño orientado a objetos)
• Adecuadamente documentado
• Ejecutable (.jar) y directorio con fuentes (.java)
Crear .jar ejecutable
• BlueJ: Project -> Create Jar File -> Main class
• Eclipse: File -> Export -> Java -> runnable Jar file
• Código: Errores a evitar
• No compila
• No está desarrollado en Java en la entrega
• No se corresponde con el libro
• No es original, está copiado
• No sigue un diseño OO encapsulado o modular
• Ejecutable:
• No termina
• Se queda sin memoria con ejemplos pequeños
• Aborta sin justificación
• No lee los ficheros previstos en el formato adecuado
• No trata los argumentos
• No se ajusta a las especificaciones
• Documentación:
• No se presenta como ha indicado el tutor
• Está incompleta
• Soporte:
• No se puede leer
• Contiene virus (Suspenso)
¿Dudas?
• Foros de debate de la asignatura en ALF
• Foro de la práctica
• Grupo de tutoría de Sevilla
• Correo electrónico al tutor

• Fernando Enríquez de Salamanca Ros: [email protected]
• Sesiones de monitorización (obligatorias)

• Se resolverán colectivamente las dudas más comunes e
individualmente las dudas particulares de cada alumno
Práctica 2
Reparto equitativo de activos
Enunciado
• Dos socios que forman una sociedad comercial desean
disolverla repartiendo a medias sus n activos que tienen un
valor entero positivo. Desean conocer todas las posibles
formas que tienen de dividir el conjunto de activos en dos
subconjuntos disjuntos de igual valor entero.
• Se pide diseñar un algoritmo, siguiendo el esquema de
vuelta atrás, que resuelva este problema
• Ejemplo:
Activo 1 2 3 4 5 6 7 8 9 10
Valor 10 9 5 3 3 2 2 2 2 2
Entonces un posible reparto válido sería:

Socio1: 10, 2, 2, 2, 2, 2
Socio2: 9, 5, 3, 3
Esquema Vuelta Atrás (C6) –
Planteamiento
• Aplicación
• problemas en los que sólo podemos recurrir a una búsqueda
exhaustiva, recorriendo el espacio de todas las posibles soluciones
hasta encontrar una o hasta que hayamos explorado todas las
opciones
• Debido al coste
• aplicar el conocimiento disponible sobre el problema para
abandonar un camino no válido lo antes posible
• pensar antes si es posible usar un algoritmo voraz
• Recorrido del grafo representa el espacio de búsqueda
• si el grafo es infinito (o muy grande) se trabaja con un grafo
implícito, porque no tiene sentido que el programa lo construya
para luego aplicar las técnicas de búsqueda
• Recorrido en profundidad podando las ramas no válidas
• Vamos generando una solución parcial (secuencia k-prometedora) y
si encontramos un “nodo de fallo” retrocedemos y exploramos
otras ramas
Elementos
• IniciarExploraciónNivel():
recoge todas las opciones posibles en que se puede extender la
solución k-prometedora
• OpcionesPendientes():
comprueba que quedan opciones por explorar en el nivel
• SoluciónCompleta():
comprueba que se haya completado una solución al problema
• ProcesarSolución():
representa las operaciones que se quieran realizar con la
solución, como imprimirla o devolverla al punto de llamada
• Completable():
comprueba que la solución k-prometedora se puede extender
con la opción elegida cumpliendo las restricciones del problema
hasta llegar a completar una solución
Esquema
Esquema
Esquema
• Objetivo: ayudar a dos socios que forman una
sociedad comercial a disolverla, buscando todas las
formas de repartir en dos subconjuntos disjuntos de
igual valor sus n activos con valor entero
• Espacio de búsqueda: árbol de grado 2 y altura n+1
• Se puede generalizar a un reparto en n subconjuntos

de igual valor
• https://www.geeksforgeeks.org/partition-set-k-subsets-
equal-sum/
1 2 … n

…
formas de repartir en dos subconjuntos disjuntos de

1 2 … n 1 2 … n
igual valor sus n activos con valor entero
1 … 2 …
• Espacio de búsqueda: árbol de grado

1 2 … n
…
2 y altura n+1
1 2 … n
1 1 … 1 2 …
• Se puede generalizar
… …
a un reparto en n subconjuntos
de igual valor
• https://www.geeksforgeeks.org/partition-set-k-subsets-
equal-sum/
Reparto equitativo dede activos
• x: vector activos
• suma1, suma2, sumaTotal: suma de
activos asignados a cada socio y el total
• Objetivo: ayudar a dos socios
• v: vectorque forman una
de asignaciones
formas de repartir en dos subconjuntos disjuntos
de igual valor sus n activos con valor entero
Falta (con suma2 también):
• Espacio de búsqueda:
suma1  suma1 árbol
- x[k+1] de grado 2 y altura n+1
cierto
falso Ojo a las erratas

del libro
Reparto equitativo dede activos
• x: vector activos
• suma1, suma2, sumaTotal: suma de
activos asignados a cada socio y el total
• Objetivo: ayudar a dos socios
• v: vectorque forman una
de asignaciones
Falta (con suma2 también):
• Espacio de búsqueda:
suma1  suma1 árbol
- x[k+1] de grado 2 superior
Cota y altura n+1
de coste:
n
forma del árbol = O(2 )
cierto
falso Ojo a las erratas

del libro
• Espacio de búsqueda: árbol de grado 2 y altura n+1
DividirSociedad(x,suma1,suma2, sumaTotal,0,v)
cierto
falso
Coste
• El coste del caso peor es del orden del tamaño del
espacio de búsqueda
• Las funciones de poda que utilicemos reducen el
coste, aunque muchas veces no es posible saber
cuanto (depende de los datos), así que se da una
cota superior
Argumentos y parámetros
• Sintaxis:
• java reparto [-t][-h] [fichero_entrada] [fichero_salida]
• java -jar reparto.jar [-t][-h] [fichero_entrada] [fichero_salida]
• Argumentos:
• -t: traza cada paso de manera que se describa la aplicación del algoritmo utilizado
• -h: muestra una ayuda y la sintaxis del comando
Ejemplo:
$ java reparto -h <ENTER>
SINTAXIS:
reparto [-t][-h][fichero_entrada][fichero_salida]
-t Traza las llamadas recursivas
-h Muestra esta ayuda
fichero_entrada Nombre del fichero de entrada
fichero_salida Nombre del fichero de salida
• fichero_entrada: nombre del fichero del que se leen los datos de entrada
• Contiene el número de activos, seguido del valor de cada activo
• Si la entrada no es correcta, el programa debe indicarlo
• fichero_salida: es el nombre del fichero que se creará para almacenar la salida
• Si el fichero ya existe, el comando dará un error
• Si falta este argumento, el programa muestra el resultado por pantalla
Argumentos y parámetros
• Sintaxis:
• java
public class Reparto{ [-t][-h] [fichero_entrada] [fichero_salida]
mayoritario
• java –jar
… mayoritario.jar [-t][-h] [fichero_entrada] [fichero_salida]
public static void main(String[] args){
• Argumentos: switch (args.length){
• -t: traza cada paso de manera caseque se describa
0: //no la aplicación del algoritmo utilizado
hay argumentos
• -h: muestra una ayuda y la sintaxis break; del comando
Ejemplo: case 1: //args[0] puede ser –t, -h, fich_ent o fich_sal
$ java mayoritario -h <ENTER>
SINTAXIS: break;
mayoritario case
[-t][-2: //args[0] y args[1]
h][fichero_entrada][fichero_salida]
break;
-t Traza las llamadas recursivas
-h case 3: //args[0],
Muestra estaargs[1],
ayudaargs[2]
fichero_entrada break;
Nombre del fichero de entrada
fichero_salida Nombre delargs[1],
case 4: //args[0], ficheroargs[2],
de salida
args[3]
break;
• fichero_entrada: nombre del fichero del que se leen
default: //demasiados los datos de entrada
argumentos
• Contiene el número de elementos en el vector de enteros y el propio vector
break;
• Si la entrada no es correcta, el programa debe indicarlo
}
• Si no existe el fichero, se utilizará la entrada estándar
}
• fichero_salida:
… es el nombre del fichero que se creará para almacenar la salida
} • Si el fichero ya existe, el comando dará un error
• Si falta este argumento, el programa muestra el resultado por pantalla
Entrada / Salida
• Entrada
• El fichero de datos de entrada consta de 2 líneas con:
• El valor del parámetro n (número de activos)
• Los valores de los activos (sin ordenar) separados por
espacios
• Ejemplo:
10
10 9 5 3 3 2 2 2 2 2
• Salida
• La salida es:
• Una línea con el número de soluciones encontradas
• Tres líneas por cada solución:
• Identificador de la solución
• Los valores de los activos asignados al socio1
• Los valores de los activos asignados al socio2
• Ejemplo (correspondiente al ejemplo de entrada):
Código auxiliar
Fragmentos de código Java que pueden ser útiles
Lectura de ficheros en java (I)
• Lectura de un fichero de texto línea a línea:
BufferedReader bf = new BufferedReader(new FileReader(nomFich));
String linea = bf.readLine();
// Si no quedan datos en el fichero, linea será null
// Para divider una línea:

String[] datos = linea.split(“ “)
// Para convertir a entero un String:

volumen = new Integer(datos[0])
// Hay que cerrar el fichero una vez leído

bf.close();
Lectura de ficheros en java (II)
• Scanner
Scanner sc = new Scanner(new File(nomFich));
while(sc.hasNextLine()){
String linea = sc.nextLine();
//procesar elemento
}
sc.close();
Escritura de ficheros en java
• PrintStream
PrintStream ps = new PrintStream(new File(nomFich));
…
ps.println(elem); //ps.print(elem + “\n”);
…
ps.close();

30178521-Practicas S2

Cargado por

Copyright:

Formatos disponibles

30178521-Practicas S2

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

30178521-Practicas S2

Cargado por

Copyright:

Formatos disponibles

PREDA - UNED

Prácticas de curso – 2019/20

• Doble entrega necesaria

Fernando Enríquez de Salamanca

• Comprobar que tenéis activadas las dos entregas

• Correo electrónico al tutor

• Sesiones de monitorización (obligatorias)

Entonces un posible reparto válido sería:

• Se puede generalizar a un reparto en n subconjuntos

sociedad comercial a disolverla, buscando todas las

formas de repartir en dos subconjuntos disjuntos de

• Espacio de búsqueda: árbol de grado

falso Ojo a las erratas

falso Ojo a las erratas

// Para divider una línea:

// Para convertir a entero un String:

// Hay que cerrar el fichero una vez leído

También podría gustarte