Biyoinformatik | Algoritma - 1


Ayşegül MURAT, Ege Üniversitesi Sağlık Biyoinformatiği A.B.D., Doktora Öğrencisi

Algoritma Nedir?


Bilgisayara yapmak istediğimiz işi tanımlarken, başlangıç ve son durumu belirtmemiz gerekiyor. Bir başlagıç durumu ile başlatıp. daha önceden belirtilmiş olduğumuz son durumu görmesiyle sonlanan bir dizi işlemler kümesine algoritmanın genel tanımı olarak bakabiliriz. Bir algoritma, girdi olarak değer veya değer kümesi alan ve çıktı olarak bazı değer veya değerler kümesi üreten iyi tanımlanmış herhangi bir hesaplama prosedürüdür. Bu tanımında söylediği gibi algoritma, girdiyi çıktıya dönüştüren bir dizi hesaplama aşamasıdır. Ayrıca bir algoritmayı, iyi tanımlanmış bir hesaplama problemini çözmek için bir araç olarak görebiliriz. Problemin ifadesi genel olarak istenen girdi/çıktı ilişkisini belirtir. Algoritma, bu girdi/çıktı ilişkisine ulaşmak için belirli bir hesaplama prosedürünü tanımlar. Örneğin, bir sayı dizisini, azalan sıraya göre sıralamamız gerekebilir. [1,2] Bu problem pratikte sık sık ortaya çıkar ve birçok standart tasarım tekniği ve analiz aracının tanıtılması için verimli bir zemin sağlar. Sıralama problemini şu şekilde tanımlayabiliriz:


girdi (input): n sayının bir dizisi (a1, a2,……an).

çıktı (output): ,…… gibi girdi dizisinin (a1, a2,……an) bir permütasyonu (yeniden sıralanması)


Örneğin, (31, 41, 59, 26, 41, 58)’den oluşan bir girdi sekansı verildiğinde bir sıralama algoritması (sorting algorithm) çalıştırdığınızda size (26, 31, 41, 41, 58, 59) şeklinde sıralanmış çıktıyı verecektir.[1,2]


Bu basit örneği bilgisayara yaptırmak için günümüzde çok sayıda iyi sıralama algoritmasına sahibiz. Belirli bir uygulama için hangi algoritmanın en iyi olduğu, diğer faktörlerin yanı sıra, sıralanacak öğelerin sayısına, öğelerin halihazırda bir şekilde sıralanma derecesine, öğe değerlerinde olası kısıtlamalara, bilgisayarın mimarisine ve türüne hatta ana bellek, disklere, kullanılacak depolama aygıtına bağlıdır.[1]


Bir algoritmanın doğru olduğunu söylememiz için birden fazla özelliği içermesi gerekmektedir. Bunlardan biri her girdi örneği için çıktıyı doğru bir şekilde bulması ve programın durmasıdır. Yukardaki sıralama örneğinde sadece pozitif sayılar verdik. Bu dizinin içerisinde negatif sayıları, ondalıklı sayıları da kattığımızda yine algoritmanın doğru sonuç vermesini isteriz. Sadece pozitif sayılar için çalışan bir algoritma doğru bir algoritma değildir. Ya da doğru sonucu bunduğunda algoritmanın çalışmasını durdurmaması da başka bir doğru olmayan algoritma sonucudur. [1,3]

Algoritmalar Tarafından Ne Tür Problemler Çözülür?

Sıralama, algoritmaların geliştirdiği tek hesaplama problemi değildir. Algoritmalar aslında her yerdeler;

  • İnsan Genom Projesi, insan DNA’sındaki 100.000 genin tümünü tanımlama, insan DNA’sını oluşturan 3 milyar kimyasal baz çiftinin dizilerini belirleme, bu bilgileri veri analizi için veri tabanlarında saklama ve araçlar geliştirme hedeflerine doğru büyük ilerleme kaydetmiştir. Artık günümüzde rahatlıkla bunlara erişebilir olduğumuz gerçeği, bu adımların her birinin karmaşık algoritmalar gerektirdiğini değiştirmez. Bu algoritmaların geliştirilmesi hem insan hem makine açısından zamandan tasarruf ve doğruluk sağlamıştır.[1,4]

  • İnternet, dünyanın her yerinden insanların büyük miktarda bilgiye hızlı bir şekilde erişmesine ve almasına olanak sağlar. Akıllı algoritmaların yardımlarıyla, internet siteleri bu büyük hacimli verileri yönetebilir ve işleyebilir. Örneğin; en iyi seyahat yolunuzu belirleyen bir algoritma başlangıcını Türkiye’den yapacağınız bir yurtdışı geziniz için en kısa en ucuz yolları size söyleyebilir. Online bir bilet alırken ya da bir internet alışverişinizde yaparken karşınıza çıkan yönlendirmeleri aklınıza getirebilirsiniz.

  • Elektronik ticaret, mal ve hizmetlerin elektronik olarak müzakere edilmesini ve değiş tokuş edilmesini sağlar. Kredi kartı numaraları, şifreler ve banka ekstreleri gibi kişisel bilgilerin mahremiyetine bağlıdır. Elektronik ticarette kullanılan temel teknolojiler, sayısal algoritmalara ve sayı teorisine dayanan açık anahtarlı kriptografi ve dijital imzaları içerir.

  • İmalat ve diğer ticari işletmelerin kıt kaynakları genellikle en faydalı şekilde tahsis etmesi gerekir. Bir petrol şirketi, beklenen karını en üst düzeye çıkarmak için kuyularını nereye yerleştireceğimi bilmek isteyebilir. Bir siyasi aday, bir seçimi kazanma şansını en üst düzeye çıkarmak için kampanya reklamı satın almak için nereye para harcayacağını belirlemek isteyebilir. Bir internet servis sağlayıcısı, müşterilerine daha etkin hizmet verebilmek için ek kaynakları nereye yerleştireceğini belirlemek isteyebilir. Bunların tümü doğrusal programlama kullanılarak çözülebilecek sorunların örnekleridir. [1-4]

