Praktisk Information
Undervisere: Valentin Goranko (322/127, vfgo@imm.dtu.dk) og Carsten
Witt (322/124, cawi@imm.dtu.dk)
Tid: onsdage 13.00-17.00
Sted: endnu ikke fastlagt
Projekter
Fagprojektet starter den 1/2-2011 kl. 13.00 med en
introduktionsforelæsning og præsentation af
standardprojekterne. Tilmelding til et standardprojekt sker i den
første uge. Ønsker man at skrive et
ikke-standardprojekt, skal det godkendes af de kursusansvarlige
inden kursusstart.
En liste over de 8 standardprojekter er
følgende. Se nedenfor for mere detaljeret
beskrivelse af projekterne.
Tilmelding til standardprojekt
Vigtige datoer i projektet (nogle af dem er
foreløbige):
7. februar: tilmeldingsfrist til standardprojekt.
8. februar: første forelæsning om projektstyring
(foreløbig dato)
15. februar: projektplan skal afleveres (via campusnet under
opgaver)
7. marts: anden forelæsning om projektstyring
(foreløbig dato)
21. marts: statusmøde 1
30. marts: revideret projektplan afleveres
11. april: tredje forelæsning om projektstyring
(foreløbig dato)
1. juni: statusmøde 2
11.-15. juni: aflevering af rapporter (nærmere aftales med
vejleder)
21.-22. juni: mundtlige eksaminer (nærmere aftales med
vejleder)
Detaljeret beskrivelse af standardprojekter
Standard project 1:
Rock solid Multimedia Integrated Development Environment or Visual
Programming Environment with tangible programming
Motivation: Today's software is plagued by bugs and the software
life involves many costly cycles. Think about it: name one
commercial software that does not have bugs or even that has been
designed within the planned budget! The Haskell programming
language (see [1]) allows one to separate the code that needs to
have side effects (changes to variables or status) from the code
that does not need to have side effects (that are very often the
source of bugs), to prove directly the correctness of the software,
and to have a very smooth and quick transition from design to
implementation. Haskell is a strongly-typed programming language
like Perl or Python, and it has strong advantages over Perl or
Python: Haskell has algebraic types, pattern matching, a
standardized language, an excellent compiler (the Glasgow Haskell
Compiler written in Haskell!), and a very nice syntax.
Description: The purpose of this project is to develop a module for
an Integrated Development Environment or a Visual Programming
Environment for Multimedia applications, that will use the Haskell
programming language (see [2]) and its libraries for tangible
values (TV, see [3]), and Gtk-based Graphical User Interface for
tangible values (GtkTV, see
[4]). The user will be able to design a multimedia application that
will incorporate graphics/image/animation/video/audio/music
renderers using the Haskell bindings for OpenGL, QuickTime, and
audio (see [5]) as well as tangible values ("visual and interactive
manifestations of pure values, including functions" _from
[6]_).
Prerequisites (optional): 02156 Formal Logical Systems or
02157
Functional Programming
Bibliographic references:
[1] http://haskell.org/haskellwiki/Haskell_in_industry
[2] http://haskell.org/haskellwiki/Introduction
[3] http://haskell.org/haskellwiki/TV
[4] http://hackage.haskell.org/package/GtkTV
[5] http://cs.yale.edu/c2/images/uploads/AudioProc-TR.pdf
[6] Conal Elliott, Tangible Functional Programming,
International
Conference on Functional Programming, 2007,
http://conal.net/papers/Eros/.
Contact: Michael Rose (mir@imm.dtu.dk) and Francois Anton
(fa@imm.dtu.dk)
--------------------------------------------------------------------------
Standard project 2:
K nearest neighbours for streaming data
In recent years, massive data sets have emerged in many
applications, including financial applications, network monitoring,
telecommunication data management, sensor networks, computer
network traffic, phone conversations, ATM transactions, web
searches. This phenomenon has led to increasing amounts of
information flowing taking the form of data streams. Data streaming
problems have engendered a large amount of interest among the
Algorithm, Database and Networking communities.
The kth order Delaunay triangulation and Voronoi diagram for a set
of generators (points) allow one to answer the nearest neighbour
and the k nearest neighbour problems efficiently. These problems
are found in the many different application fields mentionned
above. The kth order Voronoi diagram of a set of generators (points
in the plane) is the tessellation of the plane, where the tiles are
the regions of the plane that have the same k nearest points among
the set of generators.
The objective of this project is to implement a greedy algorithm
that keeps always the generators that minimize the Hausdorff
distance of the "old" Voronoi zone (before insertion of a new
generator) with respect to the "new" Voronoi zone after insertion
of a new generator.
The students will be given the description of the algorithm in
pseudo-code, the GEL library, that offers the geometric data
structure (half-edge) for storing the Delaunay triangulation and
the Voronoi diagram, and an implementation of the ordinary Voronoi
diagram for static sets. Students are free to use whichever
programming language.
Contact: Michael Rose (mir@imm.dtu.dk) and Francois Anton
(fa@imm.dtu.dk)
--------------------------------------------------------------------------
Standard project 3:
Optimale Postruter (fagområde: grafteori og algoritmik)
Projektbeskrivelse:
Hver dag går og cykler postbude tilsammen mere end 50.000km i
Danmark. Optimering af postruter kan derfor give anledning til
store besparelser. Formålet med dette projekt er at
implementere et program, der kan planlægge optimale
postruter. En postrute er optimal, hvis den distance postbuddet
går uden at levere post er mindst mulig. Postruterne skal
planlægges i en model af København, der er konstrueret
med data fra OpenStreetMap. OpenStreetMap er en gratis
crowdsource-baseret korttjeneste, der p.t. dækker ca. 97,2%
af det danske vejnet. Sammenlignet med proprietære
korttjenester har OpenStreetMap en utrolig god dækning af
småstier, gangveje, skovstier m.v., og denne information kan
være værdifuld ved planlægning af postruter.
Projektets hovedfokus er på de algoritmiske og grafteoretiske
udfordringer ved beregning af optimale postruter. De betragtede
algoritmer skal implementeres i et program, der kan beregne og
eventuelt visualisere optimale postruter i et passende udsnit af
København.
Projektet forudsætter kendskab til grafteori og algoritimik,
og det er et krav at studerende enten har gennemført kurset
01227 Grafteori eller har bestået 02105 Algoritmer og
datastrukturer 1 med en god karakter.
Contact: Hjalte Wedel Vildhøj (hwvi@imm.dtu.dk)
Optagelsesbegrænsning: maks. 2 grupper
--------------------------------------------------------------------------
Standard project 4:
An Interpreter for OCL in PROLOG
The Object Constraint Language (OCL) is a logical language to
express queries and constraints on models expressed in UML and
similar modeling languages. It combines elements of modal logic
with elements from programming languages like Java. The goal of
this project is to write an interpreter for an OCL-fragment on a
simplified representation of UML models, both of which shall be
implemented using SWI-Prolog. Therefore it is essential, that the
student has basic
Prolog programming experience.
Technically, the team will start by creating a scanner/parser using
Definite Clause Grammars, a compiler-compiler technology built into
Prolog. Next, navigational and equational expressions will have to
be covered. Then comes handling collections and quantifiers,
procedural abstraction and (recursive) procedure calling, basic
type checking, and meta-model access. Depending on the size of the
OCL fragment covered, this project can be scaled up or down to
cover more or less
of the above.
The team taking on this project will learn a good deal about OCL
and UML, and also about software engineering in general, and
particularly, using SWI-Prolog and the tools that come with it,
e.g. Javadoc-style HTML documentation generation from PROLOG-code,
unit testing, profiling, code visualization, advanced debugging,
Definite Clause Grammars, and so on. The project will be supervised
by Associate Professor Harald Störrle of IMM/DTU.
Contact: Harald Störrle (hsto@imm.dtu.dk, 322.024)
--------------------------------------------------------------------------
Standard project 5:
A Graphical User Interface (GUI) for weather radar and wind energy
data visualization and analysis
Background: Wind energy applications such as wind power prediction
require the use of large amounts of data. These data come from
multiple sources (e.g. onsite observations from measuring stations,
meteorological forecasts from Numerical Weather Prediction models,
images from weather radars) and, consequently, have very diverse
formats (times series, georeferenced data, gridded data). This
raises an important issue since there does not exist any common or
efficient platform for their visualization and analysis.
Objectives: Design a user-friendly GUI for enhancing the combined
visualization of several sources of data. The following initial
specifications will serve as a starting point for the
project:
- efficient system for data request, retrieval and
display,
- handling of animations (it is crucial as most data
consist of time series or of series of images),
- preferences should be given to open source
softwares/programming languages/solutions,
- operationability of the final GUI on web browsers
will be considered.
Besides proposing innovative solutions to the given problem, it is
expected that the students will document and justify their choices
(e.g. by taking into account potential extensions of the final
product in the future).
Supervision: The work will be supervised by Associate Professor
Pierre Pinson and PhD Student Pierre-Julien Trombe from DTU
Informatics (Mathematical Statistics Section).
Contact: Pierre Pinson (pp@imm.dtu.dk) and Pierre-Julien Trombe
(pjt@imm.dtu.dk)
--------------------------------------------------------------------------
Standard project 6:
Compiling (object-oriented|dynamic|your own) languages
Compilers are at the heart of our software development processes;
they connect the developed code with the underlying hardware.
In this project you will develop a compiler for some language of
your choice, and will target some hardware of your choice. Each
language and target platform has its own peculiarities, and you
will learn about techniques used in optimizing compilers, about
optimizations and analyzes, and about code generation.
The languages we suggest are Java, JavaScript, and, well, your own
language - or you could choose to extend Java or JavaScript with
some features not present yet.
The project is ideally suited for groups of 3-5 students, and can
be split up into modules with clearly defined interfaces.
Contact: Christian Probst (probst@imm.dtu.dk) and Sven Karlsson
(ska@imm.dtu.dk)
--------------------------------------------------------------------------
Standard project 7:
Visualizing nature-inspired metaheuristics for optimization
problems
Nature-inspired metaheuristics such as evolutionary algorithms,
simulated annealing and ant colony optimization are often applied
to hard optimization problems. In this project, we develop a Java
framework that visualizes the working principles of nature-inspired
metaheuristics for the solution of combinatorial optimization
problems, most notably
the traveling salesperson problem (TSP).
As minimum, the framework should allow the following:
- Search spaces: bit strings and permutations (i.e. TSP
tours)
- Nature-inspired algorihms: simulated annealing, an evolutionary
algorithm, an ant colony optimization algorithm
- Problems:
- test functions OneMax and LeadingOnes
- selected TSP instances from the TSPlib library
(http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/)
- Visualize the constructed solutions for two-dimensional TSP
instances
Flexibility and modularity of your implementations are desirable.
If further problem classes, heuristics and visualizations are
covered, this will be assessed positively.
Contact: Valentin Goranko (vfgo@imm.dtu.dk) and Carsten Witt
(cawi@imm.dtu.dk)