قرأت على النت مصطلح "fold speed up " و أعتقد أن له علاقة بسرعة الخوارزميات ؟ ولكن ماذا يعني ؟
مثلا:
"and 144-fold speed-up of the Smith-Waterman algorithm"
"has a about four hundred thousand-fold speed-up on average for solving the inverse problem as compared with the previous algorithm"
ولأول مرة في حياتي لا يستطيع جوجل الإجابة على سؤالي ؟
اعتقد ان المصطلح تجده في كتب معمارية الحاسوب Computer Architecture and organization ليعطي مقارنة بين التصاميم المختلفة للحاسوب.
مبرهنة بلام للتسريع الحسابي Blum's Speedup Theorem
هي مبرهنة في نظرية الحوسبة Computational Theory (أو نظرية العودية Recursion Theory)، قدمها عام 1967 عالم الحوسبة الفنزويلي الأصل مانويل بلام Manuel Blum الحائز على جائزة تورينج Turing Award لعام 1995.
و هذه المبرهنة هي من نتاج نظرية بلام (المسلماتية) في التعقيد الحسابي Axiomatic Complexity Theory التي قدمها في ستينات القرن العشرين. و تعتمد على مجموعة من المسلمات المسماة Blum's Axioms و نوع من الدوال يسمى دوال جودل الترقيمية Godel Numbering Functions، و هي دوال مجالها مجموعة الرموز Symbols و الصيغ Formulas لأي لغة رمزية Symbolic Language، و مجالها المقابل هو مجموعة الأعداد الطبيعية Natural Numbers. و قد قدم جودل هذا النوع من الدوال في عمله على مبرهنته الشهيرة لعدم الاكتمال Incompleteness Theorem.
و كان من أهم نتائج نظرية بلام المسلماتية للتعقيد الحسابي مبرهنته للتسريع Speedup Theorem. فكل دالة قابلة للحساب Computable Function لها عدد لا نهائي من التمثيلات البرمجية Program Representations في أي لغة برمجة. و من المنطقي أن نبحث عن أفضل هذه التمثيلات البرمجية Best Program (أي عن الخوارزمية ذات التعقيد الأدنى Smallest Complexity). و تثبت مبرهنة بلام ببساطة أنه لبعض الدوال المعرفة رياضياً Mathematically Defined Functions لا يوجد هذا التمثيل البرمجي الأفضل (No Best Program).
مرفق الورقتان البحثيتان:
Program Speedups in Theory and Practice
Complexity Classes of Provable Recursive Functions
كما يمكن البحث في جوجل باستخدام الكلمات المفتاحية التالية:
Speedup Theorem
Blum's Speedup Theorem
Axiomatic Complexity Theory
Complexity Measure
Godel Numberings
Godel Numbering Functions
تحيــاتي..،
تم تعديل هذه المشاركة بواسطة YDVIPER في 23 ديسمبر 2009 في 15:17
[bg=#000000]
La filosofia e scritta in questo grandissimo libro che continuamente ci sta aperto innanzi a gli occhi (io dico l’universo), ma non si pu o intender se prima non s’impara a intender la lingua e conoscere i caratteri ne’ quali e scritto. Egli e scritto in lingua matematica e i caratteri sono triangoli, cerchi, ed altre figure geometriche senza i quali mezi e impossibile a intenderne umanamente parola; senza questi e un aggirarsi vanamente per un oscuro laberinto.
Galileo
لقد كُتبت الفلسفة في هذا الكتاب العظيم الذي يوجد دائماً أمام أعيننا (و أعني به الكون)، و لكن لا يمكن لأحدٍ أن يفهمه ما لم يتعلم في البدء حروفَ اللغة التي كُتب بها. لقد كُتب بلغة الرياضيات، و الحروف هي مثلثاتٌ و دوائر و أشكالٌ هندسية أخرى؛ بدون هذه اللغة يكون من المستحيل على البشر أن يفهموا و لو كلمة، بدون هذه اللغة نُمسي كمن يتخبطُ بلا هدى في متاهةٍ مظلمة.
جاليليو
[/bg]
Yasser
مرحبا بعودة اخونا الفاضل دكتور ياسر :)
عماد حمدي احمد كتب:مرحبا بعودة اخونا الفاضل دكتور ياسر :)
بارك الله فيك دكتور عماد
و أرجو ألا تكون عبارة (المشرفين القدامى) هذه مدعاة لقلة مشاركاتك بل أرجو أن تكون مدعاة لتواجد أكبر
فلتطرح مشاركاتك القيمة كما اعتدنا منك
دعواتي بالتوفيق..،
[bg=#000000]
La filosofia e scritta in questo grandissimo libro che continuamente ci sta aperto innanzi a gli occhi (io dico l’universo), ma non si pu o intender se prima non s’impara a intender la lingua e conoscere i caratteri ne’ quali e scritto. Egli e scritto in lingua matematica e i caratteri sono triangoli, cerchi, ed altre figure geometriche senza i quali mezi e impossibile a intenderne umanamente parola; senza questi e un aggirarsi vanamente per un oscuro laberinto.
Galileo
لقد كُتبت الفلسفة في هذا الكتاب العظيم الذي يوجد دائماً أمام أعيننا (و أعني به الكون)، و لكن لا يمكن لأحدٍ أن يفهمه ما لم يتعلم في البدء حروفَ اللغة التي كُتب بها. لقد كُتب بلغة الرياضيات، و الحروف هي مثلثاتٌ و دوائر و أشكالٌ هندسية أخرى؛ بدون هذه اللغة يكون من المستحيل على البشر أن يفهموا و لو كلمة، بدون هذه اللغة نُمسي كمن يتخبطُ بلا هدى في متاهةٍ مظلمة.
جاليليو
[/bg]
Yasser
اقتباسمرحبا بعودة اخونا الفاضل دكتور ياسر
:happy:
انوه ايضا يستخدم المصطلح بكثرة في مواضيع المعالجة المتوازية Parallel Processing، اعتقد انه يعني مقدار التحسين في السرعة في الطريقة الحالية مقارنة بالطريقة السابقه.
الطريقة الحالية والطريقة السابقة قد تكون خوارزميات Software او انظمة Hardware .
تم تعديل هذه المشاركة بواسطة ibr_exn في 24 ديسمبر 2009 في 00:08
YDVIPER كتب:بارك الله فيك دكتور عماد
و أرجو ألا تكون عبارة (المشرفين القدامى) هذه مدعاة لقلة مشاركاتك بل أرجو أن تكون مدعاة لتواجد أكبر
فلتطرح مشاركاتك القيمة كما اعتدنا منك
دعواتي بالتوفيق..،
بارك الله فيك اخى الفاضل. فى الحقيقة كان الهدف من وراء عبارة (المشرفين القدامى) هو العمل على زيادة عدد المشاركات العلمية , ولذلك اتمنى النجاح فى تحقيق هذا الهدف.
بالله التوفيق ,,,
ibr_exn كتب::happy:
انوه ايضا يستخدم المصطلح بكثرة في مواضيع المعالجة المتوازية Parallel Processing، اعتقد انه يعني مقدار التحسين في السرعة في الطريقة الحالية مقارنة بالطريقة السابقه.
الطريقة الحالية والطريقة السابقة قد تكون خوارزميات Software او انظمة Hardware .
مرحباً أخي الكريم إبراهيـم..
صحيح و يمكنك أن تجدها في موضوعات أخرى كثيرة.. فأصل الخوارزميات و نظرية التعقيد تجده في نظرية العودية Recursion Theory و هي مع نظرية البرهان Proof Theory و نظرية النموذج Model Theory تشكل في مجموعها الكيان الرئيسي للمنطق الرياضياتي.
لقد تطورت نظرية العودية (أو نظرية الحاسوبية أو القابلية للحساب Computability Theory) بفضل مناطقة كبار مثل جودل Godel و تشيرش Church و تورينج Turing و غيرهم. و نظرية الحاسوبية كما يبدو من اسمها تبحث في كون الدالة (أو المشكلة) قابلة للتعريف Definability أم لا ثم كونها قابلة للحساب Computability أم لا. أي أنها تبحث في كون الدالة قابلة للحساب (من الأساس) في عدد محدد من الخطوات أم لا. و نظرية التعقيد الحسابي Computational Complexity Theory تبحث في فعالية الحساب لدالة تم إثبات قابليتها للحساب (مسبقاً) بالآليات المنطقية لنظرية الحاسوبية. أي أنها تبحث عن أكثر الحلول فعالية و تقدم الأدوات اللازمة لمقارنة مجموعات الحلول و تصنيفها في التصنيفات المعروفة للتعقيد Complexity Classes.
و النظريتان (الحاسوبية و التعقيد) يقدمان مجمل الأدوات و المفاهيم الرياضياتية التي تشكل البنية الرئيسية للخوارزميات Algorithms تصميماً و تقييماً، بالإضافة لبعض الأدوات الأخرى من رياضيات البنى المنفصلة Discrete Mathematics بوجه عام.
و هذه الخوارزميات يمكن ترجمتها أو تمثيلها ببنى مفهومية Conceptual Structures مثل البرمجيات أو ببنى ملموسة Concrete Structures مثل العتاد الحاسوبي Hardware. و لا تناقض فكلا الجانبين متكافئان في الأساس النظري.
لذا ستجد تكراراً طبيعياً لاصطلاحات الأصل الرياضياتي في جميع جوانب التطبيق الحوسبي..
و تنويهك صائب تماماً بالتبعية..
عماد حمدي احمد كتب:بارك الله فيك اخى الفاضل. فى الحقيقة كان الهدف من وراء عبارة (المشرفين القدامى) هو العمل على زيادة عدد المشاركات العلمية , ولذلك اتمنى النجاح فى تحقيق هذا الهدف.
بالله التوفيق ,,,
إنا لمنتظرون... :P
بالمناسبة لقد قرأت مؤخراً ورقتك:
Interval Schemes for Singularly Perturbed Initial Value Problems
مجهود ممتـاز.. أهنئك عليه..
و بالتوفيق دائمـاً دكتور عمـاد..
تحيــاتي..،
[bg=#000000]
La filosofia e scritta in questo grandissimo libro che continuamente ci sta aperto innanzi a gli occhi (io dico l’universo), ma non si pu o intender se prima non s’impara a intender la lingua e conoscere i caratteri ne’ quali e scritto. Egli e scritto in lingua matematica e i caratteri sono triangoli, cerchi, ed altre figure geometriche senza i quali mezi e impossibile a intenderne umanamente parola; senza questi e un aggirarsi vanamente per un oscuro laberinto.
Galileo
لقد كُتبت الفلسفة في هذا الكتاب العظيم الذي يوجد دائماً أمام أعيننا (و أعني به الكون)، و لكن لا يمكن لأحدٍ أن يفهمه ما لم يتعلم في البدء حروفَ اللغة التي كُتب بها. لقد كُتب بلغة الرياضيات، و الحروف هي مثلثاتٌ و دوائر و أشكالٌ هندسية أخرى؛ بدون هذه اللغة يكون من المستحيل على البشر أن يفهموا و لو كلمة، بدون هذه اللغة نُمسي كمن يتخبطُ بلا هدى في متاهةٍ مظلمة.
جاليليو
[/bg]
Yasser
