head 1.22; access; symbols; locks iea:1.22; strict; comment @# @; 1.22 date 2003.09.12.13.47.35; author iea; state Exp; branches; next 1.21; 1.21 date 2002.04.09.08.37.14; author iea; state Exp; branches; next 1.20; 1.20 date 2002.03.20.20.51.15; author iea; state Exp; branches; next 1.19; 1.19 date 2002.02.28.12.58.02; author iea; state Exp; branches; next 1.18; 1.18 date 2002.02.18.15.43.32; author iea; state Exp; branches; next 1.17; 1.17 date 2001.10.04.11.56.03; author iea; state Exp; branches; next 1.16; 1.16 date 2001.10.04.11.41.09; author iea; state Exp; branches; next 1.15; 1.15 date 2001.09.14.20.42.06; author iea; state Exp; branches; next 1.14; 1.14 date 2001.09.14.20.12.25; author iea; state Exp; branches; next 1.13; 1.13 date 2001.05.21.16.32.07; author iea; state Exp; branches; next 1.12; 1.12 date 2001.05.03.18.06.51; author iea; state Exp; branches; next 1.11; 1.11 date 2001.05.03.18.06.27; author iea; state Exp; branches; next 1.10; 1.10 date 2001.04.03.15.30.13; author iea; state Exp; branches; next 1.9; 1.9 date 2001.04.02.17.09.05; author iea; state Exp; branches; next 1.8; 1.8 date 2001.04.02.17.07.39; author iea; state Exp; branches; next 1.7; 1.7 date 2001.04.02.17.00.47; author iea; state Exp; branches; next 1.6; 1.6 date 2001.03.08.16.12.50; author iea; state Exp; branches; next 1.5; 1.5 date 2001.03.08.16.11.09; author iea; state Exp; branches; next 1.4; 1.4 date 2001.03.06.18.56.55; author iea; state Exp; branches; next 1.3; 1.3 date 2001.03.06.18.55.17; author iea; state Exp; branches; next 1.2; 1.2 date 2001.03.06.18.33.58; author iea; state Exp; branches; next 1.1; 1.1 date 2001.03.06.18.30.05; author iea; state Exp; branches; next ; desc @@ 1.22 log @*** empty log message *** @ text @ Practicas de IEA

Información sobre las prácticas de IEA

Desde esta página se puede acceder a la normativa de prácticas y los enunciados de prácticas. Asimismo, en esta página encontraréis  documentos software y herramientas que facilitan en gran medida el desarrollo de las prácticas de la asignatura. La mayoría del software que aquí se menciona es gratuito. Puede obtenerse sin más, descargándolo por Internet.

Recomendamos leer atentamente los contenidos de esta página ya que algunas de las informaciones que aquí se dan os serán imprescindibles para la realización de la práctica y otras os pueden ser muy útiles.


Información sobre C++

Las prácticas de la asignatura se desarrollarán en el lenguaje de programación C++. Existen abundantes libros sobre el lenguaje C++ y libros sobre estructuras de datos y algoritmos que utilizan C++ como vehículo para presentar los conceptos teóricos, p.e. Algorithms in C++ de R. Sedgewick o Data Structures and Algorithm Analysis in C++ de M.A. Weiss. Además también hay numerosos tutoriales de C++ y de su biblioteca estándar (Standard Template Library, STL) accesibles a través de Internet:
Enlaces en Internet:
Documentos:
Además existen varios grupos de notícias (comp.lang.c++.*) relacionados con C++.

En los entornos Unix/Linux recomendamos usar el compilador gcc de GNU. Éste es el compilador que se utiliza en el entorno Solaris del LCFIB (moonrey.fib.upc.es). Para MS-DOS/Windows debe utilizarse el compilador de Microsoft (Visual C++ 6.0). Aquí encontraréis algunos enlaces a información útil sobre compiladores y entornos de programación:



Informaciones diversas

