First moment problem in longest common subsequences

---

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: 2018

Tezin Dili: İngilizce

Öğrenci: ABDURRAHMAN DEMİRELLİ

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

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

Özet:

Bu tezde, rastgele kelimelerin en uzun ortak altdizilerinin özellikleri, beklenen değerlerinin alt ve üst sınırları araştırılmış ve bu ortamda en uzun ortak altdizilerin varyanslarının asimptotik davranışları tartışılmıştır. Aynı zamanda, rastgele permütas- yonlarda en uzun ortak altdizilerin ve en uzun artan altdizilerin ilişkileri çalışılmış ve rastgele permütasyonların en uzun ortak altdizilerin uzunlukları kullanılarak oluşturul-muş $L^{(n)}$ matrisinin bazı özellikleri tartışılmıştır. Bu tezin amacı, 1970'lerde çalışılmaya başlanan en uzun ortak diziler hakkında detaylı bilgiye sahibi olup günümüzde yapılan araştırmalarla gelinen noktalara ve hala ucu açık sorulara dikkat çekmektir.