نظرية الحوسبة

الموسوعة الحرة

في علوم الحاسوب النظرية والرياضيات ، تُعنى نظرية الحوسبة بدراسة المشكلات التي يمكن حلها باستخدام نموذج حاسوبي وخوارزمية ، وكفاءة حلها ، ودرجة هذه الكفاءة (مثل الحلول التقريبية مقابل الحلول الدقيقة). وينقسم هذا المجال إلى ثلاثة فروع رئيسية: نظرية الأوتوماتا واللغات الرسمية ، ونظرية قابلية الحوسبة ، ونظرية التعقيد الحسابي ، والتي يربطها السؤال التالي: "ما هي القدرات والقيود الأساسية للحواسيب؟". [ 1 ]

لإجراء دراسة دقيقة للحوسبة، يعتمد علماء الحاسوب على نموذج رياضي مجرد للحاسوب يُسمى نموذج الحوسبة . توجد عدة نماذج لهذا الغرض، مثل آلة تورينج . [ 2 ] يدرس علماء الحاسوب آلة تورينج لسهولة صياغتها، وإمكانية تحليلها واستخدامها لإثبات النتائج، ولأنها تمثل ما يعتبره الكثيرون أقوى نموذج "معقول" ممكن للحوسبة (انظر فرضية تشيرش-تورينج ). [ 3 ] قد يبدو أن سعة الذاكرة غير المحدودة المحتملة سمة غير قابلة للتحقيق، لكن أي مسألة قابلة للحسم [ 4 ] تحلها آلة تورينج لن تتطلب سوى مقدار محدود من الذاكرة. لذا، من حيث المبدأ، يمكن حل أي مسألة يمكن حلها (حسمها) بواسطة آلة تورينج بواسطة حاسوب ذي مقدار محدود من الذاكرة.

تاريخ

يمكن اعتبار نظرية الحوسبة بمثابة إنشاء نماذج من جميع الأنواع في مجال علوم الحاسوب. ولذلك، تُستخدم الرياضيات والمنطق . في القرن الماضي، انفصلت عن الرياضيات وأصبحت تخصصًا أكاديميًا مستقلًا، ولها مؤتمراتها الخاصة مثل مؤتمر أسس علوم الحاسوب (FOCS) عام 1960 ومؤتمر نظرية الحوسبة (STOC) عام 1969، وجوائزها الخاصة مثل ميدالية الاتحاد الدولي للرياضيات (IMU) أباكوس (التي أُنشئت عام 1981 باسم جائزة رولف نيفانلينا)، وجائزة غودل التي أُنشئت عام 1993، وجائزة كنوت التي أُنشئت عام 1996.

ومن رواد نظرية الحوسبة رامون لول ، وألونزو تشيرش ، وكورت غودل ، وآلان تورينج ، وستيفن كلين ، وروزا بيتر ، وجون فون نيومان ، وكلود شانون .

الفروع

نظرية الأوتوماتا

قواعد اللغةاللغاتآلةقواعد الإنتاج (القيود)
النوع 0قابل للتعداد بشكل متكررآلة تورينجα→β{\displaystyle \alpha \rightarrow \beta }(بدون قيود)
النوع 1حساس للسياقآلة تورينغ غير حتمية ذات حدود خطيةαأβ→αγβ{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }
النوع الثانيبدون سياقآلة دفع غير حتميةأ→γ{\displaystyle A\rightarrow \gamma }
النوع 3عاديآلة الحالة المحدودةأ→أ{\displaystyle A\rightarrow a}وأ→أب{\displaystyle A\rightarrow aB}

نظرية الأوتوماتا هي دراسة الآلات المجردة (أو بشكل أدق، الآلات أو الأنظمة "الرياضية" المجردة) والمسائل الحسابية التي يمكن حلها باستخدام هذه الآلات. تُسمى هذه الآلات المجردة بالأوتوماتا. كلمة "أوتوماتا" مشتقة من الكلمة اليونانية (Αυτόματα) التي تعني أن شيئًا ما يقوم بشيء ما من تلقاء نفسه. ترتبط نظرية الأوتوماتا ارتباطًا وثيقًا بنظرية اللغات الرسمية ، [ 5 ] حيث تُصنف الأوتوماتا غالبًا حسب فئة اللغات الرسمية التي تستطيع التعرف عليها. يمكن أن تكون الأوتوماتا تمثيلًا محدودًا للغة رسمية قد تكون مجموعة غير محدودة. تُستخدم الأوتوماتا كنماذج نظرية لآلات الحوسبة، وتُستخدم في إثبات قابلية الحوسبة.

نظرية اللغة الرسمية

التسلسل الهرمي لتشومسكي
المجموعات المضمنة الموصوفة في التسلسل الهرمي لتشومسكي

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

نظرية الحوسبة

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

كانت نظرية رايس خطوة مهمة أخرى في نظرية الحوسبة ، والتي تنص على أنه بالنسبة لجميع الخصائص غير التافهة للدوال الجزئية، فإنه من غير الممكن تحديد ما إذا كانت آلة تورينج تحسب دالة جزئية بتلك الخاصية. [ 8 ]

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

نظرية التعقيد الحسابي

تمثيل للعلاقة بين فئات التعقيد

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

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

لتبسيط هذه المشكلة، اعتمد علماء الحاسوب ترميز Big O ، الذي يسمح بمقارنة الدوال بطريقة تضمن عدم الحاجة إلى مراعاة جوانب محددة من بنية الآلة، بل فقط السلوك التقاربي مع ازدياد حجم المشكلات. لذا، في مثالنا السابق، يمكننا القول إن المشكلة تتطلبيا(ن){\displaystyle O(n)}خطوات الحل.

لعلّ أهمّ مشكلة مفتوحة في علوم الحاسوب هي إمكانية حلّ فئة واسعة من المسائل، يُرمز لها بـ NP، بكفاءة. وقد نُوقشت هذه المسألة بتفصيل أكبر في قسم "فئات التعقيد P وNP" ، وتُعدّ مسألة P مقابل NP إحدى مسائل جائزة الألفية السبع التي طرحها معهد كلاي للرياضيات عام 2000. وقدّم الوصف الرسمي لهذه المسألة ستيفن كوك ، الحائز على جائزة تورينج .

نماذج الحوسبة

وبصرف النظر عن آلة تورينج، يتم استخدام نماذج حسابية أخرى مكافئة (انظر أطروحة تشيرش-تورينج).

حساب التفاضل والتكامل لامدا
تتكون العملية الحسابية من تعبير لامدا أولي (أو اثنين إذا كنت تريد فصل الدالة ومدخلاتها) بالإضافة إلى سلسلة محدودة من حدود لامدا، يتم استنتاج كل منها من الحد السابق من خلال تطبيق واحد لاختزال بيتا .
المنطق التوافقي
هو مفهوم له أوجه تشابه كثيرة معλ{\displaystyle \lambda }- حساب التفاضل والتكامل، ولكن توجد أيضًا اختلافات مهمة (على سبيل المثال، مُركِّب النقطة الثابتة Y له شكل طبيعي في المنطق التوافقي ولكن ليس فيλ{\displaystyle \lambda }-حساب التفاضل والتكامل). تم تطوير المنطق التوافقي بطموحات كبيرة: فهم طبيعة المفارقات، وجعل أسس الرياضيات أكثر اقتصادية (من الناحية المفاهيمية)، وإلغاء مفهوم المتغيرات (وبالتالي توضيح دورها في الرياضيات).
الدوال التكرارية من النوع μ
تتكون العملية الحسابية من دالة تكرارية من نوع mu، أي تسلسلها المحدد، وأي قيمة (قيم) إدخال، وتسلسل من الدوال التكرارية التي تظهر في التسلسل المحدد مع مدخلات ومخرجات. وبالتالي، إذا كان في التسلسل المحدد لدالة تكراريةو(x){\displaystyle f(x)}الوظائفز(x){\displaystyle g(x)}وح(x،y){\displaystyle h(x,y)}عند ظهور الحدود، قد تظهر حدود من الشكل 'g(5)=7' أو 'h(3,2)=10'. يجب أن يكون كل عنصر في هذه المتتالية تطبيقًا لدالة أساسية أو ناتجًا عن العناصر السابقة باستخدام التركيب أو الاستدعاء الذاتي الأولي أو الاستدعاء الذاتي μ . على سبيل المثال، إذاو(x)=ح(x،ز(x)){\displaystyle f(x)=h(x,g(x))}ثم، لكي يظهر 'f(5)=3'، يجب أن تظهر حدود مثل 'g(5)=6' و'h(5,6)=3' أعلاه. لا تنتهي العملية الحسابية إلا إذا أعطت الحد الأخير قيمة الدالة التكرارية المطبقة على المدخلات.
خوارزمية ماركوف
نظام لإعادة كتابة السلاسل النصية يستخدم قواعد شبيهة بالقواعد النحوية للعمل على سلاسل الرموز.
آلة التسجيل
يُعدّ هذا نموذجًا مثاليًا مثيرًا للاهتمام من الناحية النظرية للحاسوب. توجد عدة نماذج منه. في معظمها، يمكن لكل سجل تخزين عدد طبيعي (بحجم غير محدود)، وتكون التعليمات بسيطة (وقليلة العدد)، على سبيل المثال، لا توجد سوى تعليمات الإنقاص (بالاقتران مع القفزة الشرطية) والزيادة (والتوقف). يمكن فهم غياب الذاكرة الخارجية اللانهائية (أو المتنامية ديناميكيًا) (كما هو الحال في آلات تورينج) من خلال استبدال دورها بتقنيات ترقيم غودل : فحقيقة أن كل سجل يخزن عددًا طبيعيًا تسمح بإمكانية تمثيل شيء معقد (مثل متتالية أو مصفوفة، إلخ) بعدد طبيعي ضخم مناسب - ويمكن إثبات وضوح كل من التمثيل والتفسير من خلال الأسس النظرية العددية لهذه التقنيات.

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

