Tvorba rozvrhov je považovaná za veľmi komplexnú a zložitú činnosť. S nekonečným počtom možností je to takmer nemožné bez pomoci. Preto je len logické, že v dnešnej modernej dobe si prizveme na pomoc výpočtovú technológiu.

1. Úvod

Rozvrhy sa na univerzitách robia ručne a často krát bez pomoci počítača. Táto činnosť je veľmi namáhavá a časovo náročná. Do úvahy treba brať nároky na miestnosti ich kapacitu a typ. Ďalej sú tu požiadavky od učiteľov, ktorí nemôžu učiť v určitú dobu a veľa iných. Zostavovať takto rozvrh môže zabrať niekoľko týždňov ak nie mesiacov. V súčasnosti nie je na trhu aplikácia, ktorá by tento problém riešila.

Na trhu sú aplikácie na zostavovanie rozvrhov, dokonca aplikácia od slovenskej firmy je najpoužívanejšia. Tieto aplikácie neslúžia na generovanie rozvrhov pre univerzity, ale naopak na generovanie rozvrhov pre základne a stredné školy. Keďže nároky pre univerzity sa líšia tieto aplikácie sa nedajú použiť. TimeTable² prináša riešenie týchto problémov. TimeTable² je aplikácia pre platformu Windows® od spoločnosti Microsoft®. Je to štandardná desktopová aplikácia, ktorá využíva najmodernejšie technológie.

2. TimeTable² pod kapotou

TimeTable² je kompletne naprogramovaná v jazyku C#, ktorý je najpoužívanejší z rodiny .NET Framework jazykov. Microsoft® .NET Framework je prostredie potrebné pre beh aplikácií a ponúkajúce ako spúšťacie rozhranie, tak potrebné knižnice. V súčasnosti sa nachádza vo verzii 3.5 SP1, ale čoskoro vývojári Microsoftu uvoľnia novú verziu .NET 4.0. TimeTable² využíva na svoj beh verziu frameworku 3.5 SP1 s možnosťou zmeny na verziu 4.0. Na ukladanie dát sa používa Microsoft® SQL Server Compact Edition.

2.1 Microsoft® SQL Server® Compact Edition

Je to bez inštančný server, ktorý manažuje relačné databázy. Tento server nie je potrebné inštalovať a je možné použiť ho na mobilných zariadeniach. Pri spustení programu sa na pozadí vytvorí vlastná inštancia tohto servera, ktorá spravuje všetky dotazy nad databázou. Svoje dáta si pritom v binárnej podobe ukladá do samostatného súboru na disk. Táto voľba komponentov, ktorých aplikácia využíva, ju robí kompletne prenosnou, bez nutnosti inštalácie. Pre prácu s databázou a na dotazy sa používa technológia LINQ.

2.2 Language Integrated Query

Language Integrated Query (LINQ) je súčasť Microsoft .NET Frameworku, ktorá umožňuje natívne prístup k dátam v jazykoch platformy .NET. Microsoft LINQ definuje ako súbor metód a pravidiel prekladu dotazovacích výrazov na výrazy použiteľné pre výber dát z viacerých zdrojov. Týmito zdrojmi môžu byť: dáta v poliach, enumerable triedy, XML, relačné databázy, dátové zdroje tretích strán.

Typmi LINQ providerov sú: LINQ to Objects, LINQ to XML, LINQ to SQL, LINQ to DataSets, LINQ to Entities a iné. V technológii LINQ to SQL je použitý dátový model (prípona súboru .DBML) vygenerovaný presne podľa databázového modelu spolu so vzťahmi (1:1, 1:N, M:N), tak sa vytvorí reprezentácia entít pomocou objektov, k týmto sa dá následne pristupovať pomocou jazyka LINQ. Prvá verzia LINQ bola zahrnutá vo verzii .NET Frameworku 3.5. [1]

2.3 Windows Presentation Foundation

Na užívateľské rozhranie (GUI) a komunikáciu s užívateľom je použitá technológia WPF. Windows Presentation Foundation (WPF) je nový spôsob programovania aplikácií pre Windows® Vista™ (funguje aj pod XP), ide o grafický systém .NET Frameworku 3.0 (WinFX), ďalšia varianta k doterajším Windows Forms (WinForms). [2] WPF ale nie je technológia nahradzujúca WinForms, jedná sa skôr o ďalší spôsob písania Windows aplikácií.

Oproti WinForms ale ponúka nové možnosti hlavne v oblasti grafického spracovania aplikácie, ktoré vo WinForms nie sú možné. WPF je zamerané na užívateľsky bohaté aplikácie. Až doteraz väčšina aplikácií bola “formulárového” vzhľadu, vo WPF môžete ale upustiť uzdu fantázii a využívať mnoho možností:

• vektorová grafika – umožňuje graficky bezstratovú zmenu veľkosti prvkov, farebné gradienty, používanie geometrických tvarov.
• animácia – časová alebo s použitím framov, rotácia, prechod farieb, 3D animácia a mnoho ďalších
• multimédiá – práca s audiom a videom (avi, mpeg, wmv)
• efekty – tiene, svetlá, rozostrenia, priehľadnosť alebo zrkadlenie
• interaktívne 3D aplikácie – poskytuje podmnožinu funkcií z Direct3D zameranú na multimédiá, dokumenty a užívateľské rozhranie
• DataBinding – previazanie dát v aplikácii
• XAML je deklaratívny programovací jazyk pre vytváranie užívateľského rozhrania vo WPF aplikáciách.

2.4 Hardwarové a softwarové nároky

Hardwarové nároky aplikácie nie sú veľké a v dnešnej dobe keď má každý počítač niekoľko gigabajtov pamäte je záťaž minimálna. Aplikácia funguje na 32 aj 64 bitovej architektúre procesora. Počas svojho behu spotrebuje približne 100 MB z pamäte RAM. Aplikácia dokáže využiť moderné viac jadrové procesory. Na generovanie rozvrhu vie využívať druhé jadro procesora pričom prvé obsluhuje užívateľa.

Softwarové nároky sú v operačnom systéme a v popísaných technológiách. Na svoj beh vyžaduje aplikácia operačný systém Windows® XP™ Service Pack 2 a vyšší. Taktiež sú potrebné knižnice z .NET Frameworku a knižnice z databázového servera. O všetky tieto požiadavky sa vie elegantne postarať vytvorený inštalátor, ktorý zistí chýbajúce komponenty a ponúkne možnosť ich stiahnuť z internetu.

3. Základné objekty

Aplikácia pracuje so základnými objektmi, ktoré sú:

• Krúžok
• Predmet
• Učiteľ
• Miestnosť
• Deň
• Hodina

Filozofia aplikácie spočíva v pohľade na študentov. Študenti sú zgrupovaní do krúžkov. Krúžok obsahuje informáciu o počte študentov, ročník štúdia a špecializáciu. Na začiatku semestra zadelí pedagogické oddelenie každého študenta do krúžku. Týmto spôsobom databáza nemusí obsahovať každého študenta zvlášť. V extrémnom prípade môže krúžok obsahovať len jedného študenta, ktorý má mať individuálny rozvrh. Každý krúžok má k sebe priradené predmety, ktoré musí absolvovať.

Predmet obsahuje informácie o maximálnom počte študentov, dĺžku v hodinách, nároky na miestnosť a počet opakovaní za týždeň. Každý predmet má priradených učiteľov, ktorí môžu tento predmet vyučovať. Miestnosť obsahuje informácie o kapacite, koľko študentov sa tam zmestí naraz a akého je typu napr. počítačová učebňa, laboratórium, prednášková sála atď. Dni sa dajú pridávať a uberať podľa požiadaviek školy. Každá hodina obsahuje svoje poradové číslo, čas kedy začína a končí.

3.1 Nastavenia objektov

Aplikácia zohľadňuje rozličné nároky jednotlivých objektov. Pre krúžok, učiteľa a miestnosť je možné nastaviť zakázané hodiny. Na túto pozíciu sa potom nebude dať umiestniť žiadna hodina a zostáva voľná.

Obr. 1 Nastavenie zakázaných hodín

4. Funkcionalita

Aplikácia pracuje v dvoch režimoch. Prvý režim je, keď užívateľ manuálne zadáva dáta a následne umiestňuje zvolenú hodinu do rozvrhu. Tento proces prebieha tak, že si vyberie miestnosť, ktorej rozvrh chce upraviť. Na základe výberu miestnosti má možnosť si vybrať predmet, ktorý chce aby sa tam vyučoval. Výber predmetov je filtrovaný podľa typu miestnosti.

Po výbere predmetu má možnosť vybrať krúžok a učiteľa, ktorý bude predmet vyučovať. Tu sa dá použiť filter na zobrazenie len toho krúžku a učiteľa, ktorý má priradený vybraný predmet, inak sa dá vybrať ľubovoľný krúžok a učiteľ. Následne postupom známym ako drag&drop umiestni predmet na zvolenú hodinu a deň, pričom má možnosť vidieť už obsadené pozície učiteľov a krúžkov.