Un apartado importante en la elaboración de la práctica es la documentación. Una herramienta extremadamente potente para la preparación de la documentación es TeX. TeX es un sistema para la preparación de documentos del tipo markup, como SGML o HTML, por contraposición a los procesadores de textos convencionales WYSIWYG (what you see is what you get), aunque existen algunos programas híbridos, como LyX, donde se emplea una interfaz similar a la de Microsoft Word u otros procesadores de textos WYSIWYG, pero el documento se almacena internamente en el formato TeX, que puede ser modificado llegado el caso. TeX es particularmente conveniente cuando se han de preparar documentos en los que se manejen fórmulas, símbolos, citas bibliográficas, ecuaciones, etc. Es aconsejable emplear LaTeX,  una variante de TeX, ya que ofrece múltiples facilidades incluyendo la generación automática de tablas de contenidos, numeración automática de secciones, subsecciones y ecuaciones, preparación semi-automática de las referencias bibliográficas, referencias cruzadas simbólicas, macros para crear tablas, macros para la inclusión de gráficos, ... Para obtener información sobre TeX, puede comenzarse en la página Web del  TeX Users Group, en las páginas de CervanTeX  (usuarios hispanohablantes) o en las páginas de Tirant lo TeX (usuarios catalanohablantes).
TeX, LaTeX y otros muchos programas relacionados, y toda la documentación pertinente son de dominio público y están disponibles para todo tipo de plataformas y sistemas operativos en la CTAN (Comprehensive TeX Archive Network).  No obstante, podéis preparar la documentación de la asignatura utilizando cualquier sistema, aunque no sea TeX o LaTeX.

TeX fue concebido e implementado por D. E. Knuth .

También fue Knuth quien introdujo el concepto de programación literaria (literate programming, LP): consiste en desarrollar los programas y su documentación simultáneamente. También podéis leer el fichero de preguntas frecuentes.

La idea es la siguiente: los ficheros contienen tanto el código (en Pascal, C, C++, ...) como la documentación (en  TeX, LaTeX, troff, ...). Se dispone de sendos programas para extraer el código o la documentación, a partir de esos ficheros. Knuth implementó el sistema WEB, que combina Pascal y TeX, como demostración práctica de su idea. Más tarde, otros programadores e investigadores han creado otras variantes como CWEB (C/TeX) o noweb (*/LaTeX). Por ejemplo, el equipo que ha desarrollado y mantiene LEDA está empleando estas técnicas para documentar la librería, de modo que la documentación siempre sea consistente con el código. Para aquellos de vosotros con ganas de explorar este campo, puede ser una experiencia interesante ... Muchas herramientas de LP son gratuitas y están disponibles para diversos sistemas operativos, y también pueden encontrarse en la CTAN.

Finalmente, si estás usando Linux o UNIX hay herramientas como gnuplot (formando parte del paquete 'plotutils'), con las que resulta sencillo preparar las gráficas experimentales. También puede utilizarse sistemas como Maple, Mathematica o MuPAD, que ofrecen buenas posibilidades gráficas y están disponibles para Windows '95 y para Unix; en particular, Maple V está a vuestra disposición en la red de PCs de la FIB.


 [ Página principal de IEA | Página principal de LSI | Página principal de la FIB | Página principal de la UPC ]
 
 
 




@ 1.21 log @*** empty log message *** @ text @d1 213 a213 361 Practicas de IEA


Información sobre las prácticas de IEA

Desde esta página se puede acceder a la normativa de prácticas y los enunciados de prácticas. Asimismo, en esta página encontraréis  documentos software y herramientas que facilitan en gran medida el desarrollo de las prácticas de la asignatura. La mayoría del software que aquí se menciona es gratuito. Puede obtenerse sin más, descargándolo por Internet.

Recomendamos leer atentamente los contenidos de esta página ya que algunas de las informaciones que aquí se dan os serán imprescindibles para la realización de la práctica y otras os pueden ser muy útiles.


Información sobre C++

