المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر
غزوة الحديبية والهدنة بين النبي وقريش
2024-11-01
بعد الحديبية افتروا على النبي « صلى الله عليه وآله » أنه سحر
2024-11-01
المستغفرون بالاسحار
2024-11-01
المرابطة في انتظار الفرج
2024-11-01
النضوج الجنسي للماشية sexual maturity
2024-11-01
المخرجون من ديارهم في سبيل الله
2024-11-01

الغيب عند أهل التصوف
8-11-2014
Friction
15-12-2016
إزالة مغنطة المعادن
19-9-2019
مبررات منح الشخصية القانونية الدولية للشركات متعددة الجنسية
26-2-2017
طريقة رسم منحنى المعايرة ( Titration curve )
2024-02-04
آلية نشوء مناطق التجاوز
20-6-2021

Subset Sum Problem  
  
1770   04:11 مساءً   date: 18-7-2020
Author : Borwein, J. and Bailey, D
Book or Source : Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters
Page and Part : ...


Read More
Date: 7-8-2020 556
Date: 24-9-2020 1646
Date: 9-9-2020 613

Subset Sum Problem

There are two problems commonly known as the subset sum problem.

The first ("given sum problem") is the problem of finding what subset of a list of integers has a given sum, which is an integer relation problem where the relation coefficients a_i are 0 or 1.

The ("same sum problem") is the problem of finding a set of n distinct positive real numbers with as large a collection as possible of subsets with the same sum (Proctor 1982).

The same sum problem was solved by Stanley (1980) using the tools of algebraic geometry, with the answer given for n numbers by the first n positive integers: {1,2,...,n}. Proctor (1982) gave the first elementary proof of this result. The maximal numbers of subsets of {1,2,...,n} having the same sum for n=1, 2, ... are 1, 1, 2, 2, 3, 5, 8, 14, 23, ... (OEIS A025591). Similarly, the numbers of different subset sums for n=1, 2, ... are 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, ... (OEIS A000124). For example, for n=3, the subsets of {1,2,3} are

sumemptyset = 0

(1)

1 = 1

(2)

2 = 2

(3)

3 = 3

(4)

1+2 = 3

(5)

1+3 = 4

(6)

2+3 = 5

(7)

1+2+3 = 6,

(8)

so the sum appearing most often is 3, which occurs twice, and the number of different sums is 7.

The given sum problem is NP-complete. For small cases, it be solved using generating functions. Consider the number of ways c_(m,s) to select m out of M given integers {a_1,...,a_M} such that their sum equals s, and define the generating function

 G(x,y)=product_(k=1)^M(1+x^(a_k)y).

(9)

Upon expanding in powers of y, this becomes

 G(x,y)=sum_(m=1)^MG_m(x)y^m.

(10)

But as a result of the exponent law x^mx^n=x^(m+n)G_m(x) is precisely the desired generating function

 G_m(x)=sum_(s)c_(m,s)x^s.

(11)

For example, consider the problem of picking m objects from the set {1,2,3,4,5}. The generating function G(x,y) is

 G(x,y)=y^5x^(15)+(x^(14)+x^(13)+x^(12)+x^(11)+x^(10))y^4+(x^(12)+x^(11)+2x^(10)+2x^9+2x^8+x^7+x^6)y^3+(x^9+x^8+2x^7+2x^6+2x^5+x^4+x^3)y^2+(x^5+x^4+x^3+x^2+x)y+1.

(12)

So, for example, selecting m=3 objects has the generating function

G_3(x) = sum_(s)c_(3,s)x^s

(13)

= x^(12)+x^(11)+2x^(10)+2x^9+2x^8+x^7+x^6,

(14)

so the number of ways of picking three of the integers 1 through 5 and having them sum to s=12, 11, ..., 6 are the coefficients c_(3,s) of G_3(x), namely 1, 1, 2, 2, 2, 1, and 1. These solutions are summarized in the following table.

