اقتباس

المقيِّم evaluator الذي يحدِّد معاني التعبيرات في لغة البرمجة هو برنامج بذاته.

ـــ هال أبيلسون Hal Abelson وجيرالد سوسْمَن Gerald Sussman، هياكل برامج الحاسوب وتفسيرها.

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

سنبني في هذا المقال لغة برمجة سنسميها لغة البيض Egg، حيث ستكون صغيرةً وبسيطةً لكنها قوية بما يكفي لتعبِّر عن أيّ حسابات تفكر فيها، كما ستسمح بالتجريدات abstractions البسيطة المبنية على دوال.

التحليل

إن أول ما تراه عينك عند النظر إلى لغة برمجة هو بنيتها اللغوية syntax أو صيغتها notation، والمحلل parser هو برنامج يقرأ نصًا ما وينتج هيكل بيانات data structure، بحيث يعكس بنية البرنامج الموجود في ذلك النص، فإن لم يشكِّل النص برنامجًا صالحًا، فيجب أن يخبرنا المحلل بالخطأ الذي سبب ذلك.

ستكون لغتنا ذات بنية لغوية بسيطة وموحدة، حيث سيكون كل شيء في Egg تعبيرًا، وقد يكون التعبير expresion اسم رابطة binding أو عددًا أو سلسلةً نصيةً string أو حتى تطبيقًا، كما تُستخدَم التطبيقات لاستدعاءات الدوال وللبنى اللغوية مثل if أو while.

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

تُكتَب التطبيقات بالطريقة نفسها المكتوبة بها في جافاسكربت، وذلك بوضع أقواس بعد التعبير، ويمكنها امتلاك أيّ عدد من الوسائط arguments بين هذين القوسين مفصول بين كل منها بفاصلة أجنبية ,.

do(define(x, 10),
   if(>(x, 5),
      print("large"),
      print("small")))

يعني توحيد لغة Egg أنّ الأشياء التي تُرى على أساس عوامل operators في جافاسكربت -مثل ‎>‎- هي رابطات عادية في هذه اللغة، وتُطبَّق مثل أيّ دالة أخرى، كما نحتاج إلى بنية do للتعبير عن تنفيذ عدة أشياء في تسلسل واحد، وذلك لعدم وجود مبدأ الكتل blocks في البنية التركيبية للغة.

يتكون هيكل البيانات الذي سيستخدمه المحلل لوصف برنامج ما من كائنات تعابير، لكل منها خاصية type توضِّح نوع التعبير وخصائص أخرى تصف محتواه.

تمثِّل التعابير التي من النوع "value" سلاسلًا نصيةً مجردةً أو أعدادًا، وتحتوي خاصية value لها على السلسلة النصية أو قيمة العدد الذي تمثله؛ أما التعابير التي من نوع "word" فتُستخدَم للمعرِّفات -أي الأسماء-، فمثل تلك الكائنات لها خاصية name تحمل اسم المعرِّف على أساس سلسلة نصية، وأخيرًا تمثِّل تعابير "apply" التطبيقات، إذ تملك خاصية operator التي تشير مرجعيًا إلى تعبير يُطَبَّق، بالإضافة إلى خاصية args التي تحمل مصفوفةً من تعابير الوسائط argument expressions.

سيُمثَّل جزء ‎>(x, 5)‎ من البرنامج السابق كما يلي:

{
  type: "apply",
  operator: {type: "word", name: ">"},
  args: [
    {type: "word", name: "x"},
    {type: "value", value: 5}
  ]
}

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

هذا على عكس المحلل الذي كتبناه لصيغة ملف الإعدادات في مقال التعابير النمطية Regular Expressions في جافاسكريبت، والذي كانت بنيته بسيطةً نوعًا ما، إذ يُقسِّم الدخل إلى أسطر ويعالج هذه الأسطر واحدًا واحدًا، حيث فلم يكن ممكنًا للسطر الواحد إلا بضع صور بسيطة يمكنه أن يكون عليها؛ أما هنا فيجب إيجاد طريقة أخرى، فالتعابير ليست مقسمةً إلى أسطر، كما تملك بنيةً تعاوديةً recursive، وتحتوي تعابير التطبيقات على تعابير أخرى.

يمكن حل هذه المشكلة بسهولة من خلال كتابة دالة محلل تعاودية على النحو الذي يعكس الطبيعة التعاودية للغة.

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

يكون أول جزء في المحلل كالتالي:

function parseExpression(program) {
  program = skipSpace(program);
  let match, expr;
  if (match = /^"([^"]*)"/.exec(program)) {
    expr = {type: "value", value: match[1]};
  } else if (match = /^\d+\b/.exec(program)) {
    expr = {type: "value", value: Number(match[0])};
  } else if (match = /^[^\s(),#"]+/.exec(program)) {
    expr = {type: "word", name: match[0]};
  } else {
    throw new SyntaxError("Unexpected syntax: " + program);
  }

  return parseApply(expr, program.slice(match[0].length));
}

function skipSpace(string) {
  let first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

يجب قص المسافات الفارغة من بداية السلسلة النصية للبرنامج بما أنّ لغة Egg التي نكتبها تشبه جافاسكربت في كونها تسمح لأيّ عدد من المسافات الفارغة بين عناصرها، وهنا يأتي دور دالة skipSpace.

تَستخدم parseExpression بعد تخطي أي مسافة بادئة ثلاثة تعبيرات نمطية لتحديد العناصر الصغرى الثلاثة التي تدعمها Egg، وهي السلاسل والأعداد والكلمات، كما يبني المحلل نوعًا مختلفًا من هياكل البيانات وفقًا للتي تطابق منها، فإذا كان الإدخال لا يتطابق مع أحد هذه النماذج الثلاثة، فلا يكون تعبيرًا صالحًا ويرفع المحلل خطأً.

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

function parseApply(expr, program) {
  program = skipSpace(program);
  if (program[0] != "(") {
    return {expr: expr, rest: program};
  }

  program = skipSpace(program.slice(1));
  expr = {type: "apply", operator: expr, args: []};
  while (program[0] != ")") {
    let arg = parseExpression(program);
    expr.args.push(arg.expr);
    program = skipSpace(arg.rest);
    if (program[0] == ",") {
      program = skipSpace(program.slice(1));
    } else if (program[0] != ")") {
      throw new SyntaxError("Expected ',' or ')'");
    }
  }
  return parseApply(expr, program.slice(1));
}

إذا كان المحرف التالي في البرنامج ليس قوسًا بادئًا ) فلن يكون هذا تطبيقًا، وتُعيد parseApply التعبير المعطى لها، وإلا فستتخطى القوس البادئ وتنشئ كائن شجرة بُنى syntax tree object لتعبير التطبيق ذاك، ثم تستدعي parseExpression تعاوديًا لتحلِّل كل وسيط حتى تجد القوس الغالق، كما يكون التعاود هنا غير مباشر من خلال استدعاء parseApply لدالة parseExpression والعكس، ولأن تعبير التطبيق يمكن تطبيقه كما في multiplier(2)(1)‎، فيجب أن تستدعي parseApply نفسها مرةً أخرى لتنظر فيما إذا كان يوجد زوج آخر من الأقواس أم لا، وذلك بعد تحليل تطبيق ما.

هذا كل ما نحتاجه لتحليل لغة Egg، إذ نغلفها في دالة parse لتتحقق أنها وصلت إلى نهاية سلسلة الدخل بعد تحليل التعبير -فبرنامج بلغة Egg هو تعبير وحيد-، ثم تعطينا هيكل البيانات للبرنامج.

function parse(program) {
  let {expr, rest} = parseExpression(program);
  if (skipSpace(rest).length > 0) {
    throw new SyntaxError("Unexpected text after program");
  }
  return expr;
}

console.log(parse("+(a, 10)"));
// → {type: "apply",
//    operator: {type: "word", name: "+"},
//    args: [{type: "word", name: "a"},
//           {type: "value", value: 10}]}

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

المقيم

لا شك في أننا نريد شجرة بنى لبرنامج ما من أجل تشغيلها، وهذه هي وظيفة المقيِّم evaluator، إذ تعطيه شجرة بنى وكائن نطاق يربط الأسماء بالقيم، وسيقيِّم التعبير الذي تمثله الشجرة، ثم يُعيد القيمة التي يخرجها.

const specialForms = Object.create(null);

function evaluate(expr, scope) {
  if (expr.type == "value") {
    return expr.value;
  } else if (expr.type == "word") {
    if (expr.name in scope) {
      return scope[expr.name];
    } else {
      throw new ReferenceError(
        `Undefined binding: ${expr.name}`);
    }
  } else if (expr.type == "apply") {
    let {operator, args} = expr;
    if (operator.type == "word" &&
        operator.name in specialForms) {
      return specialForms[operator.name](expr.args, scope);
    } else {
      let op = evaluate(operator, scope);
      if (typeof op == "function") {
        return op(...args.map(arg => evaluate(arg, scope)));
      } else {
        throw new TypeError("Applying a non-function.");
      }
    }
  }
}

يحتوي المقيِّم على شيفرة لكل نوع من أنواع التعابير، ويُخرج لنا تعبير القيمة مصنفة النوع literal value expression قيمته، كما في حالة التعبير 100 الذي يقيِّم إلى العدد 100 فقط؛ أما في حالة الرابطة، فيجب التحقق مما إذا كانت معرَّفةً على الحقيقة في النطاق أم لا، وإن كانت فسنجلب قيمتها.

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

نستخدِم قيمًا لدوال جافاسكربت عادية لنمثِّل قيم الدوال في Egg، كما سنعود إلى هذا بعد قليل حين تُعرَّف الصيغة الخاصة المسماة fun، ويمثِّل الهيكل التعاودي لـ evaluate هيكلًا مماثلًا للمحلِّل، وكلاهما يعكس هيكل اللغة نفسه، ومن الممكن مكاملة المحلِّل والمقيِّم أثناء التحليل أيضًا، لكن فصلهما عن بعضهما البعض بهذه الطريقة يجعل البرنامج أكثر نقاءً.

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

الصيغ الخاصة

يُستخدَم كائن الصيغ الخاصة specialForms لتعريف البُنى الخاصة في لغة Egg، حيث يربط الكلمات بالدوال التي تقيِّم مثل تلك الصيغ، ولنضف if بما أنه فارغ الآن:

specialForms.if = (args, scope) => {
  if (args.length != 3) {
    throw new SyntaxError("Wrong number of args to if");
  } else if (evaluate(args[0], scope) !== false) {
    return evaluate(args[1], scope);
  } else {
    return evaluate(args[2], scope);
  }
};

تتوقع بنية if ثلاثة وسائط بالضبط، وستقيّم الأول منها، فإذا لم تكن النتيجة هي القيمة false فستقيِّم الثاني، وإلا فالثالث هو الذي يُقيَّم، وتُعَد صيغة if هذه أقرب إلى عامل ‎?:‎ الثلاثي في جافاسكربت منها إلى عامل if في جافاسكربت أيضًا، فهو تعبير وليس تعليمة، ويُنتِج قيمةً تكون نتيجة الوسيط الثاني أو الثالث.

تختلف كذلك لغة Egg عن جافاسكربت في كيفية معالجة القيمة الشرطية إلى if، فهي لا تعامل الصفر والسلسلة النصية الفارغة على أنها خطأ false، بل القيمة false حصرًا وفقط.

السبب الذي يجعلنا في حاجة إلى تمثيل if على أساس صيغة خاصة بدلًا من دالة عادية، هو أن جميع وسائط الدوال تُقيَّم قبل استدعاء الدالة، بينما يجب ألا تقيِّم if إلا وسيطها الثاني أو الثالث بناءً على قيمة الوسيط الأول.

صيغة while شبيهة بهذا، فبما أن undefined غير موجودة في لغة Egg، فسنُعيد false لعدم وجود نتيجة أفضل وأكثر فائدة، كما في المثال التالي:

specialForms.while = (args, scope) => {
  if (args.length != 2) {
    throw new SyntaxError("Wrong number of args to while");
  }
  while (evaluate(args[0], scope) !== false) {
    evaluate(args[1], scope);
  }
  return false;
};

كذلك لدينا وحدة بنيوية أساسية أخرى هي do التي تنفِّذ كل وسائطها من الأعلى إلى الأسفل، وتكون قيمتها هي القيمة التي ينتجها الوسيط الأخير.

specialForms.do = (args, scope) => {
  let value = false;
  for (let arg of args) {
    value = evaluate(arg, scope);
  }
  return value;
};

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

specialForms.define = (args, scope) => {
  if (args.length != 2 || args[0].type != "word") {
    throw new SyntaxError("Incorrect use of define");
  }
  let value = evaluate(args[1], scope);
  scope[args[0].name] = value;
  return value;
};

البيئة

يكون النطاق الذي تقبَله evaluate كائنًا له خصائص تتوافق أسماؤها مع أسماء الرابطات، كما تتوافق قيمها مع القيم التي ترتبط بهذه الرابطات، وسنعرِّف كائنًا ليمثل النطاق العام.

يجب أن تكون لنا وصول إلى قيم بوليانية كي نستطيع استخدام بنية if التي عرفناها لتونا، وبما أنه لا يوجد إلا قيمتان منطقيتان فقط، فلا نحتاج إلى ترميز خاص لهما، بل نربطهما بالقيمتين true وfalse ثم نستخدمهما.

const topScope = Object.create(null);

topScope.true = true;
topScope.false = false;

نستطيع الآن تقييم تعبير بسيط يرفض قيمةً بوليانيةً.

let prog = parse(`if(true, false, true)`);
console.log(evaluate(prog, topScope));
// → false

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

for (let op of ["+", "-", "*", "/", "==", "<", ">"]) {
  topScope[op] = Function("a, b", `return a ${op} b;`);
}

إذا كانت لدينا طريقة لإخراج القيم، فسيكون ذلك مفيدًا لنا بلا شك، لذا سنغلِّف console.log في دالة ونسميها print.

topScope.print = value => {
  console.log(value);
  return value;
};

يعطينا هذا الأدوات الأساسية اللازمة لكتابة برامج بسيطة، حيث توفر الدالة أدناه طريقةً سهلةً لتحليل برنامج ما وتشغيله في نطاق جديد:

function run(program) {
  return evaluate(parse(program), Object.create(topScope));
}

سنستخدم سلاسل كائن النموذج الأولي لتمثيل النطاقات المتشعِّبة nested scopes كي يتمكن البرنامج من إضافة روابط إلى نطاقه المحلي دون تغيير النطاق الأعلى top-level scope.

run(`
do(define(total, 0),
   define(count, 1),
   while(<(count, 11),
         do(define(total, +(total, count)),
            define(count, +(count, 1)))),
   print(total))
`);
// → 55

ذلك هو البرنامج الذي رأيناه عدة مرات من قبل، والذي يحسب مجموع الأرقام من 1 إلى 10 مكتوبًا بلغة Egg، ومن الواضح أنه ليس أجمل من مثيله في جافاسكربت، لكنا نراه ممتازًا إذا نظرنا إلى حقيقة أنّ اللغة التي كُتب بها ليس فيها إلا 150 سطرًا من الشيفرات فقط.

الدوال

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

specialForms.fun = (args, scope) => {
  if (!args.length) {
    throw new SyntaxError("Functions need a body");
  }
  let body = args[args.length - 1];
  let params = args.slice(0, args.length - 1).map(expr => {
    if (expr.type != "word") {
      throw new SyntaxError("Parameter names must be words");
    }
    return expr.name;
  });

  return function() {
    if (arguments.length != params.length) {
      throw new TypeError("Wrong number of arguments");
    }
    let localScope = Object.create(scope);
    for (let i = 0; i < arguments.length; i++) {
      localScope[params[i]] = arguments[i];
    }
    return evaluate(body, localScope);
  };
};

تحصل الدوال في لغة Egg على نطاقاتها المحلية الخاصة بها، إذ تُنشِئ الدالة المنتَجة بواسطة صيغة fun هذا النطاق المحلي، وتضيف الرابطات الوسيطة إليه، ثم تقيِّم متن الدالة في هذا النطاق وتُعيد النتيجة.

run(`
do(define(plusOne, fun(a, +(a, 1))),
   print(plusOne(10)))
`);
// → 11

run(`
do(define(pow, fun(base, exp,
     if(==(exp, 0),
        1,
        *(base, pow(base, -(exp, 1)))))),
   print(pow(2, 10)))
`);
// → 1024

التصريف

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

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

سيكون من الممكن كتابة خطة تقييم بديلة للغة Egg، إذ تبدأ بتحويل البرنامج إلى برنامج جافاسكربت أولًا، ثم تستخدِم Function لاستدعاء مصرِّف جافاسكربت له، وبعدها سنحصل على النتيجة، فإذا كان هذا بكفاءة، فسيجعل لغة Egg تعمل بمعدل سريع جدًا مع الحفاظ على بساطة الاستخدام.

الاحتيال

لعلك لاحظت حين عرَّفنا if وwhile على أنهما ليستا سوى تغليف بسيط نوعًا ما حول نظيرتيهما في جافاسكربت، وبالمثل، فإنّ القيم في Egg ما هي إلا قيم جافاسكربت العادية.

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

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