Las prácticas de la asignatura se desarrollarán en el lenguaje de programación C++. Existen abundantes libros sobre el lenguaje C++ y libros sobre estructuras de datos y algoritmos que utilizan C++ como vehículo para presentar los conceptos teóricos, p.e. Algorithms in C++ de R. Sedgewick o Data Structures and Algorithm Analysis in C++ de M.A. Weiss. Además también hay numerosos tutoriales de C++ y de su biblioteca estándar (Standard Template Library, STL) accesibles a través de Internet:

Enlaces en Internet:
Documentos:

Además existen varios grupos de notícias (comp.lang.c++.*) relacionados con C++.

En los entornos Unix/Linux recomendamos usar el compilador gcc de GNU. Éste es el compilador que se utiliza en el entorno Solaris del LCFIB (moonrey.fib.upc.es). Para MS-DOS/Windows debe utilizarse el compilador de Microsoft (Visual C++ 6.0). Aquí encontraréis algunos enlaces a información útil sobre compiladores y entornos de programación:


Información básica y documentación sobre LEDA

Para la realización de las prácticas se habrá de utilizar LEDA  (Library of Efficient Data Structures and Algorithms). Recientemente, LEDA ha dejado de ser gratuita para investigadores y estudiantes, y actualmente se requiere una licencia para su uso. No obstante, disponemos de la última versión gratuita (versión 4.1) para las prácticas; podréis incluso instalarla en casa. Tened en cuenta que no se puede usar para el desarrollo de aplicaciones comerciales ni distribuir a terceros.

Actualmente LEDA 4.1 está instalada sobre el entorno Solaris (moonrey.fib.upc.es), y en los PCs del LCFIB para Windows 9*/NT y para Linux.

La librería LEDA trabaja sobre C++ y ofrece diversos tipos abstractos de datos incluyendo diccionarios, colas de prioridad, particiones (mfsets),  grafos (dirigidos, no dirigidos, etiquetados, no etiquetados, ...), así como facilidades para la creación de interfaces gráficas. Soporta varios formatos (p.e. GML) para entrada/salida de grafos. El móduloGraphWin permite crear potentes interfícies gráficas con poco esfuerzo. Además existen otras librerías y paquetes que pueden utilizarse junto a LEDA y amplian su funcionalidad. Por ejemplo, la librería ADG, que funciona sobre LEDA, proporciona numerosos algoritmos de visualización de grafos.

Atención: No está permitido usar ninguna de las rutinas del módulo graph_algde LEDA en vuestra práctica!

Documentación sobre LEDA

LEDA es una librería con muchas clases y módulos y, consecuentemente, su manual es extenso. El manual de LEDA 4.1 está disponible en Postscript (Postscript/Gzip, 668 Kb).
Otras alternativas para consultarlo son la versión on-line en HTML (pulsa aquí para obtener un fichero .tar.gz con el manual on-line; ocupa 431 Kb comprimido) y la copia impresa de la que se dispone en el LCFIB (de la versión 3.7; las diferencias respecto a la versión 4.1 son pequeñas). El libro LEDA: A Platform for Combinatorial and Geometric Computing, escrito por los autores de LEDA, K. Mehlhorn y S. Näher, está disponible en la biblioteca BRGF de la UPC y es la referencia más completa.

Aunque el manual contiene toda la información que puede precisarse, es bastante espartano y
conviene leer algunos capítulos del libro mencionado. Alternativamente pueden leerse los siguientes documentos (borradores iniciales del libro):

Desgraciadamente algunas de las páginas de estos ficheros están corruptas y pueden dar algunos problemas al imprimir. Los dos últimos ficheros ocupan mucho, porque están llenos de figuras, diagramas, ... Puede ser aconsejable consultarlos on-line e imprimir sólo las páginas imprescindibles o fotocopiar las páginas del libro relevantes.

El siguiente tutorial pertenece al reciente libro Algorithms on Trees and Graphs de G. Valiente y describe las principales estructuras de datos que ofrece LEDA y su uso. Puede resultar bastante útil, aunque no describe los módulos de LEDA para la creación de interfícies gráficas. Todos los algoritmos del libro están escritos usando LEDA y en su mayor parte el libro trata de algoritmos y técnicas como las que se explican en esta asignatura.

