الهندسة الحسابية

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

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

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

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

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

الفروع الرئيسية للهندسة الحسابية هي:

  • الهندسة الحسابية التوافقية ، والتي تُسمى أيضاً الهندسة الخوارزمية ، تتعامل مع الأشكال الهندسية ككيانات منفصلة . ويؤرخ كتاب رائد في هذا المجال من تأليف بريباراتا وشاموس أول استخدام لمصطلح "الهندسة الحسابية" بهذا المعنى إلى عام 1975. [ 1 ]
  • الهندسة الحسابية العددية ، وتُسمى أيضًا هندسة الآلة ، أو التصميم الهندسي بمساعدة الحاسوب (CAGD)، أو النمذجة الهندسية ، تُعنى بشكل أساسي بتمثيل الأجسام الواقعية بأشكال مناسبة للحسابات الحاسوبية في أنظمة التصميم والتصنيع بمساعدة الحاسوب (CAD/CAM). يُمكن اعتبار هذا الفرع تطورًا إضافيًا للهندسة الوصفية ، وغالبًا ما يُصنف كفرع من فروع رسومات الحاسوب أو التصميم بمساعدة الحاسوب (CAD). وقد استُخدم مصطلح "الهندسة الحسابية" بهذا المعنى منذ عام 1971. [ 2 ]

على الرغم من أن معظم خوارزميات الهندسة الحسابية قد تم تطويرها (وما زالت قيد التطوير) لأجهزة الكمبيوتر الإلكترونية، إلا أن بعض الخوارزميات قد تم تطويرها لأجهزة الكمبيوتر غير التقليدية (مثل أجهزة الكمبيوتر الضوئية [ 3 ] ).

الهندسة الحسابية التوافقية

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

تبدو بعض هذه المشكلات بسيطة للغاية لدرجة أنها لم تُعتبر مشكلات على الإطلاق حتى ظهور الحواسيب . لنأخذ على سبيل المثال مشكلة أقرب زوج :

  • بفرض وجود n نقطة في المستوى، أوجد النقطتين اللتين تفصل بينهما أقصر مسافة.

يمكن حساب المسافات بين جميع أزواج النقاط، وعددها n ( n -1)/2 ، ثم اختيار الزوج ذي أقصر مسافة. تستغرق هذه الخوارزمية المباشرة زمنًا قدره O ( n² )، أي أن زمن تنفيذها يتناسب طرديًا مع مربع عدد النقاط. ومن النتائج الكلاسيكية في الهندسة الحسابية صياغة خوارزمية تستغرق زمنًا قدره O(n log n ) . كما تم اكتشاف خوارزميات عشوائية تستغرق زمنًا متوقعًا قدره O ( n ) [ 4 ] ، بالإضافة إلى خوارزمية حتمية تستغرق زمنًا قدره O ( n log log n ) [ 5 ] .

فصول الكتب

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

مشكلة ثابتة

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

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

مشاكل الاستعلام الهندسي

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

بعض مسائل الاستعلام الهندسي الأساسية هي:

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

إذا كانت مساحة البحث ثابتة، فعادةً ما يتم تقدير التعقيد الحسابي لهذه الفئة من المشكلات من خلال:

  • الوقت والمساحة اللازمان لإنشاء بنية البيانات المراد البحث فيها
  • الوقت (وأحيانًا مساحة إضافية) للرد على الاستفسارات.

للاطلاع على الحالة التي يُسمح فيها بتغير مساحة البحث، انظر §  المشاكل الديناميكية .

المشكلات الديناميكية

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

يتم تقدير التعقيد الحسابي لهذه الفئة من المسائل من خلال:

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

الاختلافات

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

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

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

الهندسة الحسابية العددية

يُعرف هذا الفرع أيضًا باسم النمذجة الهندسية والتصميم الهندسي بمساعدة الحاسوب (CAGD).

تتمثل المشكلات الأساسية في نمذجة وتمثيل المنحنيات والأسطح.

أهم الأدوات هنا هي المنحنيات والأسطح البارامترية ، مثل منحنيات بيزير ، ومنحنيات وأسطح سبلاين. ومن الأساليب غير البارامترية المهمة طريقة مجموعة المستويات .

تشمل مجالات تطبيق الهندسة الحسابية بناء السفن والطائرات وصناعات السيارات.

قائمة الخوارزميات

انظر أيضاً

مراجع

  1. ↑ فرانكو ب. بريباراتا ومايكل إيان شاموس (1985). الهندسة الحسابية - مقدمة . سبرينغر-فيرلاغ . ISBN 0-387-96131-3الطبعة الأولى؛ الطبعة الثانية، مصححة وموسعة، 1988.
  2. ↑ AR Forrest, "الهندسة الحسابية"، وقائع الجمعية الملكية بلندن ، 321، السلسلة 4، 187-195 (1971)
  3. ↑ يفغيني ب. كاراسيك (2019). الهندسة الحسابية البصرية . ISBN 979-8511243344.
  4. ↑ إس. خولر وي. ماتياس. خوارزمية غربلة عشوائية بسيطة لمسألة أقرب زوج . معلومات وحوسبة، 118(1):34–37، 1995 ( ملف PDF )
  5. ↑ إس. فورتشن وجيه إي هوبكروفت. "ملاحظة حول خوارزمية رابين لأقرب جار". رسائل معالجة المعلومات، 8(1)، ص 20-23، 1979

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

المجلات

الهندسة الحسابية التوافقية/الخوارزمية

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