Sıra Diyagramları

Önceki ders sistemin içini bilerek kapatan bir gösterimi ölçtü: yedi iç adım gösterime hiç çıkmadı ve 128 ayrı sistem aynı diyagrama düştü. Bu ders içeriyi açıyor. Sıra gösterimi katılımcıları yan yana dizer, iletileri aralarındaki oklarla yazar ve okları yukarıdan aşağıya sıralar. Her ileti, gönderen, alan ve sıra numarasıyla birlikte yazılıdır.

İlk bakışta bu, kaybın kapandığı yerdir. Değildir. Sıra gösterimi bir kaybı başka bir kaybın karşılığında kapatır: sistemin bir koşumunu eksiksiz gösterirken, sistemin öteki bütün koşumlarını hiç göstermez. Bu dersin ölçüsü o “öteki”nin sayısıdır.

Sistemin Ürettiği İzler

Bakım atölyesinin akışı dört yerde çatallanıyor. Stok ayırma başarılı olabilir ya da olmayıp işi bekletip yeniden denetebilir. Uygun usta bulunabilir ya da bulunmayıp iş kuyruğa alınabilir. İş emri bir, iki ya da üç kalem taşıyabilir. Belge üretimi istenebilir ya da istenmeyebilir.

Bu dört boyut bağımsız olduğu için sistem $2 \times 2 \times 3 \times 2 = 24$ ayrı iz üretiyor. İz, baştan sona bir koşumun ileti dizisidir; uzunlukları altı ile on iki arasında değişiyor. Bir sıra diyagramı tanımı gereği bu 24 dizinin birini çizer.

Kapsamın Ölçülmesi

Aşağıdaki model ortak tanımın akış ve iz tanımlarını aynen kurar, üstüne parçalı diyagram kavramını ekler (DD5): bir boyut “açık” bırakılırsa diyagram o boyutu tek bir değere sabitlemek yerine bir koşullu dal ya da döngü parçasıyla çizer ve o boyutun bütün değerlerini kapsar. Simge sayımı katılımcı, ileti, parça ve koruma koşulu toplamıdır.

"""Sira gosterimi: bir diyagram kac izi kapsiyor , kac izi disarida birakiyor.
Ortak tanimin AKIS ve izler() tanimlari aynen kurulur."""
from itertools import product

AKIS = {
    "baslat": [("Kabul", "IsEmri", "olustur"), ("IsEmri", "Stok", "ayir")],
    "ayirma_basarili": [("IsEmri", "Atolye", "planla")],
    "ayirma_basarisiz": [("IsEmri", "Kabul", "beklet"), ("IsEmri", "Stok", "ayir")],
    "usta_bulundu": [("Atolye", "Usta", "ata")],
    "usta_yok": [("Atolye", "Kabul", "kuyruga_al"), ("Atolye", "Usta", "ata")],
    "her_kalem": [("Usta", "Kalem", "isle")],
    "belge": [("IsEmri", "Belge", "uret")],
    "bitir": [("IsEmri", "Kabul", "kapat")],
}
KALEM_ARALIGI = (1, 2, 3)


def iz_kur(ayirma, usta, k, belge):
    iz = list(AKIS["baslat"])
    if ayirma == "basarisiz":
        iz += AKIS["ayirma_basarisiz"]
    iz += AKIS["ayirma_basarili"]
    iz += AKIS["usta_bulundu"] if usta == "bulundu" else AKIS["usta_yok"]
    iz += AKIS["her_kalem"] * k
    if belge:
        iz += AKIS["belge"]
    iz += AKIS["bitir"]
    return tuple(iz)


def izler(kalem_araligi=KALEM_ARALIGI):
    return [iz_kur(a, u, k, b)
            for a in ("basarili", "basarisiz") for u in ("bulundu", "yok")
            for k in kalem_araligi for b in (True, False)]


def kapsam(gosterimler, tum_izler):
    kapsanan = {g for g in gosterimler if g in tum_izler}
    return {"gosterim": len(gosterimler), "kapsanan": len(kapsanan),
            "toplam": len(tum_izler), "oran": round(len(kapsanan) / len(tum_izler), 4)}