s solutions
6 (1, 2, 3)
7 (1, 2, 4)
8 (1, 2, 5), (1, 3, 4)
9 (1, 3, 5), (2, 3, 4)
10 (1, 4, 5), (2, 3, 5)
11 (2, 4, 5)
12 (3, 4, 5)

A nice explicit example original proposed by Pólya (1956) asks for the number of ways to make change from an American dollar (using pennies, nickels, dimes, quarters, and half-dollars). The answer of 292 is provided as the coefficient of the x^(100) term in the series

 sum_(n=0)^inftyP_kx^k=1/((1-x)(1-x^5)(1-x^(10))(1-x^(25))(1-x^(50)))

(15)

(Borwein and Bailey 2003, p. 21).


REFERENCES:

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 22-24, 2003.

Coster, M. J.; LaMacchia, B. A.; Odlyzko, A. M.; and Schnorr, C. P. "An Improved Low-Density Subset Sum Algorithm." In Advances in Cryptology: EUROCRYPT '91 (Brighton, 1999) (Ed. D. W. Davis). New York: Springer-Verlag, pp. 54-67, 1992.

Coster, M. J.; Joux, A.; LaMacchia, B. A.; Odlyzko, A. M.; Schnorr, C. P.; and Stern, J. "Improved Low-Density Subset Sum Algorithms." Comput. Complex. 2, 111-128, 1992.

Ferguson, H. R. P. and Bailey, D. H. "A Polynomial Time, Numerically Stable Integer Relation Algorithm." RNR Techn. Rept. RNR-91-032, Jul. 14, 1992.

Lagarias, L. C. and Odlyzko, A. M. "Solving Low-Density Subset Sum Problems." J. ACM 32, 229-246, 1985.

Pólya, G. "On Picture-Writing." Amer. Math. Monthly 63, 689-697, 1956.

Proctor, R. A. "Solution of Two Difficult Combinatorial Problems with Linear Algebra." Amer. Math. Monthly 89, 721-734, 1982.

Schnorr, C. P. and Euchner, M. "Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems." In Fundamentals of Computation Theory: Proceedings of the 8th International Conference, Fct '91 Gosen, Germany, September 9-13, 1991. Berlin: Springer-Verlag, pp. 68-85, 1991.

Sloane, N. J. A. Sequences A000124/M1041 and A025591 in "The On-Line Encyclopedia of Integer Sequences."

Stanley, R. P. "Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property." SIAM J. Alg. Disc. Math. 1, 168-184, 1980.




الجبر أحد الفروع الرئيسية في الرياضيات، حيث إن التمكن من الرياضيات يعتمد على الفهم السليم للجبر. ويستخدم المهندسون والعلماء الجبر يومياً، وتعول المشاريع التجارية والصناعية على الجبر لحل الكثير من المعضلات التي تتعرض لها. ونظراً لأهمية الجبر في الحياة العصرية فإنه يدرّس في المدارس والجامعات في جميع أنحاء العالم. ويُعجب الكثير من الدارسين للجبر بقدرته وفائدته الكبيرتين، إذ باستخدام الجبر يمكن للمرء أن يحل كثيرًا من المسائل التي يتعذر حلها باستخدام الحساب فقط.وجاء اسمه من كتاب عالم الرياضيات والفلك والرحالة محمد بن موسى الخورازمي.


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

تعتبر المعادلات التفاضلية خير وسيلة لوصف معظم المـسائل الهندسـية والرياضـية والعلمية على حد سواء، إذ يتضح ذلك جليا في وصف عمليات انتقال الحرارة، جريان الموائـع، الحركة الموجية، الدوائر الإلكترونية فضلاً عن استخدامها في مسائل الهياكل الإنشائية والوصف الرياضي للتفاعلات الكيميائية.
ففي في الرياضيات, يطلق اسم المعادلات التفاضلية على المعادلات التي تحوي مشتقات و تفاضلات لبعض الدوال الرياضية و تظهر فيها بشكل متغيرات المعادلة . و يكون الهدف من حل هذه المعادلات هو إيجاد هذه الدوال الرياضية التي تحقق مشتقات هذه المعادلات.