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

الخوارزمية هي إجراء متدرج للحسابات. تُستخدم الخوارزميات في الحساب ومعالجة البيانات والاستدلال الآلي .

الخوارزمية هي طريقة فعّالة تُعبّر عنها قائمة محدودة ^{[ 3 ]} من التعليمات المحددة جيدًا ^{[ 4 ]} لحساب دالة ما . ^{[ 5 ]} تبدأ الخوارزمية من حالة ابتدائية ومدخل ابتدائي (قد يكون فارغًا )، ^{[ 6 ]} وتصف عملية حسابية ، عند تنفيذها ، تمر عبر عدد محدود ^{[ 7 ]} من الحالات المتتالية المحددة جيدًا، لتُنتج في النهاية "مخرجًا" ^{[ 8 ]} وتنتهي عند حالة نهائية. الانتقال من حالة إلى أخرى ليس بالضرورة حتميًا ؛ فبعض الخوارزميات، المعروفة بالخوارزميات العشوائية ، تتضمن مدخلات عشوائية. ^{[ 9 ]}

نظرية الأوتوماتا هي دراسة الآلات المجردة والأوتوماتا ، بالإضافة إلى المشكلات الحسابية التي يمكن حلها باستخدامها. وهي نظرية في علوم الحاسوب النظرية، ضمن الرياضيات المتقطعة (وهي فرع من الرياضيات وعلوم الحاسوب ). كلمة "أوتوماتا " مشتقة من الكلمة اليونانية αὐτόματα، والتي تعني "ذاتية الفعل".

نظرية الأوتوماتا هي دراسة الآلات الافتراضية ذاتية التشغيل للمساعدة في الفهم المنطقي لعملية الإدخال والإخراج، بدون أو مع مرحلة (مراحل) وسيطة من الحساب (أو أي وظيفة / عملية).

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

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

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

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

كان الدافع الرئيسي لتطوير الهندسة الحسابية كتخصص هو التقدم في رسومات الحاسوب والتصميم والتصنيع بمساعدة الحاسوب ( CAD / CAM )، ولكن العديد من المشاكل في الهندسة الحسابية كلاسيكية بطبيعتها، وقد تأتي من التصور الرياضي .

تشمل التطبيقات المهمة الأخرى للهندسة الحسابية الروبوتات (تخطيط الحركة ومشاكل الرؤية)، ونظم المعلومات الجغرافية (GIS) (الموقع الهندسي والبحث، وتخطيط المسار)، وتصميم الدوائر المتكاملة (تصميم هندسة الدوائر المتكاملة والتحقق منها)، والهندسة بمساعدة الحاسوب (CAE) (توليد الشبكة)، ورؤية الحاسوب (إعادة البناء ثلاثي الأبعاد).

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

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

علم التشفير هو ممارسة ودراسة تقنيات الاتصال الآمن في وجود أطراف ثالثة (تُسمى الخصوم ). ^{[ 10 ]} وبشكل أعم، يتعلق الأمر ببناء وتحليل البروتوكولات التي تتغلب على تأثير الخصوم ^{[ 11 ]} والتي ترتبط بجوانب مختلفة في أمن المعلومات ، مثل سرية البيانات ، وسلامة البيانات ، والمصادقة ، وعدم الإنكار . ^{[ 12 ]} يتقاطع علم التشفير الحديث مع تخصصات الرياضيات ، وعلوم الحاسوب ، والهندسة الكهربائية . تشمل تطبيقات علم التشفير بطاقات الصراف الآلي ، وكلمات مرور الحاسوب ، والتجارة الإلكترونية .

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

بنية البيانات هي طريقة محددة لتنظيم البيانات في الحاسوب بحيث يمكن استخدامها بكفاءة . ^{[ 13 ] [ 14 ]}