behavior walk
  perform when
    destination ahead
  actions
    move left-foot
    move right-foot

behavior attack
  perform when
    Godzilla in-view
  actions
    fire laser-eyes
    launch arm-rockets

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

تدريبات

المصفوفات

اجعل لغة Egg تدعم المصفوفات من خلال إضافة الدوال الثلاثة التالية إلى النطاق العلوي top scope:

• array(...values)‎ لبناء مصفوفة تحتوي على قيم وسيطة.
• length(array)‎ للحصول على طول مصفوفة ما.
• element(array, n)‎ لجلب العنصر رقم n من مصفوفة ما.

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

// عدِّل هذه التعريفات...

topScope.array = "...";

topScope.length = "...";

topScope.element = "...";

run(`
do(define(sum, fun(array,
     do(define(i, 0),
        define(sum, 0),
        while(<(i, length(array)),
          do(define(sum, +(sum, element(array, i))),
             define(i, +(i, 1)))),
        sum))),
   print(sum(array(1, 2, 3))))
`);
// → 6

إرشادات للحل

إن أسهل طريقة لإضافة الدعم هي تمثيل مصفوفات Egg بمصفوفات جافاسكربت، ويجب أن تكون القيم المضافة إلى النطاق العلوي دوالًا، كما يمكن أن يكون تعريف array بسيطًا جدًا إذا استَخدَمت وسيط rest مع الصيغة ثلاثية النقاط triple-dot notation.

التغليف Closure

تسمح لنا الطريقة التي عرَّفنا بها fun بإضافة دوال في Egg للإشارة مرجعيًا إلى النطاق المحيط، مما يسمح لمتن الدالة أن تستخدِم قيمًا محليةً كانت مرئيةً في وقت تعريف الدالة، تمامًا مثلما تفعل دوال جافاسكربت، ويوضِّح البرنامج التالي هذا، إذ تُعيد دالة f دالةً تضيف وسيطها إلى وسيط f، مما يعني أنها تحتاج إلى وصول للنطاق المحلي الموجود داخل f كي تستطيع استخدام الرابطة a.

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

run(`
do(define(f, fun(a, fun(b, +(a, b)))),
   print(f(4)(5)))
`);
// → 9

ارجع الآن إلى تعريف صيغة fun واشرح الآلية المسببة لعملها.

إرشادات للحل

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

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

التعليقات

أليس من الجميل أن تتمكن من كتابة تعليقات في لغة Egg؟ فلو جعلنا التعليق يبدأ بعلامة # مثلًا كما في حال علامتي // في جافاسكربت -ولا تقلق بشأن المحلِّل، إذ لن نجري أيّ تغييرات جوهرية فيه كي يدعم التعليقات-، فما علينا سوى تغيير skipspace كي تتخطى التعليقات كذلك، كما لو كانت مسافات فارغة، بحيث نتخطى التعليقات في كل مرة نستدعي فيها skipspace.

الشيفرة أدناه تمثل skipspace، عدِّلها لتضيف دعم التعليقات في لغة Egg، مسترشدًا بما سبق.

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

function skipSpace(string) {
  let first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

console.log(parse("# hello\nx"));
// → {type: "word", name: "x"}

console.log(parse("a # one\n   # two\n()"));
// → {type: "apply",
//    operator: {type: "word", name: "a"},
//    args: []}

إرشادات للحل

• تأكد من جعل حلّك قادرًا على معالجة التعليقات المتعددة في صف مع مسافات فارغة محتملة بينها أو بعدها.
• سيكون التعبير النمطي أسهل طريقة تستخدمها في هذا التمرين للحل، لهذا اكتب شيئًا يطابق "مسافةً فارغةً أو تعليقًا أو صفرًا أو أكثر من مرة". واستخدم التابع exec أوmatch، وانظر إلى طول أول عنصر في المصفوفة المعادة -أي التطابق الكامل- لتعرف كم عدد المحارف التي عليك قصها.

إيجاد النطاق

الطريقة الوحيدة حاليًا لإسناد قيمة إلى رابطة هي define، حيث تتصرف هذه البنية مثل طريقة لتعريف رابطات جديدة وإعطاء قيمة جديدة للرابطات الحالية.

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

أضف صيغة set الخاصة التي تشبه define، وتعطي قيمةً جديدةً للرابطة لتحدِّث الرابطة في نطاق خارجي إذا لم تكن موجودةً سلفًا في النطاق الداخلي، وإن لم تكن هذه الرابطة معرفةً، فأبلغ بالخطأ ReferenceError الذي هو نوع خطأ قياسي.

سيعيقك نوعًا ما أسلوب تمثيل النطاقات على أساس كائنات بسيطة من أجل السهولة ها هنا، خاصةً إذا أردت استخدام دالة Object.getPrototypeOf مثلًا التي تعيد النموذج الأولي لكائن ما، وتذكَّر أيضًا أنّ النطاقات لا تنحدر من Object.prototype، لذا فإن أردت استدعاء hasOWnProperty عليها، فعليك استخدام التعبير التالي:

Object.prototype.hasOwnProperty.call(scope, name);
specialForms.set = (args, scope) => {
  // ضع شيفرتك هنا.
};

run(`
do(define(x, 4),
   define(setx, fun(val, set(x, val))),
   setx(50),
   print(x))
`);
// → 50
run(`set(quux, true)`);
// → ReferenceError أحد صور 

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

إرشادات للحل

سيكون عليك التكرار على نطاق واحد في كل مرة باستخدام Object.getPrototypeOf للذهاب إلى النطاق الخارجي اللاحق. واستخدِم hasOwnProperty لتعرف ما إذا كانت الرابطة الموضَّحة بخاصية name في أول وسيط لـ set موجودةً في ذلك النطاق أم لا، فإن كانت كذلك فاضبطها على نتيجة تقييم الوسيط الثاني لـ set ثم أعد تلك القيمة، وإذا وصلت إلى أقصى نطاق خارجي -بحيث تكون إعادة Object.getPrototypeOf هي null- ولم تعثر على الرابطة بعد، فستكون هذه الرابطة غير موجودة ويجب رمي خطأ هنا.

ترجمة -بتصرف- للفصل الثاني عشر من كتاب Elequent Javascript لصاحبه Marijn Haverbeke.

اقرأ أيضًا

• المقال السابق: البرمجة غير المتزامنة في جافاسكريبت
• دليلك الشامل لتعلم البرمجة
• النسخة الكامة من كتاب مدخل إلى الذكاء الاصطناعي وتعلم الآلة

الرسم التخطيطي أو المخطط هو مجموعة من النقاط والخطوط التي ترتبط ببعضها (يمكن أن تكون فارغة)، وتسمى نقاط المخطط رؤوسًا vertices أو عقدًا nodes، بينما تسمى الخطوط التي تربط رؤوس المخطط أضلاعًا edges أو أقواسًا أو خطوطًا.

يعرَّف مخطط G مثلًا كزوْج (V، E)، حيث تمثّل V مجموعة من الحروف، وتمثّل E مجموعة الأضلاع التي تربط تلك الحروف، انظر:

E ⊆ {(u,v) | u, v ∈ V}‎‎

تخزين المخططات

هناك طريقتان شائعتان لتخزين المخططات، وهما:

• مصفوفة التجاور Adjacency Matrix.
• قائمة التجاور.

مصفوفة التجاور

مصفوفة التجاور هي مصفوفة تُستخدم لتمثيل مخطط محدود finite graph، وتشير عناصر المصفوفة إلى ما إذا كانت أزواج الرؤوس متجاورة (مترابطة) في المخطط أم لا.

وفي نظرية المخططات، نقول أنّ العقدة B مجاورة للعقدة A إذا كنا نستطيع الذهاب من العقدة A إلى العقدة B، وسنتعلم الآن كيفية تخزين العُقد المتجاورة عبر مصفوفة التجاور Adjacency Matrix ثنائية الأبعاد، هذا يعني أننا سنمثل العقد التي تتشارك الأضلاع فيما بينها.

نرى في الشكل الموضح أعلاه جدولًا إلى جانب المخطط، ويمثّل هذا الجدول مصفوفة التجاور الخاصة بالمخطط المجاور له، وتمثل Matrix[‎i][j] = 1  هنا وجود ضلع بين i و j. بالمقابل، سنكتب Matrix[‎i][j] = 0 إذا لم يكن هناك أيّ ضلع يربطهما.

نستطيع وزن تلك الأضلاع، أي إلحاق رقم بكل ضلع -قد يمثل هذا الرقم المسافة بين مدينتين مثلًا-، وهنا نضع الوزن في الموضع Matrix[‎i][j]‎‎ بدلًا من 1.

والمخطط الموضح أعلاه ثنائي الاتجاه Bidirectional، أو غير موجّه Undirected، أي أنّه إذا كان بإمكاننا الانتقال من العقدة 2 إلى العقدة 1 فيمكننا أيضًا الانتقال من العقدة 1 إلى العقدة 2. إن لم تتحقّق هذه الخاصية نقول أنّ المخطط موجّه Directed. وتوضع أسهم بدل الخطوط إذا كان المخطط موجَّهًا، كما يمكن استخدام مصفوفات التجاور لتمثيل هذا النوع من المخططات.

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

انظر الشيفرة التوضيحية pseudo-code التالية لإنشاء مصفوفة التجاور، حيث يمثل N عدد العُقد:

Procedure AdjacencyMatrix(N):
Matrix[N][N]
for i from 1 to N
    for j from 1 to N
        Take input -> Matrix[i][j]
    endfor
endfor

فيما يلي طريقة أخرى لتعبئة المصفوفة، يمثل N فيها عدد العُقَد بينما يمثل E عدد الأضلاع:

Procedure AdjacencyMatrix(N, E): 
Matrix[N][E] 
for i from 1 to E
    input -> n1, n2, cost
    Matrix[n1][n2] = cost
    Matrix[n2][n1] = cost
endfor

يمكنك إزالة السطر

 Matrix[n2][n1] = cost 

من الشيفرة في المخططات الموجّهة.

عيوب استخدام مصفوفة التجاور

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

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

والفائدة الوحيدة لمصفوفة التجاور هي أنها تمكّننا من العثور بسهولة على مسار بين عقدتين مثل u-v، وكذلك تكلفة cost ذلك المسار، أي مجموع أوزان الأضلاع التي تؤلف المسار.

شيفرة جافا التالية تطبق الشيفرة العامّة أعلاه:

import java.util.Scanner;
public class Represent_Graph_Adjacency_Matrix
{
   private final int vertices;
private int[][] adjacency_matrix;
   public Represent_Graph_Adjacency_Matrix(int v)
   {
       vertices = v;
       adjacency_matrix = new int[vertices + 1][vertices + 1];
   }
   public void makeEdge(int to, int from, int edge)
   {
       try
       {
           adjacency_matrix[to][from] = edge;
       }
       catch (ArrayIndexOutOfBoundsException index)
       {
           System.out.println("The vertices does not exists");
       }
   }
   public int getEdge(int to, int from)
   {
       try
       {
           return adjacency_matrix[to][from];
       }
       catch (ArrayIndexOutOfBoundsException index)
       {
           System.out.println("The vertices does not exists");
       }
       return -1;
   }
   public static void main(String args[])
   {
       int v, e, count = 1, to = 0, from = 0;
       Scanner sc = new Scanner(System.in);
       Represent_Graph_Adjacency_Matrix graph;
       try
       {
           System.out.println("Enter the number of vertices: ");
           v = sc.nextInt();
           System.out.println("Enter the number of edges: ");
           e = sc.nextInt();
           graph = new Represent_Graph_Adjacency_Matrix(v);
           System.out.println("Enter the edges: <to> <from>");
           while (count <= e)
           {
               to = sc.nextInt();
               from = sc.nextInt();
               graph.makeEdge(to, from, 1);
               count++;
           }
           System.out.println("The adjacency matrix for the given graph is: ");
           System.out.print("  ");
           for (int i = 1; i <= v; i++)
               System.out.print(i + " ");
           System.out.println();
for (int i = 1; i <= v; i++)
           {
               System.out.print(i + " ");
               for (int j = 1; j <= v; j++)
                   System.out.print(graph.getEdge(i, j) + " ");
               System.out.println();
           }
       }
       catch (Exception E)
       {
           System.out.println("Something went wrong");
       }
       sc.close();
   }
}

لتشغيل الشيفرة أعلاه، احفظ الملف، ثم صرّف compile الشيفرة باستخدام التعليمة الآتية:

 ‎javac Represent_Graph_Adjacency_Matrix.java

انظر المثال التالي الذي يوضح هذا:

$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges:
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0

تخزين المخططات (قوائم التجاور)

قائمة التجاور هي مجموعة من القوائم غير المرتبة تُستخدم لتمثيل المخططات المحدودة finite graphs، وتصف كل قائمة في المجموعة جيرانَ كلّ حرف من حروف المخطط. وميزة قوائم التجاور أنّها تحتاج مساحة ذاكرة أقل لتخزين المخططات.

انظر المثال التالي عن مخططٍ ومصفوفة التجاور الخاصة به:

وهذه قائمة التجاور الخاصة بالمخطط أعلاه:

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

تدعم العديد من لغات البرمجة نوعي البيانات المتجهات Vector والقوائم List ، والتي يمكننا استخدامها لتخزين قائمة التجاور، وهكذا لن يكون علينا تحديد حجم القائمة إذ يكفي أن نحدّد الحد الأقصى لعدد العقد. انظر الشيفرة العامة لذلك، حيث يمثل maxN الحد الأقصى للعُقد، بينما يمثل E عدد الأضلاع، ويشير التعبير x, y إلى وجود ضلع يربط بين x وy:

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector() 
for i from 1 to E
    input -> x, y              
    edge[x].push(y)
    edge[y].push(x)
end for
Return edge

وبما أنّ هذا المخطط غير موجّه فإنّ وجود ضلع من x إلى y يستلزم وجود ضلع معاكس، أي ضلعٍ من y إلى x، ولن تتحقق هذه الخاصية في المخططات غير الموجّهة.

أما بالنسبة للمخططات الموزونة فسنحتاج إلى تخزين التكلفة (الوزن) أيضًا، من خلال إنشاء متجه أو قائمة أخرى باسم cost[]‎‎ لتخزينها، انظر الشيفرة العامة لذلك:

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
    input -> x, y, w
    edge[x].push(y)
    cost[x].push(w)
end for
Return edge, cost

يمكننا الآن أن نعثر بسهولة على العقد المتصلة بعقدة ما وعددها أيضًا، وسنحتاج وقتًا أقل مقارنة بمصفوفة التجاور. بالمقابل، ستكون مصفوفة التجاور أكثر كفاءة إن احتجنا إلى معرفة ما إذا كان هناك ضلع بين u وv.

مقدمة إلى نظرية الرسوم التخطيطية

نظرية المخططات أو الرسوم التخطيطية Graph Theory هي فرع من فروع الرياضيات يهتم بدراسة الرسوم التخطيطية، وهي كائنات رياضية تُستخدم لنمذجة العلاقات الزوجية بين الكائنات.

طُوِّرت نظرية المخططات من قبل اختراع الحاسوب، إذ كتب ليونهارت أويلر Leonhard Euler ورقة حول جسور كونيجسبرج السبعة Seven Bridges of Königsberg والتي تُعدّ أوّل ورقة علمية عن نظرية المخططات، وأدرك الناس منذ ذلك الحين أنه إذا أمكننا تحويل المشاكل إلى مسائل من نوع مدينة-طريق City-Road، فيمكننا حلها بسهولة باستخدام نظرية المخططات. وهناك تطبيقات عديدة لهذه النظرية، لعل أشهرها هو العثور على أقصر مسافة بين مدينتين.

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

إليك تعاريف من المهم الاطلاع عليها ومعرفتها:

• المخططات: لنقل أنّ لدينا 6 مدن، نرقّم هذه المدن من 1 إلى 6. سننشئ الآن مخططًا يمثّل هذه المدن، حيث تمثل الرؤوسُ المدن، مع ربط المدن التي تربطها طرق فيما بينها بأضلاع.

هذا مخطط بسيط لتمثيل المدن والطرق الرابطة بينها، ونسمي هذه المدن في نظرية المخططات عقدًا Nodes أو حروفًا Vertex فيما نسمّي الطرق أضلاعًا Edge.

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

تمثيل لمسار الفارس على رقعة الشطرنج

وببساطة، تمثّل العقدة أيّ نوع من الكائنات، وتمثّل الأضلاع العلاقات بين تلك الكائنات.

• العقدة المتجاورة Adjacent Node: تكون B مجاورة لـ A إذا اشتركت عقدة A مع عقدة أخرى B في ضلع واحد، أي نقول أنّ العقدتين متجاورتان إذا اتصلت عقدتان اتصالًا مباشرًا، ويمكن لكل عقدة أن يكون لها عدة عقد مجاورة.

• المخططات الموجّهة وغير الموجّهة Directed and Undirected Graph: توضع علامات توجيهية (مثل الأسهم) على الأضلاع في المخططات الموجّهة للدلالة على أنّ الضلع أحادي الاتجاه. من ناحية أخرى، تحتوي أضلاع المخططات غير الموجّهة على علامات اتجاه على كلا الجانبين، للدلالة على أنها ثنائية الاتجاه. لكن تُحذف علامات التوجيه تلك في الغالب من المخططات غير الموجّهة، وتمثّل حينها الأضلاع كخطوط وحسب.

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

يُطلق على النوع الأول مخططات غير موجّهة undirected graphs، وتسمّى الأضلاع أضلاعًا غير موجّهة undirected edges، بالمقابل، يسمّى النوع الثاني مخططات موجّهة directed graph وتسمّى الأضلاع أضلاعًا موجّهة directed edges.

• المخططات الموزونة وغير الموزونة Weighted and Unweighted Graph: المخطط الموزون هو مخطط يكون لكلّ ضلع من أضلاعه رقم (وزن)، يمكن أن تمثّل هذه الأوزان التكاليف أو الأطوال أو السعات وغير ذلك، وذلك اعتمادًا على المشكلة المطروحة.

بالمقابل، المخططات غير الموزونة هي مخططات نفترض أنّ أوزان جميع أضلاعها متساوية (تساوي1 افتراضيًا ).

• المسارات: يمثّل المسار طريقًا للانتقال من عقدة إلى أخرى ويتألّف من سلسلة من الأضلاع، ولا شيء يمنع وجود عدة مسارات بين عقدتين.

في المثال أعلاه، هناك مساران من A إلى D، الأول هو A-> B ،B-> C ،C-> D ، وكلفته (مجموع أوزان الأضلاع التي تؤلّفه) هي 3 + 4 + 2 = 9، أما المسار الآخر فهو A-> D، وكلفته 10. يقال أن المسار الذي يكلّف أدنى قدر هو المسار الأقصر.

• الدرجة degree: درجة الحرف degree of a vertex هي عدد الأضلاع المرتبطة به، فإذا كان هناك ضلع يرتبط بالحرف في كلا الطرفين (حلقة loop)، فسيُحسب مرتين.

يكون للعُقد في المخططات الموجّهة نوعان مختلفان من الدرجات:

• الدرجة الداخلية In-degree: عدد الأضلاع التي تشير إلى العقدة.
• الدرجة الخارجية Out-degree: عدد الأضلاع التي تنطلق من العقدة الحالية وتشير إلى العقد الأخرى. بالنسبة للمخططات غير الموجّهة، يكون هناك نوع واحد طبعا، ويُسمّى درجة الحرف.

بعض الخوارزميات المتعلقة بنظرية المخططات:

• خوارزمية بلمان‎ فورد Bellman–Ford
• خوارزمية ديكسترا Dijkstra
• خوارزمية فورد فولكرسون Ford–Fulkerson
• خوارزمية كروسكال Kruskal.
• خوارزمية الجار الأقرب Nearest neighbour algorithm.
• خوارزمية بْرِم Prim.
• خوارزمية البحث العميق أولا Depth-first search.
• خوارزمية البحث العريض أولًا Breadth-first search.

سوف نستعرضُ بعض هذه الخوارزميات لاحقًا.

الترتيب الطوبولوجي Topological Sort

يرتّب الترتيب الطوبولوجي حروف مخطط موجّه ترتيبًا خطيًا، إذ يضعها في قائمة مُرتّبة حسب الأضلاع الموجّهة التي تربط تلك الحروف. وليكون هذا الترتيب ممكنا، يجب ألّا يحتوي المخطط على دورة موجّهة directed cycle، فإن كان لدينا مخطط ‎G = (V, E)‎، فالترتيب الخطي رياضيًا هو ترتيب متوافق مع المخطط، أي يحقّق ما يلي:

• إن كانت ‎G‎ تحتوي الضلع ‎(u, v) ∈‎ E الذي ينتمي إلى E وينطلق من الحرف u إلى v، فستكون u أصغر من v وفق هذا الترتيب.

وهنا من المهم ملاحظة أنّ كلّ مخطط موجّه غير دوري directed acyclic graph، أو DAG اختصارًا له ترتيب طوبولوجي واحد على الأقل، وهناك عدد من الخوارزميات التي تمكّننا من إنشاء ترتيب طوبولوجي لمخطط موجّه غير دوري في وقتٍ خطي، هذا مثال عام على إحداها:

1. استدع دالة ‎depth_first_search(G)‎ لحساب أوقات الإنتهاء finishing times ‏بـ ‎v.f‎ لكل حرف ‎v‎ ‏
2. عقب الانتهاء من حرف ما، أدرِجه في مقدّمة قائمة مرتبطة linked list.
3. يُحدَّد الترتيب الطوبولوجي بقائمة الحروف المرتبطة التي نتجت من الخطوتين السابقتين.

يمكن إجراء ترتيب طوبولوجي في مدة ‎V + E، لأنّ "خوارزمية البحث العميق أولًا depth-first search" تستغرق مدّة ‎‎(V + E)‎‎ ـ كما ستستغرق ‎Ω(1)‎ (وقت ثابت) لإدراج كل الحروف ‎|V|‎ في مقدمة القائمة المرتبطة.

تستخدم العديدُ من التطبيقات المخططاتَ الموجّهة الدورية directed acyclic graphs لتمثيل الأسبقية بين الأحداث، إذ يُستخدم الترتيب الطوبولوجي للحصول على الترتيب الصحيح لمعالجة كل حرف من حروف المخطط. وقد تمثّل حروف المخططُ المهامَ التي يتعيّن إنجازها، فيما تمثل الأضلاع أسبقية تنفيذ تلك المهام، وهكذا يمثّل الترتيب الطوبولوجي التسلسل المناسب لأداء مجموعة المهام الموضّحة في ‎V‎.

مثال

ليكن ‎v‎ حرفًا يمثّل مهمّة ‎Task(hours_to_complete: int)‎، بحيث يمثّل الوسيط hours_to_complete الوقت المُستغرَق لتنفيذ المهمة. فمثلًا، تمثّل ‎Task(4)‎ مهمّة تستغرق ‎4‎ ساعات لإكمالها.

من جهة أخرى، يمثّل ضلع ‎e‎ قيمة ‎Cooldown(hours: int)‎، والتي تمثّل المدة الزمنية التي تنقضي قبل استئناف المهمة التالية (أي التي يشير إليها الضلع) بعد الانتهاء من المهمة الحالية (التي ينطلق منها الضلع). فإن كان هناك ضلع ‎Cooldown(3)‎ يربط بين مهمّتين أ و ب، فذلك يعني أنه بعد الانتهاء من المهمة أ، ستحتاج أن تنتظر 3 ساعات حتى تستطيع تنفيذ المهمة ب (مثلا ليبرد المحرّك).

فيما يلي، المخطط غير الدوري والموجّه ‎dag‎ يحتوي 5 رؤوس:

A <- dag.add_vertex(Task(4));
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3));
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

نربط الحروف عبر أضلاع موجّهة بحيث يكون المخططات غير دوري، انظر:

// A ---> C -----+
// |      |      |
// v      v      v
// B ---> D ---> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));

ستكون هناك ثلاثة تراتيب طوبولوجية ممكنة بين ‎A‎ و‎E‎:

• A -> B -> D -> E
• A -> C -> D -> E
• A -> C -> E

رصد الدورات في المخططات الموجهة باستخدام الاجتياز العميق أولا Depth First Traversal

إذا نتج عن الاجتياز العميق أولًا ضلعٌ خلفي back edge، فذلك يعني أنّ المخطط الموجّه يحتوي دورة cycle. والضلع الخلفي هو ضلع ينطلق من عقدة ويعود إليها أو إلى إحدى أسلافها في شجرة بحث عميق أولًا Depth-first search اختصارًا DFS.

بالنسبة لمخطط غير متصل disconnected graph، سنحصل على غابة بحث عميق أولا أو غابة DFS وهي اختصار لـ DFS forest، لذلك سيكون عليك التكرار على جميع الحروف في المخطط لإيجاد أشجار البحث العميق أولًا والمنفصلة disjoint DFS trees.

فيما يلي تنفيذ بلغة C++‎‎:

#include <iostream>
    #include <list>

   using namespace std;

   #define NUM_V   4
   bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
   {
       visited[u]=true;
       recStack[u]=true;
       list<int>::iterator i;
       for(i = graph[u].begin();i!=graph[u].end();++i)
       { 
           if(recStack[*i])

شرح السطر السابق في الشيفرة: عند إيجاد حرف v في مكدس التكرارية الخاص باجتياز DFS، أعِد true، تابع المثال الآتي:

               return true;
           else if(*i==u) // في حال كان هناك ضلع من الحرف إلى نفسه
               return true;
           else if(!visited[*i])
           {   if(helper(graph, *i, visited, recStack))
                  return true;
           }
       }
       recStack[u]=false;
       return false;
   }

هنا تستدعي دالة التغليف الدالةَ helper على كل حرف لم يُزَر بعد، وتعيد دالة helper القيمة true عند رصد ضلع خلفي في الشجيرة، وإلا فإنها تعيد false، تابع المثال الآتي:

bool isCyclic(list<int> *graph, int V)
   {
     bool visited[V];  // مصفوفة لتتبع الأحرف المُزارة سلفا
     bool recStack[V]; // مصفوفة لتتبع الأحرف في المكدس التكراري للاجتياز
     for(int i = 0;i<V;i++)
      visited[i]=false, recStack[i]=false;  // تهيئة جميع الأحرف على أنها غير مُزارة تكراريًا
     for(int u = 0; u < V; u++) // التحقق اليدوي مما إذا كانت كل الأحرف مُزارة
     {   if(visited[u]==false)
         {  if(helper(graph, u, visited, recStack)) 
// التحقق مما إذا كانت شجرةُ “بحثٍ عميقٍ أولًا” تحتوي دورة.
              return true;
}
     }
      return false;
   }
   /*
   Driver function
   */
   int main()
   {
       list<int>* graph = new list<int>[NUM_V];
       graph[0].push_back(1);
       graph[0].push_back(2);
       graph[1].push_back(2);
       graph[2].push_back(0);
       graph[2].push_back(3);
       graph[3].push_back(3);
       bool res = isCyclic(graph, NUM_V);
       cout<<res<<endl;
   }

تكون النتيجة كما هو موضّح أدناه، أن هناك ثلاثة أضلاع خلفية في المخططات، واحد بين الحرفين 0 و 2؛ وآخر بين الحروف 0 و1 و2؛ والحرف 3. والتعقيد الزمني للبحث يساوي O (V + E)‎‎، حيث يمثّل V عدد الحروف، وE يمثّل عدد الأضلاع.

خوارزمية Thorup

كيف يمكن العثور على أقصر مسار من حرف (مصدر) معيّن إلى أيّ حرف آخر في مخطط غير موجّهة؟ قدّم "ميكيل توغوب Mikkel Thorup" -نُطْقُ اسمه من الدانماركية- أول خوارزمية تحل هذه المشكلة. يساوي التعقيد الزمني لهذه الخوارزمية O (m)‎‎.

وفيما يلي الأفكارُ الأساسية التي تعتمد عليها الخوارزمية:

• هناك عدّة طرق للعثور على الشجرة المتفرّعة spanning tree في مدة O (m)‎‎ (لن نذكر هذه الطرق هنا)، سيكون عليك إنشاء الشجرة المتفرّعة من الضلع الأقصر إلى الأطول، وسينتج عن ذلك غابة (مجموعة من الأشجار غير المتصلة بالضرورة) تحتوي العديد من المكوّنات المتصلة قبل أن تنمو كاملةً.
• اختر عددًا صحيحًا b ‏(b> = 2)، ولا تأخذ بالحسبان إلّا الغابات المتفرّعة ذات الطول الأقصى b ^ k، ثم ادمج المكونات المتشابهة في كل شيء ولكن تختلف في قيمة k. سنسمّى أصغر قيم k مستوى المكوّن level of the component. ثم ضع المكوّنات بعد هذا في الشجرة في المكان المناسب بحيث يكون الحرف u أبًا للحرف v إذ كان u هي أصغر مكوّن مختلف عن v ويحتوي v بشكل كامل. الجذر سيكون المخطط بأكمله، أمّا الأوراق فهي الحروف المفردة single vertices في المخطط الأصلي (مستواها يساوي سالب ما لا نهاية). ستحتوي الشجرة على O (n)‎‎ عقدة.
• حافظ على المسافة بين كل مكوّن وبين المصدر كما هو الحال في خوارزمية Dijkstra، تساوي مسافة مكوّن يحتوي أكثر من حرفٍ المسافةَ الأقل بين أبنائها غير الموسَّعين unexpanded children. اجعل مسافة الحرف الأصلي source vertex على 0، ثمّ حدّث الأسلاف وفقًا لذلك.
• احسب المسافات بنظام العدّ من الأساس b أو base b، وعند زيارة عقدة في المستوى k للمرة الأولى، ضع أبناءها في مجموعات أو سلَّات buckets مشتركة بين جميع العقد من المستوى k. وخذ بالحسبان أوّل b سلّة وحسب في كل مرة تزور فيها عقدة، وَزُر كلّ واحدة منها ثمّ أزلها، ثمّ حدّث مسافة العقدة الحالية، وَأعِد ربط العقدة الحالية بأصلها باستخدام المسافة الجديدة وانتظر الزيارة القادمة للسلات التالية.
• عند زيارة ورقة leaf، تكون المسافة الحالية هي المسافة النهائية للحرف. وسِّع جميع الأضلاع المنطلقة منه في المخطط الأصلي، ثمّ حدّث المسافات وفقًا لذلك.
• زر العقدة الجذرية (المخطط كاملًا) بشكل متكرر إلى أن تصل إلى الوجهة المقصودة.

تعتمد هذه الخوارزمية على حقيقة أنّه لا يمكن أن يوجد ضلع ذا طول أقل من l بين مكوّنيْن متصليْن في غابة متفرّعة ذات حدّ طولي يساوي ‏‎‎length limitation، لذلك، يمكنك حصر تركيزك على مكوّن واحد متصل بدءًا من مسافة x إلى أن تصل إلى المسافة x + l. ستزور بعض الحروف في الطريق قبل زيارة جميع الحروف ذات المسافة الأقصر، لكن ذلك لا يهم بما أنّنا نعلم أنّه لن يكون هناك مسار أقصر إلى هنا من تلك الحروف.

اجتياز المخططات Graph Traversals

هناك العديد من الخوارزميات للبحث في المخططات، سنستعرض إحداها فيما يلي، وهي خوارزمية البحث العميق أولا.

تنفذ الشيفرة التالية هذه الخوارزمية، إذ تنشئ دالة تأخذ فهرس العقدة الحالي كوسيط، وقائمة التجاور (مخزّنة في متجهة من المتجهات)، ومتجهة منطقية vector of boolean لتعقّب العقدة التي تمت زيارتها، انظر:

void dfs(int node, vector<vector<int>>* graph, vector<bool>* visited) {
    // التحقّق مما إذا كانت العقدة مُزارة سلفا
    if((*visited)[node])
       return;
    // set as visited to avoid visiting the same node twice
    (*visited)[node] = true;
    // نفّذ بعض الإجراءات هنا
    cout << node;
    // اجتياز العقد المتجاورة عبر البحث العميق أولا
    for(int i = 0; i < (*graph)[node].size(); ++i)
        dfs((*graph)[node][i], graph, visited);
}

ترجمة -بتصرّف- للفصلين 9 و10 من كتاب Algorithms Notes for Professionals

اقرأ أيضًا

• المقالة السابقة: الأشجار Trees في الخوازرميات
• مدخل إلى الخوارزميات
• دليل شامل عن تحليل تعقيد الخوارزمية
• النسخة الكاملة من كتاب مدخل إلى الذكاء الاصطناعي وتعلم الآلة

تمثل الأشجار نوعًا فرعيًا لهيكل أعم من هياكل البياناتٍ التخطيطية التفرعية Node-Edge Graph Data Structure كالآتي:

والشجرة هي مخطط يحقق الشرطين التاليين:

• غير حلقي acyclic: أي لا يحتوي أيّ دورات cycles أو حلقات loops.
• متصل: أي يمكن الوصول إلى كل عقدة من عقد المخطط عبر مسار معيّن.

وهيكل الشجرة شائع جدًا في علوم الحاسوب، إذ يُستخدم لنمذجة العديد من هياكل البيانات الخوارزمية المختلفة، مثل الأشجار الثنائية العادية والأشجار الحمراء-السوداء red-black trees، وأشجار B وأشجار AB وأشجار 23 وأشجار الكومة Heap وكذلك أشجار Trie.

وتكون الشجرة جِذريةً ‎Rooted Tree‎ في حال:

• اختيار خلية واحدة لتكون جذرًا للشجرة.
• صباغة Painting الجذر في أعلى الشجرة.
• إنشاء طبقة سفلية lower layer لكل خلية في المخطط تبعًا للمسافة بينها وبين الجذر، فكلما كانت المسافة أكبر، كانت الخلية أسفل كما في الصورة التوضيحية أعلاه. ويرمز عادةً للأشجار بالرمز ‎T‎.

الأشجار اللانهائية anary tree

