On online and approximate cover time problems

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2020

Tezin Dili: İngilizce

Öğrenci: MEHMET AKİF YILDIZ

Danışman: ÜMİT IŞLAK

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Olasılık teorisindeki klasikleşmiş kupon toplama probleminin bir genellemesi olarak, Markov zincirleri üzerindeki rastgele dolaşmanın kaplama zamanı literatürdeki birçok çalışmada incelenmiştir. Özellikle, bağlantılı ve yönsüz çizgeler üzerindeki basit rastgele dolaşmanın kaplama zamanı üzerine birçok sonuç bulunmaktadır. Bu tezde, çizgelerin kaplama zamanı üzerine iki yeni problem üzerine çalışılmıştır. İlk olarak, zamanla büyüyen bir çizge üzerinde hareketlerinin zaman aralıkları rassal olan bir gezicinin olduğu bir çevrimiçi model inşa edilmiştir. Belirli bir zamana kadar kaplanan köşelerin sayısı basit bir model üzerinde incelenerek bu çalışma başlatılmış ve çeşitli araştırma alanları tartışılmıştır. İkincisi, klasik kaplama zamanı tanımı genelleştirilerek, kısmi kaplama ve tam kaplama arasındaki farklar anlaşılmaya çalışılmıştır. Yolak çizgesi ve tam çizge gibi özel çizge ailelerinde yaklaşık kaplama zamanı incelenerek bu çalışma başlatılmış, büyüklük derecesi olarak daha kolay yaklaşık zamanına izin veren çizge yapıları keşfedilmesi temel motivasyon olmuştur. Bütünlük açısından, klasik kaplama zamanı üzerine temel sonuçlar ile kenar kaplama ve dinamik versiyonlar gibi problemin literatürde yer alan çeşitli varyasyonları da tezde verilmiştir.