Wie erstellt man geschickt einen Stundenplan mit Mitteln der Informatik? Moritz Muhlenthaler ¨ [email protected] Hardware-Software-Co-Design ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ 2. November 2011 ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 1 ¨ Ubersicht 1 ¨ Stundenplane fur ¨ Groß und Klein 2 Stundenplanprobleme an der Uni 3 ¨ ¨ Stundenplane erstellen: Konflikte und Farbungen 4 Ausblick ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 2 In der Grundschule. . . Lehrer Klassen ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 1a 2b 3c 3 In der Unter- und Mittelstufe. . . Lehrer ¨ Facher Mathe Deutsch Chemie Klassen 7a 8b 9c ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 4 In der Kollegstufe Lehrer ¨ Facher Mathe (GK) Deutsch (GK) Chemie (LK) Schuler ¨ ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 5 An der Uni. . . Dozenten Vorlesungen Mathe fur ¨ Ing. BFS AuD Studierende ¨ Ahnlich zur Kollegstufe: Individueller Stundenplan fur ¨ jeden Studierenden ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 6 Kollegstufe versus Uni Kollegstufe Uni Studierende/Schuler ¨ ca. 200 25000 insgesamt, TechFak: 8000 ¨ Vorlesungen/Facher ca. 20 TechFak: ca. 300 An der Uni: Gemenge aus Wahl-, Pflicht- und Nebenfachvorlesungen ¨ Gebaude sind uber ganz Nurnberg und Erlangen verteilt ¨ ¨ ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 7 Was ist gesucht? (1) Gesucht: Wochenplan SP BFS AuD ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ GTI 8 Was ist gesucht? (1) Gesucht: Wochenplan SP BFS AuD GTI ¨ TechFak: 30 Zeitslots, 40 Raume und 300 Vorlesungen ergeben 9.404842045 × 10905 ¨ ¨ mogliche Wochenplane! ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 8 Was ist gesucht? (2) ¨ Aber: Nicht jeder theoretisch mogliche Stundenplan ist sinnvoll Mindestanvorderungen: 1. keine Doppelbelegungen ¨ zwei Vorlesungen gleichzeitig 2. kein Dozent halt ¨ 3. jeder Studierende kann alle Pflichtvorlesungen horen Jeder Studenplan, der diese Voraussetzungen erfullt ¨ ist akzeptabel ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 9 Was ist gesucht? (3) ¨ Wir mochten einen guten Stundenplan erstellen! Typische Zusatzanforderungen: 1. 2. 3. 4. ¨ ¨ ¨ moglichst keine Uberbuchung der Raume ¨ moglichst keine Leerlaufzeiten ¨ moglichst geringe Reisezeiten ¨ moglichst viele freie Tage fur ¨ Studierende und Dozenten ¨ Verschiedene Zusatzanforderungen konnen sich widersprechen ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 10 Was ist gesucht? (3) ¨ Wir mochten einen guten Stundenplan erstellen! Typische Zusatzanforderungen: 1. 2. 3. 4. ¨ ¨ ¨ moglichst keine Uberbuchung der Raume ¨ moglichst keine Leerlaufzeiten ¨ moglichst geringe Reisezeiten ¨ moglichst viele freie Tage fur ¨ Studierende und Dozenten ¨ Verschiedene Zusatzanforderungen konnen sich widersprechen Gesucht: Stundenplan, der die Mindestanforderungen erfullt ¨ und die ¨ Zusatzbedingungen soweit moglich berucksichtigt ¨ ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 10 Konflikte bei der Vorlesungsplanung EffAlg AuD BFS SP SoSy ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SYSSEC 11 Konflikte bei der Vorlesungsplanung EffAlg AuD Wanka BFS SP ¨ Kleinoder SoSy ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SYSSEC 11 Konflikte bei der Vorlesungsplanung EffAlg AuD Wanka Sem. 3 BFS SP ¨ Kleinoder SoSy ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SYSSEC 11 ¨ Farbungen (1) EffAlg AuD Wanka Sem. 3 BFS SP ¨ Kleinoder SoSy ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SYSSEC 12 ¨ Farbungen (1) EffAlg AuD Wanka Sem. 3 BFS SP ¨ Kleinoder SoSy ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SYSSEC 12 ¨ Farbungen (1) EffAlg AuD Wanka Sem. 3 BFS SP ¨ Kleinoder SoSy ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SYSSEC 12 ¨ Farbungen (1) EffAlg AuD Wanka Sem. 3 BFS SP ¨ Kleinoder SoSy ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SYSSEC 12 ¨ Farbungen (1) EffAlg AuD Wanka Sem. 3 BFS SP ¨ Kleinoder SoSy ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SYSSEC 12 ¨ Farbungen (1) EffAlg AuD Wanka Sem. 3 BFS SP ¨ Kleinoder SoSy SYSSEC Alle Vorlesungen mit der selben Farbe durfen gleichzeitig stattfinden! ¨ ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 12 ¨ Farbungen (2) Bemerkungen: ¨ ¨ 1. Es gibt viele zulassige Farbungen ¨ 2. Farbungen mit minimaler Anzahl an Farben zu finden ist schwierig ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 13 ¨ Farbungen (2) Bemerkungen: ¨ ¨ 1. Es gibt viele zulassige Farbungen ¨ 2. Farbungen mit minimaler Anzahl an Farben zu finden ist schwierig ¨ ¨ Mit Hilfe einer Farbung konnen Vorlesungen auf Zeitslots verteilt werden H6 H7 H8 8:00-10:00 EffAlg 10:00-12:00 SoSy 12:00-14:00 ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ SP AuD BFS SYSSEC 13 ¨ Farbungen (2) Bemerkungen: ¨ ¨ 1. Es gibt viele zulassige Farbungen ¨ 2. Farbungen mit minimaler Anzahl an Farben zu finden ist schwierig ¨ ¨ Mit Hilfe einer Farbung konnen Vorlesungen auf Zeitslots verteilt werden H6 H7 H8 8:00-10:00 EffAlg 10:00-12:00 SoSy 12:00-14:00 SP AuD BFS SYSSEC Dies ist ein akzeptabler Stundenplan fur ¨ unser Beispielproblem! ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 13 ¨ Farbungen (3) ¨ ¨ man nur ein Teilproblem! Durch Farbung lost Offene Fragen: 1. Welche Farbe kommt in welchen Zeitslot? 2. Was passiert, wenn es zu viele Vorlesungen einer Farbe gibt? 3. Welche Vorlesung bekommt welchen Raum? Hier kommen die Zusatzbedingungen ins Spiel! ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 14 ¨ Farbungsprobleme in der Informatik (1) ¨ Sudoku ist auch ein Farbungsproblem! 8 5 7 4 5 9 1 3 5 2 9 4 2 8 3 7 3 7 6 7 2 9 5 4 1 6 5 6 9 8 2 ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 9 6 15 ¨ Farbungsprobleme in der Informatik (1) ¨ Sudoku ist auch ein Farbungsproblem! ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 15 ¨ Farbungsprobleme in der Informatik (2) ¨ Farbungsprobleme Abstrakte Probleme Stundenplanung ¨ Landkarten Farben “Anwendungen” Registerzuweisung Kurzschlusse auf Leiterplatinen finden ¨ ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 16 ¨ Farbungsprobleme in der Informatik (2) ¨ Farbungsprobleme TSP Faktorisierung SAT Matching Covering Abstrakte Probleme Stundenplanung ¨ Landkarten Farben “Anwendungen” Registerzuweisung Kurzschlusse auf Leiterplatinen finden ¨ ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 16 Vielen Dank! ¨ Erlangen-Nurnberg Friedrich-Alexander-Universitat ¨ Moritz Muhlenthaler ¨ 17
© Copyright 2024 ExpyDoc