نُمثّل الأشجار اللانهائية -أي الأشجار التي يمكن أن يتفرّع عدد لانهائي من الفروع من عقدها- على هيئة أشجار ثنائية binary tree، وهي أشجار يتفرع عن كل عقدة منها فرعان فقط، ويُعَد الفرع الثاني منهما شقيقًا Sibling، لاحظ أنه إذا كانت الشجرة ثنائيةً، فسينشئ التمثيل عُقدًا إضافية.

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

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

struct node
 {
    struct node *next;
    struct node *child;
    std::string data;
 }
 void printtree_r(struct node *node, int depth)
 {
    int i;
    while(node)
    {
        if(node->child)
        {
           for(i=0;i<depth*3;i++)
               printf(" ");
           printf("{\n"):
           printtree_r(node->child, depth +1);
           for(i=0;i<depth*3;i++)
               printf(" ");
           printf("{\n"):

           for(i=0;i<depth*3;i++)
              printf(" ");
            printf("%s\n", node->data.c_str());
            node = node->next;
         }
     }
 }
 void printtree(node *root)
 {
    printree_r(root, 0);
 }

التحقق من تساوي شجرتين ثنائيتين

انظر الشجرتين التاليتين:

هاتان الشجرتين متساويتان، على خلاف الشجرتين التاليتين:

وفيما يلي شيفرة عامة زائفة pseudo code للتحقق من تساوي شجرتين:

boolean sameTree(node root1, node root2){
if(root1 == NULL && root2 == NULL)
return true;
if(root1 == NULL || root2 == NULL)
return false;
if(root1->data == root2->data
    && sameTree(root1->left,root2->left)
       && sameTree(root1->right, root2->right))
return true;
}

أشجار البحث الثنائية Binary Search Trees

الأشجار الثنائية هي الأشجار التي يتفرّع عن كلّ عقدة منها ابنان على الأكثر، وشجرة البحث الثنائية Binary search tree أو BST اختصارًا هي شجرة ثنائية عناصرها مُرتّبة ترتيبًا خاصًا، إذ تكون جميع القيم الموجودة في الشجيرة أو الفرع sub tree الأيسر أصغر من القيم في الشجَيرة اليمنى.

إدراج عنصر في شجرة بحث ثنائية Python

رسم يوضح كيفية إدراج عنصر في الشجرة

هذا تنفيذ بسيط لكيفية إدراج عنصر في شجرة بحث ثنائية مكتوب بلغة Python.

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def insert(root, node):
 if root is None:
        root = node
 else:
 if root.data > node.data:
 if root.l_child is None:
                root.l_child = node
 else:
                insert(root.l_child, node)
 else:
 if root.r_child is None:
                root.r_child = node
 else:
                insert(root.r_child, node)

def in_order_print(root):
 if not root:
 return
    in_order_print(root.l_child)
    print root.data
    in_order_print(root.r_child)

def pre_order_print(root):
 if not root:
 return 
    print root.data
    pre_order_print(root.l_child)
    pre_order_print(root.r_child) 

حذف عنصر من شجرة بحث ثنائية C++‎

قبل أن نبدأ، نريد أن التذكير بمفهوم شجرة البحث الثنائية BST، وهي التي يتفرّع عن كل عقدة منها عقدتان كحد أقصى (ابن أيمن وأيسر)، حيث تحتوي الشجيرة اليسرى المتفرّعة عن عقدة ما على مفتاح قيمته أصغر من أو تساوي مفتاحَ العقدة الأصلية. وتحتوي الشجيرة اليمنى للعقدة على مفتاح أكبر من مفتاح العقدة الأصلية.

سنناقش في هذه الفقرة كيفية حذف عقدة من شجرة بحث ثنائية مع الحفاظ على الخاصية أعلاه.

هناك ثلاث حالات يجب مراعاتها عند حذف العقدة، هي الآتية:

• الحالة 1: العقدة المراد حذفها هي ورقة أو عقدة طرفية leaf node، مثل العقدة ذات القيمة 22.
• الحالة 2: العقدة المراد حذفها لها ابن واحد، مثل العقدة ذات القيمة 26.
• الحالة 3: العقدة المراد حذفها لها ابنان، مثل العقدة ذات القيمة 49.

شرح الحالات

• عندما تكون العقدة المراد حذفها ورقةً، فما عليك سوى حذف العقدة وتعيين المؤشر الفارغ ‎nullptr‎ إلى العقدة الأصلية.
• عندما تحتوي العقدة المراد حذفها على ابن واحد فقط، انسخ قيمة الابن إلى قيمة العقدة ثمّ احذف الابن (ستُحوّل إلى الحالة 1).
• عندما يكون للعقدة المراد حذفها ابنان، فيمكن نسخ القيمة الأصغر من شجيرتها اليمنى إلى العقدة، بعدها يمكن حذف القيمة الدنيا من الشجيرة اليمنى للعقدة، حيث ستُحوَّل إلى الحالة 2.

اقتباس

ملاحظة: يمكن أن يحتوي الحد الأدنى في الشجيرة اليمنى على ابن واحد على الأكثر، والذي سيكون الابن الأيمن، إذ أنّه في حال كان لها ابن آخر أيسر، فذلك يعني أنّها ليست القيمة الأدنى أو لا تستوفي خاصية أشجار البحث الثنائية BST.

انظر المثال التالي على حذف عنصر من شجرة بحث ثنائية:

struct node
{
   int data;
   node *left, *right;
};
node* delete_node(node *root, int data)
{
 if(root == nullptr) return root;
 else if(data < root->data) root->left  = delete_node(root->left, data);
 else if(data > root->data) root->right = delete_node(root->right, data);
 else
 {
   if(root->left == nullptr && root->right == nullptr) // الحالة 1
   {
     free(root);
     root = nullptr;
   }
   else if(root->left == nullptr)       // الحالة 2
   {
      node* temp = root;
      root= root->right;
      free(temp);
   }
   else if(root->right == nullptr)      // الحالة 2
   {
      node* temp = root;
      root = root->left;
      free(temp);
   }
   else                                 // الحالة 3
   {
      node* temp = root->right;
      while(temp->left != nullptr) temp = temp->left;
      root->data = temp->data;
      root->right = delete_node(root->right, temp->data);
   }
 }
 return root;
}

التعقيد الزمني للشيفرة أعلاه هو O(h)‎‎، حيث تمثّل h ارتفاع الشجرة.

أدنى سلف مشترك في شجرة بحث ثنائية

انظر شجرة البحث الثنائية التالية:

• أدنى سلف مشترك Lowest common ancestor لـ 22 و26 هو 24.
• أدنى سلف مشترك لـ 26 و49 هو 46.
• أدنى سلف مشترك لـ 22 و24 هو 24.

تُستغل الخاصية المميّزة لأشجار البحث الثنائية للعثور على السلف الأدنى للعقد، فيما يلي شيفرة عامة للعثور على السلف المشترك الأدنى:

lowestCommonAncestor(root,node1, node2){
if(root == NULL)   
return NULL;
else if(node1->data == root->data || node2->data== root->data)   
   return root;

   else if((node1->data <= root->data && node2->data > root->data)
             || (node2->data <= root->data && node1->data > root->data)){

            return root;
   }

   else if(root->data > max(node1->data,node2->data)){
           return lowestCommonAncestor(root->left, node1, node2);
   }

       else {
           return lowestCommonAncestor(root->right, node1, node2);
     }
       }

شجرة البحث الثنائية Python

انظر إلى شيفرة البايثون التالية:

class Node(object):
   def __init__(self, val):
       self.l_child = None
       self.r_child = None
       self.val = val
class BinarySearchTree(object):
   def insert(self, root, node):
if root is None:
           return node
       if root.val < node.val:
           root.r_child = self.insert(root.r_child, node)
       else:
           root.l_child = self.insert(root.l_child, node)
       return root
   def in_order_place(self, root):
       if not root:
           return None
       else:
           self.in_order_place(root.l_child)
           print root.val
           self.in_order_place(root.r_child)
   def pre_order_place(self, root):
       if not root:
           return None
       else:
           print root.val
           self.pre_order_place(root.l_child)
           self.pre_order_place(root.r_child)
   def post_order_place(self, root):
       if not root:
           return None
       else:
           self.post_order_place(root.l_child)
           self.post_order_place(root.r_child)
           print root.val

هذه شيفرة لإنشاء عقدة جديدة وإدراج البيانات فيها:

r = Node(3)
node = BinarySearchTree()
nodeList = [1, 8, 5, 12, 14, 6, 15, 7, 16, 8]
for nd in nodeList:
    node.insert(r, Node(nd))
print "------In order ---------"
print (node.in_order_place(r))
print "------Pre order ---------"
print (node.pre_order_place(r))
print "------Post order ---------"
print (node.post_order_place(r))

التحقق مما إذا كانت الشجرة شجرة بحث ثنائية أم لا

تكون شجرةٌ ثنائيةٌ ما "شجرةَ بحث ثنائية" إذا كانت تستوفي أيًّا من الشروط التالية:

• إن كانت فارغة.
• لا تتفرع منها أيّ شجيرات.
• لكلّ عقدة x في الشجرة، يجب أن تكون جميع المفاتيح (إن وجدت) في الشجيرة اليسرى أصغر من مفتاح x، أي ‏key(x)‎‎، ويتعيّن أن تكون جميع المفاتيح (إذا وجدت) في الشجيرة اليمنى أكبر من key(x)‎‎.

الخوارزمية التكرارية التالية تتحقق من الشروط أعلاه:

is_BST(root):
 if root == NULL:
  return true

تحقق من القيم في الشجيرة اليسرى:

 if root->left != NULL:
   max_key_in_left = find_max_key(root->left)
   if max_key_in_left > root->key:
       return false

تحقق من القيم في الشجيرة اليمنى:

 if root->right != NULL:
   min_key_in_right = find_min_key(root->right)
   if min_key_in_right < root->key:
       return false
 return is_BST(root->left) && is_BST(root->right)

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

سنستخدم هذه الفكرة لتطوير خوازمية أكثر فعالية.

ولفعل هذا، نرمز للقيمة الدنيا الممكنة لأيّ مفتاح ‎K_MIN‎، والقيمة القصوى بالرمز K_MAX. فإن بدأتَ من جذر الشجرة يكون نطاق قيم الشجرة هو ‎[ K_MIN ،K_MAX‎]‎. وإذا كان x‎ هو مفتاح عقدة الجذر فسيكون نطاق القيم في الشجيرة اليسرى هو ‎[K_MIN,x)‎، ونطاق القيم في الشجيرة اليمنى هو (x,K_MAX].

s_BST(root, min, max):
   if root == NULL:
       return true
   // هل مفتاح العقدة الحالية خارج النطاق؟
   if root->key < min || root->key > max:
       return false
   // التحقق مما إذا كانت الشجيرتان اليسرى واليمنى أشجارَ بحث ثنائية
   return is_BST(root->left,min,root->key-1) && is_BST(root->right,root->key+1,max)

وستُستَدعى في البداية على النحو التالي:

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

هناك منظور آخر لحل الأمر، وهو الاجتياز المُرتّب inorder traversal للشجرة الثنائية -انظر أدناه-، فإذا نتج عن ذلك الاجتياز المُرتب تسلسلٌ مرتّب من المفاتيح، فستكون الشجرة شجرة بحث ثنائية. وللتحقق ممّا إذا كان التسلسل الناتج مُرتّبًا أم لا، فعليك تخزين قيمة العقدة المُزارة سابقًا، ثمّ موازنتها بالعقدة الحالية.

النظر في ما إن كانت شجرة ما تحقق شرط أشجار البحث الثنائية

انظر المثال التالي: إن كانت المدخلات كما يلي:

فإن الخرج سيكون خاطئًا false، وعليه لا تكون هذه شجرة بحث ثنائية، ذلك أنّ 4 في الشجيرة اليسرى أكبر من قيمة الجذر 3. انظر الآن مثالًا على شجرة أخرى:

النتيجة ستكون صحيحة وتكون شجرة بحث ثنائية.

اجتيازات الأشجار الثنائية Binary Tree traversals

زيارة عقدة لشجرة ثنائية بترتيب معيّن يُسمّى اجتيازَا أو عبورًا traversal، وهناك عدة أنواع من الاجتياز سنستعرض في هذه الفقرة بعضها.

الاجتياز بالمستويات: التطبيق

انظر الشجرة التالية:

يكون الاجتياز بالمستويات على الترتيب التالي:

‪‎1‎‎‎‎‪ 2 3 4 5 6 7‪ ‎

مع طبع بيانات العُقَد مستوىً بمستوى، انظر:

include<iostream>
#include<queue>
#include<malloc.h>
using namespace std;
struct node{

   int data;
   node *left;
   node *right;
};
void levelOrder(struct node *root){

       if(root == NULL)    return;

       queue<node *> Q;
       Q.push(root);

       while(!Q.empty()){
       struct    node* curr = Q.front();
           cout<< curr->data <<" ";
           if(curr->left != NULL) Q.push(curr-> left);
               if(curr->right != NULL) Q.push(curr-> right);

               Q.pop();


       }
}
struct node* newNode(int data)
{
   struct node* node = (struct node*)
                       malloc(sizeof(struct node));
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return(node);
}
int main(){

   struct node *root = newNode(1);
   root->left        = newNode(2);
   root->right       = newNode(3);
   root->left->left  = newNode(4);
   root->left->right = newNode(5);
   root->right->left  = newNode(6);
   root->right->right = newNode(7);
   printf("Level Order traversal of binary tree is \n");
   levelOrder(root);

   return 0;

}

تُستخدم الصفوف Queues -وهو نوع من البيانات- لتحقيق الهدف أعلاه.

الاجتياز التنازلي والتصاعدي والمرتب

انظر الشجرة الثنائية التالية:

• الاجتياز التنازلي Pre-order traversal: يبدأ هذا النوع باجتياز العقدة، ثم الشجيرة اليسرى للعقدة، ثمّ الشجيرة اليمنى لها. ويكون الاجتياز التنازلي بالترتيب التالي:

1 2 4 5 3 6 7

• الاجتياز المُرتّب In-order traversal: هو اجتياز الشجيرة اليسرى للعقدة، ثمّ العقدة نفسها، ثم الشجيرة اليمنى للعقدة. يكون الاجتياز المُرتّب بالترتيب التالي:

 4 2 5 1 6 3 7  

• الاجتياز التصاعدي Post-order traversal: هو اجتياز الشجيرة اليسرى للعقدة، ثم الشجيرة اليمنى، ثمّ العقدة، ويكون الاجتياز التصاعدي بالترتيب التالي:

 4 5 2 6 7 3 1

العثور على أدنَى سلف مشترك لشجرة ثنائية

السلف المشترك الأدنى للعقدتين n1 وn2 هو أدنى عقدة في الشجرة يكون كلّ من n1 وn2 أحفادًا لها. انظر الشجرة التالية:

• أدنى سلف مشترك للعقدتين ذواتي القيمتين 1 و4 هو 2.
• أدنى سلف مشترك للعقدتين ذواتي القيمتين 1 و5 هو 3.
• أدنى سلف مشترك للعقدتين ذواتي القيمتين 2 و4 هو 4.
• أدنى سلف مشترك للعقدتين ذواتي القيمتين 1 و2 هو 2.

ترجمة -بتصرّف- للفصول من 4 إلى 8 من كتاب Algorithms Notes for Professionals

اقرأ أيضًا

• المقالة السابقة: ترميز Big-O
• المرجع الشامل إلى: تعلم الخوارزميات للمبتدئين
• تعقيد الخوارزميات Algorithms Complexity
• مدخل إلى الخوارزميات
• دليل شامل عن تحليل تعقيد الخوارزمية
• النسخة الكاملة من كتاب مدخل إلى الذكاء الاصطناعي وتعلم الآلة

ترميز Big-O هو ترميز رياضي في الأساس يُستخدم لموازنة معدّلات تقارب الدوال، وسنستعرض في هذا المقال استخدامات هذا الترميز في تحليل الخوارزميات وتصنيفها كما يلي.

إذا كانت ‎n -> f(n)‎ وn -> g(n)‎ دالتين مُعرّفتين على الأعداد الطبيعية، فسنقول أنّ ‎f = O(g)‎ فقط إذا كانت ‎f(n)/g(n)‎ محصورة bounded عندما يؤول n إلى اللا نهاية. أي أن ‎f = O(g)‎ فقط إذا كان هناك ثابت A، بحيث يكون
 

‎f(n)/g(n) <= A‎

لكل n.

وفي الواقع فإن نطاق استخدام ترميز Big-O أوسع قليلاً في الرياضيات، لكن سنضيّقه في النطاق المُستخدَم في تحليل الخوارزميات للتبسيط، أي الدوال المُعرَّفة على الأعداد الطبيعية والتي ليست لها قيم صفرية أو جذور zero values عندما يؤول n إلى اللانهاية.

شرح

لنأخذ حالة هاتين الدالتين:
 

‎f(n) = 100n^2 + 10n + 1‎ 7

والدالة
 

‎g(n) = n^2‎

من الواضح تمامًا أنهما تؤولان إلى اللانهاية عندما يؤول n إلى اللانهاية. لكن قد لا يكفي أحيانًا أن نعرف النهاية limit، فقد نرغب أيضًا في معرفة السرعة التي تقترب بها الدوال من نهايتها، وهنا يأتي دور ترميز Big-O إذ يساعد على تصنيف الدوال بحسَب سرعة تقاربها.

فعندئذ نطبّق التعريف للتحقق ممّا إذا كانت ‎f = O(g)‎ حيث لدينا:

 ‎f(n)/g(n) = 100 + 10/n + 1/n^2‎

 وبما أن ‎10/n‎ يساوي القيمة 10 عندما يكون n=1 ويتناقص مع تزايد قيمة n، وبما أنّ ‎1/n^2‎ تساوي 1 عندما يساوي n القيمة 1 وهو أيضًا يتناقص مع تزايد قيمة n، فنحصل على المتراجحة

 f(n)/g(n) <= 100 +10 + 1 = 111

وقد تحقّق شرط التعريف هنا لأنّنا وجدنا حدًّا bound للتعبير
 

‎f(n)/g(n)‎‎ -

وهو 111-، ونكون بهذا قد أثبتنا أنّ‎f = O(g)‎‎، ونقول أنّ f هي Big-O لـ ‎n^2‎.

هذا يعني أنّ f تؤول إلى اللانهاية بنفس سرعة g تقريبًا. قد يبدو هذا غريبًا في البداية لأنّنا وجدنا أنّ f أكبر بـ 111 مرة من g، أو بعبارة أخرى، عندما تنمو g بمقدار 1، فإن f تنمو بمقدار 111 على أقصى حد. والحقيقة أنّ ترميز Big-O ليس دقيقًا في تصنيف سرعات تقارب الدوال، لهذا نَستخدم علاقة التكافؤ equivalence relationship في الرياضيات عندما نريد تقديرًا دقيقًا للسرعة.

لكن إن أردت تصنيف الخوارزميات إلى أصناف عامّة بحسب السرعات، فإنّ Big-O كافية، إذ لن نحتاج إلى التمييز بين دالتين تنمو إحداهما أسرع من الأخرى بعدد محدد من المرات، بل المهم هو التمييز بين الدوال التي تنمو لانهائيًا أسرع من بعضها البعض.

على سبيل المثال، في حالة
 

‎h(n) = n^2*log(n)‎

 نلاحظ أنّ ‎h(n)/g(n) = log(n)‎ تؤول إلى ما لانهاية عندما يؤول n إلى ما لا نهاية، لذا فإنّ h ليست من الصنف O (n ^ 2)‎‎، لأنّ h تنمو لانهائيًا أسرع من n ^ 2.

اقتباس

ملاحظة جانبية: إذا كانت ‎f = O(g)‎ و ‎g = O(h)‎؛ فسيكون ‎f = O(h)‎، فمثلًا في حالتنا هذه سيكون لدينا ‎f = O(n^3)‎ و ‎f = O(n^4)‎ …

وفي مجال تحليل تعقيد الخوارزميات، نكتب ‎f =‎ O(g)‎ للدلالة على أنّ:

f = O(g)‎‎ و ‎g = O(f)‎

 والتي يمكن تأويلها على أنّ g هي أصغر دالة من الصنف Big-O لــ f؛ أما في الرياضيات فنقول أنّ هاتين الدالتين Big-Theta لبعضها البعض.

كيفية الاستخدام

أول شيء عليك حسابه عند موازنة أداء الخوارزميات هو عدد العمليات التي تجريها الخوارزمية، وهو ما يُسمّى وقت التعقيد time complexity.

ونفترض في هذا النموذج أنّ كل عملية أساسية (الجمع والضرب والمقارنة والتعيين وما إلى ذلك) تستغرق مقدارًا ثابتًا من الوقت، ونحسب عدد هذه العمليات. ونعبر في الغالب عن هذا العدد كدالة لحجم الدخل -الذي نصطلح على تسميته n-، ويؤول هذا العدد (الدالة) في الغالب إلى ما لا نهاية عندما يؤول n إلى ما لا نهاية، أما خلاف ذلك، فنقول أنّ الخوارزمية من النوع O (1)‎‎.

ونحن نصنّف الخوارزميات إلى أصناف بحسب سرعات الدوال ونمثّلها بالترميز Big-O: فمثلًا إن قلنا أنّ خوارزميةً ما من النوع الآتي:

 O (n ^ 2)‎‎

 فإنّنا نقصد أنّ عدد العمليات التي تنفّذها الخوارزمية -معبَّرًا عنها كدالة لـ n- هو O (n ^ 2)‎‎. وهو ما يعني أنّ سرعة الخوارزمية تقارب سرعة خوارزمية تجري عددًا من العمليات يساوي مرّبع حجم الدخل أو أسرع. لاحظ لفظة أو أسرع، لقد وضعناها لأنّنا استخدمنا Big-O بدلاً عن Big-Theta، ذلك أنّه من الشائع أن ترى الناس تكتب Big-O، رغم أنّهم يعنون Big-Theta.

ونحن نأخذ الحالة الأسوأ في حسابنا عادة عند عدّ العمليات، فإن كانت حلقة تكرارية تُنفَّذ n مرّةً على الأكثر وكانت تحتوي على 5 عمليات، فإنّ عدد العمليات المُقدَّر سيكون 5n. كذلك من الممكن مراعاة متوسط تعقيد الحالة.

اقتباس

ملاحظة سريعة: الخوارزمية السريعة هي تلك التي تنفذ عمليات قليلة، فكلما اقترب عدد العمليات المُنفّذة إلى اللانهاية بسرعة أكبر كانت الخوارزمية أبطأ، مثلًا: O (n)‎‎ أسرع من O (n ^ 2)‎‎ لأنّ الدالة n تؤول إلى اللانهاية أبطأ من n^2.

يمكن أن نأخذ مساحة التخزين بالحسبان كذلك، وهو ما يُسمّى تعقيد المساحة space complexity للخوارزمية، ذلك أن الوقت ليس المورد الوحيد المهم، وفي هذه الحالة نحسُب عدد البايتات التي تشغلها الخوارزمية في الذاكرة كدالة لحجم الدخل، ونستخدم Big-O كما في حالة تعقيد الوقت.

مثال عن حلقة بسيطة Simple Loop

الدالة التالية تبحث عن أكبر عنصر في المصفوفة:

int find_max(const int *array, size_t len) {
   int max = INT_MIN;
     for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

حجم الدخل هو حجم المصفوفة، والذي سمّيناه ‎len‎ في الشيفرة أعلاه. دعنا الآن نَعُد العمليات.

int max = INT_MIN;
size_t i = 0;

تُنفَّذ هاتان العمليتان مرةً واحدة، لذا فلدينا عمليتان هنا. والآن نعدّ عمليات الحلقة:

if (max < array[i])
i++;
max = array[i]

لمّا كانت هناك 3 عمليات في الحلقة، وكانت الحلقة تُنفَّذ n مرة، فسنضيف ‎3n‎ إلى 2 (العمليتان اللتان حسبناهما من قبل)، ليبلغ الإجمالي ‎3n + 2‎.

تجري دالتنا إذن عددًا من العمليات مقداره ‎3n + 2‎ عملية للعثور على أكبر عنصر في المصفوفة (تعقيدها يساوي ‎3n + 2‎). وهذا يعرف بتعددية الحدود polynomial، وأسرع عواملها نموّا هو العامل n، لذا يساوي تعقيدها O (n)‎‎.

لعلّك لاحظت أنّ طريقة عدّ العمليات ليست دقيقة، فقد قلنا مثلًا أنّ  (max < array)‎ هي عملية واحدة، ولكن اعتمادًا على هندسة الحاسوب فقد تنطوي هذه العبارة على تعليمتين مثلاً، الأولى لقراءة الذاكرة والثانية للمقارنة. وقد اعتبرنا كذلك أنّ جميع العمليات متشابهة رغم أنّ العمليات التي تخصّ الذاكرة على سبيل المثال تكون أبطأ من العمليات الأخرى، كما يختلف أداؤها اختلافًا كبيرًا بسبب تأثيرات التخزين المؤقت cache.

كذلك تجاهلنا أيضًا تعليمة الإعادة return وحقيقةَ إنشاء إطار frame خاص بالدالة، وما إلى ذلك من الأمور الجانبية. لكنّ هذا لن يؤثّر في النهاية على تحليل التعقيد، ذلك أنّه مهما كانت طريقة عدّ العمليات، فلن يؤثّر إلا على معامل العامل n وكذلك لن يؤثر على الثابت، لذا ستظل النتيجة O (n)‎‎. ويُظهر التعقيد كيف تتطوّر الخوارزمية مع تطوّر حجم الدخل، بيْد أنّها ليست الجانب الوحيد الذي يمثّل الأداء.

مثال عن الحلقات المتشعبة Nested Loops

تتحقق الدالة التالية ممّا إذا كانت المصفوفة تحتوي أيّ تكرارات، وذلك عبر المرور على كل عنصر على حدة، ثم المرور مجدّدا على المصفوفة للتحقّق ممّا إذا كان هناك عنصر آخر يساويه.

_Bool contains_duplicates(const int *array, size_t len) {
   for (int i = 0; i < len - 1; i++) {
       for (int j = 0; j < len; j++) {
           if (i != j && array[i] == array[j]) {
               return 1;
           }
       }
   }
   return 0;
}

تنفّذ الحلقة الداخلية عند كل تكرار عددًا ثابتًا من العمليات (بغضّ النظر عن قيمة ‎n‎)، كما تنفّذ الحلقة الخارجية أيضًا بعض العمليات الثابتة علاوة على تنفيذ الحلقة الداخلية عدد ‎n‎ مرّة.

أيضًا، تنفَّذ الحلقةُ الخارجية نفسها ‎n‎ مرّة، وعليه تُنفّذ العمليات داخل الحلقة الداخلية ‎n^2‎ مرّة بينما تُنفّذ عمليات الحلقة الخارجية ‎n‎ مرّة، أمّا عملية التعيين إلى ‎i‎ فتُتفّذ مرّة واحدة. وهكذا يمكن التعبير عن التعقيد بمعادلة مثل ‎an^2 + bn + c‎، ولمّا كان المعامل الأعلى هو ‎n^2‎، فإنّ ترميز O سيساوي ‎O(n^2)‎.

لعلك لاحظت أن هناك فرصة لتحسين الخوارزمية أكثر، إذ يمكن مثلًا تجنّب إجراء نفس المقارنات أكثرة من مرّة. يمكننا أن نبدأ من ‎i + 1‎ في الحلقة الداخلية نظرًا لأنّ جميع العناصر التي تسبقه قد تم التحقق منها سلفًا وقورنت مع جميع عناصر المصفوفة، بما في ذلك العنصر الموجود عند الفهرس ‎i + 1‎. هذا يسمح لنا بحذف الاختبار ‎i == j‎.

_Bool faster_contains_duplicates(const int *array, size_t len) {
   for (int i = 0; i < len - 1; i++) {
       for (int j = i + 1; j < len; j++) {
           if (array[i] == array[j]) {
               return 1;
           }
       }
   }
   return 0;
}

كما ترى فإنّ هذا الإصدار أفضل لأنّه يُجري عمليات أقل، لكن كيف نترجم هذا في ترميز Big-O؟ حسنًا، في الإصدار الجديد، يُنفّذ مَتن الحلقة الداخلية المرات

 ‎1 + 2 + ... + n - 1 = n(n-1)/2‎

لا يزال هذا التعبير كثير الحدود من الدرجة الثانية، لذا سيظلّ التعقيد مساويا لـ ‎O(n^2)‎.

وقد قلّلنا التعقيد إذ خفّضنا عدد العمليات إلى النصف تقريبًا، بيْد أنّنا ما زلنا في نفس صنف التعقيد من Big-O. ونحتاج إلى تقسيم عدد العمليات على مقدار يؤول إلى اللا نهاية مع ‎n‎ من أجل تقليل التعقيد إلى صنف أدنى.

الخوارزميات اللوغاريتمية‎‎‎‎

لنفترض أنّ لدينا مشكلة ذات حجم n، ولنفترض أنّ حجم مشكلتنا الأصلية ينخفض إلى النصف (n / 2) بعد كل خطوة من خطوات الخوارزمية. أي أنّه في كل خطوة جديدة يصير حجم المشكلة نصف ما كانت عليه في الخطوة التي قبلها:

تكون المشكلة محلولة حين يتعذر تقليل حجمها أكثر بعد الخروج من شرط التحقق، أي عندما تكون n مساوية للقيمة 1.

لنفترض الآن أنّ حجم المشكلة يساوي n، نريد أن نحسب عدد الخطوات اللازمة لحل الخوارزمية، سنرمز لهذا العدد بالحرف k:

1. عند الخطوة k، سيساوي حجم المشكلة 1 (أي أنّ المشكلة ستكون قد حُلَّت).
2. من جهة أخرى، نعلم أنّه عند الخطوة k، ينبغي أن يساوي حجم المشكلة العدد (n/2^k).
3. من 1، 2، إذًا n = 2k.
4. طبّق دالة اللوغاريتم على كلا الجانبين:

log n = k * loge_2  →   k = loge n / loge 2

5. باستخدام المعادلة التالية:

logx (m) / logx (n) = logn (m)‎

حيث يرمز التعبير logt‎‎ إلى اللوغاريتم ذي الأساس t، وتصبح النتيجة k = log2 (n)‎‎ أو k = log n ببساطة.

اقتباس

نعلم الآن أنّ خوارزميتنا يمكن أن تُنفّذ log n على أقصى حدّ، وعليه يساوي تعقيد الوقت O (log n)‎‎

انظر المثال التوضيحي التالي:

for(int i=1; i<=n; i=i*2)
{
 // إجراء بعض العمليات
}

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

سنرمز للعدد الذي نبحث عنه بالرمز k، ونحسبه على النحو الآتي:

• k = log2 (256)‎‎.
• k = log2 (2^8)‎‎ ( نعلم أنّ log(a^a) = 1‎ لكل عدد a‎).
• k = 8.

هذا مثال آخر لتوضيح هذا النوع من الخوارزميات. وهي خوارزمية البحث الثنائي Binary Search Algorithm.

int bSearch(int arr[],int size,int item){
int low=0;
int high=size-1;
while(low<=high){               
    mid=low+(high-low)/2;               
    if(arr[mid]==item)                       
        return mid;               
    else if(arr[mid]<item)                       
        low=mid+1;               
    else  high=mid-1;     
    } 
 return –1;// لا يوجد
}

مثال على خوارزمية من الصنف O (log n)‎‎

انظر المشكلة التالية:

L قائمة مرتّبة تحتوي n عددًا صحيحًا نسبيًا (n كبيرة جدا)، على سبيل المثال ‎[-5, -2, -1, 0، 1، 2، 4]‎‎ (هنا، n تساوي 7). إذا كانت ‎L‎ تحتوي العدد الصحيح 0، فكيف يمكنك العثور على فهرس 0؟

المقاربة البسيطة

أول ما يتبادر إلى الذهن هو قراءة كل فهرس إلى حين العثور على 0، وفي أسوأ الحالات سيكون علينا إجراء ‎n‎ عملية، وعليه فإنّ التعقيد سيساوي O (n)‎‎.

لا مشكلة في هذا مع القيم الصغيرة لـ ‎n‎، ولكن هل هناك طريقة أفضل؟

مبدأ الحصار Dichotomy

انظر الخوارزمية التالية Python3:

a = 0
b = n-1
while True:
 h = (a+b) // (*)
 if L[h] == 0:
   return h
 elif L[h] > 0:
   b = h
 elif L[h] < 0:
   a = h

اقتباس

(*) تمثل // عملية القسمة الصحيحة integer division، لذا ستكون h عددًا صحيحًا. يحصركل من a و b فهرس العدد 0، فلا بدّ لفهرس 0 أن يكون محصورًا بينهما، وكل مرة ندخل إلى الحلقة، نختار فهرسًا بين aو‎b‎ ونستخدمه لتضييق المنطقة المراد البحث عنها.

وفي أسوأ الحالات، علينا الانتظار حتى يتساوى ‎a‎ و‎b‎، لكن كم عدد العمليات التي يتطلبها ذلك؟ قطعًا ليس n لأننا نقسم المسافة بين ‎a‎ و‎b‎ على 2 في كل مرة ندخل إلى الحلقة، لذا فالتعقيد يساوي O (log n)‎‎.

اقتباس

تنبيه: حين نكتب log فإننا نشير إلى اللوغاريتم الثنائي binary logarithm أو اللوغاريتم ذي الأساس 2، والذي يُكتب عادةً log_2 أو log2، لذا فإنّ O (log_2 n)‎‎ و O (log)‎‎ متكافئتان.

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

ترجمة -بتصرّف- للفصل الثالث من كتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• المقالة السابقة: تعقيد الخوارزميات
• مدخل إلى الخوارزميات
• دليل شامل عن تحليل تعقيد الخوارزمية
• مدخل إلى الذكاء الاصطناعي وتعلم الآلة

تستعرض هذه المقالة مفهوم التعقيد Complexity، وهو أحد المفاهيم الأساسية في علم الخوارزميات، مع ذكر بعض أهم أصناف التعقيد وبعض الترميزات المستخدمة في ذلك.

ترميز Big-Omega

تُستخدم ترميز Ω -notation لتمثيل المقارِب الأدنى asymptotic lower bound.

التعريف الرسمي

لتكن ‎fn)‎ و ‎g(n)‎ دالتين مُعرّفتين على مجموعة الأعداد الحقيقية الموجبة، فنقول أنّ ‎f(n) = Ω(g(n))‎ في حال وُجِدت ثابتان موجبان ‎c‎ و ‎n0‎ يحققان الآتي لكل n أكبر من أو تساوي n0:

 0 ≤ c g(n) ≤ f(n)‎‎

اقتباس

ملاحظة: المعادلة f(n) = Ω(g(n))‎ تعني أنّ f(‎n‎)‎ لا يمكن أن تنمو تقاربيًا asymptotically بشكل أبطأ من ‎g(n)‎، كذلك يمكن كتابة ‎Ω(‎ g(‎ n ‎))‎ عندما لا يؤكّد تحليل الخوارزمية أنّ ‎Θ(g(n))‎ أو / ‎O(g(n))‎.

نظرية

بالنسبة لدالتين ‎f(n)‎ و ‎g(n)‎، نقول أنّ ‎f(n) = Ө(g(n))‎ فقط إذا كان الآتي محققًا:

• f(n) = O(g(n))‎‎.
• f(n) = Ω(g(n))‎.

يمكن تمثيل ترميز ‎Ω‎ بيانيًا على النحو التالي:

على سبيل المثال، إذا كانت ‎
 

f(n) = 3n^2 + 5n - 4‎

فستكون ‎f(n) = Ω(n^2)‎، كما ستكون ‎f(n) = Ω(n)‎ أو حتى ‎‎f(n) = Ω(1)‎‎‎‎ صحيحة.

لدينا مثال آخر يحل خوارزمية التطابق التام matching algorithm، حيث إذا كان عدد الرؤوس vertices فرديًا، فسنحصل على الخرج "No Matching Matching"، وإلا فينبغي تجربة جميع التطابقات الممكنة.

وكنا نودّ القول أنّ الخوارزمية تتطلب وقتًا أسيًا exponential time، لكن الواقع أنه لا يمكنك إثبات وجود حدّ أدنى ‎Ω(n^2)‎ باستخدام التعريف المعتاد لـ ‎Ω‎ نظرًا لأنّ الخوارزمية تُجرى في وقت خطي linear time لقيم n الفردية.

وبدلًا من هذا فيجب علينا تعريف ‎f(n)=Ω(g(n))‎ على نحو أنه بالنسبة لثابت ‎‎c قيمته أكبر من الصفر، فهناك عدد لا نهائي من قيم ‎n‎ التي تحقّق الآتي:

‎f(n)≥ c g(n)

‎

يوفّق هذا التعريف بين الحدّين الأعلى والأدنى إذ يحقّق التكافؤ الآتي:
 

‎f(n)=Ω(g(n))‎

فقط إن كان

‎f(n) != o(g(n))‎

ترميز Big-Theta

على خلاف ترميز Big-O الذي يمثل الحد الأعلى upper bound فقط من وقت تشغيل الخوارزميات، فإنّ ترميز Big-Theta هو رابط محصور Tight bound يشمل الحدّ العلوي والسفلي معًا، وهو أكثر دقة لكنه صعب الحساب.

وترميز Big-Theta متماثلة، أي تحقق المعادلة:
 

‎f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))‎

 ولتفهم ذلك بسهولة، اعلم أن المعادلة الآتية
 

‎f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))f(x) = Ө(g(x))‎

تعني أنّ الرسمين البيانيين للدالتين f و g ينمُوان بنفس المعدّل، أو أنّ الرسمين البيانيين "يتصرّفان" بشكل متماثل عند قيم x الكبيرة.

والتعبير الرياضي الكامل لترميز Big-Theta هو كما يلي:

Ө(f(x)) = {g: N0 -> R and c1, c2, n0 > 0}

حيث تكون

c1 < abs(g(n) / f(n))‎‎

لكل n أكبر من n0، وتمثل abs القيمة المطلقة.

ﻣﺜــــﺎل

إذا كانت الخوارزمية تأخذ العدد الآتي عمليةً للانتهاء مقابل مُدخل ‎n‎، فنقول أنّ تعقيدها يساوي ‎O(n^2)‎ ، كما يساوي أيضًا ‎O(n^3)‎ وO(n^100)‎. 
 

‎42n^2 + 25n + 4‎

أمّا في حال ترميز Big-Theta، فنقول أنّ التعقيد يساوي ‎Ө(n^2)‎، لكن لا يساوي ‎Ө(n^3)‎ أو ‎Ө(n^4)‎، إلخ… . كذلك، فإن كانت الخوارزمية من نوع ‎Ө(f(n))‎، فستكون أيضًا من النوع ‎O(f(n))‎، ولكن ليس العكس.

التعريف الرياضي

تُعرّف Ө(g(x))‎‎ على أنها مجموعة من الدوال، أما تعريفها الرياضي الرسمي Formal mathematical definition فهو:

Ө(g(x))‎‎‏ = f(x)}

وإذا كانت هناك ثوابت موجبة N وc1 و c2، بحيث يكون

0‎‎ <= c1*g(x) <= f(x) <= c2g*(x)‎‎

 لكل x أكبر من N}.

وهذا يعني أنّ Ө(g(x))‎‎ هي مجموعةٌ تحتوي كلّ دالة f مُحاصَرة من قبل الدالة g، بمعنى أنّه توجد 3 ثوابت موجبة هي c1 و c2 وN، بحيث يكون لدينا: 0‎‎ <= c1*g(x) <= f(x) <= c2*g(x)‎‎ لكل عدد x أكبر من N.

وبما أن ‎Ө(g(x))‎ مجموعةً فيمكننا كتابة الآتي ‎‎ للإشارة إلى أنّ ‎f(x)‎ تنتمي إلى ‎Ө(g(x))‎. 

f(x) ∈ Ө(g(x))

غير أن الشائع هو كتابة الآتي للتعبير عن نفس الترميز:

 ‎f(x) = Ө(g(x))‎

ويمكن تفسير ‎Ө(g(x))‎ عندما تظهر في ترميز ما على أنّها كناية عن دالة مجهولة لا تهمّنا تسميتها، فمثلًا، المعادلة الآتية:

‎T(n) = T(n/2) + Ө(n)‎

 تكافئ
 

‎T(n) = T(n/2) + f(n)‎

 حيث تمثّل ‎f(n)‎ دالةً ما من المجموعة ‎Ө(n)‎ا

وإن كانت ‎f‎ و ‎g‎ دالتين مُعرَّفتين على نفس النطاق من مجموعة الأعداد الحقيقية real numbers، فإننا نكتب  الآتي:
 

‎f(x) = Ө(g(x))‎

عندما تؤول x إلى ما لا نهاية x->infinity، وذلك فقط في حالة وجود ثابتْين موجبيْن K و L وعدد حقيقي x0 يحققون
 

K|g(x)| <= f(x) <= L|g(x)|‎‎

لكل x أكبر من أو تساوي x0.

يكون التعريف مكافئًا للعبارة التالية:

f(x) = O(g(x))‎‎

والعبارة:

f(x) = Ω(g(x))‎‎ 

استخدام مفهوم النهايات limits

إذا كان لدينا
 

limit(x->infinity) f(x)/g(x) = c ∈ ( 0,∞)‎

 أي أنّ النهاية موجودة وموجبة، أي:
 

f(x) = Ө(g(x))

‎ وفيما يلي بعض أصناف التعقيد الشائعة:

موازنة الصيغ المقاربة asymptotic notations

لتكن ‎f(n)‎ و ‎g(n)‎ دالتين مُعرّفتين على مجموعة الأعداد الحقيقية الموجبة، ولتكن ‎c, c1, c2, n0‎ ثوابت حقيقية موجبة.

يوضّح الجدول التالي الفروق بين مختلف الصيغ:

الترميز	f(n) = O(g(n))	f(n) = Ω(g(n))	f(n) = Θ(g(n))	f(n) = o(g(n))	f(n) = ω(g(n))
التعريف الرسمي	∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ c g(n)	∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c g(n) ≤ f(n)	∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)	∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < c g(n)	∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c g(n) < f(n)
التشابه مع الموازنة بين عددين a وb	a ≤ b	a ≥ b	a = b	a < b	a > b
أمثلة	7n + 10 = O(n^2 + n - 9)	n^3 - 34 = Ω(10n^2 - 7n + 1)	1/2 n^2 - 7n = Θ(n^2)	5n^2 = o(n^3)	7n^2 = ω(n)
الرسوم البيانية

يمكن تمثيل الصيغ المُقارِبة بواسطة مخطّط فِن كما يلي:

ترجمة -بتصرّف- للفصل الثاني من كتاب Algorithms Notes for Professionals

اقرأ أيضًا

• المقالة السابقة: مدخل إلى الخوارزميات
• دليل شامل عن تحليل تعقيد الخوارزمية
• بناء مصنف بالاعتماد على طرق تعلم الآلة بلغة بايثون باستخدام مكتبة Scikit-Learn
• النسخة الكامة من كتاب مدخل إلى الذكاء الاصطناعي وتعلم الآلة

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

ما هي الخوارزميات Algorithms

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

فهناك خوارزميات تستخدم في مجال الرياضيات مثل خوارزمية خوارزمية إقليدس Euclidean algorithm وخوارزمية غربال إراتوستينس Sieve of Eratosthenes و خوارزميات تستخدم في مجال البرمجة وعلوم الحاسوب مثل خوارزميات الترتيب Sorting algorithms التي تساعدك على ترتيب مجموعة من العناصر وفق ترتيب تصاعدي، ويفيدنا الترتيب في حل الكثير من المشكلات الحاسوبية بسهولة أكبر على سبيل المثال البحث عن اسم ما في سلسلة عناصر مرتبة وفق التسلسل الأبجدي أسرع وأسهل من البحث في سلسلة عناصر غير مرتبة لذا من الأفضل أن ترتب العناصر قبل البحث فيها.

كما تستخدم الخوارزميات كذلك في حياتنا اليومية في العديد من المواقف، على سبيل المثال لكل منا طريقة أو خوارزمية يعد من خلالها كوب القهوة الصباحي يوميًا بنفس الطريقة، بالنسبة لي أتبع الخطوات التالية:

• املأ الركوة أو دلة القهوة بالماء.
• سخّن الماء.
• انتظر حتى يغلي الماء.
• أضف القهوة وحركها.
• اسكب القهوة في الكوب.

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

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

خصائص الخوارزميات

يجب أن تتسم الخوارزمية بمجموعة من المواصفات أو الخصائص الأساسية، وتساعدك معرفة هذه الخصائص على تصميم الخوارزمية بشكل صحيح، ومن أهم هذه الخصائص:

• يجب أن تتكون الخوارزمية من تعليمات محددة وواضحة ومفهومة وقابلة للتنفيذ.

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

• يمكن أن لا تحتوي الخوارزمية على مدخلات أو قد تتضمن عدة مدخلات.

• يجب أن تحتوي الخوارزمية على خرج واحد أو أكثر وينبغي أن تؤدي نفس المدخلات دائمًا إلى نفس النتائج أو المخرجات.

• يجب أن تجد الخوارزمية حلاً للمشكلة المطلوبة بعد عدد منتهي من الخطوات وتنجز خلال فترة زمنية محددة لتكون فعالة وذات جدوى.

طرق تمثيل الخوارزمية

يمكن تمثيل الخوارزمية بطرق مختلفة تصف من خلالها كيفية حل المشكلة، وفيما يلي نوضح عدة طرق ممكنة لتمثيل الخوارزمية:

• يمكنك تمثيل الخوارزمية بلغتك المحكية أو اللغة العامية بأي طريقة تفهمها وتستوعبها دون الحاجة للالتزام بأي قواعد محددة، وهذا الأسلوب يسهل عليك مشاركة الخوارزمية مع أشخاص آخرين مهما كانت خلفياتهم التقنية.
• كما يكمن أن تتبع طريقة أكثر رسمية في التعبير اللفظي باستخدام ما يعرف بالكود الزائف Pseudo-code الذي يشبه أسلوب الكتابة في لغة البرمجة ويعمل كحل وسط بين اللغة المحكية ولغة البرمجة.
• كما يمكن تمثيل الخوارزمية بطريقة رسومية باستخدام المخططات الهيكلية أو المخططات الانسيابية Flowcharts التي تتكون من رموز وأشكال أساسية مرتبطة بأسهم تظهر الترتيب المنطقي للخطوات، ولكل شكل هدف محدد. حيث يمثل الشكل البيضوي بداية ونهاية المخطط، ويمثل المستطيل عملية ما، ويشير متوازي الأضلاع إلى إدخال وإخراج البيانات، ويدل المعين على عملية اتخاذ قرار.

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

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

ويمكن كذلك تمثيل خوارزمية عمل كوب القهوة بشكل مخطط تدفقي رسومي كما يلي:

خطوات كتابة الخوارزمية

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

على سبيل المثال تُعرَّف مشكلة خوارزمية الفرز أو الترتيب sorting على النحو التالي:

• المشكلة: الترتيب.
• المدخلات: تسلسل من عدد n من المفاتيح ‎a_1, a_2, ..., a_n‎
• الخرج: إعادة ترتيب تسلسل المدخلات بحيث يكون لدينا:

b_1, b_2,<= ... <= b_{n-1}, b_n

يمكن أن تعمل خوارزمية الفرز على عدة حالات instances، على سبيل المثال يمكن أن يكون دخل هذه الخوارزمية عبارة عن مصفوفة من السلاسل النصية التي نحتاج لترتيبها أبجديًا مثل {Haskell, Emacs} أو يكون عبارة عن تسلسل من الأرقام التي نريد ترتيبها تصاعديًا مثل {154، 245، 1337}.

الخطوة التالية هي معرفة التعليمات التي ستعمل بها الخوارزمية وتعالج المدخلات للحصول على المخرجات وكتابتها بالترتيب الصحيح والتعبير عنها بالطريقة التي تفضلها وبعدها ستكون جاهزًا لتحويل الخوارزمية إلى كود برمجي قابل للتنفيذ على الحاسوب.

مثال على كتابة خوارزمية Fizz Buzz

سنوضح في هذه الفقرة كيفية حل مسألة Fizz Buzz وهي خوارزمية معروفة تحل مشكلة بسيطة ويطلب منك حلها في معظم المقابلات البرمجية والهدف منها طباعة مجموعة من الأعداد الصحيحة من واحد إلى N ولكنك ستطبع كلمة Fizz إذا كان العدد قابلاً للقسمة على 3، و كلمة Buzz إذا كان العدد قابلاً للقسمة على 5، وكلمة Fizzbuzz إذا كان العدد قابلاً للقسمة على العددين 3 و 5 بذات الوقت.

يشير المعنى الحرفي لهاتين الكلمتين إلى الصوت التي تحدثه كل كلمة منهما، ويرجع أصل استخدامها إلى لعبة أطفال شهيرة تُسمّى fizz buzz تقوم على نفس المبدأ وتستخدم لتعلم الأطفال عملية القسمة.

في الفقرات التالية سنكتب هذه الخوارزمية بلغة البرمجة سويفت Swift وفي حال لم تكن تملك خبرة في هذه اللغة اكتبها بأي لغة برمجة تعرفها مثل لغة بايثون أو جافا او اكتبها بالكود الزائف.

بفرض أن دخل الخوارزمية هو سلسلة الأرقام التالية:

1 2 3 4 5 6 7 8 9 10

كما وضحنا سابقًا، يشير المصطلحَان Fizz و Buzz إلى أيّ عدد مضاعف للعدد 3 أو 5 على الترتيب، أي إذا كان العدد يقبل القسمة على 3 فيمكن استبداله بالكلمة Fizz، وإذا كان قابلاً للقسمة على 5 فيمكن استبداله بكلمة Buzz. أما إذا كان من مضاعفات 3 و 5 بذات الوقت فيُستبدَل بكلمة FzzBuzz أي سيكون الخرج كما هو مبين في الصورة التالية:

يمكن التعبير عن الخوارزمية بشكل كود زائف كما يلي:

• ابدأ.
• قم بتكرار الأعداد من 1 إلى 10.
• تحقق مما إذا كان العدد الحالي قابلاً للقسمة على 3.
• إذا كان الجواب صحيح اطبع الكلمة fizz.
• إذا لم يكن الجواب صحيح، انتقل إلى الخطوة التالية.
• تحقق فيما إذا كان العدد الحالي قابلاً للقسمة على 5.
• إذا كان الجواب صحيح اطبع الكلمة buzz.
• إذا لم يكن الجواب صحيح، اعرض العدد الحالي.
• كرر الحلقة حتى تصل إلى الرقم 10.
• النهاية.

لنعبر عن هذه الخطوات من خلال رسم مخطط تدفقي يوضح بشكل رسومي خطوات عمل الخوارزمية.

