On online and approximate cover time problems
Çevrimiçi ve yaklaşık kaplama zamanı problemleri üzerine
- Tez No: 649858
- Danışmanlar: DR. ÖĞR. ÜYESİ ÜMİT IŞLAK
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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.
Özet (Çeviri)
As a generalization of the classical coupon collector problem in the probability theory, the cover time in random walks on Markov chains has been investigated in numerous studies in the literature. Especially, there are several results for the cover time of a simple random walk on connected and undirected graphs. In this thesis, we study two new problems about the cover time of graphs. Firstly, we build an on-line model where there is a walker moving with random time intervals on a graph growing in time. We initiate this study by examining the number of vertices covered up to a fixed time for a simple model, and we discuss further research directions. Secondly, we generalize the classical cover time definition in order to understand the differences between the partial covering and the full covering. We initiate this study with the investigation of the approximate covering time on specific graph families such as path graphs and complete graphs, and our main motivation is to explore the structure of the graphs allowing easy partial covering in terms of the order of magnitude. For the sake of completeness, we also give some preliminary results about the classical cover time problem and several variations of the problem from the literature such as edge covering and dynamic versions in the thesis.
Benzer Tezler
- Müziğin dünyadaki gelişim süreci içinde Türk müziğinin yeri ve problemleri
Place of Turkish music and it's problems during development of music in the world
FATMAGÜL DEMİRSÜ
- Türk sigorta sektöründe reasürans uygulamaları, karşılaşılan sorunlar ve çözüm yolları
Reinsurance practice in Turkish insurance sectör, main problems and solutions
ARZU TEMİMHAN (BAYER)
- Tarihi yüzer köprü için bakım onarım metodu ve maliyet değerlendirmesi
Maintenance and repair method and cost assessment for historical floating bridge
CİHAT KOÇ
Yüksek Lisans
Türkçe
2024
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. ZÜBEYDE ÖZTÜRK
- Yeni Çeltek Linyit Ocağı havalandırma sisteminin etüdü
The Research of Yeni Çeltek Colliery ventilation system
NAİL AŞIK
Yüksek Lisans
Türkçe
1993
Maden Mühendisliği ve Madencilikİstanbul Teknik ÜniversitesiPROF.DR. ERDİL AYVAZOĞLU
- Avrupa Birliği ve Türk Banka Hukuku yönünden fintek
Fintech from European Union and Turkish Banking Law perspectives
ŞEBNEM ELİF KOCAOĞLU ULBRİCH
Yüksek Lisans
Türkçe
2019
HukukGalatasaray ÜniversitesiÖzel Hukuk Ana Bilim Dalı
DOÇ. DR. SITKI ANLAM ALTAY