Obr. 2 Drag&Drop novej hodiny

Druhý režim je automatické generovanie rozvrhu.

4.1 Automatické generovanie rozvrhu

Po dlhých úvahách sa veľa hodín skúšania rôznych prístupov generovaniu rozvrhu, som zvolil metódu náhodného generovania.

Začínal som s algoritmom, ktorý postupne generoval rozvrh. Ten prešiel fázou hodnotenia za základe určitých kritérií. Následne sa optimalizoval. V tejto časti som narazil na netriviálny problém. Ak sa budem snažiť optimalizovať rozvrh, tým že zoberiem predmet A z pozície 1 na pozíciu 2 môžem, ale nemusím týmto získať lepšie celkové hodnotenie. Ak sa hodnotenie zlepší predmet tam nechám, ak sa zhorší vrátim ho naspäť. Nastala otázka, čo ak po jednej horšej zmene príde taká zmena k lepšiemu, ktorú by som inak nedosiahol. Do akej hĺbky by bolo nutné isť s tými zmenami k horšiemu aby prišla zmena k lepšiemu. Aj keby som tento výpočet robil na viac jadrovom procesore nároky na pamäť by boli veľké a výpočet by trval veľmi dlho.

Opačný prístup bol cez náhodné generovanie celého rozvrhu. Vygenerovať náhodný rozvrh sa prejavilo byť veľmi rýchle. Fázu hodnotenia som z časti prebral, po každom vygenerovaní náhodného rozvrhu sa ohodnotí a porovná z predcházajúcim najlepším rozvrhom a ak má lepšie hodnotenie tak sa uloží ako najlepší. Štatisticky ak vyskúšam vygenerovať dostatočné množstvo náhodných rozvrhov mal by som dostať uspokojujúci výsledok. Aplikácia generuje 10 000 rozvrhov.

Obr. 3 Generovanie rozvrhu

4.2 Náhľady rozvrhov

Užívateľské rozhranie umožňuje používateľovi prezeranie rozvrhov z troch pohľadov: učiteľ, krúžok a miestnosť. Pridávať nové hodiny je možné len z náhľadu miestnosti. Toto obmedzenie je z dôvodu náročnosti na tvorbu GUI. Pri zobrazovaní rozvrhu sú farebne odlíšené hodiny vložené užívateľom, ktoré algoritmus nemôže presúvať a hodiny vygenerované. Obidvoje sa dajú z rozvrhu odstrániť, tak že sa na zvolené hodinu klikne pravým tlačidlom a z ponuky sa vybere odstrániť.

V hlavom menu je nástroj na hromadné odstraňovanie hodín v prípade ak nie je užívateľ spokojný. Na výber sú možnosti na odstránenie všetkých hodín, hodín zadaných užívateľom alebo vygenerovaných hodín. Ak chce užívateľ rozvrh uložiť tak si v hlavom menu vybere a klikne na položku uložiť. Týmto sa zmeny uložia do databázy a pri ďalšom spustení sa znova načítajú.

4.3 Exportovanie a tlač

Aplikácia dokáže zobrazovaný rozvrh exportovať na užívateľom zvolené miesto vo forme pdf dokumentu. Tento dokument si následne otvorí v prehliadači pdf dokumentov ako je Adobe® Reader®, z ktorého je možné rozvrh vytlačiť.

5. Záver

V článku som popísal súčasný stav na trhu s generátormi rozvrhov. Navrhol a implementoval som riešenie nedostatku aplikácií pre vysoké školy a univerzity. Popísal som použité technológie, štruktúru a základné vlastnosti môjho riešenia.

Obr. 4 Rozvrh

6. Odkazy na literatúru

1. Dynatech s.r.o., Language Integrated Query (LINQ) – Slovník pojmov – Dynatech s.r.o., [online], Dostupné z http://www.dynatech.sk/en/information-systems/technologies/LINQ.aspx
2. Dynatech s.r.o., Windows Presentation Foundation (WPF) – Slovník pojmov – Dynatech s.r.o., [online], Dostupné z http://www.dynatech.eu/informacne-systemy/technologie/WPF.aspx
3. Nathan, A., “Windows Presentation Foundation Unleashed“, Sams Publishing Inc., 2006, ISBN-10: 0-672-32891-7
4. Bishop, J., “C# 3.0 Design Patterns“, O’Reilly Media, 2009, Ebook ISBN: 978-0-596-10257-9
5. Delikát, T., ”Základy projektovania databázových systémov“, Bratislava, Delint, 2007, ISBN 978-80-969613-0-6

Spoluautorom článku je Frank Schindler