Etkinlik Diyagramları

Önceki ders sıra gösteriminin bir koşumu eksiksiz, öteki 23 koşumu hiç göstermediğini saydı. O gösterimin yazdığı her ileti bir sıra numarası taşıyordu ve o numaralar zorunluymuş gibi duruyordu. Oysa atölyedeki işlerin çoğu birbirini beklemiyor: müşteriyi bilgilendirmekle maliyeti hesaplamak arasında hiçbir öncelik yok ve ikisi herhangi bir sırada yapılabilir.

Etkinlik gösterimi bunu düzeltir. Sıra yazmaz, önkoşul yazar: hangi işin hangi işlerden sonra başlayabileceğini söyler, hangisinin önce yapılacağını söylemez. Böylece gösterim bir yalan söylemekten kurtulur. Karşılığında başka bir şey yapar: tek bir yürütmeyi değil, bir yürütme kümesini birden anlatır. Bu dersin ölçüsü o kümenin büyüklüğüdür.

Kısmi Sıra Bir Küme Anlatır

Atölyenin iş akışı on iş içeriyor: kabul, stok ayırma, usta atama, tezgâh ayırma, müşteri bilgilendirme, maliyet hesabı, işleme, belgeleme, fatura kesme, kapatma. Aralarında on üç önkoşul var. Bu on üç önkoşul bir kısmi sıralama kurar: bazı iş çiftlerinin sırasını belirler, bazılarını serbest bırakır.

Sistemin gerçekte yaptığı şey ise bir tam sıralamadır. Bir iş emri koşarken işler tek tek olur ve belirli bir sıraya girer; o koşumun bir tek sırası vardır. Gösterim ise bu sıraların tamamını birden kabul eder. Kabul edilen sıra sayısı, gösterimin bıraktığı gevşekliğin ölçüsüdür.

Bu sayı, Veri Yapıları kursundaki topolojik sıralamanın kaç ayrı çıktı verebildiğidir. O ders giriş dereceli yordamı kurdu ve sıralamanın tek olmadığını, kuyrukta birden çok düğüm varken algoritmanın bir seçim yaptığını gösterdi — ama seçimlerin kaç ayrı sonuç verdiğini saymadı. Bu ders o sayımı yapıyor. Yordam tekrarlanmıyor, aynen çağrılıyor.

Sayının Kendisi

"""Etkinlik gosterimi: kismi siralama kac tam siralamayi birden kabul ediyor.
Ortak tanimin ETKINLIK ve tam_siralamalar tanimlari aynen kurulur; topolojik
siralama Veri Yapilari kursundaki giris dereceli yordamdir."""
from collections import deque
from itertools import combinations

ETKINLIK = {                      # is -> onkosul isler
    "kabul": [],
    "stok_ayir": ["kabul"],
    "usta_ata": ["kabul"],
    "tezgah_ayir": ["usta_ata"],
    "musteri_bilgilendir": ["kabul"],
    "maliyet_hesapla": ["stok_ayir"],
    "isle": ["stok_ayir", "tezgah_ayir"],
    "belgele": ["isle"],
    "fatura_kes": ["maliyet_hesapla", "isle"],
    "kapat": ["belgele", "fatura_kes", "musteri_bilgilendir"],
}


def tam_siralamalar(onkosul):
    isler = list(onkosul)
    sonuc = []

    def gez(kalan, dizi):
        if not kalan:
            sonuc.append(tuple(dizi))
            return
        for i in kalan:
            if all(o in dizi for o in onkosul[i]):
                dizi.append(i)
                gez([x for x in kalan if x != i], dizi)
                dizi.pop()
    gez(isler, [])
    return sonuc


def komsuluk(onkosul):
    """Onkosul esleme -> yonlu cizge: onkosul isten bagimli ise kenar."""
    k = {i: [] for i in onkosul}
    for i, oncekiler in onkosul.items():
        for o in oncekiler:
            k[o].append(i)
    return k


def topolojik_sirala(k):
    """Veri Yapilari kursundaki giris dereceli yordam , aynen."""
    giris = {d: 0 for d in k}
    for d in k:
        for h in k[d]:
            giris[h] += 1
    kuyruk = deque(sorted(d for d in giris if giris[d] == 0))
    sonuc = []
    while kuyruk:
        d = kuyruk.popleft()
        sonuc.append(d)
        for h in k[d]:
            giris[h] -= 1
            if giris[h] == 0:
                kuyruk.append(h)
    return sonuc if len(sonuc) == len(k) else None


def katmanlar(k):
    giris = {d: 0 for d in k}
    for d in k:
        for h in k[d]:
            giris[h] += 1
    hazir = sorted(d for d in giris if giris[d] == 0)
    sonuc, islenen = [], 0
    while hazir:
        sonuc.append(hazir)
        islenen += len(hazir)
        sonraki = []
        for d in hazir:
            for h in k[d]:
                giris[h] -= 1
                if giris[h] == 0:
                    sonraki.append(h)
        hazir = sorted(sonraki)
    return sonuc if islenen == len(k) else None


def once_gelenler(onkosul):
    """Gecisli kapanis: her isin kendisinden once gelmesi zorunlu isler."""
    kapanis = {i: set(onkosul[i]) for i in onkosul}
    degisti = True
    while degisti:
        degisti = False
        for i in kapanis:
            yeni = set(kapanis[i])
            for o in kapanis[i]:
                yeni |= kapanis[o]
            if yeni != kapanis[i]:
                kapanis[i] = yeni
                degisti = True
    return kapanis


def karsilastirilamaz(onkosul):
    kap = once_gelenler(onkosul)
    return [(a, b) for a, b in combinations(sorted(onkosul), 2)
            if b not in kap[a] and a not in kap[b]]


def carpan(n):
    s = 1
    for i in range(2, n + 1):
        s *= i
    return s


IS = len(ETKINLIK)
ONKOSUL = sum(len(v) for v in ETKINLIK.values())
TS = tam_siralamalar(ETKINLIK)
print("SISTEM  : her kosumda TEK bir yurutme sirasi gerceklesir")
print("GOSTERIM:", IS + ONKOSUL, "simge =", IS, "is +", ONKOSUL, "onkosul")
print("BEDEL   :", len(TS), "tam siralama kabul ediliyor | tek siralamayi cizmek kapsam",
      round(1 / len(TS), 4))
print()
K = komsuluk(ETKINLIK)
print("topolojik siralama tek bir cikti veriyor:")
print(" ", topolojik_sirala(K))
print("ayni cizgenin gecerli cikti sayisi:", len(TS))
KAT = katmanlar(K)
print("katmanlar (esazamanli baslatilabilir isler):")
for i, kat in enumerate(KAT, 1):
    print(f"  {i}. {kat}")
print("kritik yol uzunlugu:", len(KAT), "adim | sirali yurutme", IS, "adim")
print()
KI = karsilastirilamaz(ETKINLIK)
CIFT = carpan(IS) // (carpan(2) * carpan(IS - 2))
print("is cifti:", CIFT, "| onkosulun sirasini belirledigi cift:", CIFT - len(KI),
      "| serbest cift:", len(KI))
print("onkosulsuz kabul:", carpan(IS), "-> onkosullu kabul:", len(TS),
      "| daralma", carpan(IS) // len(TS), "kat")
print()
print("bir onkosul eklenirse 168 nereye iner")
sonuc = []
for a, b in KI:
    for x, y in ((a, b), (b, a)):
        yeni = {i: list(v) for i, v in ETKINLIK.items()}
        yeni[y].append(x)
        if topolojik_sirala(komsuluk(yeni)) is None:
            continue
        sonuc.append((len(tam_siralamalar(yeni)), f"{x} -> {y}"))
sonuc.sort()
print("  eklenebilir onkosul sayisi:", len(sonuc))
print("  en cok daraltan uc secim:")
for n, ad in sonuc[:3]:
    print(f"    {ad:38s} {len(TS)} -> {n}")
print("  en az daraltan uc secim:")
for n, ad in sonuc[-3:]:
    print(f"    {ad:38s} {len(TS)} -> {n}")
print("  hepsinin ortalamasi:", round(sum(n for n, _ in sonuc) / len(sonuc), 1))
print("  atolyede anlami olan iki secim (DD9):")
for x, y in (("musteri_bilgilendir", "isle"), ("belgele", "fatura_kes")):
    yeni = {i: list(v) for i, v in ETKINLIK.items()}
    yeni[y].append(x)
    print(f"    {x + ' -> ' + y:38s} {len(TS)} -> {len(tam_siralamalar(yeni))}")
print()
# DD10: karar dugumu. Yeniden isleme dali istege bagli bir is ekliyor.
DAL = {i: list(v) for i, v in ETKINLIK.items()}
DAL["yeniden_isle"] = ["isle"]
DAL["belgele"] = ["yeniden_isle"]
TS2 = tam_siralamalar(DAL)
print("karar dugumu eklenirse (yeniden isleme dali):")
print("  simge", IS + ONKOSUL, "->",
      len(DAL) + sum(len(v) for v in DAL.values()) + 1, "(karar dugumu dahil)")
print("  dal A", len(TS), "tam siralama | dal B", len(TS2), "tam siralama | toplam kabul",
      len(TS) + len(TS2))

SISTEM  : her kosumda TEK bir yurutme sirasi gerceklesir
GOSTERIM: 23 simge = 10 is + 13 onkosul
BEDEL   : 168 tam siralama kabul ediliyor | tek siralamayi cizmek kapsam 0.006

topolojik siralama tek bir cikti veriyor:
  ['kabul', 'stok_ayir', 'usta_ata', 'musteri_bilgilendir', 'maliyet_hesapla', 'tezgah_ayir', 'isle', 'belgele', 'fatura_kes', 'kapat']
ayni cizgenin gecerli cikti sayisi: 168
katmanlar (esazamanli baslatilabilir isler):
  1. ['kabul']
  2. ['musteri_bilgilendir', 'stok_ayir', 'usta_ata']
  3. ['maliyet_hesapla', 'tezgah_ayir']
  4. ['isle']
  5. ['belgele', 'fatura_kes']
  6. ['kapat']
kritik yol uzunlugu: 6 adim | sirali yurutme 10 adim

is cifti: 45 | onkosulun sirasini belirledigi cift: 31 | serbest cift: 14
onkosulsuz kabul: 3628800 -> onkosullu kabul: 168 | daralma 21600 kat

bir onkosul eklenirse 168 nereye iner
  eklenebilir onkosul sayisi: 28
  en cok daraltan uc secim:
    maliyet_hesapla -> usta_ata            168 -> 16
    belgele -> maliyet_hesapla             168 -> 24
    fatura_kes -> musteri_bilgilendir      168 -> 30
  en az daraltan uc secim:
    musteri_bilgilendir -> fatura_kes      168 -> 138
    maliyet_hesapla -> belgele             168 -> 144
    usta_ata -> maliyet_hesapla            168 -> 152
  hepsinin ortalamasi: 84.0
  atolyede anlami olan iki secim (DD9):
    musteri_bilgilendir -> isle            168 -> 96
    belgele -> fatura_kes                  168 -> 96

karar dugumu eklenirse (yeniden isleme dali):
  simge 23 -> 26 (karar dugumu dahil)
  dal A 168 tam siralama | dal B 324 tam siralama | toplam kabul 492

Üç sayı: sistem her koşumda tek bir sıra gerçekleştiriyor, gösterim 23 simge yazıyor, bedel 168 tam sıralama kabul etmek. Tek bir sırayı çizmek kapsamı 1/168, yani 0,006 yapar.

Bir Çıktı ile Yüz Altmış Sekiz Çıktı

Giriş dereceli yordam bir sıralama döndürüyor ve o sıralama geçerlidir. Ama tek geçerli sıralama değildir; yordam kuyrukta birden çok iş varken alfabetik sırayla seçim yaptığı için hep aynı çıktıyı veriyor. Bu, gösterimin bir özelliği değil, yordamın belirliliğini sağlamak için konmuş bir ölçüttür. Başka bir ölçüt başka bir sıra verirdi ve o sıra da geçerli olurdu.

Kaç tanesi geçerli olurdu sorusunun yanıtı 168’dir. Kırk beş iş çiftinin 31’inin sırası önkoşullarla belirlenmiş, 14’ü serbest bırakılmıştır. Serbest çiftler birbirinden bağımsız değildir — biri sabitlenince başkaları da kısıtlanır — bu yüzden sayı iki üzeri on dört değil, tam sayımla bulunan 168’dir.

Buradaki asıl sonuç, gösterimin ne kadar iş yaptığıdır. Hiçbir önkoşul yazılmasaydı on iş, ondan bire inen çarpımın verdiği 3.628.800 ayrı sırada yapılabilirdi. On üç önkoşul bu sayıyı 168’e indiriyor: 21600 kat daralma. Gösterim ciddi bir bilgi taşıyor. Yine de 168 kalıyor, ve 168 sıfır değildir.

Eşzamanlı Dallar ve Katmanlar

Katman listesi aynı yordamın ikinci çıktısıdır: her turda kuyruğa giren işler kümesi. Atölyenin işleri altı katmana ayrılıyor. İkinci katmanda üç iş birden hazır oluyor — müşteri bilgilendirme, stok ayırma, usta atama — ve üçü de birbirini beklemiyor.

Katman sayısı kritik yol uzunluğudur: sınırsız paralellikle bütün işlerin bitebileceği en kısa adım sayısı. Altı adım, sıralı yürütmenin 10 adımına karşılık geliyor. Eşzamanlı dal gösterimi bu farkı yazan şeydir; dalları çizmeyen bir gösterim on adımlık bir zincir gibi okunur ve dört adımlık kazanç görünmez olur.

Katman yapısının 168 ile ilişkisi doğrudandır: gevşeklik tam olarak katman içindeki işlerin birbirine göre serbest olmasından doğuyor. Eşzamanlılık ile belirsizlik burada aynı olgunun iki adıdır — gösterim paralelliği ancak sırayı serbest bırakarak söyleyebilir.

Bir Önkoşul Eklemenin Sayısı

Yirmi sekiz ayrı önkoşul, döngü yaratmadan eklenebiliyor. Her biri 168’i başka bir yere indiriyor ve aralık geniş: en dar sonuç 16, en geniş sonuç 152, ortalama 84.

Aradaki fark yazılan cümlenin uzunluğundan gelmiyor. Her seçim tek bir önkoşuldur ve gösterime tek bir simge ekler; ama bir simge 168’i 16’ya indirirken bir başkası onu 152’de bırakıyor, yani neredeyse hiçbir şey söylemiyor. Bir simgenin belirsizlikten aldığı pay, o simgenin nereye konduğuyla belirlenir, ve bu pay dokuz kattan fazla değişebiliyor.

En çok daraltan seçim, atölyede en anlamlı seçim de değil. Maliyet hesabını usta atamasından önce zorlamak 168’i 16’ya indiriyor, ama böyle bir kural atölyenin işleyişinde karşılığı olmayan bir kuraldır. Atölyede gerçekten savunulabilecek iki kural — müşteri işleme başlamadan bilgilendirilir, belge fatura kesilmeden hazırlanır (DD9) — 168’i 96’ya indiriyor. Doğru sayı en küçük sayı değildir; doğru sayı, gerçekten var olan kısıtların bıraktığı sayıdır. Bir gösterimi daraltmak için olmayan bir kısıt yazmak, belirsizliği yalanla değiştirmektir.

Bunun bir yan sonucu, kullanım senaryosu dersinde ayrılan iki kaybın burada da karşımıza çıkmasıdır. Serbest bırakılmış 14 çiftin bir kısmı gerçekten serbesttir — atölye o iki işi istediği sırada yapabilir. Bir kısmı ise yalnızca yazılmamıştır: sıra gerçekte bellidir ama önkoşul kâğıda geçmemiştir. Gösterim ikisini aynı biçimde yazar, çünkü kısmi sıralamanın “serbest” ile “bilinmiyor” için ayrı bir simgesi yoktur. On dört çiftin kaçının hangi türden olduğu diyagramdan okunamaz; ancak akış sahibine tek tek sorularak ayrılabilir. Bu ayrım yapılmadığı sürece 168 sayısı gevşekliğin üst sınırıdır, ölçüsü değildir.

Karar Düğümü Belirsizliği Çoğaltır

Etkinlik gösteriminin üçüncü ögesi karardır: akış bir noktada koşula göre iki dala ayrılır. Atölyede böyle bir dal var — işleme sonrası denetim başarısız olursa iş yeniden işlenir (DD10).

Karar düğümü eklendiğinde gösterim 23 simgeden 26’ya çıkıyor. Kabul edilen tam sıralama sayısı ise 168 değil, iki dalın toplamı oluyor: dal A 168, dal B 324, toplam 492. Bir düğüm ve iki kenar eklemek kabul edilen yürütme sayısını yaklaşık üç katına çıkardı.

Nedeni şudur: gösterim dalın hangi koşulda seçildiğini bir metin olarak yazar, ama o metni sınayan bir yapı taşımaz. Diyagrama bakan biri için iki dal da her zaman açıktır. Karar, akışı ayıran bir şey gibi görünür; ölçüldüğünde birleştiren bir şey olduğu çıkar — iki ayrı yürütme kümesini tek gösterimin altında toplar.

Özet

• Etkinlik gösterimi sıra yazmaz, önkoşul yazar; on iş ve on üç önkoşul 23 simge ile bir kısmi sıra kurar ve o kısmi sıralama 168 tam sıralamayı birden kabul eder. Tek bir sırayı çizmek kapsamı 0,006 yapar.
• Topolojik sıralama tek bir çıktı verir çünkü kuyruktan seçim için bir ölçüt kullanır; geçerli çıktı sayısı 168’dir. Kırk beş iş çiftinin 31’i belirli, 14’ü serbesttir ve serbest çiftler bağımsız olmadığı için sayı tam sayımla bulunur.
• Önkoşulsuz on iş 3.628.800 sırada yapılabilirdi; on üç önkoşul bunu 21600 kat daraltıyor. Gevşeklik yazılmadıkça okur 168’i 1 sanır.
• İşler altı katmana ayrılıyor: kritik yol 6 adım, sıralı yürütme 10 adım. Paralellik ile belirsizlik aynı olgunun iki adıdır; gösterim paralelliği ancak sırayı serbest bırakarak söyler.
• Döngü yaratmadan eklenebilecek 28 önkoşuldan biri 168’i 16’ya indirirken bir başkası 152’de bırakıyor; atölyede gerçekten savunulabilir iki kural 96 veriyor. En çok daraltan kısıt en doğru kısıt değildir.
• Karar düğümü 23 simgeyi 26’ya çıkarırken kabul edilen tam sıralamayı 168’den 492’ye taşıyor: karar akışı ayırmaz, iki yürütme kümesini tek gösterimde birleştirir.

Sonraki Adım

Bu ders gösterimin fazla kabul ettiği yürütmeleri saydı: 168 sıranın hepsi geçerlidir, ama sistem her koşumda yalnız birini yapar. Kabul fazlaydı ve fazlalığın tamamı bilinçliydi — kısmi sıra zaten gevşek olmak için yazılır.

Sonraki gösterim aynı fazlalığı bilinçsizce üretir, ve üstüne bir de tersini yapar. Durum makinesi bir nesnenin geçebileceği durumları ve geçişleri yazar; atölyede iş emrinin dört durumu ve altı geçişi var. Bu makine gerçekte olan altı diziden ikisini reddediyor ve sistemde olmayan iki diziyi kabul ediyor. Reddedilenleri kurtarmak için iki geçiş eklendiğinde reddedilen sıfıra iniyor, ama fazla kabul 2’den 26’ya çıkıyor. Ders bunu bir kural olarak yazar: eksik kabulü kapatmanın bedeli fazla kabuldür.