Otras fuentes adicionales de información sobre LEDA son las listas de discusión de usuarios de LEDA y el grupo de noticias sobre LEDA.

Descarga de la librería LEDA

Pulsa aquí para acceder a la página de descarga de LEDA. Te solicitará una contraseña, que es la que os hemos proporcionado en clase. Si no la tienes, envía un mensaje a iea@@lsi.upc.es.

Si tenéis problemas para instalaros LEDA en casa es aconsejable que consultéis   la lista de discusión de LEDA: puede que el problema lo haya solucionado antes alguien. Si no es así enviad vuestra pregunta a la lista de discusión, es bastante probable que os den una respuesta pronto y satisfactoria.

Compilación con LEDA

Podréis compilar programas que usan LEDA sin (demasiadas ;-) dificultades sobre Solaris,  sobre Linux y sobre Windows 9*/Windows NT (usando Visual C++ 6.0). En esta página se describen los comandos a utilizar para compilar con LEDA en los diversos entornos del LCFIB.

El entorno de trabajo en los laboratorios de IEA es Solaris, pero LEDA está también instalada en otros entornos del LCFIB y resulta sencillo instalarla en un equipo particular.  


Informaciones diversas

El formato GML (Graph Modelling Language) permite especificar en ficheros de texto todo tipo de grafos, dirigidos y no dirigidos, etiquetados y no etiquetados.  Este formato se está convirtiendo en un estándar de facto para el intercambio de datos entre programas que usan grafos; son muchas las aplicaciones y librerías que son capaces de procesar GML, incluyendo la librería LEDA y las librerías/clases estándar de Java.

La librería LEDA y en concreto GraphWin os permite generar un fichero Postscript con los contenidos de una ventana de edición de grafos (graphwin) lo que puede ser muy útil para incluir ejemplos y facilitar las explicaciones en la documentación de las prácticas.

Para crear los juegos de pruebas naturalmente habrá que incluir la opción de generación aleatoria, pero también es posible que queráis experimentar utilizando datos reales para construir los grafos. En general será necesario hacer un pequeño programa que preprocese los datos existentes y genere un fichero GML. Por ejemplo, podemos tener un fichero con las distancias kilométricas entre todas las ciudades de una región. A estos datos les corresponde de manera natural un grafo no dirigido completo, pero por eso será necesario un pequeño programa que lea el fichero original y que escriba un fichero GML que describe el grafo en cuestión.

Por ejemplo, D. E. Knuth, autor de la conocida serie de libros The Art of Computer Programming, ha desarrollado la Stanford GraphBase, un conjunto de librerías, juegos de pruebas (reales) y programas de demostración  escritos en C (de hecho, escritos en CWEB, ver el apartado  dedicado a las herramientas de documentación). Otro punto de partida para explorar Internet en busca de información sobre algoritmos, estructuras de datos, etc.  es  The Stony Brook Algorithms Repository.

Un apartado importante en la elaboración de la práctica es la documentación. Una herramienta extremadamente potente para la preparación de la documentación es TeX. TeX es un sistema para la preparación de documentos del tipo markup, como SGML o HTML, por contraposición a los procesadores de textos convencionales WYSIWYG (what you see is what you get), aunque existen algunos programas híbridos, como LyX, donde se emplea una interfaz similar a la de Microsoft Word u otros procesadores de textos WYSIWYG, pero el documento se almacena internamente en el formato TeX, que puede ser modificado llegado el caso. TeX es particularmente conveniente cuando se han de preparar documentos en los que se manejen fórmulas, símbolos, citas bibliográficas, ecuaciones, etc. Es aconsejable emplear LaTeX,  una variante de TeX, ya que ofrece múltiples facilidades incluyendo la generación automática de tablas de contenidos, numeración automática de secciones, subsecciones y ecuaciones, preparación semi-automática de las referencias bibliográficas, referencias cruzadas simbólicas, macros para crear tablas, macros para la inclusión de gráficos, ... Para obtener información sobre TeX, puede comenzarse en la página Web del  TeX Users Group, en las páginas de CervanTeX  (usuarios hispanohablantes) o en las páginas de Tirant lo TeX (usuarios catalanohablantes).
TeX, LaTeX y otros muchos programas relacionados, y toda la documentación pertinente son de dominio público y están disponibles para todo tipo de plataformas y sistemas operativos en la CTAN (Comprehensive TeX Archive Network).  No obstante, podéis preparar la documentación de la asignatura utilizando cualquier sistema, aunque no sea TeX o LaTeX.

