Contenidos del curso

Conceptos Básicos
Arquitectura de Computadores
Programación C
Sistemas Operativos
Programación de Sistemas

Lecciones

Presentación

Lección 0

Sept 30

Introducción al Curso de Computadores

Computadores

Lección 1		Computadores e Internet
Leccion 2		Arquitectura de Computadores
Leccion 3		Sistemas Operativos

Programación C

Lección 4		Programación en C
Lección 5		Entornos de desarrollo
Leccion 6		Desarrollo de sistemas empotrados

Sistemas Operativos

Lección 7		Estructura de un sistema operativo
Lección 8		Servicios basicos de un Sistema Operativo
Lección 9		Sistema Operativo Linux

Programación de Sistemas

Leccion 10		Programación de Sistemas
Leccion 11		POSIX
Leccion 12		POSIX API
		POSIX Function calls: POSIX.1, POSIX.1b and POSIX.1c Open Group UNIX 03 Status

Trabajo de Curso

Descripción

El trabajo del curso 2005-2006 consiste en el desarrollo de un programa para resolver Sudokus.

Ejemplo de sudoku

El programa leerá el Sudoku de un fichero de entrada compuesto de nueve líneas de nueve caracteres cada una. Los caracteres del fichero de entrada pueden ser dígitos o guiones de subrayado.

_6_1_4_5_
__83_56__
2_______1
8__4_7__6
__6___3__
7__9_1__4
5_______2
__72_69__
_4_5_8_7_

Fichero de entrada del ejemplo anterior.

Este es el fichero de entrada correpondiente a este ejemplo.

El programa producirá la salida en un fichero con el mismo formato.

Solución al sudoku anterior

El programa se llamará "sudoku" y aceptará tres argumentos en linea de comandos:

El nombre del fichero de entrada (el sudoku a resolver)
El nombre del fichero de salida
El tiempo máximo (en milisegundos) para producir la salida. Este argumento es opcional.

El ultimo argumento indica el tiempo máximo concedido para resolver el sudoku. El programa debe producir el fichero de salida en un tiempo menor o igual a este tiempo límite. En caso de alcanzar el tiempo límite el programa generará un fichero de salida con una solución parcial. Si el ultimo argumento no se incluye se entenderá que no hay tiempo límite.

Si el sudoku tiene solucion el programa terminará devolviendo un código de retorno '0' y si no tiene solución devolverá un código de retorno '1'.

Organización

El trabajo del curso se realizará de forma individual.

Entrega y Evaluación

El kit de evaluación a entregar se compondrá de:

Código fuente ANSI/ISO C
Memoria del trabajo (detalles del proceso de desarrollo con los principales problemas y formas de solución).

La entrega se hará por correo electrónico a Ricardo.Sanz@etsii.upm.es en forma de "attachment" de un solo fichero .tar.gz con el número de matrícula como nombre del fichero (por ejemplo 99342.tar.gz).

La entrega se hará antes del examen de febrero.

Los programas se evaluarán automáticamente empleando una batería de sudokus de prueba y diferentes límites temporales. Las calificaciones se harán en base a los resultados obtenidos y realizando una ordenación en función de la efectividad temporal (esto es, obtendrá mayor calificacion el trabajo cuyo programa sea más rápido en resolver sudokus). Todos los programas deben ser capaces de resolver cualquier sudoku si no hay tiempo límite o ser capaces de determinar que no hay solución.

Calificaciones finales

Resultados de la Evaluación de Trabajos

Etapas de la evaluación

Resultados de los tests

Ficheros de prueba: Sudoku01.in Sudoku02.in Sudoku03.in

Enlaces

Por supuesto, Google.

La wikipedia es siempre un recurso.

Algunos heurísticos para solucionarlo.

Algunas pistas sobre algoritmos de búsqueda.

Algunas distribuciones de GCC para MS Windows son CygWin, MinGW, GNUWin.
La distribución recomendada para este trabajo es CygWin.

Un programa inspirador sobre como temporizar el resolvedor de sudokus.

Información sobre GDB: manual y referencia rápida.

The Open Group Single UNIX Specification

Entregas

Lista de entregas hasta el 1 de Febrero de 2006:

Matricula	Nombre	Entrega	Fecha	Verificación	Nota
00195	Lalo Grande	00195.tar.gz	18/1/2006	OK
02504	Matias Trocki	02504.tar.gz	19/1/2006	OK
97135	Manuel Fernández	97135.tar.gz	19/1/2006	OK
05783	Stefan Müller	05783.tar.gz	24/1/2006	OK
02288	Alberto Moreno	02288.tar.gz	26/1/2006	OK
00313	Juan Morago	Varios ficheros	26/1/2006	OK
05488	Luis Bracho	05488.tar.gz	26/1/2006	OK
02307	María Oyarzábal	02307.tar.gz	27/1/2006	OK
02335	Paloma de la Puente	02335.tgz	27/1/2006	OK
02089	Pedro Conejo	02089.tar.gz	28/1/2006	OK
00013	Luis Alonso	00013.tar.gz	28/1/2006	OK
01762	Victor Martin	01762.tar.gz	29/1/2006	OK
00146	Eduardo Fuentes	00146.tzr.gz	30/1/2005 +	OK
00359	Edmundo Pérez-Íñigo	00359.tzr.gz	30/1/2006	OK
05831	Pascal Osman	05831.tar.gz	31/1/2006	OK
01238	Luis Jiménez	Varios ficheros	31/1/2006	OK
01323	Felipe Montero	Varios ficheros	31/1/2006	OK
05796	Benjamin Brunner	05796.tar	31/1/2006	OK
98022	Antonio Álvarez	98022.rar	31/1/2006 +	OK
99103	David Cortés	99103.tar.gz	31/1/2006	OK
05822	Andrew Egan	05822.tar.gz	31/1/2006	OK
01282	Raul Marcos	01282.tar.gz	31/1/2006	OK
00433	Alberto Turrión	Varios ficheros	31/1/2006	OK
02355	Diego Rodriguez	02355.tar.gz	31/1/2006	OK
01248	Julio Larriba	01248.tar.gz	31/1/2006 +	OK
01210	Gonzalo Guadano	Varios ficheros	31/1/2006	OK
00337	Jaime Orozco	00337.tar	1/2/2006	OK
02054	Lara Briñon	02054.tar	1/2/2006	OK
00168	Julio García-Polo	00168.zip	1/2/2006	Falta la memoria
00334	Fernando Olivera	00334.tar.gz	1/2/2006	OK
00249	Diego López	00249.tar.gz	1/2/2006 +	OK
01748	Alfonso Grau	01748.tar.gz	1/2/2006	OK
02632	Juan Jenaro	Varios ficheros	1/2/2006	OK
00087	Sergio Centeno	Varios ficheros	1/2/2006	OK
01341	David Navarro	Varios ficheros	1/2/2006	OK
99105	Sergio Covo	99105.tar.gz	2/2/2006	OK

OK: El trabajo ha sido recibido y descomprimido. No indica que el trabajo es correcto.
+: El trabajo ha sido re-enviado.

Trabajos Adicionales de Curso

Descripción

Se valorará la participación en las actividades complementarias del curso.

Actividad 1

Read Alan M. Turing’s Computing machinery and intelligence
Published in MIND : A Quarterly Review of Psychology and Philosophy, (Vol. LIX, N.S. No.236, Oct. 1950).

Send 500-1000 word comment before Oct 14 by email