[ تعرٌف على ] خوارزمية أقليدس # اخر تحديث اليوم 2024-04-27

تم النشر اليوم 2024-04-27 | خوارزمية أقليدس

الفعالية الخوارزمية

عدد الخطوات المطلوبة في الخوارزمية الإقليدية لحساب القاسم المشترك الأكبر(x،y). النقط الحمراء تدل على عدد صغير نسبيا من الخطوات (سريع)، بينما النقط الصفراء والخضراء والزرقاء تدل على عدد أكبر على التوالي من النقط (بطيء). المنطقة الداكنة الزرقاء تخضع لمعادلة المستقيم y = Φx، حيث Φ يمثل النسبة الذهبية.
دُرست فعالية خوارزمية أقليدس بشكل كثيف. تتمثل هذه الفعالية في عدد الخطوات اللازمة من أجل إيجاد القاسم المشترك الأكبر المراد حسابه. أول تحليل لفعالية الخوارزمية يرجع إلى العالم غيينو، (كان ذلك عام 1811)، حيث أثبت أنه أثناء حساب القاسم المشترك الأكبر للعددين u و v، عدد الخطوات اللازمة، لا يمكن أن يتجاوز v. وزاد فيما بعد هذا البرهانَ دقة عندما برهن أن هذا العدد لا يمكن أن يتجاوز v/2 +2. انظر إلى بيير جوزيف إتيان فينك. في عام 1837، درس إيميل ليجي أسوأ حالة، والتي هي حيث يكون المقسوم والمقسوم عليه عددان متتاليان من متتالية فيبوناتشي. واصل غابرييل لامي سير فينك في عام 1844، مبرهنا على أن عدد خطوات خوارزمية إقليدس لا تتجاوز أبدا خمس مرات عدد الأرقام اللائي يكونن المقسوم عليه، مكتوبا في القاعدة العشرية.

في النظم العددية الأخرى

الأعداد الجذرية والأعداد الحقيقية
متعددات الحدود المقالة الرئيسة: القاسم المشترك الأكبر لمتعددتي حدود r k
−
2
(
x
)
= q k
(
x
) r k
−
1
(
x
)
+ r k
(
x
)
,
{\displaystyle r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x),}
a
(
x
) = x 4
−
4 x 3
+
4 x 2
−
3
x
+
14
=
( x 2
−
5
x
+
7
)
( x 2
+
x
+
2
)
and b
(
x
) = x 4
+
8 x 3
+
12 x 2
+
17
x
+
6
=
( x 2
+
7
x
+
3
)
( x 2
+
x
+
2
)
.
{\displaystyle {\begin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{and}}\\b(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).\end{aligned}}}
الأعداد الطبيعية الغاوسية
توزيع الأعداد الطبيعية الغاوسية u+vi في المستوى العقدي، من معايير u2+v2 أصغر من 500
الأعداد الغاوسية الصحيحة هن أعداد مركبة α = u + vi حيث u و v أعداد صحيحة، وi هو الجذر التربيعي لناقص واحد. بتعريف خوارزمية مماثلة لخوارزمية أقليدس، يتبين أن الأعداد الغاوسية تقبل هي الأخرى تفكيكا وحيدا لجداء أعداد غاوسية أخرى، وذلك باستعمال الحجة نفسها التي استعمل أعلاه. هذا التفكيك الوحيد يساعد في العديد من المجالات، منها على سبيل المثال، ايجاد جميع ثلاثيات فيثاغورس، ومنها أيضا البرهان على مبرهنة فيرما حول مجموع مربعين. مساهمة خوارزمية أقليدس في هذه التطبيقات غير أساسية حيث يمكن أن يُبرهن عليها بطرق أخرى. المجالات الإقليدية
الحلقات غير التبادلية

مثال

القاسم المشترك الأكبر ل 48 و 60 هو 12. القاسم المشترك الأكبر للعددين 252 و 198: 252 = 198 * 1 + 54 ‘ أربع وخمسون هو باقي قسمة 252 على 198 فنجد القاسم المشترك للعددين 198 و 54 198 = 54 * 3 + 36 ‘ ست وثلاثون هو باقي القسمة. نكرر العملية هذه المرة مع: 54 و 36 54 = 36 * 1 + 18 مرة أخرى:
36 = 18 * 2 + 0 هنا وصلنا للصفر فيكون العدد الثاني 18 هو القاسم المشترك الأكبر.