TeX fue concebido e implementado por D. E. Knuth .

También fue Knuth quien introdujo el concepto de programación literaria (literate programming, LP): consiste en desarrollar los programas y su documentación simultáneamente. También podéis leer el fichero de preguntas frecuentes.

La idea es la siguiente: los ficheros contienen tanto el código (en Pascal, C, C++, ...) como la documentación (en  TeX, LaTeX, troff, ...). Se dispone de sendos programas para extraer el código o la documentación, a partir de esos ficheros. Knuth implementó el sistema WEB, que combina Pascal y TeX, como demostración práctica de su idea. Más tarde, otros programadores e investigadores han creado otras variantes como CWEB (C/TeX) o noweb (*/LaTeX). Por ejemplo, el equipo que ha desarrollado y mantiene LEDA está empleando estas técnicas para documentar la librería, de modo que la documentación siempre sea consistente con el código. Para aquellos de vosotros con ganas de explorar este campo, puede ser una experiencia interesante ... Muchas herramientas de LP son gratuitas y están disponibles para diversos sistemas operativos, y también pueden encontrarse en la CTAN.

Finalmente, si estás usando Linux o UNIX hay herramientas como gnuplot (formando parte del paquete 'plotutils'), con las que resulta sencillo preparar las gráficas experimentales. También puede utilizarse sistemas como Maple, Mathematica o MuPAD, que ofrecen buenas posibilidades gráficas y están disponibles para Windows '95 y para Unix; en particular, Maple V está a vuestra disposición en la red de PCs de la FIB.


 [ Página principal de IEA | Página principal de LSI | Página principal de la FIB | Página principal de la UPC ]
 
 
 

@ 1.20 log @*** empty log message *** @ text @d230 1 a230 1

Compilación con LEDA

d234 1 a234 2 9*/Windows NT (usando comandos de línea del compilador de C++ de Microsoft (Visual C++ 6.0)). En esta página se describen los d34 1 a34 1 Normativa general y enunciados @ 1.18 log @*** empty log message *** @ text @d25 1 a25 2 Internet. A veces habrá que obtener una licencia previa (gratuita) y entonces descargarlo.

a31 1
d34 1 a34 1 Normativa general y enunciados d40 4 a43 2
 

Información sobre C++

d48 1 a48 1 de datos y algoritmos que utilizan C++ como vehículo de los d55 2 d69 4 d78 2 a79 1 d105 62 a166 36

Información básica y documentación sobre LEDA

Para la realización de las prácticas se habrá de utilizar LEDA  (Library of Efficient Data Structures and Algorithms). Recientemente, LEDA ha dejado de ser gratuita para investigadores y estudiantes, y actualmente se requiere una licencia para su uso. No obstante, disponemos de la última versión gratuita (versión 4.1) para las prácticas; podréis incluso instalarla en casa. Pero no se puede usar para el desarrollo de aplicaciones comerciales ni distribuir a terceros. Actualmente está disponible sobre el entorno Solaris (moonrey.fib.upc.es), y en los PCs del LCFIB para Windows 9*/NT y para Linux.

LEDA es una librería con muchas clases y módulos y, consecuentemente, su manual es extenso. El manual de LEDA 4.1 está disponible en Postscript (Postscript/Gzip, 668 Kb).
Otras alternativas para consultarlo son la versión on-line en HTML (pulsa aquí para obtener un fichero .tar.gz con el manual on-line; ocupa 431 Kb comprimido) y la copia impresa de la que se dispone en el LCFIB (de la versión 3.7; las diferencias respecto a la versión 4.1 son pequeñas). El libro LEDA: A Platform for Combinatorial and Geometric Computing, escrito por los autores de LEDA, K. Mehlhorn y S. Näher, está disponible en la biblioteca BRGF de la UPC y es la referencia más completa.