# ---- DD5: parcali diyagram. Acik boyut bir parca simgesiyle cizilir , kapali
# boyut tek bir degere sabitlenir. Simge sayimi: katilimci + ileti + parca + koruma.
KATILIMCI = 7   # Kabul , IsEmri , Stok , Atolye , Usta , Kalem , Belge


def parcali(acik, sabit=("basarili", "bulundu", 3, True), kalem_ust=3):
    ayirma, usta, k, belge = sabit
    ileti = len(AKIS["baslat"]) + len(AKIS["ayirma_basarili"]) + len(AKIS["bitir"])
    parca = koruma = 0
    if "ayirma" in acik:
        ileti += len(AKIS["ayirma_basarisiz"]); parca += 1; koruma += 2
    elif ayirma == "basarisiz":
        ileti += len(AKIS["ayirma_basarisiz"])
    if "usta" in acik:
        ileti += len(AKIS["usta_bulundu"]) + len(AKIS["usta_yok"]); parca += 1; koruma += 2
    else:
        ileti += len(AKIS["usta_bulundu"] if usta == "bulundu" else AKIS["usta_yok"])
    if "kalem" in acik:
        ileti += 1; parca += 1; koruma += 1
    else:
        ileti += k
    if "belge" in acik:
        ileti += 1; parca += 1; koruma += 1
    elif belge:
        ileti += 1
    kabul = [iz_kur(a, u, kk, b)
             for a in (("basarili", "basarisiz") if "ayirma" in acik else (ayirma,))
             for u in (("bulundu", "yok") if "usta" in acik else (usta,))
             for kk in (range(1, kalem_ust + 1) if "kalem" in acik else (k,))
             for b in ((True, False) if "belge" in acik else (belge,))]
    return {"simge": KATILIMCI + ileti + parca + koruma, "ileti": ileti,
            "parca": parca, "kabul": kabul}


def duz_simge(iz):
    """Parcasiz bir sira diyagraminin simgesi: katilimci + cizilen ileti."""
    return KATILIMCI + len(iz)


IZ = izler()
print("SISTEM  :", len(IZ), "iz | uzunluklar:", sorted({len(i) for i in IZ}))
print("GOSTERIM:", parcali(())["simge"], "simge (parcasiz tek iz)")
print("BEDEL   :", len(IZ) - 1, "iz gosterime hic girmiyor")
print()
for n in (1, 2, 3, 4):
    k = kapsam([tuple(i) for i in IZ[:n]], IZ)
    print(f"  {n} parcasiz diyagram -> kapsam {k['kapsanan']}/{k['toplam']}"
          f" = {k['oran']} | simge {sum(duz_simge(i) for i in IZ[:n])}")
print()
print("parca eklendikce")
print("acik boyut                     simge  kapsanan  kapsam  simge/iz")
birikim = ()
for ek in ("kalem", "belge", "ayirma", "usta"):
    birikim += (ek,)
    p = parcali(birikim)
    kap = kapsam(p["kabul"], IZ)
    print(f"{'+'.join(birikim):30s} {p['simge']:5d} {kap['kapsanan']:9d}"
          f"  {kap['oran']:6} {p['simge'] / kap['kapsanan']:9.2f}")
print()
print("24 izin hepsini parcasiz kapsamak:", sum(duz_simge(i) for i in IZ),
      "simge | parcali kapsamak:",
      parcali(("kalem", "belge", "ayirma", "usta"))["simge"], "simge")
print()
# DD6: dongu siniri [1..*] yazilirsa. Karsilastirma penceresi kalem <= 6.
acik = ("kalem", "belge", "ayirma", "usta")
for ust, ad in ((3, "dongu siniri [1..3]"), (6, "dongu siniri [1..*]")):
    p = parcali(acik, kalem_ust=ust)
    kap = kapsam(p["kabul"], IZ)
    fazla = [i for i in p["kabul"] if i not in IZ]
    print(f"{ad:22s} kabul {len(p['kabul']):3d} | kapsam"
          f" {kap['kapsanan']}/{kap['toplam']} = {kap['oran']} | fazla kabul {len(fazla)}")