Şekil 1: Algoritmalar hangi konuda işlevsel olarak kullanılabilir olduğunun tablosu. [2]

Mevcut birden çok farklı algoritma olduğunu biliyoruz. Bu birçok algoritmik problem iki ortak özelliği sergiler:

  1. Bir problemi çözecek algoritmanın, ezici çoğunluğu problemi çözmeyen pek çok aday çözümü vardır. İşe yarayan veya “en iyi” olanı bulmak oldukça zor olabilir.

  2. Pratik uygulamalarının olması. Yukardaki örneklerden yola çıkarak en kısa yolu bularak en düşük maliyetle en hızlı sürede bir yere ulaşmak isteyen kişi, bir algoritma oluşturmak ya da sizin algoritmanızdan daha hızlı çözüm bulan bir web sitesinden yol tarifi almak isteyebilir veya araba kullanırken GPS kullanabilir. Yani hep en hızlı, en ucuz, en doğru işi yapma zorunluluğu var. Birey bazında ise siz bir algoritma geliştirdiğiniz sırada bir başkası sizden daha hızlı olanını yazar ve sizi değil onu tercih edebilirler.

Bir Algoritmanın Çeşitleri ve Özellikleri Nelerdir?

Kapsamlı arama (exhaustive search), kaba kuvvet (brute force), dal-ve-sınır (branch-and-bound), dinamik programlama (dynamic programming), bçl ve yönet algoritmaları (divide- and-conquer algorithms), makine öğrenmesi (machine learning) ve randomize algoritmalar (randomized algorithms) gibi çok sayıda algoritma çeşidi vardır.[2] Kapsamlı arama (exhaustive search) veya kaba kuvvet (brute force) algoritması, belirli bir çözüm bulmak için olası her alternatifi dener. Bazı durumlarda kaba kuvvet algoritmesında çeşitli alternatifler araştırırken, çok sayıda alternatifi, genellikle dal-ve-sınır (branch-and-bound) veya budama (pruning) olarak adlandırılan bir teknikten çıkarabiliriz. Bazı algoritmalar bir problemi daha küçük alt problemlere böler ve daha büyük olanın çözümünü oluşturmak için alt problemlerin çözümlerini kullanır. Alt problemlerin sayısıyla oluşan süre ve diğer problemleri dinamik programlama (dynamic programming) zaten bildiğimiz çözümleri hesaplamaktan kaçınır ve büyük ölçüde zaman kazandırması gibi farklı avantajları vardır.[1,2] Diğer yazıda derinlemesine inceleyeceğimiz algoritmanın özellikleri temelde şunlardır;

  1. Giriş (input)

  2. Belirlilik (definiteness)

  3. Çıkış (output)

  4. Etkililik (efficiency)

  5. Sınırlılık (boundedness)




Referanslar

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.

2. Jones, N. C., Pevzner, P. A., & Pevzner, P. (2004). An introduction to bioinformatics algorithms. MIT press.

3. Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3), 557-581.

4. Shopova, E. G., & Vaklieva-Bancheva, N. G. (2006). BASIC—A genetic algorithm for engineering problems solution. Computers & chemical engineering, 30(8), 1293-1309.

85 görüntüleme

Türkiye'nin Tek Popüler Genetik Bilim Dergisi

Bezelye Dergi ISSN: 2587-0173

Bizi Takip Et
  • Beyaz Facebook Simge
  • Beyaz Instagram Simge
  • White Twitter Icon
  • Icon-gmail
  • kisspng-white-logo-brand-pattern-three-d
  • images
  • medium
  • Dergilik
  • YouTube

© 2019 by Bezelye Dergi