توطئة شفارتز-زيبل
قبل الخوض في التفاصيل، توطئة شفارتز-زيبل أو مبرهنة شفارتز-زيبل هي نتيجة أساسية في علم الاحتمال ولها تأثير على عدة مجالات في الرياضيات وعلم الحاسوب. وفيما يلي تفاصيل أوسع عن ذلك.
استخدامات
علاوةً على ذلك، هذه المبرهنة تقول بانه إذا كان عندنا في الحقل على الاقل اعداد عندها يوجد خوارزمية احتمالية واحتمال خطأه على الأكثر وفي حالة انه يوجد اقل حينها نوسع ونختار نقاط عشوائية لذا فان هذه المسألة تتبع قسم التعقيد co-RP .
علاوةً على ذلك، المبرهنة والتي تبحث مسألة تطابق متعددي حدود لها الكثير من التطبيقات في علم الحاسوب والرياضيات حيث ان مسألة التطابق كانت مهمة في برهنة مسألة أخرى هي فحص إذا ما مخطوط معطى هو مخطط ثنائي وذلك حسب نظرية برهنها Tutte . ويمتد استخدامها لفحص إذا ما معطى عدد هو اولي.
مقدمة
إضافةً إلى ذلك، وهناك طريقة بسيطة لفحص هذه المتطابقات وهي عن طريق فتح الأقواس وفحص كل منهما إذا ما كانا متطابقين ! ولكن هذه العملية هي عملية أُسية بالنسبة لطول المدخل، إذ ان عدد احادية الحدود الناتجة عدد هو عندما d هو اعلى درجة احادي الحدود وما نريده إذا هي خوارزمية سريعة (أي تعقيدها الوقتي هو متعدد حدود بالنسبة للمدخل) ولكن هذا غير معلوم للان ومبرهنة شوارتز-زيبل تعطينا خوارزمية احتمالية سريعة.
وفي هذا السياق، من الشائع جدا معرفة متطابقات متعددة الحدود مثل: أو مبرهنة المربعات الأربع للاغرانج وهي:
تعريف المسألة
وفي هذا الصدد، مسألة تطابق متعددات الحدود هي: معطى دائرة حسابية والتي تحسب متعدد الحدود في , جد خوارزمية حتمية التي تفحص إذا ما p صفر ويستعمل فقط حسابات في
البرهان
في هذا الإطار، إذا n=1 , حسب المبرهنة الأساسية في الجبر هناك على الأكثر d جذور لذا فان المبرهنة تصح في هذه الحالة أي انه:
إضافةً إلى ذلك، إذا حينها والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي أي:
وفي هذا الصدد، لنفرض ان المبرهنة صحيحة لكل متعددات الحدود مع متغيرات وبدون تقييد العموم نستطيع ان نفترض ان متعدد الحدود ب- ونستطيع ان نكتبه بالطريقة التالية:
حينها:
.
سوف نستعمل استقراء رياضي (Induction) على n ,
ومن جهة أخرى، بما ان ليس صفرا يوجد i بحيث ان ليس صفراً ونختار i ليكون الأكبر وصفته كما هو مذكور، مفهوم ضمنا أن وذلك لان متعدد احادي الحدود درجته i وبما ان حاصل ضرب متعدد الحدود: مع احادي الحدود هذا هو على الأكثر d لذا فان هذه الصفة صحيحة. الآن نختار عشوائيا من , وحسب فرضية الاستقراء الرياضي:
المبرهنة
ومن جهة أخرى، لنفرض ان متعدد حدودي ليس صفرا ودرجته فوق حقل ولنفرض ان S مجموعة جزئية نهائية ل- حينها:
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