تتمتع نماذج الحوسبة المختلفة بقدرات متنوعة لأداء مهام مختلفة. ومن طرق قياس قوة نموذج الحوسبة دراسة فئة اللغات الرسمية التي يمكن للنموذج توليدها؛ ومن خلال هذه الطريقة يتم الحصول على التسلسل الهرمي للغات وفقًا لتصنيف تشومسكي .

مراجع

  1. ↑ سيبسر (2013 ، ص 1) : 
    "المجالات المركزية لنظرية الحوسبة: الأوتوماتا، وقابلية الحوسبة، والتعقيد."
  2. ↑ هودجز، أندرو (2012). آلان تورينج: اللغز (  طبعة الذكرى المئوية). مطبعة جامعة برينستون . ISBN 978-0-691-15564-7.
  3. ↑ رابين، مايكل أو. (يونيو 2012). تورينج، تشيرش، غودل، قابلية الحوسبة، التعقيد والعشوائية: وجهة نظر شخصية .
  4. ↑ دونالد مونك (1976). المنطق الرياضي . سبرينغر-فيرلاغ. ISBN 9780387901701.
  5. ↑ هوبكروفت، جون إي. وجيفري دي. أولمان (2006). مقدمة في نظرية الأوتوماتا واللغات والحوسبة. الطبعة الثالثة . ريدينغ، ماساتشوستس: أديسون-ويسلي. ISBN 978-0-321-45536-9.
  6. ↑ تشومسكي، ن. (1956). "ثلاثة نماذج لوصف اللغة". معاملات IEEE في نظرية المعلومات . 2 (3): 113-124 . Bibcode : 1956IRTIT...2..113C . doi : 10.1109/TIT.1956.1056813 . S2CID 19519474 . 
  7. ↑ آلان تورينج (1937). "حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار" . وقائع الجمعية الرياضية بلندن . 2 (42). IEEE: 230-265 . Bibcode : 1937PLMS...42..230T . doi : 10.1112/plms/s2-42.1.230 . S2CID 73712. تاريخ الاسترجاع: 6 يناير 2015 . 
  8. ↑ هنري جوردون رايس (1953). "فئات المجموعات القابلة للتعداد التكراري ومسائل القرار الخاصة بها" . معاملات الجمعية الرياضية الأمريكية . 74 (2). الجمعية الرياضية الأمريكية: 358-366 . doi : 10.2307/1990888 . JSTOR 1990888 . 
  9. ↑ مارتن ديفيس (2004). غير القابل للتقرير: أوراق أساسية حول القضايا غير القابلة للتقرير، والمسائل غير القابلة للحل، والدوال القابلة للحساب (طبعة دوفر) . منشورات دوفر. ISBN 978-0486432281.

