Netwerkalgoritmen

Website:website containing additional information
Course code:INFONA
Credits:7.5 ECTS (=5.25 old credit points)
Period:periode 3 (week 6 t/m 16, dwz 2-2-2004 t/m 16-4-2004; herkansing week 21)
Participants:up till now 11 subscriptions
Schedule:Dit is een oud rooster!
formgrouptimeweekroomteacher
college   ma 15-176-8,10-15 BBL-505 Hans Bodlaender
  
wo 15-176-8,10-15 BBL-505
Contents:In veel toepassingen komen netwerken en grafen voor als model - voor de hand liggende voorbeelden zijn wegennetwerken, electrische schakelingen. Bij andere toepassingen ligt het graafmodel minder voor de hand, maar blijkt het ook heel nuttig te zijn, bijvoorbeeld roosteringsproblemen. In dit college wil zowel kijken naar de vertaling van probleemstelling naar netwerkmodel, als kijken naar algoritmische problemen en hun oplossingen op netwerken en grafen.

Aan de orde komen onder andere: kortste paden, stroming in netwerken, koppelingen, getrianguleerde grafen en boombreedte (met een toepassing in de probabilistische netwerken), tekenen van grafen.

In many applications, networks and graphs are used as a model. Tyical examples are networks of roads, or electronic networks. In other applications, the graph model may be less obvious, but appears to be very useful, like for scheduling problems. In this course, we look to the translation of problem to network model, and we look to algorithmic problems and their solutions on networks and graphs.

Some topics are: shortest paths, flow, matchings, triangulated graphs, treewidth (with an application in probabilistic networks), graph drawing.

Literature:Wordt tijdens college uitgereikt.

Will be handed out during the course.

Course form:Lectures, two per week. Exercises.
Exam form:Er zijn twee toetsen. Beide beslaan de helft van de collegestof. De toetsen tellen even zwaar. Daarnaast worden een aantal opgaven gegeven. Het eindcijfer is het gemiddelde van het cijfer voor de 1e toets, het cijfer voor de 2e toets, en het cijfer voor de 3e toets, tenzij een van deze cijfers lager dan 4 is. Het is mogelijk om in plaats van de toetsen een taak te doen/

There are two tests, each about half the materials of the course. Students also make a number of exercises. The end note is the average of the note for the first test, the note of the second test, and the average note for the exercises, unless one of these notes is less than 4.

It is possible to do some assignment instead of the tests.

Minimum effort to qualify for 2nd chance exam:Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.
wijzigen?