Aunque el manual contiene toda la información que puede precisarse, es bastante espartano y
conviene leer algunos capítulos del libro mencionado. Alternativamente pueden leerse los siguientes documentos (borradores iniciales del libro): d193 16 a208 6 imprimir sólo las páginas imprescindibles o fotocopiar las páginas del libro relevantes.

Otras fuentes adicionales de información sobre LEDA son la  lista de discusión de usuarios de LEDA y un La librería LEDA trabaja sobre C++ y ofrece diversos tipos abstractos de datos incluyendo diccionarios, colas de prioridad, particiones (mfsets),  grafos (dirigidos, no dirigidos, etiquetados, no etiquetados, ...), así como facilidades para la creación de interfaces gráficas. Soporta el formato GML (mirad el punto dedicado a GML) para entrada/salida de grafos, y la librería GraphWin permite crear un editor/visualizador de grafos en poco tiempo. LEDA esta disponible para Windows 95, Linux  y SunOS 5.* (Solaris), entre otros. Además puede utilizarse la librería ADG en conjunción con LEDA, si se quiere disponer de más algoritmos de visualización de grafos.

Pero no está permitido usar ninguna de las rutinas del módulo graph_alg de LEDA en vuestra práctica!
 

Compilación con LEDA 4.1

Podréis compilar programas que usan LEDA sin (demasiadas ;-) dificultades sobre Solaris,  sobre Linux y sobre Windows 9*/Windows NT (usando comandos de línea del compilador de C++ de Microsoft (Visual C++ 6.0)). En esta página se describen los comandos a utilizar para compilar con LEDA en los diversos entornos del LCFIB.

El entorno de trabajo en los laboratorios de IEA es Solaris, pero LEDA está también instalada en otros entornos del LCFIB y resulta sencillo instalarla en un equipo particular.  

Si tenéis problemas para instalaros LEDA en casa es aconsejable que consultéis   la lista de discusión de LEDA: puede que el problema lo haya solucionado antes alguien. Si no es así enviad vuestra pregunta a la lista de discusión, es bastante probable que os den una respuesta pronto y satisfactoria.

d242 2 a243 1

Informaciones diversas

@ 1.17 log @*** empty log message *** @ text @d10 1 a10 1 d12 1 a12 1

Departament de Llenguatges i Sistemes Informàtics d36 3 a38 3 Normativa general y enunciados

  • Listado provisional de grupos de prácticas
  • d319 2 a320 2 IEA | Página principal de LSI | Página @ 1.16 log @*** empty log message *** @ text @d21 13 a33 11

    Desde esta página se puede acceder a la normativa de prácticas y los enunciados de prácticas. Asimismo, en esta página encontraréis  documentos software y herramientas que facilitan en gran medida el desarrollo de las prácticas de la asignatura. La mayoría del software que aquí se menciona es gratuito. Puede obtenerse sin más, descargándolo por Internet. A veces habrá que obtener una licencia previa (gratuita) y entonces descargarlo.

    Recomendamos leer atentamente los contenidos de esta página ya que algunas de las informaciones que aquí se dan os serán imprescindibles para la realización de la práctica y otras os pueden ser muy útiles. d37 2 a38 2

  • Normativa general y enunciados
  • d40 1 a40 1 prácticas
    d46 12 a57 7

    Las prácticas de la asignatura se desarrollarán en el lenguaje de programación C++. Existen abundantes libros sobre el lenguaje C++ y libros sobre estructuras de datos y algoritmos que utilizan C++ como vehículo de los conceptos teóricos, p.e. Algorithms in C++ de R. Sedgewick o Data Structures and Algorithm Analysis in C++ de M.A. Weiss. Además también hay numerosos tutoriales de C++ y de su biblioteca estándar (Standard Template Library, STL) accesibles a través de Internet: