المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

مبرهنة شوارتز-زيبل

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من مبرهنة شوارتز -زيبل)
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

مبرهنة شوارتز -زيبل هي نتيجة اساسية في علم الاحتمال ولها تأثير على عدة مجالات في الرياضيات وعلم الحاسوب

مقدمة[عدل]

من الشائع جدا معرفة متطابقات متعددة الحدود مثل : او مبرهنة المربعات الأربع للاغرانج وهي : وهناك طريقة بسيطة لفحص هذه المتطابقات وهي عن طريق فتح الأقواس وفحص كل منهما اذا ما كانا متطابقين ! ولكن هذه العملية هي عملية أُسية بالنسبة لطول المدخل , إذ ان عدد احادية الحدود الناتجة عدد هو عندما d هو اعلى درجة احادي الحدود وما نريده اذا هي خوارزمية سريعة (اي تعقيدها الوقتي هو متعدد حدود بالنسبة للمدخل ) ولكن هذا غير معلوم للان ومبرهنة شوارتز-زيبل تعطينا خوارزمية احتمالية سريعة .

تعريف المسألة[عدل]

مسألة تطابق متعددات الحدود هي : معطى دائرة حسابية والتي تحسب متعدد الحدود في , جد خوارزمية حتمية التي تفحص اذا ما p صفر ويستخدم فقط حسابات في

المبرهنة[عدل]

لنفرض ان متعدد حدودي ليس صفرا ودرجته فوق حقل ولنفرض ان S مجموعة جزئية نهائية ل- حينها :

البرهان[عدل]

سوف نستخدم استقراء رياضي (Induction) على n ,

اذا n=1 , حسب المبرهنة الأساسية في الجبر هناك على الاكثر d جذور لذا فان المبرهنة تصح في هذه الحالة اي انه :

لنفرض ان المبرهنة صحيحة لكل متعددات الحدود مع متغيرات وبدون تقييد العموم نستطيع ان نفترض ان متعدد الحدود ب- ونستطيع ان نكتبه بالطريقة التالية :

بما ان ليس صفرا يوجد i بحيث ان ليس صفراً ونختار i ليكون الأكبر وصفته كما هو مذكور , مفهوم ضمنا أن وذلك لان متعدد احادي الحدود درجته i وبما ان حاصل ضرب متعدد الحدود : مع احادي الحدود هذا هو على الاكثر d لذا فان هذه الصفة صحيحة . الان نختار عشوائيا من , وحسب فرضية الاستقراء الرياضي :

.

اذا حينها والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي اي :

حينها :

استخدامات[عدل]

  1. هذه المبرهنة تقول بانه اذا كان عندنا في الحقل على الاقل اعداد عندها يوجد خوارزمية احتمالية واحتمال خطأه على الاكثر وفي حالة انه يوجد اقل حينها نوسع ونختار نقاط عشوائية لذا فان هذه المسألة تتبع قسم التعقيد co-RP .
  2. المبرهنة والتي تبحث مسألة تطابق متعددي حدود لها الكثير من التطبيقات في علم الحاسوب والرياضيات حيث ان مسألة التطابق كانت مهمة في برهنة مسألة اخرى هي فحص اذا ما مخطوط معطى هو مخطط ثنائي وذلك حسب نظرية برهنها Tutte . ويمتد استخدامها لفحص اذا ما معطى عدد هو اولي .