تعميمات إلى بُنى رياضياتية أخرى

يمكن أن تطبق الخوارزمية الإقليدية في نظرية العقد.

تطبيقات رياضياتية

متطابقة بيزو
تنص متطابقة بيزو على أن القاسم المشترك الأكبر g لعددين a و b يمكن أن يمثل مجموعا خطيا للعددين a و b؛ أي أنه يوجد عددان، s و t حيث يتوفر ما يلي:
g
=
s
a
+
t
b
{\displaystyle g=sa+tb} الخوارزمية الإقليدية الممتدة المقالة الرئيسة: خوارزمية إقليدس الممددة
یمكن تمثیل القاسم المشترك الأكبر للعددین عن طریق دمج خطي مع عددین آخرین، كیف یمكن أیجاد قیمتي n و m وذلك عن طریق خوارزمیة اقلیدس الممتدة وهناك ثلاثة طرق لمعرفة هذه القیم (الطرق هي مشابه لبعض، لكن یمكن القول أنها مختصره من الأخریات).
الطريقة الأولى: وهي يمكن ان نطلق عليها التراجع وفي هذه الطريقة نقوم بالحل عن طريق خوارزمية اقليدس وبعدها تقول بالتراجع الخلفي لايجاد قيمتي m،n كما في المثال التالي:
مثال: قم بتمثيل العددين 26 و 21 بطريقة اقليدس الممتدة:
فنبدأ بالحل كما هو الحال في طريقة اقليدس:
26 = 1* 21 + 5 و 21 = 4 * 5 + 1 و 5 = 5 * 1 + 0
وتتوقف عند الصفر. الآن المعادلة التي قبل المعادلة التي باقيها صفر أي المعادلة الثانية نقوم بكتابتها بالشكل التالي: 1
=
21
−
4
∗
5
{\displaystyle 1=21-4*5}
أیضا المعادلة الأولى بنفس الشكل: 5
=
26
−
1
∗
21
{\displaystyle 5=26-1*21}
في المعادلتين السابقتين 1 = 21 – 4 * (26 – 1 * 21)
ومن غیر أجراء عملیة حسابیة، فقط نفك القوس لینتج:
1 = 21 -4*26 +4*21
1=21(1+4)-4*26 حيث 21 عامل مشترك
لیكون لدینا الناتج النهائي: 4*21 +21 1 = 5*21 + (-4)*26
نتاكد من النتيجة 5*21+ -4*26 والناتج يساوي واحد إذاً المعادلة صحيحة إذاً قيمة m هي 5 وقيمة n هي -4. طريقة المصفوفات
a = q 0
b
+ r 0
b = q 1 r 0
+ r 1 ⋮ r N
−
2 = q N r N
−
1
+
0
{\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}}
( a
b )
=
(
q 0
1
1
0 )
( b r 0 )
=
(
q 0
1
1
0 )
(
q 1
1
1
0 )
(
r 0 r 1 )
=
⋯
= ∏ i
=
0
N
(
q i
1
1
0 )
(
r N
−
1
0 ) .
{\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}\,.} M =
(
m 11 m 12 m 21 m 22 )
= ∏ i
=
0
N
(
q i
1
1
0 )
=
(
q 0
1
1
0 )
(
q 1
1
1
0 )
⋯
(
q N
1
1
0 ) .
{\displaystyle \mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}\,.}
( a
b )
= M (
r N
−
1
0 )
= M ( g
0 ) .
{\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.}
( g
0 )
=
M
−
1
( a
b )
=
(
−
1 ) N
+
1
(
m 22
− m 12
− m 21 m 11 )
( a
b ) .
{\displaystyle {\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}\,.}
g = (−1)N+1 ( m22 a − m12 b),
المعادلات الديوفانتية الخطية
يمكن لخوارزمية أقليدس أيضا أن تستعمل من أجل حلحلة العديد من المعادلات الديوفانتية الخطية. تظهر واحدة من هده المعادلات في مبرهنة الباقي الصيني.
x 1 ≡
x
mod m 1 x 2 ≡
x
mod m 2
⋮ x N ≡
x
mod m N .
{\displaystyle {\begin{aligned}x_{1}&\equiv x{\bmod {m}}_{1}\\x_{2}&\equiv x{\bmod {m}}_{2}\\&\vdots \\x_{N}&\equiv x{\bmod {m}}_{N}\,.\end{aligned}}}
مبرهنة الباقي الصيني
مبرهنة الباقي الصيني
x 1 ≡
x
(
mod
m 1
)
x 2 ≡
x
(
mod
m 2
)
⋮ x N ≡
x
(
mod
m N
)
.
{\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}}
شجرة ستيرن-بروكوت
شجرة ستيرن-بروكوت، و متتاليات ستيرن-بروكوت من الرتبة i حيث i = 1، 2، 3، 4.
تُستعمل خوارزمية أقليدس من أجل ترتيب جميع الأعداد الجذرية الموجبة في شجرة ثنائية البحث غير منتهية، تسمى شجرة ستيرن-بروكوت. الكسور المستمرة
a
b = q 0
+ r 0
b
b r 0 = q 1
+ r 1 r 0 r 0 r 1 = q 2
+ r 2 r 1 ⋮ r k
−
2 r k
−
1 = q k
+ r k r k
−
1 ⋮ r N
−
2 r N
−
1 = q N .
{\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&\,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&\,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\,.\end{aligned}}}
a
b
= q 0
+
1
q 1
+ r 1
r 0 .
{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.}
a
b
= q 0
+
1
q 1
+
1
q 2
+ r 2
r 1
.
{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.}
a
b
= q 0
+
1
q 1
+
1
q 2
+
1 ⋱
+
1
q N
=
[ q 0
; q 1
, q 2
,
…
, q N
] .
{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.}
1071
462
=
2
+
1 3
+
1 7
=
[
2
;
3
,
7
]
{\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]}

