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ı: 83
Ö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
- 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
BankacılıkGalatasaray ÜniversitesiÖzel Hukuk Ana Bilim Dalı
DOÇ. DR. SITKI ANLAM ALTAY
- Atıkların yüksek sıcaklıkta sürekli pirolizi için yarı-pilot ölçek yeni bir vidalı reaktör geliştirilmesi
Development of a new semi-pilot scale screw reactor for continuous pyrolysis of wastes at high temperature
ANIL ÜNSAÇ
Doktora
Türkçe
2024
Enerjiİstanbul Teknik ÜniversitesiEnerji Bilim ve Teknoloji Ana Bilim Dalı
PROF. DR. NİLGÜN YAVUZ
PROF. DR. HASAN CAN OKUTAN
- Potentialities for and limits to inclusion by education: The case of Syrian children's education in Turkey and child labour
Eğitim tarafından içermede potansiyeller ve limitler: Türkiye'deki Suriyeli çocukların eğitimi ve çocuk işçiliği
YASEMİN KIZILOĞLU
Yüksek Lisans
İngilizce
2021
Sosyal HizmetOrta Doğu Teknik ÜniversitesiSosyal Politika Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MEHMET OKYAYUZ
- Keeping memories on social media
Sosyal medyada anıları saklamak
ÇAĞRI GİZEM VARLI
Yüksek Lisans
İngilizce
2017
Endüstri Ürünleri Tasarımıİstanbul Teknik ÜniversitesiEndüstri Ürünleri Tasarımı Ana Bilim Dalı
DOÇ. DR. GÜLNAME TURAN
- Tekirdağ havzası yüksek çözünürlüklü sismik yansıma verilerinin işlenmesi ve yorumlanması
Processing and interpreting high resolutioned seismic reflection datas of the Tekirdag basin
EMRE PERİNÇEK
Yüksek Lisans
Türkçe
2011
Jeofizik Mühendisliğiİstanbul Teknik ÜniversitesiJeofizik Mühendisliği Ana Bilim Dalı
DOÇ. DR. HÜLYA KURT