Otomata Teorisi #04 | Çizgeler, yollar ve ağaçlar

Eğitmen: Dr. Süleyman Burak ÇELİK

Ekrandaki altı noktayı küçük bir bağlantı düzeni olarak düşünün. Noktalar yer değiştirirken çizgiler uçlarına bağlı kalıyor. Şimdi sorumuz şu: Çizim değiştiğinde bağlantılar da değişti mi? Bir noktayı yukarı taşımak, onun hangi noktalarla komşu olduğunu kendiliğinden değiştirmez. Bugün şeklin görünüşüyle matematiksel yapıyı ayıracağız. Sayılar yalnız düğümlerin adları; aralarındaki fiziksel uzaklığı veya taşıma süresini belirtmiyor. Altı düğümlü özgün bir çizgede kenarları, dereceleri ve bağlantıları izliyoruz. Bir yolun hangi kenarları kullandığını denetliyor; yineleme, basit yol ve çevrimi ayırıyoruz. Bağlı olmakla ağaç olmanın farkını, seçili düğümlerin indüklediği alt çizgeyi ve yönlü çizgelerde ulaşılabilirliği çalışan mekanizmalarla inceliyoruz. Bu derste: 1. Düğüm ve kenar kümeleri 2. Bir düğüme değen kenarları saymak 3. Ardışık her adımın kenarı bulunmalı 4. Geçerli yol, basit yol ve çevrim 5. Erişmek ile komşu olmak farklıdır 6. Seçilen düğümlerin bütün iç kenarları 7. Bağlı ve çevrimsiz bir yapı 8. Ok yönü tanımın bir parçasıdır 9. Her sıralı çift için yönlü erişim 10. Örnek, sözleşme ve kontrol sınırları Bölümler: 0:00 Çizim değişir, bağlantı korunabilir 1:22 Düğüm ve kenar kümeleri 2:39 Bir düğüme değen kenarları saymak 3:55 Ardışık her adımın kenarı bulunmalı 5:09 Geçerli yol, basit yol ve çevrim 6:23 Erişmek ile komşu olmak farklıdır 7:38 Seçilen düğümlerin bütün iç kenarları 8:55 Bağlı ve çevrimsiz bir yapı 10:12 Ok yönü tanımın bir parçasıdır 11:28 Her sıralı çift için yönlü erişim 12:43 Örnek, sözleşme ve kontrol sınırları 14:01 Aynı çizime ayrı sorular sor Kaynak kitap: Michael Sipser, Introduction to the Theory of Computation, Third Edition; §0.2 Graphs. Basılı 10–13 / fiziksel PDF 34–37, §0.2 Graphs, Example 0.17 ve Figure 0.18 sonuna kadar. Konu sırası kaynaktan izlenir; anlatım, çizimler ve örnekler özgündür. TypeScript yığın ve derinlik taramaları, bağımsız Python bağıntı kapanışı ve ayrık küme yöntemleriyle çapraz denetlenmiştir. Yol yinelemeye izin verir; basit yol vermez. Seçili düğümler arasındaki bütün kenarları koruyan işlem indüklenmiş alt çizgedir. Bağlı bir çizge çevrim içeriyorsa ağaç değildir. Yönlü çizgede tek adım bağlantısı ve çok adımda ulaşılabilirlik ayrıdır. Boş olmayan, döngüsüz basit çizge bu öğretim arayüzünün sınırıdır. Sonlu örnek kontrolleri genel teorem, donanım hızı veya güvenlik kanıtı değildir. Hedef kitle: bilgisayar mühendisliği ve kuramsal bilgisayar bilimine giriş öğrencileri.