Alt küme toplamı problemi (subset sum problem)


yazan: Şadi Evren ŞEKER

Algoritma teorisinde meşhur problemlerden birisidir. NP-Complete problemlere iyi bir örnektir. Problemin tanımı aşağıdaki şekildedir:

verilen eksi ve artı tam sayılar kümesinin herhangi bir alt kümesinin toplamının 0 olduğunu bulmak.

Bu problemin kontrol edilmesi oldukça basittir ancak verilen sayı kümesinden yukarıdaki tanımı sağlayan bir alt küme bulmak kolay değildir.

Problemin örnek çözümü:

verilen sayı kümesi : { 1,4,-5,2,7,-4,2,9} olsun. Bu sayı kümesinin öyle bir alt kümesi var mıdır ki toplamı 0 olsun?

evet böyle bir alt küme buluna bilir örnek:
{-4,4} veya {-4,2,2} veya {1,4,-5} veya {9,-4,-5} … gibi

yukarıdaki örnek için bütün çözümleri verecek bir yöntemin geliştirilmesi mümkün olsa bile bu yöntemin çalışmas süresi problem kümesi büyüdükçe çok çok yüksek değerlere çıkacaktır.

daha fazla bilgi için.
NP-Complete
NP-Hard
tanımlarına bakabilirsiniz.


« Bir tümleyeni   |   Önermeler (kaziye) Mantığı (Propositional Logic) »



Yorumlar

Kullanıcı girişi yaparak ya da zorunlu olan * alanlarını doldurarak yorum yapabilirsiniz.

İsminiz *

Email adresiniz *

Web siteniz

Mesajınızı buraya yazabilirsiniz:

Henüz yorum yapılmamış.

  1. Belirsiz Çokterimli Tam (NP-Complete, Nondeterministic Polynomial Complete) : bilgisayar.kavramlari.com | 24 Mar 2008, 11:55

    [...] NP kümesinde bulunan başka bir probleme dönüştürmektir. En meşhur problemlerden bazıları: Altküme toplam problemi RSA [...]

  2. Merkle-Hellman Şifreleme (Merkle-Hellman Encryption) : bilgisayar.kavramlari.com | 24 Mar 2008, 12:23

    [...] mesaja saldırmak isteyen kişinin uğraşması gereken zorluk alt küme toplam problemi zorluğudur çünkü saldıran kişi B değerlerini bilmemektedir ve tahmin etmesinin tek yolu [...]

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Alt küme toplamı problemi (subset sum problem)' isimli yazı 29 Nov 2007 tarihinde, saat: 13:43 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1638 defa okunmuştur.

Benzer yazıları Automata (otomatlar, özdevinirler), Bilgisayar Kavramları, Bilgisayar Matematiği, Temel Bilimler kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.


Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar
Yapılan Son Yorumlar
Yakın Yazılar
Bağlantılar