تُناسب أنواع مختلفة من هياكل البيانات أنواعًا مختلفة من التطبيقات، وبعضها متخصص للغاية في مهام محددة. على سبيل المثال، تستخدم قواعد البيانات فهارس B-tree لنسبة صغيرة من استرجاع البيانات، وتستخدم المترجمات وقواعد البيانات جداول التجزئة الديناميكية كجداول بحث.

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

يدرس علم الحوسبة الموزعة الأنظمة الموزعة. النظام الموزع هو نظام برمجي تتواصل فيه المكونات الموجودة على أجهزة كمبيوتر متصلة بشبكة وتنسق أعمالها عبر تبادل الرسائل . ^{[ 15 ]} تتفاعل هذه المكونات فيما بينها لتحقيق هدف مشترك. من أبرز خصائص الأنظمة الموزعة: تزامن المكونات، وعدم وجود ساعة مركزية، وإمكانية تعطل المكونات بشكل مستقل. ^{[ 15 ]} تتنوع أمثلة الأنظمة الموزعة من الأنظمة القائمة على بنية الخدمات الموجهة (SOA) إلى ألعاب الإنترنت متعددة اللاعبين على نطاق واسع، وصولاً إلى تطبيقات الند للند ، وشبكات البلوك تشين مثل بيتكوين .

يُطلق على برنامج الحاسوب الذي يعمل ضمن نظام موزّع اسم البرنامج الموزّع ، وتُعرف عملية كتابة هذه البرامج بالبرمجة الموزّعة. ^{[ 16 ]} توجد بدائل عديدة لآلية تمرير الرسائل، بما في ذلك الموصلات الشبيهة بـ RPC وقوائم انتظار الرسائل . ويُعدّ ضمان شفافية الموقع هدفًا وتحديًا هامًا للأنظمة الموزّعة .

يدرس علم التعقيد القائم على المعلومات (IBC) الخوارزميات المثلى والتعقيد الحسابي للمسائل المتصلة. وقد تناول هذا العلم مسائل متصلة مثل تكامل المسار، والمعادلات التفاضلية الجزئية، وأنظمة المعادلات التفاضلية العادية، والمعادلات غير الخطية، والمعادلات التكاملية، والنقاط الثابتة، والتكامل في الأبعاد العالية جدًا.

الأساليب الرسمية هي نوع خاص من التقنيات الرياضية المستخدمة في تحديد وتطوير والتحقق من أنظمة البرمجيات والأجهزة . ^{[ 17 ]} ويُعزى استخدام الأساليب الرسمية في تصميم البرمجيات والأجهزة إلى التوقع بأن إجراء تحليل رياضي مناسب، كما هو الحال في التخصصات الهندسية الأخرى، يُسهم في موثوقية التصميم ومتانته. ^{[ 18 ]}

يمكن وصف الأساليب الرسمية بأنها تطبيق مجموعة واسعة من أساسيات علوم الحاسوب النظرية، ولا سيما حسابات المنطق ، واللغات الرسمية ، ونظرية الأوتوماتا ، ودلالات البرامج ، بالإضافة إلى أنظمة الأنواع وأنواع البيانات الجبرية ، على مشاكل في مواصفات البرامج والأجهزة والتحقق منها. ^{[ 19 ]}

نظرية المعلومات هي فرع من فروع الرياضيات التطبيقية والهندسة الكهربائية وعلوم الحاسوب ، وتتناول قياس المعلومات كميًا . وقد طوّرها كلود إي. شانون لإيجاد حدود أساسية لعمليات معالجة الإشارات ، مثل ضغط البيانات وتخزينها ونقلها بشكل موثوق . ومنذ نشأتها، اتسع نطاق تطبيقاتها ليشمل العديد من المجالات الأخرى، بما في ذلك الاستدلال الإحصائي ، ومعالجة اللغات الطبيعية ، والتشفير ، وعلم الأحياء العصبي ، ^{[ 20 ]} وتطور ^{[ 21 ]} ووظيفة ^{[ 22 ]} الشفرات الجزيئية، واختيار النماذج في الإحصاء، ^{[ 23 ]} والفيزياء الحرارية، ^{[ 24 ]} والحوسبة الكمومية ، وعلم اللغويات ، وكشف الانتحال، ^{[ 25 ]} والتعرف على الأنماط ، وكشف الشذوذ ، وغيرها من أشكال تحليل البيانات . ^{[ 26 ]}