print()
# DD7: sistem degismeden IZ KUMESI buyurse. Kalem araligi 1..6 olan atolye.
IZ6 = izler((1, 2, 3, 4, 5, 6))
tek = [iz_kur("basarili", "bulundu", 3, True)]
p3 = parcali(acik, kalem_ust=3)
print("ayni iki diyagram , iz kumesi", len(IZ), "yerine", len(IZ6), "olsaydi")
for ad, g in (("parcasiz tek iz", tek), ("dort parcali diyagram", p3["kabul"])):
    a, b = kapsam(g, IZ), kapsam(g, IZ6)
    print(f"  {ad:22s} kapsam {a['kapsanan']}/{a['toplam']} = {a['oran']}"
          f"  ->  {b['kapsanan']}/{b['toplam']} = {b['oran']}")
print()
# DD8: her ileti turu senkron ya da eszamansiz. Gosterim yazmazsa kac sistem duser.
ILETI_TURU = sorted({m[2] for a in AKIS.values() for m in a})
GERCEK_KIP = {x: ("eszamansiz" if x in ("uret", "kuyruga_al") else "senkron")
              for x in ILETI_TURU}


def kip_gosterimi(kip, yazilan):
    return tuple(kip[x] if x in yazilan else None for x in ILETI_TURU)


def kip_dusen(yazilan):
    hedef = kip_gosterimi(GERCEK_KIP, yazilan)
    return sum(1 for s in product(("senkron", "eszamansiz"), repeat=len(ILETI_TURU))
               if kip_gosterimi(dict(zip(ILETI_TURU, s)), yazilan) == hedef)


tam = parcali(acik, kalem_ust=3)["simge"]
print("kapsami 1.0 olan diyagramda", len(ILETI_TURU), "ileti turu var")
for ad, yazilan in (("kip hic yazilmaz", ()),
                    ("yalniz iki eszamansiz kip yazilir", ("uret", "kuyruga_al")),
                    ("dokuz kipin dokuzu yazilir", tuple(ILETI_TURU))):
    print(f"  {ad:34s} simge {tam + len(yazilan):3d}"
          f" | ayni gosterime dusen {kip_dusen(yazilan):4d}")

SISTEM  : 24 iz | uzunluklar: [6, 7, 8, 9, 10, 11, 12]
GOSTERIM: 16 simge (parcasiz tek iz)
BEDEL   : 23 iz gosterime hic girmiyor

  1 parcasiz diyagram -> kapsam 1/24 = 0.0417 | simge 14
  2 parcasiz diyagram -> kapsam 2/24 = 0.0833 | simge 27
  3 parcasiz diyagram -> kapsam 3/24 = 0.125 | simge 42
  4 parcasiz diyagram -> kapsam 4/24 = 0.1667 | simge 56

parca eklendikce
acik boyut                     simge  kapsanan  kapsam  simge/iz
kalem                             16         3   0.125      5.33
kalem+belge                       18         6    0.25      3.00
kalem+belge+ayirma                23        12     0.5      1.92
kalem+belge+ayirma+usta           28        24     1.0      1.17

24 izin hepsini parcasiz kapsamak: 384 simge | parcali kapsamak: 28 simge

dongu siniri [1..3]    kabul  24 | kapsam 24/24 = 1.0 | fazla kabul 0
dongu siniri [1..*]    kabul  48 | kapsam 24/24 = 1.0 | fazla kabul 24

ayni iki diyagram , iz kumesi 24 yerine 48 olsaydi
  parcasiz tek iz        kapsam 1/24 = 0.0417  ->  1/48 = 0.0208
  dort parcali diyagram  kapsam 24/24 = 1.0  ->  24/48 = 0.5

kapsami 1.0 olan diyagramda 9 ileti turu var
  kip hic yazilmaz                   simge  28 | ayni gosterime dusen  512
  yalniz iki eszamansiz kip yazilir  simge  30 | ayni gosterime dusen  128
  dokuz kipin dokuzu yazilir         simge  37 | ayni gosterime dusen    1

Üç sayı: sistem 24 iz, gösterim 16 simge, bedel 23 iz gösterime hiç girmiyor. Kapsam 1/24, yani 0,0417.

Dört Diyagram Yetmez

Kapsam doğrusal artıyor. İki diyagram 2/24 = 0,0833, üç diyagram 3/24 = 0,125, dört diyagram 4/24 = 0,1667. Her yeni diyagram tam olarak bir iz ekliyor, çünkü her biri tek bir koşumdur ve koşumlar birbirinin yerini tutmaz.

