Bölüm 14 · SimülasyonDers Ön Koşul Planlayıcısı ? ← Bölüm 14 Yeni ders Ders Ekle Önce Sonra Ön Koşul Ekle Kaldır u → v: u, v'den önce alınır ÖrnekDöngülüTemizle kahn(adj) giris[] q sonuc plan Kapat Ders Ön Koşul Planlayıcısı Dersler düğüm, ön koşullar yönlü kenardır: u → v kenarı, u'nun v'den önce alınması gerektiğini gösterir. Geçerli bir ders planı bu çizgenin topolojik sıralamasıdır; burada Kahn algoritmasıyla adım adım hesaplanır. Kullanım Adıyla bir ders ekleyin, ardından Önce ve Sonra derslerini seçip Ön Koşul Ekle'ye basın (kenarı silmek için Kaldır). Örnek 7 ön koşullu 6 ders yükler; Döngülü örneği yükleyip bir döngüyü kapatan kenar ekler; Temizle her şeyi siler. Adımlar arasında ⏮ ◀ ▶ ile gezinin ya da hepsini çalıştırmak için Oynat'a basın. kahn(adj) içindeki vurgulu satır, o an yürütülen satırdır. Düğümdeki g giriş derecesini, D dersin alınacağı dönemi gösterir. Satırlar ne gösterir giris[]: her dersin giriş derecesi (karşılanmamış ön koşul sayısı). q: giriş derecesi 0 olan, yani hemen alınabilecek derslerin kuyruğu. sonuc: o ana kadar üretilen topolojik sıra. plan: en uzun ön koşul zincirlerine göre dönemlere ayrılmış dersler. Kahn algoritması Tüm giriş dereceleri hesaplanır ve giriş derecesi 0 olan dersler kuyruğa alınır. Ardından her adımda kuyruktan bir ders çıkarılır, sonuca eklenir ve ardıllarının giriş derecesi bir azaltılır; derecesi 0'a inenler kuyruğa girer. Sonuçtaki ders sayısı çizgedekinden azsa kalan dersler bir döngü üzerindedir ya da döngüdeki bir dersi bekler; geçerli bir plan yoktur. Algoritma O(n + m) sürede çalışır.