تشمل تطبيقات المواضيع الأساسية لنظرية المعلومات ضغط البيانات بدون فقدان (مثل ملفات ZIP )، وضغط البيانات مع فقدان (مثل ملفات MP3 و JPEG )، وتشفير القنوات (مثل خط المشترك الرقمي DSL ). يقع هذا المجال عند تقاطع الرياضيات والإحصاء وعلوم الحاسوب والفيزياء وعلم الأحياء العصبي والهندسة الكهربائية . وكان تأثيره حاسماً في نجاح مهمات فوياجر إلى الفضاء السحيق، واختراع القرص المضغوط، وجدوى الهواتف المحمولة، وتطوير الإنترنت ، ودراسة اللغويات والإدراك البشري، وفهم الثقوب السوداء ، والعديد من المجالات الأخرى. ومن المجالات الفرعية المهمة لنظرية المعلومات: تشفير المصدر ، وتشفير القنوات ، ونظرية التعقيد الخوارزمي ، ونظرية المعلومات الخوارزمية ، والأمن المعلوماتي ، ومقاييس المعلومات.

يُعدّ التعلّم الآلي فرعًا علميًا يُعنى ببناء ودراسة الخوارزميات القادرة على التعلّم من البيانات. ^{[ 27 ]} تعمل هذه الخوارزميات من خلال بناء نموذج قائم على المدخلات ^{[ 28 ] : 2} واستخدامه للتنبؤ أو اتخاذ القرارات، بدلاً من اتباع التعليمات المبرمجة صراحةً فقط.

يمكن اعتبار التعلّم الآلي فرعًا من فروع علوم الحاسوب والإحصاء . ويرتبط ارتباطًا وثيقًا بالذكاء الاصطناعي والتحسين ، اللذين يُسهمان في تطوير أساليب ونظريات ومجالات تطبيقية لهذا المجال. يُستخدم التعلّم الآلي في مجموعة واسعة من مهام الحوسبة التي يصعب فيها تصميم وبرمجة خوارزميات صريحة قائمة على قواعد محددة. ومن أمثلة تطبيقاته: تصفية البريد العشوائي ، والتعرّف الضوئي على الأحرف (OCR)، ^{[ 29 ]} ومحركات البحث ، ورؤية الحاسوب . يُخلط أحيانًا بين التعلّم الآلي واستخراج البيانات ، ^{[ 30 ]} على الرغم من أن الأخير يركز بشكل أكبر على تحليل البيانات الاستكشافي. ^{[ 31 ]} ويمكن النظر إلى التعلّم الآلي والتعرّف على الأنماط على أنهما وجهان لنفس المجال. ^{[ 28 ] : vii}

^{[ 39 ]}

الحوسبة المتوازية هي شكل من أشكال الحوسبة يتم فيه تنفيذ العديد من العمليات الحسابية في وقت واحد، ^{[ 40 ]} وتعتمد على مبدأ إمكانية تقسيم المشكلات الكبيرة إلى مشكلات أصغر، يتم حلها بعد ذلك "بالتوازي" . توجد عدة أشكال مختلفة للحوسبة المتوازية: التوازي على مستوى البت ، والتوازي على مستوى التعليمات ، والتوازي على مستوى البيانات ، والتوازي على مستوى المهام . استُخدمت الحوسبة المتوازية لسنوات عديدة، لا سيما في الحوسبة عالية الأداء ، ولكن ازداد الاهتمام بها مؤخرًا بسبب القيود الفيزيائية التي تحول دون زيادة تردد المعالجة . ^{[ 41 ]} ونظرًا لأن استهلاك الطاقة (وما يترتب عليه من توليد حرارة) في أجهزة الكمبيوتر أصبح مصدر قلق في السنوات الأخيرة، ^{[ 42 ]} فقد أصبحت الحوسبة المتوازية النموذج السائد في هندسة الحاسوب ، وخاصة في شكل معالجات متعددة النوى . ^{[ 43 ]}

