Important Problem Types

Kategori: Algorithm Design and Analysis , 30 Mayıs 2020 , JanFranco


Bu yazımda önemli problem tiplerinden bahsedeceğim. Tabi ki problemleri tek tek sınıflandıramayız fakat göreceğimiz, çözeceğimiz problemlerin çoğunluğunu aşağıdaki problem tipleri oluşturacaktır:

Sorting (sıralama): Sıralama problemleri, bir listedeki, dizideki elemanların büyükten küçüğe veya küçükten büyüğe sıralanmasını ele alır. Elemanların sıranabilmesi için elemanlar arasında bir ilişki olmalıdır. Bu elemeanlar sayılar olabilir, harfler olabilir, stringler olabilir vs. Bilgisayar bilimcileri tarafından bulunmuş bir çok sıralama algoritması vardır. Bu algoritmaların en iyisi şeklinde bir ifade kullanamayız. Zaten en iyisi diye bir kavram olsa diğer algoritmalardan bahsetmezdik. En iyi denilen algoritma, karşılaştığımız problemde en kötü sonucu verebilir. Zaman efektifliği altında şuanda en hızlı çalışan algoritma n log2 n karşılaştırma yapmaktadır, daha azı henüz bulunamamıştır. Bir algoritmayı değerlendirirken sadece zaman efektifliği değil, yer efektifliği de kontrol edilmelidir. Bazı sıralama algoritmaları direk dizi üzerinde sıralama yaparken, bazı algoritmalar ekstra yer talep etmektedir.

Searching (arama): Arama problemlerinde, aradığımız değerin, keyin, verilen dizide olup olmadığını kontrol ederiz. Sıralama problemlerinde olduğu gibi, arama problemlerinde de bir çok algoritma mevcuttur fakat yine her durumda birbirinden farklı algoritmalar iyi sonuç verebilir. En iyi algoritma şudur şeklinde bir şey diyemeyiz.

String Processing (string işleme): Stringler karakter dizisidir. En çok bilinen string problemleri, string eşleştirme ve DNA dizilimleridir.

Graph Problems (graph problemleri): Graph, nodeların belirli açılarla birbirlerine bağlandığı bir veri yapısıdır. Ulaşım, iletişim, sosyal ve ekonomik ağlar, proje yönetimi, oyunlar vs. her türlü alanda kullanılabilirler. En basit graph algoritmaları graph-traversal algoritmaları (graph yapısında dolaşma), shortest-path algoritmaları (en kısa mesafe), yönlü graphlar için topological sorting algoritmalarıdır diyebiliriz. Kolay problemlerin yanında oldukça zor problemler de mevcuttur, traveling salesman problemi, graph renklendirme problemleri gibi.

Geometric Problems (geometrik problemler): Adı üstünde, geometrik problemlerdir. Bu bölümde klasik algoritmalardan closest-pair ve convex-hull problemlerini inceleyeceğiz.

Numerical Problems (sayısal problemler): Denklem çözme, intergral hesapları, fonksiyon hesapları vs. gibi matematiksel problemleri bu problem sınıfında gruplayabiliriz. Genellikle bu problemlerdeki ana sorun belirli bir sonuç alamamızdır. Genellikle exact sonuç almak yerine, o sonuca yaklaşmaya çalışacağız.


Sonraki Yazı: The Analysis Framework
Yorumlar

Henüz bir yorum bulunmuyor.