الفصل الأول

The Role of Algorithms in Computing

دور الـ algorithms في علم الكمبيوتر

Algorithms

يعني إيه algorithm?

ال algorithm هو ببساطة طريقة لحل مشكلة معينة , أو بشكل أدق هو مجموعة من ال steps(خطوات) لحل مشكلة.

يعني إيه problem(مشكلة)؟

مشكلة يعني عندي input(دخل) عايز احوله ل output(خرج) وفق relationship(علاقة) واضحة بينهم.

مثال : مشكلة ال sorting(الترتيب) هي ان عندي مجموعة أرقام(دخل) وعايز أحوله لنفس مجموعة الأرقام ولكن مرتبة(خرج).

المشكلة بتتوصف بما يسمى الـ problem statement وكلمة statement يعني جملة , باختصار ال problem statement هو وصف واضح للمشكلة , بيتكون من وصف لل input ووصف لل output ومن الوصفين ال relationship بتكون واضحة.

تعالى نكتب problem statement لمشكلة ال sorting

دخل : مجموعة من الأرقام(a₁, a₂, a₃, ... a_n)

خرج : نفس مجموعة الأرقام بحيث (a1>=a2>=a3>=...>=a_n)

من وصف الـ input وال output اقدر الاحظ ان ال relationship هي علاقة ترتيب تنازلي

في حاجة بقى إسمها problem instance وكلمة instance يعني وحدة , ال problem instance هو دخل واحد للمشكلة مقيد ب constraints(قيود) ال problem statement.

قيود زي إيه؟ زي في ال problem statement اللي فاتت قيود الدخل ان الدخل يكون مجموعة أرقام , وبالتالي (10, 13, 7, 9, 20) ده problem instance لل sorting problem , ولكن (f, b, z, e) ده مش problem instance لأن دول مش مجموعة أرقام دول مجموعة حروف.

في مشكلة ال sorting تم تصميم عدد كبير من الـ algorithms لحلها وسيتم بإذن الله شرح أكتر من algorithm منهم في الفصل التاني , ولكن السؤال إمتى نختار إيه؟ أو ازاي أحدد أي algorithm أكثر كفاءة ل application(تطبيق) معين؟ الإجابة إن مفيش algorithm أكثر كفاءة من غيره في كل ال applications ولكن بشكل عام الاختيار الأنسب بيتوقف على عوامل بتختلف من مشكلة لمشكلة , وبشكل خاص في مشكلة ال sorting الاختيار بيتوقف على عدة عوامل منها:

• حجم الدخل(عدد الأرقام اللي هتترتب) وده لإن في algorithm ممكن يكون سريع جدا على حجم صغير من الدخل ولكن عند زيادة حجم الدخل ال algorithm بيكون بطئ ودي مشكلة معروفة في ال computer science اسمها scalability وكلمة scalability معناها القابلية للامتداد ومعناها في ال computer science مدى كفاءة ال algorithm في حل نفس المشكلة ولكن بدخل متزايد , يعني انت صممت algorithm لمشكلة ال sorting بايدك وجربناه على دخل مكون من الف رقم وكان ليه أداء معين إيه يكون أداءه لو جربناه على دخل مكون من مليون رقم؟؟
• مدى أمكانية إن الأرقام تكون مرتبة أو أقرب إلى الترتيب , ولتقريب الصورة فرضا ان algorithm معين رتب الف رقم ملخبطين في 100 مللي ثانية ودخلتله 1000 رقم تاني هما أصلا مرتبين خد 00ا مللي ثانية برده , أما algorithm تاني دخلتله 1000 رقم ملخبطين رتبهم في 100 مللي ثانية زي الأول ولكن لما دخلتله ألف رقم مترتبين طلع الخرج في 10 ميللي ثانية بس.
• نوع ال storage(التخزين) المستخدم وحجمه قد إيه ﻷن ده constraint مهم لازم يكون في بالك وانت بتصمم أي algorithm لأن ببساطة ممكن تصمم algorithm سريع جدا ولكن بيحتاج memory أكبر من المتاحة ليك , وبشكل عام حجم ال memory اللي بيستهلكه أي algorithm هو parameter(معامل) من معاملات ال performance جنب ال speed وغيرهم.

ال algorithm ممكن يكون correct(صحيح) أو incorrect(غير صحيح)

ال algorithm بيكون correct لو هو بيطلع الخرج الصحيح لأي problem instance وبيكون incorrect لو مش بيطلع خرج أو بيطلع خرج خطأ ل problem instance واحدة أو أكتر. تطبيقا على مشكلة ال sorting ال algorithm بيكون correct لو قدرت تثبت رياضيا ان ال algorithm بيطلع خرج صحيح لأي مجموعة أرقام كدخل , وطرق الإثبات دي بندرسها في كورسات وكتب ال Discrete mathematics. كملحوظة أحيانا ال incorrect algorithms بتكون مفيدة لو ال error بتاعها قليل ومفيش correct algorithm للمشكلة.

في أكتر من طريقة لتوصيف ال algorithm منها

1/ ما يسمى ال pseudocode وده عبارة عن كلام English بيوصف خطوات ال algorithm بشكل informal(غير رسمي يعني كلام انجليزي عادي ووسطيه كلمات مشهورة في أي لغة برمجة زي if, for واخواتهم)