الخلفية: القاسم المشترك الأكبر

المقالة الرئيسة: قاسم مشترك أكبر

وصف الخوارزمية

القاسم المشترك الأكبر لعددين طبيعيين A، B يساوي القاسم المشترك الأكبر للعدد الثاني B وباقي قسمة A على B، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر.
حيث r هو باقي قسمة A على B. N هو القاسم المشترك الأكبر.

التطور التاريخي

من المحتمل أن تكون الخوارزمية الإقليدية قد اكتشفت قرونا قبل إقليدس. بُين هنا في رسم يعود تاريخه إلى عام 1474، حاملا لقدمة ذات الورنية
خوارزمية أقليدس هي واحدة من أقدم الخوارزميات الجارية الاستعمال. ظهرت في كتاب الأصول لإقليدس (في حوالي عام 300 قبل الميلاد)، وبالتحديد في الكتاب السابع (الخاصيتان الأولى والثانية) والكتاب العاشر (الخاصيتان الثانية والثالثة). في الكاتب السابع، طُبقت الخوارزمية على الأعداد الطبيعية بينما في الكتاب العاشر، طُبقت على أطوال القطع المستقيمة. خلال القرن التاسع عشر، فتحت خوارزمية أقليدس الباب نحو تطور أنظمة عددية جديدة. الأعداد الغاوسية وأعداد أيزنشتاين مثالان على ذلك. في عام 1815، استعمل غاوس خوارزمية أقليدس من أجل البرهان على وحدانية تفكيك الأعداد الغاوسية. رغم أن العمل قِيم بي في عام 1815، إلا أنه لم ينشر لأول مرة إلي في عام 1832. أشار غاوس إلى الخوارزمية في كتابه استفسارات حسابية والذي نُشر في عام 1801، ولكن فقط في شكل طريقة تمكن من حساب الكسور المستمرة.

شرح مبسط

تعديل - تعديل مصدري - تعديل ويكي بيانات