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
- Ovulasyon indüksiyonu tedavisinde folliküler gelişimin ultrasonografik takibi
Başlık çevirisi yok
MERİH BAYRAM
Tıpta Uzmanlık
Türkçe
1987
Kadın Hastalıkları ve DoğumGazi ÜniversitesiKadın Hastalıkları ve Doğum Ana Bilim Dalı
DOÇ. DR. MÜLAZIM YILDIRIM
- Çimentonun sertleşmesi üzerinde kimyasal komponentlerin etkisi
Başlık çevirisi yok
NACİYE TÜRKEL
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- İzmir'de bazı yolların kapatılarak yaya bölgeleri oluşturma da kent peyzajını geliştirme açısından yeniden planlanması üzerinde araştırmalar
Başlık çevirisi yok
BAHAR TÜRKYILMAZ
Yüksek Lisans
Türkçe
1985
Şehircilik ve Bölge PlanlamaEge ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
- Atherosklerotik kalp hastalıklarında risk faktörleri
Risk factors in the coronary artery disease
MURAT SUHER
- Diesel motorları yakıt püskürtme sistemlerinin dinamik simülasyonu
Başlık çevirisi yok
İRFAN KARAGÖZ
Yüksek Lisans
Türkçe
1986
Makine MühendisliğiUludağ ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. OĞUZ BORAT