Fehler über Fehler

Alles, was zu Kurs42 passt

Moderator: wschrewe

M. Plümper
Fachberater*in
Beiträge: 699
Registriert: Montag 1. Oktober 2018, 20:30
Schulform: Gymnasium
Kontaktdaten:

Re: Fehler über Fehler

Beitrag von M. Plümper »

NielsWestphal hat geschrieben: Montag 7. Juni 2021, 16:34 Es darf eigentlich nie Kollisionen / Umwähler geben. Dann muss halt die Kursdifferenz höher sein. So ist in Kurs42_To_CNF ja auch die Anfangseinstellung: Umwähler 0, KD20. Und das wird dann automatisch bis KD1 (falls möglich) runtergerechnet.
Manchmal gibt es von zwei Fächern nur einen Kurs. Werden die parallel gesetzt, ergeben sich automatisch Umwähler. Sprich in solchen Fällen helfen keine größeren Kursgrößendifferenzen.

Jetzt kann man natürlich sagen, die kommen nicht in eine Schiene, das kann man bei einer Kombination von zwei Kursen hinbekommen. Hat man davon in kleinen Oberstufen aber mehrere Kombinationen wird das schon schwieriger. Selbst wenn das noch gehen sollte, kann das zu Kursgrößendifferenzen von 14 zu 25 führen (aus praktischer Erfahrung mit Kurs42ToCNF). Sie schreiben ja zurecht (falls möglich) KD1, das muss nicht gehen.

Und Kurse in der Form 14, 18, 25 würde ich nur sehr ungerne einrichten. Da können dann ein oder zwei Umwähler schon Wunder bewirken.
NielsWestphal
Beiträge: 565
Registriert: Sonntag 2. Dezember 2018, 18:33
Schulform: Gymnasium

Re: Fehler über Fehler

Beitrag von NielsWestphal »

Ob das immer funktioniert, ist tatsächlich nicht klar. Unsere Erfahrungen mit CNF sind aber tatsächlich super…
mfg
Niels Westphal
M. Plümper
Fachberater*in
Beiträge: 699
Registriert: Montag 1. Oktober 2018, 20:30
Schulform: Gymnasium
Kontaktdaten:

Re: Fehler über Fehler

Beitrag von M. Plümper »

B. Bartsch hat geschrieben: Montag 7. Juni 2021, 16:29 Nichtwähler sind algorithmisch betrachtet das bessere Maß im Vergleich zu Kollisionen. D.h. so wie der neue Algorithmus derzeit läuft heißt X Nichtwähler exakt X Kollisionen. Umgekehrt muss das nicht unbedingt sein. Y Umwähler könnten theoretisch Y-1 Nichtwähler sein (wenn der Algorithmus die Umwähler nicht minimal wählt pro Schüler).

Um es etwas zu vertiefen. Der neue Algorithmus verteilt im Hintergrund bei fixierter Kurslage jeden Schüler nacheinander. Dabei wendet er bei jedem Schüler ein "gewichtetes bipartitets Matching" an, welcher eine maximale Kurszuordnung findet. D.h. wenn ein Schüler z. B. 1 Nichtwahl hat, dann geht es mathematisch nicht besser (bei der aktuellen Lage der Kurse).

Natürlich könnte der Algorithmus einfach bei jedem Schüler der eine Nichtwahl in einem Fach hat einen zufälligen Kurs aus der Fachmenge nehmen, aber das finde ich keine gute Lösung.
Hallo Benjamin,

nur zur Klarstellung: Was gibt Kurs42 im Blockungsdialog an? Die nicht verteilten Schüler oder die nicht verteilten Fachwahlen?

Das ist wichtig, denn ich ging davon aus, dass es die Schüleranzahl mit mindestens einer nicht verteilten Fachwahl ist. Dann kann die Angabe 1 nicht verteilter Schüler bei fixierter Kurzuordnung mehrere Kollisionen auslösen. Beispiel: Wenn ein SuS L, G und KU, LI hat und dann L und G sowie KU und LI bei der Kursanordnung parallel zueinander liegen, dann erzeugt der Schüler automatisch zwei Kollisionen.
M. Plümper
Fachberater*in
Beiträge: 699
Registriert: Montag 1. Oktober 2018, 20:30
Schulform: Gymnasium
Kontaktdaten:

Re: Fehler über Fehler

Beitrag von M. Plümper »

NielsWestphal hat geschrieben: Dienstag 8. Juni 2021, 13:27 Ob das immer funktioniert, ist tatsächlich nicht klar. Unsere Erfahrungen mit CNF sind aber tatsächlich super…
Das ist bei mir auch so, aber mir geht es um den Grundsatz.

Auch wenn ich sagen muss das CNF dieses Jahr ein Problem auch nicht in 12 Stunden lösen konnte, für das der Algorithmus in Kurs42 keine 20 Minuten brauchte.
Benutzeravatar
wschrewe
Fachberater*in
Beiträge: 1686
Registriert: Dienstag 25. September 2018, 17:36
Schulform: BK (Pensionär)
Kontaktdaten:

Re: Fehler über Fehler

Beitrag von wschrewe »

Ich habe (sozusagen als private Spielerei) den Algorithmus von Kurs2Cnf mal in eine private Version von Kurs 42 integriert. Das funktioniert IMHO schon ganz ordentlich, ist allerdings nicht so ausgefeilt wie Herrn Bartsch' Originalversion mit n parallelen Prozessen. Für Ottonormalblocker ist vermutlich der jetzt in Kurs 42 eingebaute Algorithmus (Dank an Herrn Bartsch!) ausreichend.

Für solche Fälle wie die von Herrn Westphal ist Kurs2Cnf offensichtlich besser geeignet, weil die möglichen Regeln weit über das hinausgehen, was Kurs 42 bietet (Sperren, Fixieren).
Mit freundlichen Grüßen
Walter Schrewe
"If all else fails, read the instructions" (Donald E. Knuth, letzter TeX - Hilfehinweis)
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Fehler über Fehler

Beitrag von B. Bartsch »

M. Plümper hat geschrieben: Dienstag 8. Juni 2021, 13:30 Hallo Benjamin,
nur zur Klarstellung: Was gibt Kurs42 im Blockungsdialog an? Die nicht verteilten Schüler oder die nicht verteilten Fachwahlen?

Das ist wichtig, denn ich ging davon aus, dass es die Schüleranzahl mit mindestens einer nicht verteilten Fachwahl ist. Dann kann die Angabe 1 nicht verteilter Schüler bei fixierter Kurzuordnung mehrere Kollisionen auslösen. Beispiel: Wenn ein SuS L, G und KU, LI hat und dann L und G sowie KU und LI bei der Kursanordnung parallel zueinander liegen, dann erzeugt der Schüler automatisch zwei Kollisionen.
...Lisa Müller hat nicht SW-GK
So erzeugt jede nicht verteile Schüler-Fachwahl genau 1 Kollision.
B. Bartsch
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Fehler über Fehler

Beitrag von B. Bartsch »

M. Plümper hat geschrieben: Dienstag 8. Juni 2021, 13:31 Das ist bei mir auch so, aber mir geht es um den Grundsatz.
Auch wenn ich sagen muss das CNF dieses Jahr ein Problem auch nicht in 12 Stunden lösen konnte, für das der Algorithmus in Kurs42 keine 20 Minuten brauchte.
Beide Algorithmen ergänzen sich unglaublich gut. Ich arbeite auch an einer Hybrid-Variante.

Ich habe hier eine Blockung mit 12 EF Schienen und völligen Freiheiten. Diese brachte CNF nur auf KD4 und Kurs42 auf KD1. Dann habe ich 4 Kerngruppen fixiert (ergo 4 Schienen weniger zu berechnen) und plötzlich drehte sich das Bild. CNF schaffte relataiv schnell KD1 und Kurs42 blieb bei KD4 (nach einer Stunde KD3).
B. Bartsch
M. Plümper
Fachberater*in
Beiträge: 699
Registriert: Montag 1. Oktober 2018, 20:30
Schulform: Gymnasium
Kontaktdaten:

Re: Fehler über Fehler

Beitrag von M. Plümper »

Hallo Benjamin,

sorry das ich so hartnäckig bin. Aber noch einmal: Die Anzeige in Kurs42 "Nicht verteilte" im Blocken-Dialog bedeutet:

a) Schüler mit einer oder mehreren nicht verteilten Fachwahlen (d. h. die Anzeige zählt Schüler)
b) Nicht verteilte Fachwahlen.

Und in meinem Beispiel oben gibt es mehr als eine Kollision für Lisa Müller. Daher verstehe ich den SW-GK nicht.
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Fehler über Fehler

Beitrag von B. Bartsch »

wschrewe hat geschrieben: Dienstag 8. Juni 2021, 15:17 Ich habe (sozusagen als private Spielerei) den Algorithmus von Kurs2Cnf mal in eine private Version von Kurs 42 integriert. Das funktioniert IMHO schon ganz ordentlich, ist allerdings nicht so ausgefeilt wie Herrn Bartsch' Originalversion mit n parallelen Prozessen. Für Ottonormalblocker ist vermutlich der jetzt in Kurs 42 eingebaute Algorithmus (Dank an Herrn Bartsch!) ausreichend.

Für solche Fälle wie die von Herrn Westphal ist Kurs2Cnf offensichtlich besser geeignet, weil die möglichen Regeln weit über das hinausgehen, was Kurs 42 bietet (Sperren, Fixieren).
Sehr gerne ;-)

Ich denke was Kurs42 nochmal einen erheblichen Schritt weiter bringen könnte, wäre eine Hybridvariante. Und zwar kann CNF relativ schnell und gut die Kursverteilung finden, bei Einhaltung aller Regeln (minimale Nichtwahlen, Kursfixierungen, Sperrungen, max. Facharten pro Schiene, etc...). Nur die KD muss relativ hoch bleiben, damit man schnell ein Ergebnis bekommt. Je nach Datensatz KD5 bis KD15.

Hat man dann eine Kursverteilung könnte man diese Kursverteilung dem neuen Algorithmus von Kurs42 geben. Dieser startet ja Anfangs mit einer zufälligen Lage der Kurse und optimiert diese schrittweise. Anstelle der zufälligen Lage, könnte von auch mit der Kurslage von CNF starten.
Zuletzt geändert von B. Bartsch am Dienstag 8. Juni 2021, 22:15, insgesamt 1-mal geändert.
B. Bartsch
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Fehler über Fehler

Beitrag von B. Bartsch »

M. Plümper hat geschrieben: Dienstag 8. Juni 2021, 22:00 Hallo Benjamin,

sorry das ich so hartnäckig bin. Aber noch einmal: Die Anzeige in Kurs42 "Nicht verteilte" im Blocken-Dialog bedeutet:

a) Schüler mit einer oder mehreren nicht verteilten Fachwahlen (d. h. die Anzeige zählt Schüler)
b) Nicht verteilte Fachwahlen.

Und in meinem Beispiel oben gibt es mehr als eine Kollision für Lisa Müller. Daher verstehe ich den SW-GK nicht.
b) ....wobei es sehr selten vorkommt, dass es einen Schüler doppelt trifft.
Beispiel: Wenn ein SuS L, G und KU, LI hat und dann L und G sowie KU und LI bei der Kursanordnung parallel zueinander liegen, dann erzeugt der Schüler automatisch zwei Kollisionen.
Der Algrotihmus erzeugt einen bipartiten Graphen pro S. und maximiert die mögliche kollisionsfreie Kantenmenge.

Linke Knoten = Fächer des S., Rechte Knoten = Schiene

Code: Alles auswählen

L                                             Schiene 1
G                                            Schiene 2
KU                                          Schiene 3
LI                                            ...
...                                           ....
...                                           ...
                                              Schiene 12
Es existiert eine Kante nun zwischen den linken und rechten Knoten, wenn das Fach X in Schiene Y sich befindet. Wir tun mal so, also hätte der S. nur die 4 Fächer gewählt und L/G liegen in Schiene 1 und KU/LI liegen in Schiene 2 (und nirgendwo anders noch).
Dann gibt es vier Kanten. L-1, G-1, KU-2, LI-2. Ein maximales bipartites Matching findet nun ein Matching der Größe 2. D.h. der S. kann maximal 2 Fächer ohne Kollision wählen. Z. B. könnte der Algorithmus sagen der S. hat L-1 und KU-2. Dieser S. hat zwei Nicht-Wahlen der Fächer G und LI.
B. Bartsch
Antworten

Zurück zu „Allgemeines“