للمزيد من القراءة

كتب دراسية موجهة لعلماء الحاسوب

(توجد العديد من الكتب الدراسية في هذا المجال؛ وهذه القائمة غير مكتملة بالضرورة.)

  • هوبكروفت، جون إي .؛ موتاني، راجيف ؛ أولمان، جيفري د. (2006) [1979]. مقدمة في نظرية الأوتوماتا واللغات والحوسبة (الطبعة الثالثة  ). أديسون-ويسلي. ISBN 0-321-45536-3.— أحد المراجع القياسية في هذا المجال.
  • لينز ف (2007). مقدمة للغة الرسمية والأتمتة . ناروسا للنشر. رقم ISBN 9788173197819.
  • سيبسر، مايكل (2013). مقدمة في نظرية الحوسبة (  الطبعة الثالثة). سينجايج ليرنينج. ISBN 978-1-133-18779-0.
  • إيتان غوراري (1989). مقدمة في نظرية الحوسبة . دار نشر علوم الحاسوب. رقم ISBN 0-7167-8182-4تمت أرشفة النسخة الأصلية بتاريخ 2007-01-07.
  • هاين، جيمس ل. (1996) نظرية الحوسبة. سودبري، ماساتشوستس: جونز وبارتليت. ISBN 978-0-86720-497-1مقدمة لطيفة للمجال، مناسبة لطلاب السنة الثانية في المرحلة الجامعية الأولى في علوم الحاسوب.
  • تايلور، ر. غريغوري (1998). نماذج الحوسبة واللغات الرسمية. نيويورك: مطبعة جامعة أكسفورد. ISBN 978-0-19-510983-2 كتاب دراسي سهل القراءة بشكل غير عادي، مناسب لطلاب المرحلة الجامعية العليا أو طلاب الدراسات العليا المبتدئين.
  • جون كلاينبرغ، وإيفا تاردوس (2006): تصميم الخوارزميات ، بيرسون/أديسون ويسلي، ISBN 978-0-32129535-4
  • لويس، إف دي (2007). أساسيات علوم الحاسوب النظرية: كتابٌ دراسيٌّ يُغطي موضوعات اللغات الرسمية، والآلات، والقواعد النحوية. ويبدو أن التركيز ينصبّ على تقديم نظرة عامة على النتائج وتطبيقاتها بدلاً من تقديم براهينها.
  • مارتن ديفيس ، رون سيغال، إيلين جيه. ويوكر، الحوسبة، والتعقيد، واللغات: أساسيات علوم الحاسوب النظرية ، الطبعة الثانية، دار النشر الأكاديمية، 1994، رقم ISBN 0-12-206382-1يغطي هذا الكتاب نطاقًا أوسع من المواضيع مقارنة بمعظم الكتب التمهيدية الأخرى، بما في ذلك دلالات البرامج ونظرية التكميم . وهو موجه لطلاب الدراسات العليا.
كتب عن نظرية الحوسبة من منظور رياضي (أوسع)
  • هارتلي روجرز الابن (1987). نظرية الدوال التكرارية والحوسبة الفعالة ، مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 0-262-68052-1
  • إس. باري كوبر (2004). نظرية الحوسبة . تشابمان آند هول/سي آر سي. رقم ISBN 1-58488-237-9..
  • كارل هـ. سميث ، مقدمة متكررة لنظرية الحوسبة ، سبرينغر، 1994، رقم ISBN 0-387-94332-3كتاب دراسي مختصر مناسب لطلاب الدراسات العليا في علوم الحاسوب.
منظور تاريخي
  • ريتشارد ل. إبستين ووالتر أ. كارنيلي (2000). الحوسبة: الدوال القابلة للحوسبة، والمنطق، وأسس الرياضيات، مع الحوسبة: جدول زمني (الطبعة الثانية) . وادزورث/تومسون ليرنينج. ISBN 0-534-54644-7..