Yirmi dört izin hepsini parçasız diyagramlarla kapsamak 384 simge gerektiriyor. Bu, ileti sayısı toplamına katılımcı listelerinin yirmi dört kez tekrar edilmesinin eklenmesidir. Böyle bir belge kimse tarafından okunmaz; sıra diyagramlarının pratikte üç beş taneyle sınırlı kalmasının nedeni budur, ve o üç beş tane 0,125 civarında bir kapsam demektir.

Buradan çıkan cümle şudur: bir sıra diyagramı kümesi sistemi göstermez, sistemden birkaç örnek gösterir. Örneklerin hangileri olduğu bir seçimdir ve o seçim gösterimde yazmaz — okur, elindeki dört izin 24’ün hangi dördü olduğunu diyagramdan okuyamaz.

Parça Simgeleri Kapsamı Simge Başına Büyütür

Orta tablo başka bir yol ölçüyor. Döngü parçası açıldığında kalem boyutu tek bir değere sabitlenmiyor: üç ileti yerine bir ileti ve bir döngü parçası çiziliyor. Simge sayısı 16’da kalıyor — parçasız diyagramla aynı — ama kapsanan iz 1’den 3’e çıkıyor.

Sıradaki üç satır aynı biçimde ilerliyor. İsteğe bağlı belge üretimi bir parçaya alınınca 18 simge 6 iz kapsıyor. Ayırmanın iki dalı koşullu dala alınınca 23 simge 12 iz. Usta bulunmasının iki dalı da alınınca 28 simge 24 izin hepsini kapsıyor. İz başına simge 5,33’ten 1,17’ye iniyor; aynı kapsamı parçasız elde etmek 384 simge isterken parçalı gösterim 28 simge ile bitiriyor, yaklaşık on dört kat az.

Bu, parçalı gösterimin bedava olduğu anlamına gelmez. Parçasız bir diyagram tek bir yukarıdan aşağıya okumadır; parçalı diyagram, dört parçanın her birinde okuyucudan bir seçim yapmasını ister ve okuma sayısı 24’e çıkar. Kapsam kazanıldı, tek okunurluk verildi. Gösterimin söylediği şey de değişti: parçasız diyagram “böyle bir koşum olmuştur” der, parçalı diyagram “şu koşumlar olabilir” der. Birincisi bir gözlem, ikincisi bir iddiadır ve iddia yanlış olabilir.

Kapsam Bir Kalite Ölçüsü Değildir

Alt iki blok bunun iki ayrı kanıtını veriyor.

Birincisi: döngü parçasına üst sınır yazılmazsa (DD6), yani “bir ya da daha çok kalem” denip üst sınır verilmezse, kapsam yine 24/24 = 1,0 kalıyor ama diyagramın kabul ettiği dizi sayısı 24’ten 48’e çıkıyor. Yirmi dörtü gerçek, yirmi dördü sistemde olmayan dizilerdir: dört, beş, altı kalemli iş emirleri. Fazla kabul 0’dan 24’e çıktı ve kapsam hiç değişmedi. Kapsam yalnız “gerçek izlerin kaçı gösterildi” sorusunu yanıtlar; “gösterilenlerin kaçı gerçek” sorusunu yanıtlamaz, ve ikinci soru sorulmadıkça bir gösterim ölçülmüş sayılmaz.

İkincisi: iz kümesi büyüyünce oran, gösterim hiç değişmeden düşüyor. Kalem aralığı üç yerine altı olan bir atölyede (DD7) aynı sistem 48 iz üretiyor. Parçasız tek diyagramın kapsamı 0,0417’den 0,0208‘e, dört parçalı diyagramın kapsamı 1,0’dan 0,5’e iniyor. Diyagramlara tek bir simge eklenmedi, tek bir simge silinmedi.

Bu yüzden kapsam oranı hiçbir yerde yalnız yazılmaz. “Kapsam 0,5” bir bilgi taşımaz; “48 izin 24’ü” taşır. Oran, paydanın büyüklüğüne bağlı bir sayıdır ve payda yazılmadığında karşılaştırma yapılamaz.

Kapsanan İz de Eksik Yazılabilir