2/ ممكن computer program(برنامج مكتوب بلغة برمجة معينة)

3/ ممكن hardware design يعني تصميم لدائرة hardware بتحل المشكلة وده شغل نادر جدا في مصر والشرق الأوسط كله.

4/ ممكن flow chart ودي خرائط فيها أشكال كل شكل له معنى معين بتستخدم برده في وصف ال algorithms.

أهم حاجة ان الطريقة توصف خطوات التنفيذ بشكل precise(محكم)

في الكتاب في فقرة طويلة عن أمثلة ل applications مهمة لل algorithms , الغرض منها توضيح أهمية علم ال algorithms , أنا هكتفي بعرض مشكلة واحدة وهي خاصة بالانترنت وهي مشكلة ال Routing , طبعا الكل يعرف ان أي data(بيانات) بتتحرك على الانترنت من ال source(المصدر) بتاعها ومن router ل router لغاية متوصل ال destination(الوجهة) بتاعتها , ازاي نقدر نحدد أفضل طريق لل data دي علشان توصل بسرعة وبدون خطأ هي مشكلة ال Routing ودي مشكلة complex(معقدة).

Data Structure

كلمة data يعني بيانات وكلمة Structure يعني تركيب أو هيكل , يعني إيه بقى تركيب البيانات , باختصار هي طريقة لتمثيل البيانات بشكل منظم لتسهيل ال access(أي قراءتها) وال modification(أي تعديلها). كمثال بسيط لو عندك في البيت 100 كتاب ممكن ترميهم في مكان وكل متحتاج تقرأ(access) أو تكتب حاجة(modification) في كتاب منهم تقعد تدور في ال 100 كتاب وتاخد وقت طويل لغاية متوصل للي انت عايزه , وممكن بدل منرميهم في مكان نرتبهم في مكتبة(data structure) ونقسم المكتبة لأقسام تاريخ وعلم نفس ودين وغيره وكل متحتاج كتاب انت عارف هو قسم ايه وتجيبه بسرعة جدا , بكدة انت سهلت وسرعت عملية ال access وال modification , وده اللي احنا بنحتاجه في البرمجة انك تنظم ال data في data structure علشان تسهل ال access وال modification.

وكلمة data structure دايما بتيجي جنب ال algorithms حتى هما في كورس واحد , لان تنظيم البيانات هو في الحقيقة مشكلة وبتحتاج حل , وكمان لان معظم ال problems بتكون access أو modification لبيانات زي مثلا عملية البحث في جوجل هي عملية access للبيانات الموجودة على الانترنت علشان تجيب ال data المشابهة لكلمة البحث , وبالتالي تنظيم البيانات بيمثل أكتر من نص المشكلة.

Efficiency

كلمة efficiency تعني الكفاءة وال efficiency في ال algorithms دايما بتتقاس بال speed(السرعة) ولكن في التطبيق العملي أي algorithm لازم يكون محدود ب constraints تخص ال machine(الالة) اللي هيشتغل عليها(حجم ال memory كمثال ل constraint). في الكتاب شرح مثال رائع علشان يبين الفرق الشاسع بين ال algorithms في الكفاءة وكمان علشان يثبت ان ال algorithms تعتبر technology(تكنولوجيا) بيحصلها تطور زي أي technology.

المثال : عندنا 2 algorithms بيستخدموا في حل مشكلة ال sorting هما ال insertion sort وال merge sort وال 2 هيتم شرحهم باذن الله في الفصل التاني بشئ من التفصيل , ال insertion sort بيتنفذ في c₁n² instructions بحيث أن c₁ هو ثابت و n هو عدد الأرقام اللي هتترتب و instruction يعني عملية , أما ال merge sort بيتنفذ في c₂nlg(n) instructions بحيث أن c₂ ثابت و n عدد الأرقام و lg يعني log₂ , هنفرض ان ال insertion sort هيشتغل على كمبيوتر A سريع جدا بينفذ بليون عملية في الثانية وكمان الـ programmer(المبرمج) اللي صممه وصل الثابت بتاعه ل 2, أما ال merge sort هيتنفذ على كمبيوتر B بطئ بينفذ 10 مليون عملية في الثانية وال programmer اللي صممه وصل الثابت بتاعه ل 50 , يعني كمبيوتر A أسرع من كمبيوتر B ب 100 مرة , ال 2 كمبيوتر هيرتبوا مليون رقم , لما نحسب ال efficiency بتاع ال 2 كمبيوتر هنلاقي كمبيوتر A(الأسرع) هيرتبهم في 2000 ثانية وكمبيوتر B(الأبطأ) هيرتبهم في 100 ثانية بس , يعني كمبيوتر B أسرع في التنفيذ من كمبيوتر A ب 20 مرة , وده بسبب ان ال algorithm اللي شغال على كمبيوتر B أكثر كفاءة من ال algorithm اللي شغال على كمبيوتر A . والفرق بيتضح أكتر لو زودنا الدخل من مليون رقم ل 10 مليون رقم , في الحالة دي هنلاقي ان كمبيوتر A محتاج 2.3 يوم علشان يرتبهم لكن كمبيوتر B محتاج بس 20 دقيقة!!