Pro jaro 2024 je plánovaná reforma přijímacích zkoušek na střední školy, aby se zabránilo podobnému chaosu jako v roce 2023. Chystané změny jsou krok dobrým směrem, avšak stále panují nejasnosti ohledně algoritmu, který vyhodnotí data z přihlášek a výsledky zkoušek a přiřadí žáky na školy.
Tento algoritmus (zvaný párovací mechanismus) není nepodstatný technický detail, ale má zásadní vliv na to, kteří žáci se na své vybrané školy dostanou a kteří nikoli.
Vědci po celém světě tyto algoritmy studují již desítky let a rozlišili několik základních mechanismů. Mechanismus odloženého přijetí je dnes ve světě nejčastěji zaváděným systémem zkoušek a jeho kvalita je ověřena praxí i matematickými důkazy.
Důrazně doporučujeme, aby MŠMT pro následující přijímací zkoušky využilo právě tento mechanismus: nepředstavuje žádnou dodatečnou zátěž a nabízí žákům jednoznačně lepší přiřazení do škol při plném respektování výsledků zkoušek.
Jednotlivé podstránky ukazují průběh vybraných algoritmů na různých modelových situacích, aby ilustrovaly jejich silné a slabé stránky. První dva příklady, "Zadáni dle Cermatu" a "Optimalita pro studenty vs. pro školy" jasně ukazují, proč je mechanismus odloženého přijetí lepší než zvažovaná alternativa.
Tento obsah je automaticky generovaný a může se v budoucnu měnit. Stránka je optimalizovaná především pro zobrazení na klasických monitorech a nemusí být plně přehledná na mobilních zařízeních.
IDEA Talks
Rozhovor s autorem studie, ve kterém popisuje některé párovací mechanismy a uvádí další návrhy pro zlepšení organizace přijímacích zkoušek na střední školy.
Párovací mechanismy zjednodušené představují algoritmy, které přiřazují žáky dle výsledků školních
přijímacích zkoušek k jednotlivým středním školám. Jak ukazují zde uvedené příklady, tento algoritmus
není nepodstatný technický detail, ale přímo ovlivňuje, zdali se žáci dostanou na svoji preferovanou školu
nebo nikoli.
Tři základní vlastnosti, které by mělo výsledné přiřazení splňovat (a podle kterých můžeme posuzovat
párovací mechanismy):
Spravedlnost: o přijetí rozhoduje především výsledek zkoušky a méně úspěšný žák nikdy nemůže
předběhnout žáka s lepším výsledkem ve zkoušce. Technický pojem označující tuto vlastnost je
stabilita (nebo také neexistence opodstatněné závisti).
Respektování žákovských preferencí: pokud žák může být přiřazený na jeho více preferovanou školu,
aniž by tím došlo k horšímu přiřazení kohokoli jiného, pak by tak mělo být učiněno
(například formou výměny dvou žáků, pokud oba chtějí být na škole toho druhého). Technicky se tato
vlastnost nazývá Pareto efektivita z pohledu studentů.
Odolnost vůči strategizování: zdali žáci jsou motivováni uvádět školy v přihláškách dle
skutečných preferencí, nebo se jim vyplatí uvést školy v jiném pořadí nebo některé školy
vynechat.
Tyto tři vlastnosti však nemohou být zcela naplněny zároveň, neboť v některých případech by vzájemné
prohození studentů pro dosažení vyšší efektivity porušilo spravedlivost výsledku (jak ukazuje příklad
o nedosažitelnosti stability a efektivity).
Zde prezentujeme několik možných párovacích mechanismů:
Původní mechanismus navržený Cermatem: vede ke spravedlivému výsledku, ale nezaručuje plné
respektování žákovských preferencí (výsledek by bylo možné dále zlepšit vzájemnou výměnou žáků).
Jednalo se o první verzi algoritmu sdílenou pouze na vyžádáni, MŠMT momentálně preferuje
právě tuto verzi.
Mechanismus odloženého přijetí: nazývaný také stabilní mechanismus optimální pro studenty,
neboť nejvíce zachovává preference žáků mezi všemi spravedlivými mechanismy.
Naivní mechanismus: představuje prosté překlopení stávajícího průběhu zkoušek do verze s pořadím
škol. Tento algoritmus by sice nejlépe odpovídal doslovnému znění předložené novely školského
zákona, avšak nezaručuje spravedlivý výsledek.
Ačkoli právě poslední naivní mechanismus doslovně vychází z
novely školského zákona §60j Způsob hodnocení výsledků přijímacího řízení (odst. 2 a 3), za hlavní podstatu
lze však mnohem více považovat právě požadavek spravedlnosti
a respektování žákovských preferencí.
(2) Pokud splní kritéria přijímacího řízení více uchazečů než kolik lze přijmout,
rozhoduje jejich pořadí podle výsledků hodnocení kritérií přijímacího řízení.
(3) Umístí-li se uchazeč na místě opravňujícím k přijetí do více oborů středního
vzdělání, bude přijat do oboru umístěného z těchto oborů středního vzdělání na
přednostnějším pořadí uvedeném v přihlášce podle § 60b; do ostatních oborů středního
vzdělání nebude uchazeč přijat.
Poslední mechanismus, stabilní mechanismus optimální pro školy, je uvedený pouze jako doplňující,
neboť dosáhne vždy stejného výsledku jako mechanismus představený Cermatem. Tento mechanismus vede
vždy k výsledku, který by byl nejvíce preferovaný pro školy, avšak nikoli pro žáky. Rozdíl mezi takovými
výsledky ilustruje příklad optimalita pro studenty vs. pro školy.
Jednotlivé příklady na této stránce názorně ukazují, jak velké rozdíly mezi výsledky mohou být, a stručně
popisují jejich průběh po jednotlivých krocích. Výsledkem všech algoritmů je vždy finální přiřazení
k jednotlivým školám (případně odmítnutí na všech školách a nutnost pokračování do druhého kola.
Odolnost vůči strategizování zde detailně rozebírána není, protože s nízkým počtem vybíraných škol
při přihlašování ji nelze plně dosáhnout.
Matematicky bylo dokázáno již v roce 1962, že mechanismus odloženého přijetí je pro žáky
nejlepším spravedlivým mechanismem. Dnes je ve světě nejčastěji zaváděným mechanismem pro přijímací
zkoušky na střední školy a v roce 2012 byla udělena Nobelova cena matematiku Lloydu Shapleymu a ekonomovi Alvinu Rothovi
právě za výzkum v této oblasti.
Proto by bylo velmi žádoucí, aby v souladu s moderními vědeckými poznatky použila mechanismus
odloženého přijetí pro přijímací zkoušky i Česká republika. Použití tohoto mechanismu
je stejně snadné jako u kteréhokoli jiného algoritmu a nepředstavuje žádnou dodatečnou zátěž.
Zadání dle Cermatu
Tento příklad použil Cermat při vysvětlování jimi navrhnutého algoritmu.
Jedná se o více realistický příklad, který zároveň ilustruje některé zajímavé vlastnosti.
Mechanismus představený Cermatem, který je stabilní a optimální pro školy, zde v původní
verzi nemůže dosáhnout tak dobrého výsledku z pohledu studentů jako mechanismus odloženého
přijetí, který je stabilní a optimální pro studenty.
Mechanismus odloženého přijetí umístí 6 žáků na jejich první volbu z přihlášek a nikoho
na poslední třetí volbu, oproti tomu neoptimalizovaný mechanismus dle Cermatu umístí
pouze 4 žáky na jejich první volbu a 2 žáky na jejich poslední školy z přihlášek. Zároveň oba
mechanismy plně respektují pořadí výsledků zkoušek a nemůže se stát, že by se žák s horším výsledkem
dostal na pozici před žáka s lepším výsledkem ze zkoušky.
Matematicky bylo dokázáno již v roce 1962, že mechanismus odloženého přijetí je pro žáky
nejlepším spravedlivým mechanismem.
Mechanismus odloženého přijetí
Také nazývaný stabilní mechanismus optimální pro žáky.
Každá škola posoudí všechny žaky, kteří si ji vybrali jako první, a těm
s nejvyšší prioritou dle své kapacity nabídne podmíněné přijetí.
U žáků, kteří nejsou podmíněně přijati, se pokračuje podle pořadí škol
na přihláškách k další uvedené škole. Zde jsou tito žáci posouzeni společně
se všemi dříve přijatými žáky a škola z nich opět vybere ty,
které podmíněně přijme. Dle své kapacity může odmítnout i některé
z již podmíněně přijatých žáků.
Opakuje se bod 2, dokud nejsou všichni žáci podmíněně přijati nebo
dokud nejsou zcela posouzené přihlášky všech nepřijatých žáků.
Všichni podmíněně přijatí žáci jsou na tyto školy zapsáni.
DA je nazývaný také student-optimal stable mechanism, protože je nejlepším mechanismem
pro studenty mezi všemi stabilními mechanismy (tedy bez opodstatněné závisti).
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 4 ]
Bára, Dan, Eda, Lenka
Lyceum Mělník
[ Míst = 3 ]
Adam, Hanka, Katka
SOŠ Smíchov
[ Míst = 5 ]
Cecílie, Gustav, Ivana, Jana, Marek
Nepřijatí žáci
Filip
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Bára
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Cecílie
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Dan
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Eda
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Filip
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Gustav
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Hanka
Gymnázium Nymburk
Lyceum Mělník
SOŠ Smíchov
Ivana
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Jana
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Katka
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Lenka
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Marek
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Průběh algoritmu
Barevné značení
žák
společně posuzování žáci na jednotlivých školách (dosud přijatí a noví uchazeči)
žák
podmíněně přijatí žáci (podmíněné přijetí je finalizováno v posledním kroku)
žák
odmítnutí žáci, kteří se v dalším kroku uchází o jinou školu
žák
žáci s podmíněným přijetím na jiné škole (zde se ve vyhodnocování zatím nepokračuje)
žák
další školy odmítnutých žáků, u kterých se následně pokračuje ve vyhodnocování
Krok 1
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 2
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 3
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 4
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 5
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
Eda
Filip
Gustav
Hanka
...
1. škola
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
...
2. škola
SOŠ Smíchov
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
...
3. škola
Gymnázium Nymburk
SOŠ Smíchov
Gymnázium Nymburk
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
SOŠ Smíchov
...
...
...
...
...
...
Ivana
Jana
Katka
Lenka
Marek
1. škola
SOŠ Smíchov
Lyceum Mělník
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
2. škola
Lyceum Mělník
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Lyceum Mělník
3. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
Gymnázium Nymburk
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Zadání dle Cermatu
Tento příklad použil Cermat při vysvětlování jimi navrhnutého algoritmu.
Jedná se o více realistický příklad, který zároveň ilustruje některé zajímavé vlastnosti.
Mechanismus představený Cermatem, který je stabilní a optimální pro školy, zde v původní
verzi nemůže dosáhnout tak dobrého výsledku z pohledu studentů jako mechanismus odloženého
přijetí, který je stabilní a optimální pro studenty.
Mechanismus odloženého přijetí umístí 6 žáků na jejich první volbu z přihlášek a nikoho
na poslední třetí volbu, oproti tomu neoptimalizovaný mechanismus dle Cermatu umístí
pouze 4 žáky na jejich první volbu a 2 žáky na jejich poslední školy z přihlášek. Zároveň oba
mechanismy plně respektují pořadí výsledků zkoušek a nemůže se stát, že by se žák s horším výsledkem
dostal na pozici před žáka s lepším výsledkem ze zkoušky.
Matematicky bylo dokázáno již v roce 1962, že mechanismus odloženého přijetí je pro žáky
nejlepším spravedlivým mechanismem.
Původní mechanismus navržený Cermatem
Jedná se o původní verzi algoritmu, jak nám ji po publikaci studie
představil Cermat (a byl vstřícný diskuzi o možných
vylepšeních). MŠMT se však momentálně přiklání k této verzi.
Algoritmus
Podle výsledků zkoušky a vlastní kapacity každá škola stanoví,
kteří žáci mají nárok na přijetí.
Mezi žáky s nárokem na přijetí se vyberou ti, kteří tuto školu
uvedli na prvním místě. Pokud se žádní
takoví žáci nevyskytují, vyberou se žáci přijatí na školu na
druhém místě (pokud by se ani takoví nevyskytovali, lze analogicky
pokračovat k dalším v pořadí).
Tito žáci jsou přijatí na danou školu a jsou vyškrnuti ze seznamů
všech škol, které uvedli na horší pozici v přihláškách. Mohou tak
být vyškrnuti i ze školy, na kterou byli dříve přijati.
Tím se na školách uvolní nová místa a přijímací hranici se posunou
níže.
Opakuje se od bodu 2, dokud zbývají nepřijatí žáci a je možné
pokračovat.
Tento mechanismus je ekvivalentní ke school-optimal stable mechanism.
Vede tedy také ke stabilnímu párování, které je však optimální z pohledu
škol, nikoli studentů.
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 4 ]
Bára, Dan, Eda, Jana
Lyceum Mělník
[ Míst = 3 ]
Adam, Hanka, Lenka
SOŠ Smíchov
[ Míst = 5 ]
Cecílie, Gustav, Ivana, Katka, Marek
Nepřijatí žáci
Filip
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Bára
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Cecílie
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Dan
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Eda
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Filip
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Gustav
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Hanka
Gymnázium Nymburk
Lyceum Mělník
SOŠ Smíchov
Ivana
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Jana
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Katka
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Lenka
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Marek
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Průběh algoritmu
Barevné značení
žák
žáci, kteří aktuálně mohou být přijati na nejvíce preferovanou školu (mezi všemi žáky nad čarou)
žák
přijatí žáci (pokud v dalším kroku mohou být přijati i na lepší školu, mohou své rozhodnutí změnit)
žák
žáci, kteří již nestojí o přijetí na této škole a mohou po nich být uvolněna místa
žák
žáci pod čarou
žák
žáci nad čarou, kteří se dosud nevyhodnocují (nejedná se o nejvíce preferovanou školu)
Krok 1
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 2
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 3
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 4
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 5
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 6
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 7
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Zadání dle Cermatu
Tento příklad použil Cermat při vysvětlování jimi navrhnutého algoritmu.
Jedná se o více realistický příklad, který zároveň ilustruje některé zajímavé vlastnosti.
Mechanismus představený Cermatem, který je stabilní a optimální pro školy, zde v původní
verzi nemůže dosáhnout tak dobrého výsledku z pohledu studentů jako mechanismus odloženého
přijetí, který je stabilní a optimální pro studenty.
Mechanismus odloženého přijetí umístí 6 žáků na jejich první volbu z přihlášek a nikoho
na poslední třetí volbu, oproti tomu neoptimalizovaný mechanismus dle Cermatu umístí
pouze 4 žáky na jejich první volbu a 2 žáky na jejich poslední školy z přihlášek. Zároveň oba
mechanismy plně respektují pořadí výsledků zkoušek a nemůže se stát, že by se žák s horším výsledkem
dostal na pozici před žáka s lepším výsledkem ze zkoušky.
Matematicky bylo dokázáno již v roce 1962, že mechanismus odloženého přijetí je pro žáky
nejlepším spravedlivým mechanismem.
Naivní mechanismus
§60j Způsob hodnocení výsledků přijímacího řízení
(2) Pokud splní kritéria přijímacího řízení více uchazečů než kolik lze přijmout,
rozhoduje jejich pořadí podle výsledků hodnocení kritérií přijímacího řízení.
(3) Umístí-li se uchazeč na místě opravňujícím k přijetí do více oborů středního
vzdělání, bude přijat do oboru umístěného z těchto oborů středního vzdělání na
přednostnějším pořadí uvedeném v přihlášce podle § 60b; do ostatních oborů středního
vzdělání nebude uchazeč přijat.
Doslovnému znění nejvíce odpovídá právě naivní mechanismus popsaný níže.
Algoritmus
Ze všech žáků hlásících se na danou školu nabídni přijetí všem nad čarou.
Každý žák je zapsán na nejlepší ze škol, na které je přijatý.
Zapsaní žáci jsou vyřazeni, uvolní se místa a s dosud nezapsanými žáky
se vše opakuje od kroku 1.
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 4 ]
Adam, Dan, Eda, Marek
Lyceum Mělník
[ Míst = 3 ]
Hanka, Jana, Lenka
SOŠ Smíchov
[ Míst = 5 ]
Bára, Cecílie, Gustav, Ivana, Katka
Nepřijatí žáci
Filip
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Bára
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Cecílie
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Dan
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Eda
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Filip
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Gustav
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Hanka
Gymnázium Nymburk
Lyceum Mělník
SOŠ Smíchov
Ivana
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Jana
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Katka
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Lenka
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Marek
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Průběh algoritmu
Barevné značení
žák
žáci, kteří v tomto kroku byli přijatí na danou školu
žák
automaticky zapsaní žáci (na nejvíce preferovanou ze škol, na které byli přijati)
žák
odmítnutí žáci (v aktuálním kroku)
žák
žáci, kteří jsou již zapsaní jinde (uvolňují se po nich místa)
žák
nezapsaní žáci, kteří pokračují do dalšího kroku
Krok 1
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 2
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Zadání dle Cermatu
Tento příklad použil Cermat při vysvětlování jimi navrhnutého algoritmu.
Jedná se o více realistický příklad, který zároveň ilustruje některé zajímavé vlastnosti.
Mechanismus představený Cermatem, který je stabilní a optimální pro školy, zde v původní
verzi nemůže dosáhnout tak dobrého výsledku z pohledu studentů jako mechanismus odloženého
přijetí, který je stabilní a optimální pro studenty.
Mechanismus odloženého přijetí umístí 6 žáků na jejich první volbu z přihlášek a nikoho
na poslední třetí volbu, oproti tomu neoptimalizovaný mechanismus dle Cermatu umístí
pouze 4 žáky na jejich první volbu a 2 žáky na jejich poslední školy z přihlášek. Zároveň oba
mechanismy plně respektují pořadí výsledků zkoušek a nemůže se stát, že by se žák s horším výsledkem
dostal na pozici před žáka s lepším výsledkem ze zkoušky.
Matematicky bylo dokázáno již v roce 1962, že mechanismus odloženého přijetí je pro žáky
nejlepším spravedlivým mechanismem.
Stabilní mechanismus optimální pro školy
Mechanismus navržený Cermatem je ekvivalentní ke stabilnímu mechanismu optimálnímu
pro školy. Školy by tedy preferovaly tuto verzi algoritmu, avšak pro studenty
tento algoritmus není optimální a mohou dosáhnout lepšího stabilního výsledku
při použití mechanismu odloženého přijetí.
Algoritmus
Podle výsledků zkoušky a vlastní kapacity každá škola stanoví,
kteří žáci mají nárok na přijetí.
Žáci s nárokem na přijetí jsou podmíněně přijati na nejlepší z těchto škol
(podmíněnost zde znamená, že se mohou následně rozhodnou pro lepší školu, pokud jim
bude později nabídnuto přijetí) a z ostatních škol nad čarou jsou vyškrtnuti.
Tím se na školách uvolní nová místa a přijímací hranici se posunou
níže.
Opakuje se od bodu 1, dokud zbývají žáci bez podmíněného přijetí a je možné
pokračovat. Pokud v dalších kolech je žákům nabídnuta více preferovaná
škola, mohou své rozhodnutí změnit.
Tento algoritmus je analogický k deferred acceptance, pouze role škol a žáků
je obrácená. DA prochází pořadí dle preferencí žáků a školy je podmíněně přijímají
(nebo zcela odmítají). School-optimal SM prochází výsledky dle pořadí dle zkoušek
ve školách a žáci buď nabídku přijetí podmíněně akceptují, nebo ji odmítají.
Tento algoritmus je také velice podobný naivnímu, pouze přijetí žáků jsou pouze podmíněná
a vyškrtnutí jsou pouze ze škol, kde oni sami odmítnuli přijetí (a bylo jim nabídnuto).
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 4 ]
Bára, Dan, Eda, Jana
Lyceum Mělník
[ Míst = 3 ]
Adam, Hanka, Lenka
SOŠ Smíchov
[ Míst = 5 ]
Cecílie, Gustav, Ivana, Katka, Marek
Nepřijatí žáci
Filip
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Bára
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Cecílie
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Dan
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Eda
Lyceum Mělník
Gymnázium Nymburk
SOŠ Smíchov
Filip
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Gustav
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Hanka
Gymnázium Nymburk
Lyceum Mělník
SOŠ Smíchov
Ivana
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Jana
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Katka
Lyceum Mělník
SOŠ Smíchov
Gymnázium Nymburk
Lenka
Gymnázium Nymburk
SOŠ Smíchov
Lyceum Mělník
Marek
SOŠ Smíchov
Lyceum Mělník
Gymnázium Nymburk
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Průběh algoritmu
Barevné značení
žák
žáci s nabídkou na přijetí na dané škole
žák
žáci, kteří přijímají nabídku na této škole (mohou později změnit, pokud dostanou lepší nabídku)
žák
žáci, kteři již odmítli místo na této škole (jsou zde vyřazeni a uvolňují se jejich místa)
žák
žáci, kteří jsou pod čarou a nebylo jim nabídnuto přijetí
Krok 1
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 2
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 3
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 4
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 5
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 6
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 7
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Krok 8
Nabídky
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 4
Lyceum Mělník Míst = 3
SOŠ Smíchov Míst = 5
1.
Adam (#3)
Cecílie (#2)
Ivana (#1)
2.
Ivana (#3)
Gustav (#3)
Gustav (#2)
3.
Dan (#2)
Ivana (#2)
Bára (#3)
4.
Marek (#3)
Adam (#1)
Katka (#2)
5.
Eda (#2)
Hanka (#2)
Cecílie (#1)
6.
Cecílie (#3)
Marek (#2)
Adam (#2)
7.
Jana (#3)
Lenka (#3)
Dan (#3)
8.
Bára (#2)
Katka (#1)
Marek (#1)
9.
Lenka (#1)
Jana (#1)
Eda (#3)
10.
Filip (#1)
Eda (#1)
Hanka (#3)
11.
Hanka (#1)
Filip (#3)
Lenka (#2)
12.
Katka (#3)
Dan (#1)
Jana (#2)
13.
Gustav (#1)
Bára (#1)
Filip (#2)
Příklad: optimalita pro studenty vs. pro školy
Příklad je záměrně navržený tak, aby zvýraznil rozdíly mezi:
mechanismem odloženého přijetí (optimální pro studenty) a
Cermatem navrženým mechanismem bez dodatečných optimalizací (optimální pro školy).
Oba mechanismy zde vedou ke stabilnímu výsledku bez opodstatněné závisti, i tak jsou mezi
výsledky zásadní rozdíly.
Mechanismus odloženého přijetí přiřadí všechny žáky podle jejich první volby, zatímco mechanismus
představený Cermatem přiřadí žáky na jejich poslední volby z přihlášek.
Mechanismus odloženého přijetí
Také nazývaný stabilní mechanismus optimální pro žáky.
Každá škola posoudí všechny žaky, kteří si ji vybrali jako první, a těm
s nejvyšší prioritou dle své kapacity nabídne podmíněné přijetí.
U žáků, kteří nejsou podmíněně přijati, se pokračuje podle pořadí škol
na přihláškách k další uvedené škole. Zde jsou tito žáci posouzeni společně
se všemi dříve přijatými žáky a škola z nich opět vybere ty,
které podmíněně přijme. Dle své kapacity může odmítnout i některé
z již podmíněně přijatých žáků.
Opakuje se bod 2, dokud nejsou všichni žáci podmíněně přijati nebo
dokud nejsou zcela posouzené přihlášky všech nepřijatých žáků.
Všichni podmíněně přijatí žáci jsou na tyto školy zapsáni.
DA je nazývaný také student-optimal stable mechanism, protože je nejlepším mechanismem
pro studenty mezi všemi stabilními mechanismy (tedy bez opodstatněné závisti).
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Bára
OA Kladno
[ Míst = 1 ]
Cecílie
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Bára
Lyceum Mělník
OA Kladno
Gymnázium Nymburk
Cecílie
OA Kladno
Gymnázium Nymburk
Lyceum Mělník
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Průběh algoritmu
Barevné značení
žák
společně posuzování žáci na jednotlivých školách (dosud přijatí a noví uchazeči)
žák
podmíněně přijatí žáci (podmíněné přijetí je finalizováno v posledním kroku)
žák
odmítnutí žáci, kteří se v dalším kroku uchází o jinou školu
žák
žáci s podmíněným přijetím na jiné škole (zde se ve vyhodnocování zatím nepokračuje)
žák
další školy odmítnutých žáků, u kterých se následně pokračuje ve vyhodnocování
Krok 1
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
2. škola
Lyceum Mělník
OA Kladno
Gymnázium Nymburk
3. škola
OA Kladno
Gymnázium Nymburk
Lyceum Mělník
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
2. škola
Lyceum Mělník
OA Kladno
Gymnázium Nymburk
3. škola
OA Kladno
Gymnázium Nymburk
Lyceum Mělník
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Příklad: optimalita pro studenty vs. pro školy
Příklad je záměrně navržený tak, aby zvýraznil rozdíly mezi:
mechanismem odloženého přijetí (optimální pro studenty) a
Cermatem navrženým mechanismem bez dodatečných optimalizací (optimální pro školy).
Oba mechanismy zde vedou ke stabilnímu výsledku bez opodstatněné závisti, i tak jsou mezi
výsledky zásadní rozdíly.
Mechanismus odloženého přijetí přiřadí všechny žáky podle jejich první volby, zatímco mechanismus
představený Cermatem přiřadí žáky na jejich poslední volby z přihlášek.
Původní mechanismus navržený Cermatem
Jedná se o původní verzi algoritmu, jak nám ji po publikaci studie
představil Cermat (a byl vstřícný diskuzi o možných
vylepšeních). MŠMT se však momentálně přiklání k této verzi.
Algoritmus
Podle výsledků zkoušky a vlastní kapacity každá škola stanoví,
kteří žáci mají nárok na přijetí.
Mezi žáky s nárokem na přijetí se vyberou ti, kteří tuto školu
uvedli na prvním místě. Pokud se žádní
takoví žáci nevyskytují, vyberou se žáci přijatí na školu na
druhém místě (pokud by se ani takoví nevyskytovali, lze analogicky
pokračovat k dalším v pořadí).
Tito žáci jsou přijatí na danou školu a jsou vyškrnuti ze seznamů
všech škol, které uvedli na horší pozici v přihláškách. Mohou tak
být vyškrnuti i ze školy, na kterou byli dříve přijati.
Tím se na školách uvolní nová místa a přijímací hranici se posunou
níže.
Opakuje se od bodu 2, dokud zbývají nepřijatí žáci a je možné
pokračovat.
Tento mechanismus je ekvivalentní ke school-optimal stable mechanism.
Vede tedy také ke stabilnímu párování, které je však optimální z pohledu
škol, nikoli studentů.
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Bára
Lyceum Mělník
[ Míst = 1 ]
Cecílie
OA Kladno
[ Míst = 1 ]
Adam
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Bára
Lyceum Mělník
OA Kladno
Gymnázium Nymburk
Cecílie
OA Kladno
Gymnázium Nymburk
Lyceum Mělník
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Průběh algoritmu
Barevné značení
žák
žáci, kteří aktuálně mohou být přijati na nejvíce preferovanou školu (mezi všemi žáky nad čarou)
žák
přijatí žáci (pokud v dalším kroku mohou být přijati i na lepší školu, mohou své rozhodnutí změnit)
žák
žáci, kteří již nestojí o přijetí na této škole a mohou po nich být uvolněna místa
žák
žáci pod čarou
žák
žáci nad čarou, kteří se dosud nevyhodnocují (nejedná se o nejvíce preferovanou školu)
Krok 1
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Příklad: optimalita pro studenty vs. pro školy
Příklad je záměrně navržený tak, aby zvýraznil rozdíly mezi:
mechanismem odloženého přijetí (optimální pro studenty) a
Cermatem navrženým mechanismem bez dodatečných optimalizací (optimální pro školy).
Oba mechanismy zde vedou ke stabilnímu výsledku bez opodstatněné závisti, i tak jsou mezi
výsledky zásadní rozdíly.
Mechanismus odloženého přijetí přiřadí všechny žáky podle jejich první volby, zatímco mechanismus
představený Cermatem přiřadí žáky na jejich poslední volby z přihlášek.
Naivní mechanismus
§60j Způsob hodnocení výsledků přijímacího řízení
(2) Pokud splní kritéria přijímacího řízení více uchazečů než kolik lze přijmout,
rozhoduje jejich pořadí podle výsledků hodnocení kritérií přijímacího řízení.
(3) Umístí-li se uchazeč na místě opravňujícím k přijetí do více oborů středního
vzdělání, bude přijat do oboru umístěného z těchto oborů středního vzdělání na
přednostnějším pořadí uvedeném v přihlášce podle § 60b; do ostatních oborů středního
vzdělání nebude uchazeč přijat.
Doslovnému znění nejvíce odpovídá právě naivní mechanismus popsaný níže.
Algoritmus
Ze všech žáků hlásících se na danou školu nabídni přijetí všem nad čarou.
Každý žák je zapsán na nejlepší ze škol, na které je přijatý.
Zapsaní žáci jsou vyřazeni, uvolní se místa a s dosud nezapsanými žáky
se vše opakuje od kroku 1.
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Bára
Lyceum Mělník
[ Míst = 1 ]
Cecílie
OA Kladno
[ Míst = 1 ]
Adam
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Bára
Lyceum Mělník
OA Kladno
Gymnázium Nymburk
Cecílie
OA Kladno
Gymnázium Nymburk
Lyceum Mělník
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Průběh algoritmu
Barevné značení
žák
žáci, kteří v tomto kroku byli přijatí na danou školu
žák
automaticky zapsaní žáci (na nejvíce preferovanou ze škol, na které byli přijati)
žák
odmítnutí žáci (v aktuálním kroku)
žák
žáci, kteří jsou již zapsaní jinde (uvolňují se po nich místa)
žák
nezapsaní žáci, kteří pokračují do dalšího kroku
Krok 1
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Příklad: optimalita pro studenty vs. pro školy
Příklad je záměrně navržený tak, aby zvýraznil rozdíly mezi:
mechanismem odloženého přijetí (optimální pro studenty) a
Cermatem navrženým mechanismem bez dodatečných optimalizací (optimální pro školy).
Oba mechanismy zde vedou ke stabilnímu výsledku bez opodstatněné závisti, i tak jsou mezi
výsledky zásadní rozdíly.
Mechanismus odloženého přijetí přiřadí všechny žáky podle jejich první volby, zatímco mechanismus
představený Cermatem přiřadí žáky na jejich poslední volby z přihlášek.
Stabilní mechanismus optimální pro školy
Mechanismus navržený Cermatem je ekvivalentní ke stabilnímu mechanismu optimálnímu
pro školy. Školy by tedy preferovaly tuto verzi algoritmu, avšak pro studenty
tento algoritmus není optimální a mohou dosáhnout lepšího stabilního výsledku
při použití mechanismu odloženého přijetí.
Algoritmus
Podle výsledků zkoušky a vlastní kapacity každá škola stanoví,
kteří žáci mají nárok na přijetí.
Žáci s nárokem na přijetí jsou podmíněně přijati na nejlepší z těchto škol
(podmíněnost zde znamená, že se mohou následně rozhodnou pro lepší školu, pokud jim
bude později nabídnuto přijetí) a z ostatních škol nad čarou jsou vyškrtnuti.
Tím se na školách uvolní nová místa a přijímací hranici se posunou
níže.
Opakuje se od bodu 1, dokud zbývají žáci bez podmíněného přijetí a je možné
pokračovat. Pokud v dalších kolech je žákům nabídnuta více preferovaná
škola, mohou své rozhodnutí změnit.
Tento algoritmus je analogický k deferred acceptance, pouze role škol a žáků
je obrácená. DA prochází pořadí dle preferencí žáků a školy je podmíněně přijímají
(nebo zcela odmítají). School-optimal SM prochází výsledky dle pořadí dle zkoušek
ve školách a žáci buď nabídku přijetí podmíněně akceptují, nebo ji odmítají.
Tento algoritmus je také velice podobný naivnímu, pouze přijetí žáků jsou pouze podmíněná
a vyškrtnutí jsou pouze ze škol, kde oni sami odmítnuli přijetí (a bylo jim nabídnuto).
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Bára
Lyceum Mělník
[ Míst = 1 ]
Cecílie
OA Kladno
[ Míst = 1 ]
Adam
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Bára
Lyceum Mělník
OA Kladno
Gymnázium Nymburk
Cecílie
OA Kladno
Gymnázium Nymburk
Lyceum Mělník
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Průběh algoritmu
Barevné značení
žák
žáci s nabídkou na přijetí na dané škole
žák
žáci, kteří přijímají nabídku na této škole (mohou později změnit, pokud dostanou lepší nabídku)
žák
žáci, kteři již odmítli místo na této škole (jsou zde vyřazeni a uvolňují se jejich místa)
žák
žáci, kteří jsou pod čarou a nebylo jim nabídnuto přijetí
Krok 1
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Bára (#3)
Cecílie (#3)
Adam (#3)
2.
Cecílie (#2)
Adam (#2)
Bára (#2)
3.
Adam (#1)
Bára (#1)
Cecílie (#1)
Příklad: nedosažitelnost stability a efektivity
Příklad ilustruje, že není možné zároveň dosáhnout stability (neexistence opodstatněné závisti)
a Pareto efektivity pro studenty.
Všechny zde uvedené mechanismy přiřadí Adama na Gymnázium Nymburk a Báru na Lyceum Mělník,
ačkoli oba žáci by preferovali si tyto školy vzájemně vyměnit. Tím by byla zvýšena Pareto efektivita
pro žáky (oba by si polepšili a nikdo jiný by nebyl přímo poškozený).
Stabilní mechanismy však tuto výměnu neumožňují, neboť by vznikla opodstatněná závist (a tedy byla
porušena stabilita): Bára nemůže být přijata na Gymnázium Nymburk, neboť Cecílie se tam také hlásila,
byla úspěšnější v přijímací zkoušce a měla tuto školu na první pozici na přihlášce.
Mechanismus odloženého přijetí je nejvíce Pareto efektivní pro studenty ze všech stabilních mechanismů
(tzv. optimálně stabilní).
Maximální efektivity pro studenty by zde dosáhl mechanismus efektivních přesunů (uváděný pouze
ve studii), který však není stabilní.
Mechanismus odloženého přijetí
Také nazývaný stabilní mechanismus optimální pro žáky.
Každá škola posoudí všechny žaky, kteří si ji vybrali jako první, a těm
s nejvyšší prioritou dle své kapacity nabídne podmíněné přijetí.
U žáků, kteří nejsou podmíněně přijati, se pokračuje podle pořadí škol
na přihláškách k další uvedené škole. Zde jsou tito žáci posouzeni společně
se všemi dříve přijatými žáky a škola z nich opět vybere ty,
které podmíněně přijme. Dle své kapacity může odmítnout i některé
z již podmíněně přijatých žáků.
Opakuje se bod 2, dokud nejsou všichni žáci podmíněně přijati nebo
dokud nejsou zcela posouzené přihlášky všech nepřijatých žáků.
Všichni podmíněně přijatí žáci jsou na tyto školy zapsáni.
DA je nazývaný také student-optimal stable mechanism, protože je nejlepším mechanismem
pro studenty mezi všemi stabilními mechanismy (tedy bez opodstatněné závisti).
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Bára
OA Kladno
[ Míst = 1 ]
Cecílie
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Lyceum Mělník
Gymnázium Nymburk
OA Kladno
Bára
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Cecílie
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Průběh algoritmu
Barevné značení
žák
společně posuzování žáci na jednotlivých školách (dosud přijatí a noví uchazeči)
žák
podmíněně přijatí žáci (podmíněné přijetí je finalizováno v posledním kroku)
žák
odmítnutí žáci, kteří se v dalším kroku uchází o jinou školu
žák
žáci s podmíněným přijetím na jiné škole (zde se ve vyhodnocování zatím nepokračuje)
žák
další školy odmítnutých žáků, u kterých se následně pokračuje ve vyhodnocování
Krok 1
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Krok 2
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Krok 3
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Krok 4
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Krok 5
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
1. škola
Lyceum Mělník
Gymnázium Nymburk
Gymnázium Nymburk
2. škola
Gymnázium Nymburk
Lyceum Mělník
Lyceum Mělník
3. škola
OA Kladno
OA Kladno
OA Kladno
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Příklad: nedosažitelnost stability a efektivity
Příklad ilustruje, že není možné zároveň dosáhnout stability (neexistence opodstatněné závisti)
a Pareto efektivity pro studenty.
Všechny zde uvedené mechanismy přiřadí Adama na Gymnázium Nymburk a Báru na Lyceum Mělník,
ačkoli oba žáci by preferovali si tyto školy vzájemně vyměnit. Tím by byla zvýšena Pareto efektivita
pro žáky (oba by si polepšili a nikdo jiný by nebyl přímo poškozený).
Stabilní mechanismy však tuto výměnu neumožňují, neboť by vznikla opodstatněná závist (a tedy byla
porušena stabilita): Bára nemůže být přijata na Gymnázium Nymburk, neboť Cecílie se tam také hlásila,
byla úspěšnější v přijímací zkoušce a měla tuto školu na první pozici na přihlášce.
Mechanismus odloženého přijetí je nejvíce Pareto efektivní pro studenty ze všech stabilních mechanismů
(tzv. optimálně stabilní).
Maximální efektivity pro studenty by zde dosáhl mechanismus efektivních přesunů (uváděný pouze
ve studii), který však není stabilní.
Původní mechanismus navržený Cermatem
Jedná se o původní verzi algoritmu, jak nám ji po publikaci studie
představil Cermat (a byl vstřícný diskuzi o možných
vylepšeních). MŠMT se však momentálně přiklání k této verzi.
Algoritmus
Podle výsledků zkoušky a vlastní kapacity každá škola stanoví,
kteří žáci mají nárok na přijetí.
Mezi žáky s nárokem na přijetí se vyberou ti, kteří tuto školu
uvedli na prvním místě. Pokud se žádní
takoví žáci nevyskytují, vyberou se žáci přijatí na školu na
druhém místě (pokud by se ani takoví nevyskytovali, lze analogicky
pokračovat k dalším v pořadí).
Tito žáci jsou přijatí na danou školu a jsou vyškrnuti ze seznamů
všech škol, které uvedli na horší pozici v přihláškách. Mohou tak
být vyškrnuti i ze školy, na kterou byli dříve přijati.
Tím se na školách uvolní nová místa a přijímací hranici se posunou
níže.
Opakuje se od bodu 2, dokud zbývají nepřijatí žáci a je možné
pokračovat.
Tento mechanismus je ekvivalentní ke school-optimal stable mechanism.
Vede tedy také ke stabilnímu párování, které je však optimální z pohledu
škol, nikoli studentů.
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Bára
OA Kladno
[ Míst = 1 ]
Cecílie
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Lyceum Mělník
Gymnázium Nymburk
OA Kladno
Bára
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Cecílie
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Průběh algoritmu
Barevné značení
žák
žáci, kteří aktuálně mohou být přijati na nejvíce preferovanou školu (mezi všemi žáky nad čarou)
žák
přijatí žáci (pokud v dalším kroku mohou být přijati i na lepší školu, mohou své rozhodnutí změnit)
žák
žáci, kteří již nestojí o přijetí na této škole a mohou po nich být uvolněna místa
žák
žáci pod čarou
žák
žáci nad čarou, kteří se dosud nevyhodnocují (nejedná se o nejvíce preferovanou školu)
Krok 1
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Krok 2
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Příklad: nedosažitelnost stability a efektivity
Příklad ilustruje, že není možné zároveň dosáhnout stability (neexistence opodstatněné závisti)
a Pareto efektivity pro studenty.
Všechny zde uvedené mechanismy přiřadí Adama na Gymnázium Nymburk a Báru na Lyceum Mělník,
ačkoli oba žáci by preferovali si tyto školy vzájemně vyměnit. Tím by byla zvýšena Pareto efektivita
pro žáky (oba by si polepšili a nikdo jiný by nebyl přímo poškozený).
Stabilní mechanismy však tuto výměnu neumožňují, neboť by vznikla opodstatněná závist (a tedy byla
porušena stabilita): Bára nemůže být přijata na Gymnázium Nymburk, neboť Cecílie se tam také hlásila,
byla úspěšnější v přijímací zkoušce a měla tuto školu na první pozici na přihlášce.
Mechanismus odloženého přijetí je nejvíce Pareto efektivní pro studenty ze všech stabilních mechanismů
(tzv. optimálně stabilní).
Maximální efektivity pro studenty by zde dosáhl mechanismus efektivních přesunů (uváděný pouze
ve studii), který však není stabilní.
Naivní mechanismus
§60j Způsob hodnocení výsledků přijímacího řízení
(2) Pokud splní kritéria přijímacího řízení více uchazečů než kolik lze přijmout,
rozhoduje jejich pořadí podle výsledků hodnocení kritérií přijímacího řízení.
(3) Umístí-li se uchazeč na místě opravňujícím k přijetí do více oborů středního
vzdělání, bude přijat do oboru umístěného z těchto oborů středního vzdělání na
přednostnějším pořadí uvedeném v přihlášce podle § 60b; do ostatních oborů středního
vzdělání nebude uchazeč přijat.
Doslovnému znění nejvíce odpovídá právě naivní mechanismus popsaný níže.
Algoritmus
Ze všech žáků hlásících se na danou školu nabídni přijetí všem nad čarou.
Každý žák je zapsán na nejlepší ze škol, na které je přijatý.
Zapsaní žáci jsou vyřazeni, uvolní se místa a s dosud nezapsanými žáky
se vše opakuje od kroku 1.
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Bára
OA Kladno
[ Míst = 1 ]
Cecílie
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Lyceum Mělník
Gymnázium Nymburk
OA Kladno
Bára
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Cecílie
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Průběh algoritmu
Barevné značení
žák
žáci, kteří v tomto kroku byli přijatí na danou školu
žák
automaticky zapsaní žáci (na nejvíce preferovanou ze škol, na které byli přijati)
žák
odmítnutí žáci (v aktuálním kroku)
žák
žáci, kteří jsou již zapsaní jinde (uvolňují se po nich místa)
žák
nezapsaní žáci, kteří pokračují do dalšího kroku
Krok 1
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Krok 2
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Příklad: nedosažitelnost stability a efektivity
Příklad ilustruje, že není možné zároveň dosáhnout stability (neexistence opodstatněné závisti)
a Pareto efektivity pro studenty.
Všechny zde uvedené mechanismy přiřadí Adama na Gymnázium Nymburk a Báru na Lyceum Mělník,
ačkoli oba žáci by preferovali si tyto školy vzájemně vyměnit. Tím by byla zvýšena Pareto efektivita
pro žáky (oba by si polepšili a nikdo jiný by nebyl přímo poškozený).
Stabilní mechanismy však tuto výměnu neumožňují, neboť by vznikla opodstatněná závist (a tedy byla
porušena stabilita): Bára nemůže být přijata na Gymnázium Nymburk, neboť Cecílie se tam také hlásila,
byla úspěšnější v přijímací zkoušce a měla tuto školu na první pozici na přihlášce.
Mechanismus odloženého přijetí je nejvíce Pareto efektivní pro studenty ze všech stabilních mechanismů
(tzv. optimálně stabilní).
Maximální efektivity pro studenty by zde dosáhl mechanismus efektivních přesunů (uváděný pouze
ve studii), který však není stabilní.
Stabilní mechanismus optimální pro školy
Mechanismus navržený Cermatem je ekvivalentní ke stabilnímu mechanismu optimálnímu
pro školy. Školy by tedy preferovaly tuto verzi algoritmu, avšak pro studenty
tento algoritmus není optimální a mohou dosáhnout lepšího stabilního výsledku
při použití mechanismu odloženého přijetí.
Algoritmus
Podle výsledků zkoušky a vlastní kapacity každá škola stanoví,
kteří žáci mají nárok na přijetí.
Žáci s nárokem na přijetí jsou podmíněně přijati na nejlepší z těchto škol
(podmíněnost zde znamená, že se mohou následně rozhodnou pro lepší školu, pokud jim
bude později nabídnuto přijetí) a z ostatních škol nad čarou jsou vyškrtnuti.
Tím se na školách uvolní nová místa a přijímací hranici se posunou
níže.
Opakuje se od bodu 1, dokud zbývají žáci bez podmíněného přijetí a je možné
pokračovat. Pokud v dalších kolech je žákům nabídnuta více preferovaná
škola, mohou své rozhodnutí změnit.
Tento algoritmus je analogický k deferred acceptance, pouze role škol a žáků
je obrácená. DA prochází pořadí dle preferencí žáků a školy je podmíněně přijímají
(nebo zcela odmítají). School-optimal SM prochází výsledky dle pořadí dle zkoušek
ve školách a žáci buď nabídku přijetí podmíněně akceptují, nebo ji odmítají.
Tento algoritmus je také velice podobný naivnímu, pouze přijetí žáků jsou pouze podmíněná
a vyškrtnutí jsou pouze ze škol, kde oni sami odmítnuli přijetí (a bylo jim nabídnuto).
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Bára
OA Kladno
[ Míst = 1 ]
Cecílie
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Lyceum Mělník
Gymnázium Nymburk
OA Kladno
Bára
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Cecílie
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Průběh algoritmu
Barevné značení
žák
žáci s nabídkou na přijetí na dané škole
žák
žáci, kteří přijímají nabídku na této škole (mohou později změnit, pokud dostanou lepší nabídku)
žák
žáci, kteři již odmítli místo na této škole (jsou zde vyřazeni a uvolňují se jejich místa)
žák
žáci, kteří jsou pod čarou a nebylo jim nabídnuto přijetí
Krok 1
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Krok 2
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Krok 3
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
1.
Adam (#2)
Bára (#2)
Bára (#3)
2.
Cecílie (#1)
Adam (#1)
Adam (#3)
3.
Bára (#1)
Cecílie (#2)
Cecílie (#3)
Příklad ze studie IDEA
Hlavní příklad ze studie, který jasně ukazuje nestabilitu (opodstatněnou závist)
u naivního mechanismu. Stabilní mechanismy (DA, Cermat, School-optimal SM) toto zadání
vyřeší uspokojivě.
Mechanismus odloženého přijetí
Také nazývaný stabilní mechanismus optimální pro žáky.
Každá škola posoudí všechny žaky, kteří si ji vybrali jako první, a těm
s nejvyšší prioritou dle své kapacity nabídne podmíněné přijetí.
U žáků, kteří nejsou podmíněně přijati, se pokračuje podle pořadí škol
na přihláškách k další uvedené škole. Zde jsou tito žáci posouzeni společně
se všemi dříve přijatými žáky a škola z nich opět vybere ty,
které podmíněně přijme. Dle své kapacity může odmítnout i některé
z již podmíněně přijatých žáků.
Opakuje se bod 2, dokud nejsou všichni žáci podmíněně přijati nebo
dokud nejsou zcela posouzené přihlášky všech nepřijatých žáků.
Všichni podmíněně přijatí žáci jsou na tyto školy zapsáni.
DA je nazývaný také student-optimal stable mechanism, protože je nejlepším mechanismem
pro studenty mezi všemi stabilními mechanismy (tedy bez opodstatněné závisti).
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Bára
OA Kladno
[ Míst = 1 ]
Cecílie
SOŠ Smíchov
[ Míst = 1 ]
Dan
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Bára
Gymnázium Nymburk
Lyceum Mělník
SOŠ Smíchov
Cecílie
Gymnázium Nymburk
OA Kladno
SOŠ Smíchov
Dan
Lyceum Mělník
OA Kladno
SOŠ Smíchov
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Průběh algoritmu
Barevné značení
žák
společně posuzování žáci na jednotlivých školách (dosud přijatí a noví uchazeči)
žák
podmíněně přijatí žáci (podmíněné přijetí je finalizováno v posledním kroku)
žák
odmítnutí žáci, kteří se v dalším kroku uchází o jinou školu
žák
žáci s podmíněným přijetím na jiné škole (zde se ve vyhodnocování zatím nepokračuje)
žák
další školy odmítnutých žáků, u kterých se následně pokračuje ve vyhodnocování
Krok 1
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
1. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
2. škola
Lyceum Mělník
Lyceum Mělník
OA Kladno
OA Kladno
3. škola
OA Kladno
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
1. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
2. škola
Lyceum Mělník
Lyceum Mělník
OA Kladno
OA Kladno
3. škola
OA Kladno
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Krok 2
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
1. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
2. škola
Lyceum Mělník
Lyceum Mělník
OA Kladno
OA Kladno
3. škola
OA Kladno
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
1. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
2. škola
Lyceum Mělník
Lyceum Mělník
OA Kladno
OA Kladno
3. škola
OA Kladno
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Krok 3
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
1. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
2. škola
Lyceum Mělník
Lyceum Mělník
OA Kladno
OA Kladno
3. škola
OA Kladno
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
1. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
2. škola
Lyceum Mělník
Lyceum Mělník
OA Kladno
OA Kladno
3. škola
OA Kladno
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Krok 4
Nabídky
Podle přihlášek
Adam
Bára
Cecílie
Dan
1. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
2. škola
Lyceum Mělník
Lyceum Mělník
OA Kladno
OA Kladno
3. škola
OA Kladno
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Podle přihlášek
Adam
Bára
Cecílie
Dan
1. škola
Gymnázium Nymburk
Gymnázium Nymburk
Gymnázium Nymburk
Lyceum Mělník
2. škola
Lyceum Mělník
Lyceum Mělník
OA Kladno
OA Kladno
3. škola
OA Kladno
SOŠ Smíchov
SOŠ Smíchov
SOŠ Smíchov
Podle výsledků zkoušky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Příklad ze studie IDEA
Hlavní příklad ze studie, který jasně ukazuje nestabilitu (opodstatněnou závist)
u naivního mechanismu. Stabilní mechanismy (DA, Cermat, School-optimal SM) toto zadání
vyřeší uspokojivě.
Původní mechanismus navržený Cermatem
Jedná se o původní verzi algoritmu, jak nám ji po publikaci studie
představil Cermat (a byl vstřícný diskuzi o možných
vylepšeních). MŠMT se však momentálně přiklání k této verzi.
Algoritmus
Podle výsledků zkoušky a vlastní kapacity každá škola stanoví,
kteří žáci mají nárok na přijetí.
Mezi žáky s nárokem na přijetí se vyberou ti, kteří tuto školu
uvedli na prvním místě. Pokud se žádní
takoví žáci nevyskytují, vyberou se žáci přijatí na školu na
druhém místě (pokud by se ani takoví nevyskytovali, lze analogicky
pokračovat k dalším v pořadí).
Tito žáci jsou přijatí na danou školu a jsou vyškrnuti ze seznamů
všech škol, které uvedli na horší pozici v přihláškách. Mohou tak
být vyškrnuti i ze školy, na kterou byli dříve přijati.
Tím se na školách uvolní nová místa a přijímací hranici se posunou
níže.
Opakuje se od bodu 2, dokud zbývají nepřijatí žáci a je možné
pokračovat.
Tento mechanismus je ekvivalentní ke school-optimal stable mechanism.
Vede tedy také ke stabilnímu párování, které je však optimální z pohledu
škol, nikoli studentů.
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Bára
OA Kladno
[ Míst = 1 ]
Cecílie
SOŠ Smíchov
[ Míst = 1 ]
Dan
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Bára
Gymnázium Nymburk
Lyceum Mělník
SOŠ Smíchov
Cecílie
Gymnázium Nymburk
OA Kladno
SOŠ Smíchov
Dan
Lyceum Mělník
OA Kladno
SOŠ Smíchov
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Průběh algoritmu
Barevné značení
žák
žáci, kteří aktuálně mohou být přijati na nejvíce preferovanou školu (mezi všemi žáky nad čarou)
žák
přijatí žáci (pokud v dalším kroku mohou být přijati i na lepší školu, mohou své rozhodnutí změnit)
žák
žáci, kteří již nestojí o přijetí na této škole a mohou po nich být uvolněna místa
žák
žáci pod čarou
žák
žáci nad čarou, kteří se dosud nevyhodnocují (nejedná se o nejvíce preferovanou školu)
Krok 1
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Krok 2
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Krok 3
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Příklad ze studie IDEA
Hlavní příklad ze studie, který jasně ukazuje nestabilitu (opodstatněnou závist)
u naivního mechanismu. Stabilní mechanismy (DA, Cermat, School-optimal SM) toto zadání
vyřeší uspokojivě.
Naivní mechanismus
§60j Způsob hodnocení výsledků přijímacího řízení
(2) Pokud splní kritéria přijímacího řízení více uchazečů než kolik lze přijmout,
rozhoduje jejich pořadí podle výsledků hodnocení kritérií přijímacího řízení.
(3) Umístí-li se uchazeč na místě opravňujícím k přijetí do více oborů středního
vzdělání, bude přijat do oboru umístěného z těchto oborů středního vzdělání na
přednostnějším pořadí uvedeném v přihlášce podle § 60b; do ostatních oborů středního
vzdělání nebude uchazeč přijat.
Doslovnému znění nejvíce odpovídá právě naivní mechanismus popsaný níže.
Algoritmus
Ze všech žáků hlásících se na danou školu nabídni přijetí všem nad čarou.
Každý žák je zapsán na nejlepší ze škol, na které je přijatý.
Zapsaní žáci jsou vyřazeni, uvolní se místa a s dosud nezapsanými žáky
se vše opakuje od kroku 1.
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Dan
OA Kladno
[ Míst = 1 ]
Cecílie
SOŠ Smíchov
[ Míst = 1 ]
Bára
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Bára
Gymnázium Nymburk
Lyceum Mělník
SOŠ Smíchov
Cecílie
Gymnázium Nymburk
OA Kladno
SOŠ Smíchov
Dan
Lyceum Mělník
OA Kladno
SOŠ Smíchov
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Průběh algoritmu
Barevné značení
žák
žáci, kteří v tomto kroku byli přijatí na danou školu
žák
automaticky zapsaní žáci (na nejvíce preferovanou ze škol, na které byli přijati)
žák
odmítnutí žáci (v aktuálním kroku)
žák
žáci, kteří jsou již zapsaní jinde (uvolňují se po nich místa)
žák
nezapsaní žáci, kteří pokračují do dalšího kroku
Krok 1
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Krok 2
Nabídky
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Přijaté a odmítnuté
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Příklad ze studie IDEA
Hlavní příklad ze studie, který jasně ukazuje nestabilitu (opodstatněnou závist)
u naivního mechanismu. Stabilní mechanismy (DA, Cermat, School-optimal SM) toto zadání
vyřeší uspokojivě.
Stabilní mechanismus optimální pro školy
Mechanismus navržený Cermatem je ekvivalentní ke stabilnímu mechanismu optimálnímu
pro školy. Školy by tedy preferovaly tuto verzi algoritmu, avšak pro studenty
tento algoritmus není optimální a mohou dosáhnout lepšího stabilního výsledku
při použití mechanismu odloženého přijetí.
Algoritmus
Podle výsledků zkoušky a vlastní kapacity každá škola stanoví,
kteří žáci mají nárok na přijetí.
Žáci s nárokem na přijetí jsou podmíněně přijati na nejlepší z těchto škol
(podmíněnost zde znamená, že se mohou následně rozhodnou pro lepší školu, pokud jim
bude později nabídnuto přijetí) a z ostatních škol nad čarou jsou vyškrtnuti.
Tím se na školách uvolní nová místa a přijímací hranici se posunou
níže.
Opakuje se od bodu 1, dokud zbývají žáci bez podmíněného přijetí a je možné
pokračovat. Pokud v dalších kolech je žákům nabídnuta více preferovaná
škola, mohou své rozhodnutí změnit.
Tento algoritmus je analogický k deferred acceptance, pouze role škol a žáků
je obrácená. DA prochází pořadí dle preferencí žáků a školy je podmíněně přijímají
(nebo zcela odmítají). School-optimal SM prochází výsledky dle pořadí dle zkoušek
ve školách a žáci buď nabídku přijetí podmíněně akceptují, nebo ji odmítají.
Tento algoritmus je také velice podobný naivnímu, pouze přijetí žáků jsou pouze podmíněná
a vyškrtnutí jsou pouze ze škol, kde oni sami odmítnuli přijetí (a bylo jim nabídnuto).
Výsledek přijímaček
Přijatí žáci
Gymnázium Nymburk
[ Míst = 1 ]
Adam
Lyceum Mělník
[ Míst = 1 ]
Bára
OA Kladno
[ Míst = 1 ]
Cecílie
SOŠ Smíchov
[ Míst = 1 ]
Dan
Vstupní data
Vstupní data tvoří přihlášky žáků na 3 školy seřazené dle preferencí
a výsledky přijímacích zkoušek z jednotlivých škol. Barevné kódování označuje,
na které školy byli žáci nakonec přijati, a bylo doplněno pro snadnější
posouzení kvality výsledného přiřazení.
Studentské přihlášky
1. škola
2. škola
3. škola
Adam
Gymnázium Nymburk
Lyceum Mělník
OA Kladno
Bára
Gymnázium Nymburk
Lyceum Mělník
SOŠ Smíchov
Cecílie
Gymnázium Nymburk
OA Kladno
SOŠ Smíchov
Dan
Lyceum Mělník
OA Kladno
SOŠ Smíchov
Výsledky školních zkoušek
Čísla v závorce označují pořadí školy na přihlášce daného žáka.
Gymnázium Nymburk Míst = 1
Lyceum Mělník Míst = 1
OA Kladno Míst = 1
SOŠ Smíchov Míst = 1
1.
Adam (#1)
Adam (#2)
Adam (#3)
Bára (#3)
2.
Bára (#1)
Bára (#2)
Cecílie (#2)
Cecílie (#3)
3.
Cecílie (#1)
Dan (#1)
Dan (#2)
Dan (#3)
Průběh algoritmu
Barevné značení
žák
žáci s nabídkou na přijetí na dané škole
žák
žáci, kteří přijímají nabídku na této škole (mohou později změnit, pokud dostanou lepší nabídku)
žák
žáci, kteři již odmítli místo na této škole (jsou zde vyřazeni a uvolňují se jejich místa)
žák
žáci, kteří jsou pod čarou a nebylo jim nabídnuto přijetí