تُعدّ كتابة البرامج الحاسوبية المتوازية أكثر صعوبة من كتابة البرامج التسلسلية، ^{[ 44 ]} لأن التزامن يُدخل عدة أنواع جديدة من الأخطاء البرمجية المحتملة ، وأكثرها شيوعًا حالات التزامن المتنافس . ويُعتبر التواصل والتزامن بين المهام الفرعية المختلفة عادةً من أكبر العقبات التي تحول دون تحقيق أداء جيد للبرامج المتوازية.

يُعرف الحد الأقصى الممكن لتسريع برنامج واحد نتيجة للتوازي باسم قانون أمدال .

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

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

الحاسوب الكمومي هو نظام حسابي يستخدم ظواهر ميكانيكا الكم مباشرةً ، مثل التراكب والتشابك ، لإجراء عمليات على البيانات . ^{[ 45 ]} تختلف الحواسيب الكمومية عن الحواسيب الرقمية القائمة على الترانزستورات . فبينما تتطلب الحواسيب الرقمية ترميز البيانات إلى أرقام ثنائية ( بتات )، كل منها يكون دائمًا في إحدى حالتين محددتين (0 أو 1)، تستخدم الحوسبة الكمومية الكيوبتات (بتات كمومية)، التي يمكن أن تكون في تراكبات من الحالات. ومن النماذج النظرية آلة تورينج الكمومية ، المعروفة أيضًا باسم الحاسوب الكمومي الشامل. تتشابه الحواسيب الكمومية نظريًا مع الحواسيب غير الحتمية والاحتمالية ؛ ومن الأمثلة على ذلك قدرتها على التواجد في أكثر من حالة في آن واحد. تم تقديم مجال الحوسبة الكمومية لأول مرة من قبل يوري مانين في عام 1980 ^{[ 46 ]} وريتشارد فاينمان في عام 1982. ^{[ 47 ] [ 48 ]} كما تم صياغة حاسوب كمومي باستخدام اللف المغزلي كبتات كمومية لاستخدامه كزمكان كمومي في عام 1968. ^{[ 49 ]}

أُجريت تجارب نُفذت فيها عمليات حسابية كمومية على عدد قليل جدًا من الكيوبتات. ^{[ 50 ]} ويستمر البحث العملي والنظري، وتدعم العديد من الحكومات الوطنية ووكالات التمويل العسكرية أبحاث الحوسبة الكمومية لتطوير أجهزة حاسوب كمومية لأغراض مدنية وأمنية، مثل تحليل الشفرات . ^{[ 51 ]}

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

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

التكامل واسع النطاق جدًا ( VLSI ) هو عملية إنشاء دائرة متكاملة (IC) من خلال دمج آلاف الترانزستورات في شريحة واحدة. بدأ استخدام تقنية VLSI في سبعينيات القرن الماضي مع تطوير تقنيات أشباه الموصلات والاتصالات المعقدة. المعالج الدقيق هو جهاز VLSI. قبل ظهور تقنية VLSI، كانت معظم الدوائر المتكاملة محدودة الوظائف. قد تتكون الدائرة الإلكترونية من وحدة معالجة مركزية ( CPU ) وذاكرة قراءة فقط ( ROM ) وذاكرة وصول عشوائي (RAM) ودوائر منطقية أخرى . تتيح تقنية VLSI لمصنعي الدوائر المتكاملة دمج جميع هذه الدوائر في شريحة واحدة.