تنفيذ خوارزمية Fizz Buzz من خلال لغة البرمجة Swift

بعد أن فهمت الخوارزمية ستتمكن من تنفيذ هذه الخوارزمية بسهولة وتحويلها لبرنامج حاسوبي، افتح محرر الأكواد البرمجية Xcode أو VS code أو أي محرر آخر تفضله لكتابة برنامج جديد، يبدأ البرنامج بتعلمية تهيئة مصفوفة من 1 إلى 10

let number  = [1,2,3,4,5,6,7,8,9,10]

نريد أن نعالج مصفوفة الدخل والحصول على الخرج المطلوب، أي نريد أن نستبدل 3 بالكلمة fizz هنا و 5 بالكلمة buzz كما شرحنا سابقًا. ولتحقيق ذلك نمرّ على جميع عناصر المصفوفة والتحقق من كل عنصر من عناصرها ولذا سننشئ حلقة for تمرّ عبر هذه العناصر كما يلي:

for num in number {
 // الحسابات هنا
}

بعد هذا، سنستخدم العبارة الشرطية if else، وعامل باقي القسمة module operator في لغة swift أي % لتحديد مواقع fizz و buzz كما يلي:

for num in number {
 if num % 3 == 0 {
    print("\(num) fizz")
 } else {
    print(num)
 }
}

يكون الخرج الناتج من تنفيذ البرنامج هو كالتالي:

1
2
3 fizz
4
5
6 fizz
7
8
9 fizz
10

سنضيف الآن الجزء المتعلق بالكلمة Buzz مستخدمين نفس الآلية التي اتبعناها في كتابة الكود السابق:

for num in number {
 if num % 3 == 0 {
    print("\(num) fizz")
 } else if num % 5 == 0 {
    print("\(num) buzz")
 } else {
    print(num)
 }
}

بعد إضافة الكود السابق سيكون الخرج الناتج من تنفيذ البرنامج بالشكل التالي:

1
2
3 fizz
4
5 buzz
6 fizz
7
8
9 fizz
10

سنزيد عناصر المصفوفة إلى 1-15. لاحظ أنّه بما أن 15 مضاعف لكلّ من 3 و 5، فينبغي استبدالها بـ fizz buzz:

for num in number {
 if num % 3 == 0 && num % 5 == 0 {
    print("\(num) fizz buzz")
 } else if num % 3 == 0 {
    print("\(num) fizz")
 } else if num % 5 == 0 {
    print("\(num) buzz")
 } else {
    print(num)
 }
}

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

ولتسريع هذه العملية، يمكن أن نأمر المصرّف بقسمة الأعداد على 15 مباشرة. انظر الشيفرة النهائية:

for num in number {
 if num % 15 == 0 {
    print("\(num) fizz buzz")
 } else if num % 3 == 0 {
    print("\(num) fizz")
 } else if num % 5 == 0 {
    print("\(num) buzz")
 } else {
    print(num)
 }
}

هنيئًا لك، بهذا تكون قد كتبت أوّل خوارزمية لك، يمكنك استخدامها في أيّ لغة برمجة، وستعمل كما هو مُتوقّع.

تعلم الخوارزميات

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

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

وإليك أهم النصائح والخطوات التي تساعدك على تعلم الخوارزميات بكفاءة:

1. عزز مهارة التفكير المنطقي فهي مهارة أساسية يحتاجها أي مبرمج.

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

3. تعلم أهم أنواع الخوارزميات المعروفة التي يحتاجها معظم المطورين والطرق المختلفة لتنفيذها وكفاءة كل طريقة منها.

4. تعلم كيف تحلل أي مشكلة برمجية وتفهمها جيدًا وتخطط لها على الورق وتمثلها بالطرق الخوارزمية وتأكد من أنك فهمتها بشكل كامل قبل كتابة كودها البرمجي.

5. تعرف على أهم هياكل البيانات في لغة البرمجة التي تستخدمها لكتابة برامجك وتطبيقاتك وفكر بالبنية الأفضل لحل مشكلتك.

6. طبق الخوارزميات لحل مشكلات بسيطة وتدرب على حل التحديات البرمجية Problem Solving وهي كثيرة عبر الإنترنت وتضم الكثير من المهتمين بالبرمجة والتطوير وقارن إجاباتك مع إجابات الآخرين وتناقش معهم حول حلولهم لتكسب المزيد من الخبرات.

7. فكر في تنفيذ عدة طرق لحل المشكلات البرمجية التي تواجهك وقارن أيّ هذه الطرق أسرع وأكثر كفاءة وفعالية.

8. تعلم مفهوم تعقيد الخوارزميات الذي يعبر عن مقدار الوقت أو مساحة الذاكرة التي تستغرقها الخوارزمية للتنفيذ واستفذ منه في كتابة شيفرات برمجية فعالة.

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

الخلاصة

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

ترجمة -بتصرّف- للفصل الأول من كتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• المرجع الشامل إلى تعلم الخوارزميات للمبتدئين
• دليل شامل عن تحليل تعقيد الخوارزمية
• بناء مصنف بالاعتماد على طرق تعلم الآلة بلغة بايثون باستخدام مكتبة Scikit-Learn - النسخة الكاملة لكتاب مدخل إلى الذكاء الاصطناعي وتعلم الآلة

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

يستهدف هذا المقال المبرمجين الذين يعرفون عملهم جيدًا ولكنهم لا يملكون خلفيةً نظريةً في علوم الحاسوب، وذلك من خلال واحدة من أكثر أدوات علوم الحاسوب واقعيةً، وهي: صيغة O الكبير Big O notation، وتحليل تعقيد الخوارزمية algorithm complexity.

تُعَدّ هذه الأداة واحدةً من الأدوات المفيدة عمليًا للأشخاص العاملين في المجال الأكاديمي لعلوم الحاسوب، وفي إنشاء برامج على مستوى الإنتاج في الصناعة، لذلك نأمل أن تتمكن من تطبيقها في الشيفرة الخاصة بك لتحسينها بعد قراءة هذا المقال، كما يُفتَرض أن تكون قادرًا على فهم جميع المصطلحات الشائعة التي يستخدمها المختصون في علوم الحاسوب، مثل مصطلحات: التعقيد "Big O"، و"السلوك المقارب asymptotic behavior"، و"تحليل الحالة الأسوأ worst-case analysis" بعد قراءة هذا المقال.

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

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

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

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

لا تحتاج إلى خلفية رياضية لأن النص الأصلي لهذا المقال قد استهدف طلاب المدارس الثانوية، لذلك سيكون أي شخصٍ لديه بعض الخبرة في البرمجة -أي إن عرف ما هي العَودية recursion على سبيل المثال- قادرًا على المتابعة دون أي مشكلة.

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

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

يُعَدّ تعقيد الخوارزمية طريقةً لقياس سرعة تشغيل برنامج ما أو خوارزمية ما، لذلك يُعَد أمرًا عمليًا.

الدافع Motivation

يوجد أدوات لقياس مدى سرعة تشغيل البرنامج، فهناك برامج تسمى المشخِّصات profilers، حيث تقيس وقت التشغيل بالميلي ثانية ويمكنها مساعدتنا في تحسين الشيفرة الخاصة بنا عن طريق تحديد الاختناقات bottlenecks، وعلى الرغم من فائدة هذه الأداة إلا أنها ليست ذات صلة فعلية بتعقيد الخوارزمية، فتعقيد الخوارزمية مصمَّمٌ لمقارنة خوارزميتين ضمن المستوى المثالي، أي تجاهل التفاصيل منخفضة المستوى، مثل: لغة برمجة التطبيق، أو العتاد الذي تعمل عليه الخوارزمية، أو مجموعة تعليمات وحدة المعالجة المركزية CPU.

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

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

تتضمن أمثلة العمليات الحسابية البحتة العمليات العشرية العددية numerical floating-point operations، مثل: الجمع والضرب، أو البحث داخل قاعدة بيانات متناسبة مع الذاكرة العشوائية RAM عن قيمة معينة، أو تحديد المسار الذي ستمر به شخصية ذكاء اصطناعي في لعبة فيديو، بحيث يتعين عليها فقط السير مسافةً قصيرةً داخل عالمها الافتراضي (كما في الشكل الآتي)، أو تشغيل تطابق نمط تعبير نمطي regular expressions مع سلسلة، فالعمليات الحسابية موجودة في كل مكان في البرامج الحاسوبية.

تستخدم شخصيات الذكاء الاصطناعي في ألعاب الفيديو الخوارزميات لتجنب العقبات عند تنقّلها في العالم الافتراضي

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

يمنحنا تحليل التعقيد في مسابقات الخوارزميات رؤيةً عن المدة التي سيستغرقها تشغيل الشيفرة لأكبر حالات الاختبار التي تُستخدَم لاختبار صحة البرنامج، لذلك إذا قِسنا سلوك برنامجنا مع دخل صغير، فسنعرف سلوكه مع الدخل الأكبر.

لنبدأ بمثال بسيط هو إيجاد العنصر الأكبر في مصفوفة.

عد التعليمات

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

إذا كنت طالبًا منافسًا في مسابقات الخوارزميات، فيُرجَّح استخدمك لغة C++‎، لذلك لن تواجه مشكلة، وبالتالي نوصي في هذه الحالة التدرّب باستخدام لغة C++‎.

يمكن البحث عن العنصر الأكبر في مصفوفة باستخدام شيفرة لغة جافا سكريبت التالية، بافتراض أن مصفوفة الدخل هي A، وحجمها n:

var M = A[ 0 ];

for ( var i = 0; i < n; ++i ) {
   if ( A[ i ] >= M ) {
       M = A[ i ];
   }
}

أول شيء سنفعله هو حساب عدد التعليمات الأساسية التي ينفذها هذا الجزء من الشيفرة، حيث سنفعل هذا مرةً واحدةً فقط، ولن يكون ضروريًا لاحقًا، لذلك تحمَّل لبضع لحظات.

نقسّم الشيفرة إلى تعليماتٍ بسيطة عندما نحللها، فهذه التعليمات البسيطة هي ذات التعليمات، أو قريبة منها، والتي يمكن لوحدة المعالجة المركزية من تنفيذها مباشرةً، كما سنفترض أن معالجنا يمكنه تنفيذ العمليات التالية على أساس تعليمة واحدة لكل منها:

• إسناد قيمة لمتغير.
• البحث عن قيمة عنصر معين في مصفوفة.
• مقارنة قيمتين.
• زيادة قيمة.
• العمليات الحسابية الأساسية، مثل: الجمع، والضرب.

سنفترض أن التفرع -أي الاختيار بين جزئي if وelse بعد تقييم شرط if- سيحدث على الفور ولن يحسب هذه التعليمات.

السطر الأول من الشيفرة السابقة هو:

var M = A[ 0 ];

يتطلب هذا السطر تعليمتين: إحداهما للبحث عن العنصر A[ 0 ]، والأخرى لإسناد قيمته إلى M، حيث سنفترض أن قيمة n تساوي 1 على الأقل دائمًا، كما تتطلّب الخوارزمية هاتين التعليمتين دائمًا، بغض النظر عن قيمة n، ويجب أيضًا تشغيل شيفرة تهيئة حلقة for دائمًا، ويعطينا هذا تعليمتين أخريين، هما: الإسناد assignment، والمقارنة comparison:

i = 0;
i < n;

ستشغَّل هاتان التعليمتان قبل أول تكرار من حلقة for، كما نحتاج إلى تعليمتين إضافيتين للتشغيل بعد كل تكرار لحلقة for، وهما: زيادة المتغير i، ومقارنة للتحقق من أننا ما زلنا ضمن الحلقة، أي كما يلي:

++i;
i < n;

إذا تجاهلنا جسم الحلقة، فسيكون عدد التعليمات التي تحتاجها هذه الخوارزمية هو 4 + 2n، أي 4 تعليمات في بداية حلقة for، وتعليمتين في نهاية كل تكرار من n تكرار. يمكننا الآن تحديد دالة رياضية f( n )، حيث تعطينا عدد التعليمات التي تحتاجها الخوارزمية عند إعطاء n، أي لدينا f( n ) = 4 + 2n عندما يكون جسم حلقة for فارغًا.

تحليل الحالة الأسوأ Worst-case analysis

لدينا بالنظر إلى جسم حلقة for عملية بحث في مصفوفة، وعملية مقارنة تحدث دائمًا، كما يلي:

if ( A[ i ] >= M ) { …

أي يوجد تعليمتان، ولكن اعتمادًا على قيم المصفوفة، فقد يعمل جسم تعليمة if وقد لا يعمل. فإذا تحقق A[ i ] >= M، فسنشغّل هاتين التعليمتين الإضافيتين -أي البحث في مصفوفة والإسناد-، كما يلي:

M = A[ i ]

لكن لا يمكننا الآن تحديد الدالة f( n ) بسهولة، وذلك لعدم اعتماد عدد التعليمات على n فقط، وإنما على الدخل أيضًا، فإذا كان الدخل A = [ 1, 2, 3, 4 ] مثلًا، فستحتاج الخوارزمية إلى تعليمات أكثر مما إذا كان الدخل A = [ 4, 3, 2, 1 ].

نفكر عند تحليل الخوارزميات في أسوأ سيناريو غالبًا، فما هو أسوأ شيء يمكن حدوثه لخوارزميتنا؟ ومتى تحتاج الخوارزمية إلى معظم التعليمات لإكمالها؟ في هذه الحالة، يحدث ذلك عندما يكون لدينا مصفوفة بترتيب تصاعدي مثل A = [ 1, 2, 3, 4 ]، حيث يجب استبدال المتغير M في كل مرة، وبالتالي، سينتج عن ذلك تنفيذ معظم التعليمات، ويُطلَق على هذه الحالة اسم تحليل الحالة الأسوأ Worst-case analysis؛ وهذا ليس أكثر من مجرد التفكير في الحالة التي تحدث عندما نكون الأقل حظًا.

لدينا في أسوأ الحالات 4 تعليمات للتشغيل داخل جسم حلقة for، لذلك لدينا f( n ) = 4 + 2n + 4n = 6n + 4، حيث تعطينا الدالة f عدد التعليمات التي قد تكون مطلوبةً في الحالة الأسوأ بالاعتماد على حجم المشكلة n.

السلوك المقارب Asymptotic behavior

تمنحنا الدالة السابقة فكرةً جيدةً عن مدى سرعة الخوارزمية، ولكن كما وعدناك، فلن تحتاج إلى القيام بالمهمة الشاقة المتمثلة في عد التعليمات في البرنامج.

يعتمد عدد تعليمات وحدة المعالجة المركزية الفعلية اللازمة لكل عبارة لغة برمجة، على مُصرِّف compiler لغة البرمجة، وكذا على مجموعة تعليمات وحدة المعالجة المركزية المتاحة، سواءً كان معالج AMD أو Intel Pentium على حاسوبك، أو كان معالج MIPS على Playstation 2 الخاصة بك، وسنتجاهل ذلك أيضًا كما ذكرنا سابقًا.

سنشغّل الآن الدالة "f" الخاصة بنا من خلال "مرشِّح filter" ليساعدنا في التخلص من التفاصيل الصغيرة التي يفضّل المتخصصون في علوم الحاسوب تجاهلها.

يوجد قسمان في الدالة f التي تساوي 6n + 4، وهما: 6n، و4، كما لا نهتم في تحليل التعقيد إلا بما يحدث لدالة عد التعليمات عندما يكبر دخل البرنامج (n)، ويتماشى هذا مع الأفكار السابقة لسلوك "السيناريو الأسوأ" الذي ينص على الاهتمام بكيفية تصرّف الخوارزمية عند معالجتها بصورة سيئة، أي عندما تفعل هذه الخوارزمية شيئًا صعبًا، وهذا مفيد حقًا عند مقارنة الخوارزميات.

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

سنحذف الأقسام التي تنمو ببطء ونبقي فقط الأقسام التي تنمو بسرعة عندما تصبح n أكبر، ومن الواضح أن 4 ستبقى 4 لأن n تنمو بصورة أكبر؛ أما 6n فتنمو بصورةٍ أكبر وأكبر، لذلك تميل إلى كونها أهم بالنسبة للمشكلات الأكبر، وبالتالي، أول شيء سنفعله هو حذف 4 والاحتفاظ بالدالة على صورة f( n ) = 6n.

يُعَدّ ما سبق منطقيًا، وذلك لأنّ الرقم 4 هو "ثابت التهيئة initialization constant" ببساطة، وقد تتطلب لغات البرمجة المختلفة وقتًا مختلفًا لعملية الإعداد، فمثلًا، تحتاج لغة جافا إلى بعض الوقت لتهيئة آلتها الافتراضية virtual machine، وبما أننا نتجاهل الاختلافات في لغات البرمجة، فمن المنطقي تجاهل هذه القيمة فقط.

الشيء الثاني الذي سنتجاهله هو معامل الضرب الثابت أمام n، وبالتالي ستصبح الدالة f( n ) = n، مما يجعل الأمور أكثر بساطةً.

يُعَدّ إهمال معامل الضرب أمرًا منطقيًا إذا فكرنا في كيفية تصريف لغات البرمجة المختلفة، فقد تُصرَّف عبارة "البحث في المصفوفة" في إحدى لغات البرمجة إلى تعليمات مختلفة عن لغات برمجةٍ مختلفة، كما لا يتضمّن الإجراء A[ i ] التحقق من عدم تجاوز المتغير i لحجم المصفوفة المُصرَّح عنها في لغة سي C على سبيل المثال، ولكنه يتضمّن ذلك في لغة باسكال Pascal؛ إذًا فالشيفرة التالية المكتوبة بلغة باسكال:

M := A[ i ]

تكافئ الشيفرة التالية المكتوبة بلغة سي:

if ( i >= 0 && i < n ) {
   M = A[ i ];
}

لذلك نتوقّع أن لغات البرمجة المختلفة ستنتج عوامِلًا مختلفةً عندما نعُد تعليماتها.

تستخدِم لغة باسكال مصرِّفًا غبيًا يغفَل عن التحسينات الممكنة في هذا المثال، كما تتطلب ثلاث تعليمات لكل وصول إلى مصفوفة، في حين تتطلب لغة سي تعليمةً واحدةً.

يُطبَّق إهمال هذا العامل على جميع الاختلافات بين لغات البرمجة والمصرِّفات أيضًا، وبالتالي، تُحلَّل فكرة الخوارزمية فقط.

يُسمَّى المرشِّح المتمثِّل بعمليتَي "إهمال جميع العوامل"، و"الإبقاء على القسم الذي يكبر أكثر" كما هو موصوف أعلاه بالسلوك المقارب asymptotic behavior، ولذلك نمثِّل السلوك المقارب للدالة f( n ) = 2n + 8 من خلال الدالة f( n ) = n.

نهتم رياضيًا بنهاية الدالة f لأن n يميل إلى اللانهاية؛ ولكن إن لم تفهم ما تعنيه هذه العبارة، فلا تقلق لأنّ هذا كل ما تحتاج إلى معرفته، كما لن نستطيع إهمال الثوابت في النهاية في إطار رياضي صارم، ولكننا نفعل ذلك لأغراض علوم الحاسوب وللأسباب الموضَّحة أعلاه.

سنحل بعض الأمثلة لفهم الفكرة أكثر، فمثلًا، لنجد السلوك المقارب لدوال المثال التالي بإهمال العوامِل الثابتة، والحفاظ على الأقسام التي تكبر بسرعة:

1. تعطي الدالة f( n ) = 5n + 12 الدالة f( n ) = n باستخدام الاستنتاج نفسه بالضبط كما هو مذكور أعلاه.
2. تعطي الدالة f (n) = 109 الدالة f( n ) = 1، حيث سنهمل معامل الضرب 109 * 1، لكن لا يزال يتعين علينا وضع 1 هنا للإشارة إلى أنّ لهذه الدالة قيمة غير صفرية.
3. تعطي الدالة f( n ) =n² + 3n + 112 الدالة f( n ) = n²، حيث تكبرn² أكثر من 3n بالنسبة لقيمة n كبيرة بدرجة كافية، لذلك نحتفظ بها.
4. تعطي الدالة f( n ) = n³ + 1999n + 1337 الدالة f( n ) = n³، فعلى الرغم من أنّ العامل الموجود أمام n كبير جدًا، لكن لا يزال بإمكاننا العثور على قيمة n كبيرة بما يكفي، بحيث يكون n³ أكبر من 1999n، وبما أننا مهتمون بسلوك قيم n الكبيرة جدًا، فسنبقي على n³ فقط، أي تصبح الدالة n³ المرسومة باللون الأزرق في الشكل التالي أكبر من الدالة 1999n المرسومة باللون الأحمر بعد القيمة n = 45، كما تبقى هي الأكبر بعد هذه النقطة إلى الأبد.

5. تعطي الدالة f( n ) = n +√n الدالة f (n) = n، وذلك لأنّ n تنمو أسرع من ‎√n كلما زادتn ويمكنك تجربة الأمثلة الآتية بنفسك.

تمرين 1

1. f( n ) = n⁶ + 3n
2. f( n ) = 2ⁿ + 12
3. f( n ) = 3ⁿ + 2ⁿ
4. f( n ) = nⁿ + n

(اكتب نتائجك، وسترى الحل أدناه).

إذا واجهتك مشكلة مع أحد العناصر المذكورة أعلاه، فجرِّب بعض قيم n الكبيرة لمعرفة القسم الأكبر، وهذا بسيط جدًا، أليس كذلك؟

التعقيد Complexity

بما أنه يمكننا إهمال كل هذه الثوابت "الشكلية"، فمن السهل جدًا معرفة السلوك المقارب لدالة عدّ تعليمات البرنامج، حيث يملك البرنامج الذي لا يحتوي على حلقات، الدالة f( n ) = 1، لأن عدد التعليمات التي يحتاجها هو مجرد عددٍ ثابت -إلا في حالة استخدامه العودية كما سنرى لاحقًا-.

يملك البرنامج الذي يحتوي حلقةً واحدةً تمتد من 1 إلى n، الدالة f( n ) = n، حيث سينفِّذ عددًا ثابتًا من التعليمات قبل الحلقة، وعددًا ثابتًا من التعليمات بعد الحلقة، وعددًا ثابتًا من التعليمات داخل الحلقة التي تُشغَّل جميعًا n مرة.

يجب أن يكون هذا أكثر سهولةً وأقل مللًا من عدّ التعليمات الفردية، لذلك لنلقِ نظرةً على بعض الأمثلة لفهم ذلك أكثر. يتحقق البرنامج التالي المكتوب بلغة PHP من وجود قيمة معيَّنة داخل مصفوفة A لها الحجم n:

<?php
   $exists = false;
   for ( $i = 0; $i < n; ++$i ) {
       if ( $A[ $i ] == $value ) {
           $exists = true;
           break;
       }
   }
?>

تسمَّى هذه الطريقة للبحث عن قيمة داخل مصفوفة البحث الخطي linear search، وهذا اسم معقول لاحتواء هذا البرنامج على الدالة f( n ) = n، كما سنحدد بالضبط ما تعنيه كلمة "خطي" في القسم التالي.

لاحظ وجود عبارة "break" هنا، والتي قد تؤدّي إلى إنهاء البرنامج في وقت قريب، وربما بعد تكرارٍ واحد؛ لكن تذكّر اهتمامنا بالسيناريو الأسوأ، وهو بالنسبة لهذا البرنامج عدم احتواء المصفوفة A على القيمة التي نبحث عنها، لذلك لا يزال لدينا الدالة f( n ) = n.

تمرين 2

حلّل عدد التعليمات التي يحتاجها برنامج PHP أعلاه بالنسبة إلى n في الحالة الأسوأ للعثور على الدالة ( f( n، وذلك على غرار الطريقة التي حلّلنا بها البرنامج الأول المكتوب بلغة جافا سكريبت، ثم تحقق من أنه لدينا f( n ) = n بصورةٍ مقاربة.

لنلقِ نظرةً على البرنامج المكتوب بلغة بايثون Python، والذي يجمع عنصرين من مصفوفة معًا لينتج مجموع يُخزَّن في متغير آخر:

v = a[ 0 ] + a[ 1 ]

لدينا هنا عددٌ ثابت من التعليمات، لذلك f (n) = 1.

يتحقق البرنامج التالي المكتوب بلغة C++‎ من احتواء متّجه -مصفوفة مختارة أو جزء من مصفوفة- يُسمَّى A، وذو حجم n على قيمتين متماثلتين في أي مكان ضمنه:

bool duplicate = false;
for ( int i = 0; i < n; ++i ) {
   for ( int j = 0; j < n; ++j ) {
       if ( i != j && A[ i ] == A[ j ] ) {
           duplicate = true;
           break;
       }
   }
   if ( duplicate ) {
       break;
   }
}

بما أنه توجد هنا حلقتان متداخلتان داخل بعضهما البعض، فسيكون لدينا سلوكًا مقاربًا موصوفًا بالدالة f( n ) = n².

اقتباس

قاعدة عامة: يمكن تحليل البرامج البسيطة عن طريق عدّ الحلقات المتداخلة في البرنامج، بحيث تنتج حلقة مفردة مارة على n عنصر الدالة f( n ) = n، وتنتج حلقة داخل حلقة الدالةf( n ) = n²، كما تنتج حلقة داخل حلقة داخل حلقة الدالة f (n) = n³.

إذا استدعى برنامج دالةً داخل حلقة وعرفنا عدد التعليمات التي تجريها الدالة المستدعاة، فمن السهل تحديد عدد تعليمات البرنامج بأكمله.

لنلقِ نظرةً على المثال التالي المكتوب بلغة ?

int i;
for ( i = 0; i < n; ++i ) {
   f( n );
}

إذا علمنا أن f( n ) هي دالة تنفِّذ n تعليمة بالضبط، فيمكننا حينئذٍ معرفة أن عدد تعليمات البرنامج بأكمله هو n² بصورةٍ مقاربة، حيث تُستدعى الدالة n مرة تمامًا.

اقتباس

قاعدة عامة: إذا كان لدينا سلسلة من حلقات for المتسلسلة، فستحدِّد أبطأ حلقة سلوك البرنامج المقارب، وإذا وُجِدت حلقتان متداخلتان متبوعتان بحلقةٍ واحدة، فهذا يكافئ وجود الحلقات المتداخلة وحدها فقط، وذلك لأنّ الحلقات المتداخلة ستطغى على الحلقة البسيطة.

ننتقل الآن إلى الصيغة التخيُّلية التي يستخدمها علماء الحاسوب للسلوك المقارب، حيث سنقول أن برنامجنا هو Θ ( f( n )) عندما نحدِّد الدالة f بصورة مقاربة، فمثلًا، البرامج المذكورة أعلاه هي Θ (1) وΘ( n² ) وΘ( n²  ) على التوالي، حيث تُقرَأ Θ( n ) "ثيتا بالنسبة إلى n".

نقول أحيانًا أنّ f( n ) -وهي الدالة الأصلية التي تحسب عدد التعليمات بما في ذلك الثوابت- هي شيء ما Θ، حيث نقول مثلًا أنّ f( n ) = 2n هي دالة Θ( n )، كما يمكننا كتابة 2n ∈ Θ (n)‎ أيضًا، والتي تُنطَق "2n هي ثيتا بالنسبة إلى n".

لا ترتبك بشأن هذا الصيغة، فكل ما تنص عليه هو أنه إذا حسبنا عدد التعليمات التي يحتاجها البرنامج وهي 2n، فسيُوصَف السلوك المقارب للخوارزمية بـ n والذي نتج بإهمال الثوابت.

فيما يلي بعض العبارات الرياضية الصحيحة باستخدام هذا الصيغة:

1. n⁶ + 3n ∈ Θ( n⁶ )
2. 2ⁿ + 12 ∈ Θ( 2ⁿ )
3. 3ⁿ + 2ⁿ ∈ Θ( 3ⁿ )
4. nⁿ + n ∈ Θ( nⁿ )

بالمناسبة، إذا حللت التمرين 1 السابق، فهذه هي بالضبط الإجابات التي يجب أن تصل إليها.

نسمّي ما نضعه ( هنا )Θ التعقيد الزمني time complexity، أو تعقيد complexity الخوارزمية، لذلك فللخوارزمية التي تحتوي على الصيغة Θ( n ) تعقيدٌ هو n.

لدينا أيضًا أسماءً خاصةً للصيغ التالية: Θ( 1 )، وΘ( n )، وΘ( n² ) وΘ( log( n ) )، وذلك لكثرة ظهورها، حيث نقول أنّ خوارزمية Θ( 1 ) هي خوارزمية ذات وقت ثابت constant-time algorithm، والخوارزمية Θ( n ) خطية linear، وΘ( n² ) تربيعية quadratic؛ أما الخوارمية Θ( log( n ) )  فهي لوغاريتمية logarithmic. لا تقلق إن لم تعرف ما هي اللوغاريتمات حتى الآن، سنشرح ذلك لاحقًا.

اقتباس

قاعدة عامة: تعمل البرامج ذات صيغة Θ الأكبر بصورةٍ أبطأ من البرامج ذات صيغة Θ الأصغر.

صيغة O الكبير Big-O notation

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

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

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

الطريقة التالية هي طريقة غير فعالة لفرز مصفوفة في لغة روبي Ruby، حيث تدعم لغة روبي فرز المصفوفات باستخدام دوال مبنيّة مسبقًا يجب استخدامها بدلًا من ذلك، وهي بالتأكيد أسرع مما سنراه هنا، ولكن ما سنستخدمه هنا هي شيفرة بغرض التوضيح فقط:

b = []
n.times do
   m = a[ 0 ]
   mi = 0
   a.each_with_index do |element, i|
       if element < m
           m = element
           mi = i
       end
   end
   a.delete_at( mi )
   b << m
end

تسمى هذه الطريقة الفرز الانتقائي Selection sort، حيث تجد هذه الخوارزمية الحد الأدنى من المصفوفة -يُرمَز إلى المصفوفة بالمتغير a في الشيفرة السابقة، بينما يُرمَز إلى الحد الأدنى بالمتغير m، والمتغير mi هو دليله في المصفوفة-، وتضعه في نهاية مصفوفة جديدة -أي المصفوفة b في حالتنا-، ثم تزيله من المصفوفة الأصلية، وبعدها تجد الحد الأدنى بين القيم المتبقية للمصفوفة الأصلية، وتلحِقه بالمصفوفة الجديدة التي تحتوي على عنصرين الآن، ثم تزيله من المصفوفة الأصلية؛ وتستمر هذه العملية إلى حين إزالة جميع العناصر من المصفوفة الأصلية وإدخالها في المصفوفة الجديدة، مما يعني فرز المصفوفة.

نلاحظ وجود حلقتين متداخلتين في الشيفرة السابقة، حيث تعمل الحلقة الخارجية n مرة، وتعمل الحلقة الداخلية مرةً واحدةً لكل عنصر من عناصر المصفوفة a. تحتوي المصفوفة a في البداية على n عنصر، ونزيل عنصر مصفوفة واحد في كل تكرار، لذلك تتكرر الحلقة الداخلية n مرة خلال التكرار الأول للحلقة الخارجية، ثم n - 1 مرة، وبعدها n - 2 مرة، وهكذا دواليك حتى التكرار الأخير للحلقة الخارجية التي تعمل خلالها مرةً واحدةً فقط.

من الصعب قليلًا تقييم تعقيد هذا البرنامج، حيث يجب معرفة المجموع 1 + 2 + … +(n+(n-1، ولكن يمكننا بالتأكيد إيجاد "الحد الأعلى" لهذا المجموع، وهذا يعني أنه يمكننا تغيير برنامجنا - أي يمكنك فعل ذلك في عقلك، وليس في الشيفرة الفعلية- لجعله أسوأ مما هو عليه، ومن ثم إيجاد تعقيد هذا البرنامج الجديد، فإذا تمكّنا من العثور على تعقيد البرنامج الأسوأ الذي أنشأناه، فسنعلم أنّ برنامجنا الأصلي أسوأ أو ربما أفضل. بالتالي إذا أوجدنا تعقيدًا جيدًا لبرنامجنا المعدَّل الذي هو أسوأ من برنامجنا الأصلي، فيمكننا معرفة أنه سيكون لبرنامجنا الأصلي تعقيدًا جيدًا جدًا أيضًا، أي إما جيدًا بمستوى برنامجنا المعدَّل أو أفضل منه.

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

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

تُنطَق O( n² ) "أوه كبيرة لمربع n، أي big oh of n squared"، وهذا يقودنا للقول بأن برنامجنا ليس أسوأ من n² بصورةٍ مقاربة، فقد يكون أفضل من ذلك أو مثله.

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

قد لايكون البرنامج O( n² ) هو Θ( n² ) أيضًا، فأيّ برنامج Θ( n ) مثلًا هو O( n² ) وO( n ) كذلك، وإذا تخيلنا أن برنامج Θ( n ) هو عبارة عن حلقة for بسيطة تتكرر n مرة، فيمكن جعلها أسوأ بتغليفها ضمن حلقة for أخرى تتكرر n مرة أيضًا، وبالتالي ينتج برنامج له دالة f( n ) = n²، كما يمكن تعميم ذلك بالقول أنّ أي برنامج Θ( a ) هو O( b ) عندما يكون b أسوأ من a.

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

لذا يمكن القول بأن برنامجنا هو O( n² ) بطريقةٍ آمنة، وذلك لأننا حلّلنا خوارزميتنا، ووجدناها ليست أسوأ من n²، ولكنها في الواقع قد تساوي n²، وبالتالي يمكننا تقدير سرعة تشغيل برنامجنا.

لنستعرض بعض الأمثلة لتساعدك على التعرف على هذه الصيغة الجديدة.

تمرين 3

أيٌّ مما يلي صحيح؟

1. خوارزمية Θ( n ) هي O( n )
2. خوارزمية Θ( n ) هي O( n² )
3. خوارزمية Θ( n² ) هي O( n³ )
4. خوارزمية Θ( n ) هي O( 1 )
5. خوارزمية O( 1 ) هي Θ( 1 )
6. خوارزمية O( n ) هي Θ( 1 )