Kapsam bir izin çizilip çizilmediğini ölçüyor, nasıl çizildiğini ölçmüyor. Son blok bu ikinci ekseni sayıyor. Sıra gösterimi her iletiyi bir kip ile yazabilir: çağıran, yanıt gelene kadar bekliyorsa senkron, beklemiyorsa eşzamansız. Akıştaki dokuz ayrı ileti türünün her biri için bu bir ikili karardır ve atölyede ikisi eşzamansızdır — belge üretimi ile kuyruğa alma (DD8).

Kapsamı 1,0 olan 28 simgelik diyagram bu dokuz kararın hiçbirini yazmıyor. Sonuç: 512 ayrı sistem aynı diyagrama düşüyor. Diyagram bütün izleri kapsıyor ve gene de hangi sistemi gösterdiğini söylemiyor. İki eşzamansız kip yazıldığında sayı 128’e, dokuzunun dokuzu yazıldığında 1‘e iniyor; bedel 28 simgeden 37’ye çıkmaktır.

İki eksen birbirinden bağımsızdır ve ikisi de ayrı ayrı yazılmadıkça gösterim ölçülmüş sayılmaz. Birincisi hangi izler sorusudur ve yanıtı kapsamdır. İkincisi her izin ne kadarı sorusudur ve yanıtı aynı gösterime düşen sistem sayısıdır. Bir gösterim ilkinde tam not alıp ikincisinde 512’de kalabilir; tersi de olur, tek bir izi bütün alanlarıyla yazan bir diyagram ikinci eksende 1’dir ve birincide 0,0417.

Özet

• Bakım atölyesinin akışı dört bağımsız çatallanmayla 24 iz üretiyor; bir sıra diyagramı tanımı gereği bu izlerin birini çizer, kapsamı 1/24 = 0,0417 ve 23 iz dışarıda kalır.
• Kapsam parçasız diyagram sayısıyla doğrusal artar: dört diyagram 4/24 = 0,1667 ve 56 simge. Yirmi dört izin hepsini parçasız kapsamak 384 simge ister.
• Döngü ve koşullu dal parçaları kapsamı simge başına büyütür: 16 simge 3 iz, 18 simge 6 iz, 23 simge 12 iz, 28 simge 24 iz. İz başına simge 5,33’ten 1,17’ye iner.
• Parçalı gösterim tek okunurluğu verir: dört parça okuyucudan dört seçim ister ve olası okuma sayısı 24’e çıkar. Gösterim bir gözlem olmaktan çıkıp bir iddiaya dönüşür.
• Kapsam 1,0 bir başarı ölçüsü değildir: döngü sınırı yazılmayınca kapsam 1,0 kalırken fazla kabul 0’dan 24’e çıkıyor; iz kümesi 24’ten 48’e büyüyünce aynı diyagramların kapsamı 0,0417’den 0,0208’e ve 1,0’dan 0,5’e iniyor.
• Kapsam ile belirsizlik ayrı eksenlerdir: kapsamı 1,0 olan 28 simgelik diyagram dokuz iletinin kipini yazmadığı için 512 sistemi ayırt edemiyor; dokuzu da yazılınca 37 simgeyle 1’e iner.

Sonraki Adım

Sıra gösterimi bir soruyu hiç sormadı: bu iletiler başka bir sırayla gidebilir miydi. Her diyagram tek bir sıra yazıyor ve o sırayı zorunluymuş gibi gösteriyor. Oysa atölyedeki işlerin çoğu birbirini beklemiyor; müşteriyi bilgilendirmekle maliyet hesaplamak arasında hiçbir öncelik yok, ve ikisi herhangi bir sırada yapılabilir.

Sonraki gösterim tam olarak bunu yazar: işler arasındaki önkoşulları yazar, sırayı yazmaz. On iş ve on üç önkoşul, hangi sıraların geçerli olduğunu belirler ve bu sıraların sayısı Veri Yapıları kursundaki topolojik sıralamanın kaç ayrı çıktı verebildiğidir. Sayı 168’dir. Bir etkinlik diyagramı, tek bir yürütme sırası değil, 168 yürütme sırasının tamamını birden kabul eder — ve gevşekliğin sayısı yazılmadıkça okur onu kesinlik sanar.