stanford-oval/wikipedia huggingface dataset:
تشارلز ويجيليوس

تشارلز ويجيليوس (بالإنجليزية: Charles Wegelius)‏ مواليد 26 أبريل 1978 في إسبو، هو دراج إنجليزي سابق في صنف سباق الدراجات على الطريق. سبق أن شارك في دورة الألعاب الأولمبية الصيفية.
مراجع

↑  "معلومات عن تشارلز ويجيليوس على موقع cantic.bnc.cat". cantic.bnc.cat. مؤرشف من الأصل في 2020-03-20.
↑  "معلومات عن تشارلز ويجيليوس على موقع thecgf.com". thecgf.com. مؤرشف من الأصل في 2019-12-15.
↑  "معلومات عن تشارلز ويجيليوس على موقع datos.bne.es". datos.bne.es. مؤرشف من الأصل في 2019-12-15.
تمثال داود

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

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

Italy guides
Ms
1 2   https://www.galleriaaccademiafirenze.it/opere/david/. {{استشهاد ويب}}: |url= بحاجة لعنوان (مساعدة) والوسيط |title= غير موجود أو فارغ (من ويكي بيانات) (مساعدة)
↑  Make Lists, Not War (بالإنجليزية), QID:Q97309629
↑   https://accademia.stanford.edu/mich/more-david/more-david.html. {{استشهاد ويب}}: |url= بحاجة لعنوان (مساعدة) والوسيط |title= غير موجود أو فارغ (من ويكي بيانات) (مساعدة)
↑   https://muzeodrome.substack.com/p/la-reproductibilite-technique-de. {{استشهاد ويب}}: |url= بحاجة لعنوان (مساعدة) والوسيط |title= غير موجود أو فارغ (من ويكي بيانات) (مساعدة)
↑  alimbratur نسخة محفوظة 16 فبراير 2007 على موقع واي باك مشين. "نسخة مؤرشفة". مؤرشف من الأصل في 2016-03-14. اطلع عليه بتاريخ 2018-07-30.{{استشهاد ويب}}:  صيانة الاستشهاد: BOT: original URL status unknown (link)
↑  almustaqbal نسخة محفوظة 19 أبريل 2009 على موقع واي باك مشين. "نسخة مؤرشفة". مؤرشف من الأصل في 2009-04-19. اطلع عليه بتاريخ 2007-03-03.{{استشهاد ويب}}:  صيانة الاستشهاد: BOT: original URL status unknown (link)
في كومنز مواد ذات صلة بـ تمثال داود.
بوابة إيطاليا
بوابة الإنجيل
بوابة المسيحية
بوابة اليهودية
بوابة روما
بوابة فنون
| ضبط استنادي  | ضبط استنادي  |
| --- | --- |
دولية: ملف الضبط الاستنادي الافتراضي الدَّولي (VIAF)
وطنية: الملف الاستنادي المتكامِل (GND) مكتبة الكونغرس (LCNAF) المكتبة الوطنية الفرنسية (BnF) المكتبة القومية في بولندا (NLP) المكتبة القومية الإسرائيلية (J9U)
أخرى: النظام الجامعي للتوثيق (IdRef)
تيري أنتونيس
مراجع

↑  Sydney FC Home | Sydney FC نسخة محفوظة 25 مارس 2018 على موقع واي باك مشين.
| ع ن تشكيلة منتخب أستراليا  –  كأس آسيا 2015 (اللقب الأول) | ع ن تشكيلة منتخب أستراليا  –  كأس آسيا 2015 (اللقب الأول) | ع ن تشكيلة منتخب أستراليا  –  كأس آسيا 2015 (اللقب الأول) |
| --- | --- | --- |
|  1 رايان  2 فرانيتش  3 ديفيدسون  4 كاهيل  5 ميليغان  6 سبيرانوفيتش  7 لكي  8 هرد  9 يوريتش  10 كروز  11 أور  12 لانغيراك  13 بيهيتش  14 ترويسي  15 يديناك   16 برنز  17 مكاي  18 غاليكوفيتش  19 أنتونيس  20 سينزبوري  21 لونغو  22 ويلكينسون  23 بريشيانو   المدرب: إنج بوستيكوغلو  |  1 رايان  2 فرانيتش  3 ديفيدسون  4 كاهيل  5 ميليغان  6 سبيرانوفيتش  7 لكي  8 هرد  9 يوريتش  10 كروز  11 أور  12 لانغيراك  13 بيهيتش  14 ترويسي  15 يديناك   16 برنز  17 مكاي  18 غاليكوفيتش  19 أنتونيس  20 سينزبوري  21 لونغو  22 ويلكينسون  23 بريشيانو   المدرب: إنج بوستيكوغلو  |  |
| ع ن نادي وسترن سيدني واندررز  – التشكيلة الحالية | ع ن نادي وسترن سيدني واندررز  – التشكيلة الحالية |
| --- | --- |
 1 ماركوش  2 Gabriel Cleur‏  3 تراوري  4 وليامز  5 Tomislav Mrčela‏  6 مارسيلو  7 Ramy Najjarine‏  8 بوزانيتش  9 Kusini Yengi‏  10 نينكوفيتش  11 Sulejman Krpić‏  12 تونغيك  13 Tate Russell‏  16 Tom Beadling‏  17 أمالفيتانو  19 Daniel Wilmering‏  20 توماس  21 Jarrod Carluccio‏  23 نجباكوتو  26 بوريلو  28 Calem Nieuwenhof‏  29 أنتونيس  31 Simmons  32 Blair  33 Bonetig  35 Zac Sapsford‏  36 Alessandro Lopane‏  37 Alexander Badolato‏  مدرب: روتان :  1 ماركوش  2 Gabriel Cleur‏  3 تراوري  4 وليامز  5 Tomislav Mrčela‏  6 مارسيلو  7 Ramy Najjarine‏  8 بوزانيتش  9 Kusini Yengi‏  10 نينكوفيتش  11 Sulejman Krpić‏  12 تونغيك  13 Tate Russell‏  16 Tom Beadling‏  17 أمالفيتانو  19 Daniel Wilmering‏  20 توماس  21 Jarrod Carluccio‏  23 نجباكوتو  26 بوريلو  28 Calem Nieuwenhof‏  29 أنتونيس  31 Simmons  32 Blair  33 Bonetig  35 Zac Sapsford‏  36 Alessandro Lopane‏  37 Alexander Badolato‏  مدرب: روتان 
بوابة أستراليا
بوابة أعلام
بوابة عقد 2010
بوابة كرة القدم
نيكي مكري

نيكي مكري (بالإنجليزية: Nikki McCray)‏ مواليد 17 ديسمبر 1971، هي لاعبة كرة سلة أمريكية أصبحت مدربة مساعدة بعد تقاعدها. بدأت مسيرتها الاحترافية في سنة 1998. بلغ طولها 5 قدم 11 بوصة (1.8 م). شاركت في دورة الألعاب الأولمبية الصيفية سنة 1996. اعتزلت اللعب في 2006. شاركت 3 مرات في مباراة كل النجوم.
المسيرة الاحترافية

لعبت مع واشنطن ميستيكس من سنة 1998 إلى 2001، ثم لعبت مع إنديانا فيفر في موسم 2002–2003، ثم لعبت مع فينيكس ميركوري في سنة 2004، ثم لعبت مع سان أنطونيو ستارز في سنة 2005، ثم لعبت مع شيكاغو سكاي في سنة 2006.
الميداليات

| الميدالية | المسابقة |
| --- | --- |
 ذهبية: الألعاب الأولمبية الصيفية 1996
 ذهبية: الألعاب الأولمبية الصيفية 2000
 ذهبية: كأس العالم لكرة السلة للسيدات 1998
:
مراجع

↑   https://www.nbcsports.com/olympics/news/nikki-mccray-penson-dies. {{استشهاد ويب}}: |url= بحاجة لعنوان (مساعدة) والوسيط |title= غير موجود أو فارغ (من ويكي بيانات) (مساعدة)
↑  Basketball Reference (بالإنجليزية), QID:Q22235911
↑  eurobasket.com (بالإنجليزية), QID:Q3060570
↑  WNBA.com profile  نسخة محفوظة 24 مارس 2015 على موقع واي باك مشين.
جورج غاردنر

لمعانٍ أخرى، طالع جورج غاردنر (توضيح).
| جورج غاردنر> معلومات شخصية   | جورج غاردنر> معلومات شخصية   |
| --- | --- |
الميلاد: مايو 1812(1812-05-00)خطأ في التعبير: عامل > غير متوقع. غلاسغو
الوفاة: 10 مارس 1849 (خطأ في التعبير: معامل مفقود للعامل -. سنة) [[تصنيف:وفيات بعمر خطأ في التعبير: معامل مفقود للعامل -.]] خطأ في التعبير: عامل > غير متوقع.  كاندي  
مواطنة: المملكة المتحدة
الحياة العملية  : الحياة العملية  
اختصار اسم علماء النبات: Gardner  
المهنة: عالم نبات، وعالم حشرات  
مجال العمل: علم النبات  
موظف في: جامعة غلاسكو  
تعديل مصدري - تعديل  : تعديل مصدري - تعديل  
جورج غاردنر (1812-1849) (بالإنجليزية: George Gardner)‏ هو عالم نبات اسكتلندي.
مراجع

↑  المؤشر الدولي لأسماء النباتات - تفاصيل واضع الأسماء IPNI جورج غاردنر تاريخ الولوج 01 تموز 2014 نسخة محفوظة 04 أبريل 2016 على موقع واي باك مشين.
بوابة أعلام
بوابة إسكتلندا
بوابة المملكة المتحدة
بوابة تاريخ العلوم
بوابة علم النبات
| ضبط استنادي  | ضبط استنادي  |
| --- | --- |
دولية: الاسم المعياري الدولي (ISNI) ملف الضبط الاستنادي الافتراضي الدَّولي (VIAF) مركز المكتبة الرقمية على الإنترنت (WC Entities)
وطنية: الملف الاستنادي المتكامِل (GND) مكتبة الكونغرس (LCNAF) المَكنز الوطني للمؤلِّفين (NTA) مكتبة الفاتيكان (VcBA)
بحثية: مختصر اسم عالم نبات
فنية: متحف نيوزلندا (TePapa)
تراجم: نفائس المكتبة القومية الأسترالية (NLA Trove) الفهارس الألمانية (DtBio) المكتبة الألمانية الرقمية (DDB)
قبائل البندو والبحرصوف

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

↑  "Erythrina melanacantha subsp. somala". CABI Compendium. 11 أكتوبر 2017. اطلع عليه بتاريخ 2025-03-08.
نظرية التعقيد الحسابي

نظرية التعقيد الحسابي
| 0 | 1 |
| --- | --- |
صنف فرعي من:  نظرية الحاسوبية — complexity theory   
جزء من:  رياضيات — معلوماتية نظرية 
المواضيع:  تفوق كمومي  — التعقيد الحسابي 
تعديل - تعديل مصدري - تعديل ويكي بيانات
نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد complexity classes ببعضها البعض. المسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها.
ويمكن اعتبارها مسألة صعبة إذا استخدمت كمية مُعينة من الموارد أياً كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة مثل: الوقت أو حجم المكان الإضافي اللازم، وتوجد معايير تعقيد أخرى مثل: الاتصال (مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية (مستخدم في نظرية تعقيد الدارات المنطقية) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي).
وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به.
المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات ونظرية الحاسوبية، والفرق بين تحليل الخوارزميات ونظرية التعقيد الحسابية هو أن الأول يسأل عن خوارزمية معينة لحل مسألة، بينما الآخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة، وبالتحديد فإن الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية مُحددة من الموارد، أما وضع الحدود للموارد الموجودة هو ما يميز نظرية التعقيد الحسابي عن النظرية الحاسوبية أي أن النظرية الحاسوبية تسأل عن أية مسائل يمكن حلها بواسطة خوارزمية.
مسائل، مُدخل وطول المُدخل > تعريف المُدخل

بشكل عام مُدخل (instance) لمسألة حاسوبية هو مجموعة معطيات  x_{1},\cdots ,x_{d}، والمسألة الحاسوبية هي حساب دالة متعلقة بهذه المعطيات.
مثال حساب المُحدد لمصفوفة: المدخلات لهذه المسألة هي القيم في المصفوفة والمُخرج هو المحدد، وقد يُنظر إلى المسألة على أنها مجموعة من المدخلات والمُخرج الملائم للمُدخل، ويمكن أن تكون المدخلات بأطوال مختلفة، وطول المُدخل هو كمية البتات اللازمة لترميز المُدخل بشكل ملائم، أي أن المُدخل يكون سلسلة (string) تابعة ل-  \{0,1\}^{*}، مثال يمكن ترميز العدد بواسطة تمثيله بنظام العد الثنائي (الترميز الملائم للعدد 15 هو 1111)، أما ترميز المخطط فيكون بواسطة القيم في المصفوفة الملائمة له.
مسائل، مُدخل وطول المُدخل > لغات أو مسائل التقرير

مسألة التقرير هي نوع خاص من المسائل الحاسوبية التي يكون جوابها إما نعم أو لا، أو 0 و 1، وهذا النوع من المسائل يُعرف أيضا باللغات، في حين أن الأعضاء التابعة لهذه اللغة هي المُدخلات التي جوابها نعم، والهدف يكون بإعطائنا مُدخل يجب التقرير إذا ما هو عضو في هذه اللغة أو لا وذلك بواسطة خوارزمية.
مثال: فلتكن مسألة تقرير إذا كان عدد معطى هو أولي، اللغة هي كل الأعداد الأولية، ولتقرير إذا كان مُدخل معين هو أولي نشغل الخوارزمية التالية: «فحص إذا ما كان العدد المعطى يقبل القسمة على أي عدد من 2 حتى العدد نفسه - ما عدا للعدد نفسه- ، إذا قَبِل (الجواب نعم) فهو ليس أولياً وخلاف ذلك العدد أولي».
مسائل، مُدخل وطول المُدخل > مسائل دالة

مسائل دالة (function problem) هي مسائل يكون فيها لكل مُدخل مُخرجٌ وحيد، وتختلف هذه المسائل عن مسائل التقرير في أن مُخرجها قد يكون غير الإجابة بـ (نعم ولا).
مثال تحليل لعوامل أولية حيث يكون المُدخل هو عدد، والمُخرج هو التحليل لعوامل لهذا العدد، وقد يُعتقد أن مسائل الدالة أغنى من مسائل التقرير، ولكن هذا غير صحيح بالضرورة، إذ يمكن تحويل كل مسألة دالة إلى مسألة تقرير، وفي مثال التحليل لعوامل أولية المدخل هو عدد x، وقائمة أعداد x1,x2,...,xd، والمُخرج هو نعم فقط إذا كان حاصل ضرب الأعداد هو x، إضافة إلى أن كل عدد بالقائمة هو أولي.
مسائل، مُدخل وطول المُدخل > قياس تعقيد الخوارزمية

لقياس صعوبة مسألة حاسوبية وجب على المرء أن يقيس الوقت اللازم لأفضل خوارزمية كي تحل المسألة، وبشكل عام فالوقت قد يرتبط بطول المُدخل فالمُدخلات الطويلة حتماً ستحتاج وقتاً أطول للوصول إلى الحل. لذا فإن قياس الوقت اللازم لحل مسألة هو دالة مرتبطة بطول المُدخل، وبشكل عام طول المُدخل يكون ب الإثباتات، لذا فإن علم التعقيد بالأساس يبحث مدى قابلية الخوارزمية للتوسع.
فلنفرض أن n هو طول المُدخل، حينها يمكن التعبير عن الوقت اللازم للخوارزمية بواسطة n، وبما أن الوقت اللازم لحل المسألة قد يختلف تبعاً لكل مُدخل فإنه يُؤخذ بالاعتبار تعقيد وقت الحالة الأسوأ (T(n، والذي هو الوقت الأطول الذي ستحتاجه الخوارزمية بالنسبة لكل المدخلات.
إذا كانت (T(n حدودية، أي يوجد ثابت c > 0 بحيث أن (T(n)=O(nc حينها نصف الخوارزمية بأنها (خوارزمية حدودية الوقت) أي أن وقت الخوارزمية هو وقت حل حدودي. وأطروحة كوبهام تقترح أن أي مسألة يمكن حلها بكمية معقولة من الموارد إذا وجدت خوارزمية تحلها بوقت حدودي.
نماذج حاسوبية ومقاييس التعقيد > نماذج حاسوبية

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

ولكي يكون قياس التعقيد، والذي هو استخدام كمية مُعينة من الموارد مثل: الوقت أو المكان، دقيقا ومُعرفا بشكل رياضياتى سليم كانت الحاجة للنماذج الحاسوبية مثال: آلة تيورنج، وقد نعرف الوقت اللازم لحل مسألة بواسطة آلة تيورنج،M , مع المدخل للالة،x, هو عدد الخطوات أو التحول من وضعية لوضعية اللازمة للالة حتى التوقف والاتيان بالنتيجة (مثل: نعم أو لا). ونقول أنَّ آلة تيورنج، M , وقت عملها هو (f(n إذا كان الوقت اللازم للالة M على كل مُدخل طولة n هو (f(n . ونقول أنَّ مسألة يمكن حلها بوقت (f(n إذا يوجد آلة تيورنج M الوقت الذي تحتاجه لحل مُدخل طوله n هو (f(n . وبما أنَّ نظرية التعقيد اهتمامها بتصنيف المسائل حسب صعوبتها لذا فالمرئ يمكنه تعريف مجموعة مسائل تحقق معيار مُعين مثال ذلك المجموعة ((DTIME(f(n وهي مجموعة المسائل التي يوجد آلة تيورنج قطعية التي تحلها بوقت (f(n .
هنالك عدة مقاييس للتعقيد ولعل اهمها هو الوقت والمكان، ولعل بديهيات بلم (Blum axioms) في نظرية التعقيد تُعرف هذه المقاييس. مقاييس أخرى مُستخدمة في نظرية التعقيد هي تعقيد الاتصال وتعقيد الدارات المنطقية وتعقيد شجرة التقرير. وبشكل عام في قياس تعقيد الخوارزميات شاع استخدام رمز O الكبير.
نماذج حاسوبية ومقاييس التعقيد > تعقيد الحالة الأفضل والحالة الأسوأ وتعقيد الحالة المتوسطة

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

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

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

كثير من أقسام التعقيد يمكن تعريفها بواسطة تحديد الوقت أو المكان التي تستخدمها الخوارزمية، وفي هذا السياق يمكن تعريف بعض الأقسام كالتالي:
| اقسام تعقيد | النموذج الحاسوبي | قيود الموارد |
| --- | --- | --- |
| ((DTIME(f(n | آلة تيورنج قطعية | وقت (f(n |
| P | آلة تيورنج قطعية | وقت (poly(n |
| EXPTIME | آلة تيورنج قطعية | وقت(2poly(n |
| ((NTIME(f(n | آلة تيورنج غير قطعية | وقت (f(n |
| NP | آلة تيورنج غير قطعية | وقت (poly(n |
| NEXPTIME | آلة تيورنج غير قطعية | وقت (2poly(n |
| ((DSPACE(f(n | آلة تيورنج قطعية | مكان (f(n |
| L | آلة تيورنج قطعية | مكان (O(log n |
| بيسبايس | آلة تيورنج قطعية | مكان (poly(n |
| EXPSPACE | آلة تيورنج قطعية | مكان (2poly(n |
| ((NSPACE(f(n | آلة تيورنج غير قطعية | مكان (f(n |
| NL (تعقيد حسابي) | آلة تيورنج غير قطعية | مكان (O(log n |
| بيسبايس | آلة تيورنج غير قطعية | مكان (poly(n |
| NEXPSPACE | آلة تيورنج غير قطعية | مكان (2poly(n |
لقد تبين أن NSPACE(f(n))\subseteq DSPACE(f^{2}(n)) وكذلك:  PSPACE=NPSPACE و  EXPSPACE=NEXPSPACE وهذا كله بواسطة مبرهنة سافيتش (Savitch theorem).
أقسام مهمة أخرى من ضمنها ZPP , BPP ,Co-RP,RP وهي تستخدم آلة تيورنج احتمالية في تعريفها، أما BQP و QMA ففيهما استخدم آلة تيورنج كمومية، أما NC و- AC وكذلك P/Poly تعرف بواسطة الدارات المنطقية، أما بالنسبة ل-P# فهو قسم مسائل عد واحد أهمها على الإطلاق، أقسام مثل: IP و-AM تستخدم نظام براهين تفاعلي، ALL هو قسم كل المسائل.
اقسام تعقيد > مسائل كاملة

المقالة الرئيسة: مسألة كثيرة حدود غير قطعية كاملة
فلتكن  L\in {\mbox{NP}} نقول أنَّ  L مسألة  {\mbox{NP}} كاملة إذا تحقق:
لكل  L'\in {\mbox{NP}} يتحقق:  L'\leq _{p}L
نسمي  {\mbox{NP-complete}} قسم اللغات التي هي NP كاملة.
بشكل مشابه يمكن تعريف مسائل كاملة في كل قسم لغات مثل:  {\mbox{P,PSPACE}},... .
إن المسائل الكاملة تعتبر «مسائل صعبة» بمفهوم انه لو وُجد حل بوقت حدودي لإحداها هذا يعني أن كل المسائل في  {\mbox{ NP}}يمكن حلها بوقت حدودي.
النظرية التالية تشرح هذا الأمر:
إذا وفقط إذا  .
اقسام تعقيد > مسائل كاملة > مبرهنة كوك وليفين

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

هذه المبرهنات تعتبر نتائج أساسية بواسطتها يمكن فصل أقسام التعقيد، والحدس خلف هذه المبرهنات هو إذا كان لديك موارد أكثر باستطاعتك ان تفعل أكثر، ولهذه المبرهنات عدة نصوص إذ أنه لكل مورد ومقياس تعقيد يوجد نص خاص به، وندرج بعض هذه:
إذا كانت (f(n يمكن حسابها بوقت ((O(f(n حيث أن (log(n)<f(n حينها:  {\mbox{DTIME(f(n))}}\subsetneq {\mbox{DTIME(f(n)log(f(n)))}}
فلتكن (s(n و- (g(n دالتين يمكن حسابهما بواسطة ((O(s(n و- ((O(g(n مكان حينها وإذا: (o(g(n))=s(n , حينها:  {\mbox{SPACE(s(n))}}\subsetneq {\mbox{SPACE(g(n))}}
ونتيجة لهذه المبرهنات فأننا نحصل على:  {\mbox{P}}\neq {\mbox{EXP}} وكذلك:  {\mbox{NP}}\neq {\mbox{NEXP}} وكذلك:  {\mbox{L}}\neq {\mbox{PSPACE}}، كما أن هذه الاثباتات بشكل ما تناقض أطروحة ادموندز- كوبهام إذ انه هذا يعني أن هنالك مسائل لا يمكن حلها بوقت اقل من  {\mbox{n}}^{1000} وبشكل واضح هذا الوقت يُعتبر غير واقعي وغير قابل للوصول حتى بالنسبة ل- n=2 !
الاختصار

الاختصار (reduction) هو: وسيلة لنقل مسألة إلى مسألة أخرى، بحيث انه يمكن الاستعانة بحل المسألة الثانية لحل المسألة الأولى.
وقد شاع استخدام هذه الاختصارات في الحياة اليومية، مثال واضح على هذا هو: لنفرض اننا نريد ان نجد شارع في مدينة معينة لعل هذا يكون أسهل بوجود خريطة، إذا استخدمنا الخريطة نكون بهذا قد اختصرنا مسألة ايجاد الشارع في المدينة لإيجاد الشارع في الخريطة.
وبالعادة في الاختصارات عندنا مسألتين A و- B إذا فرضنا أن B يمكن اختصارها ل-A حينها حل المسألة A يمكن الاستعانة به لحل المسألة B، ولننظر إلى المسائل التالية:
السفر من إسطنبول إلى مكة.
شراء تذكرة طيران من إسطنبول إلى مكة.
جمع النقود لشراء التذكرة من إسطنبول إلى مكة.
إيجاد عمل لتحصيل النقود.
يمكن رؤية ان كل واحدة من المسائل يمكن اختصارها للأخرى بالشكل التالي: إذا حللنا مسألة ايجاد عمل حينها يمكن جمع النقود لشراء التذكرة من إسطنبول إلى مكة في الوقت الذي جمعنا فيه مالا كافيا لشراء التذكرة يمكن حينها شراء التذكرة وأخيرا السفر إلى مكة من إسطنبول.
كما ان الاختصارات تظهر كذلك في المسائل الرياضية مثل: قياس مساحة الدائرة يمكن اختصاره لإيجاد طول نصف القُطُر، كما انه يمكن اختصار حل هيئة معادلات خطية لعكس مصفوفة. يظهر الاختصار في كثير من المجالات في الرياضيات وذلك لانه بواسطة الاختصارات يمكن تصنيف مسائل الرياضيات إذ انه إذا يمكن اختصار مسألة A للمسألة B حينها المسألة A لا يمكن ان تكون أصعب من المسألة B، وهذه النظرة اخذها علوم الحاسوب لتصنيف الخوارزميات وقد تمكن علماء الحاسوب بناء نظرية التعقيد الحسابي بواسطتها.
يوجد عدة أنواع من الاختصارات ومنها:
اختصارات تورنغ: نقول ان اللغة  A\subseteq \{0,1\}^{*} يمكن اختصارها للغة  B\subseteq \{0,1\}^{*} إذا لكل  x\in A عدد خطوات* الحساب هو حدودي بالنسبة لطول المدخل أي  Poly(|x|) . * نقصد هنا بالخطوة الحسابية هو إما ان تكون خطوة حسابية بالمفهوم العادي أو تكون الخطوة هي الدخول لدالة تحل المسألة B.
اختصارات كارب أو قابلية اختصار بواسطة تطبيق حدودي: نقول أن لغة  A\subseteq \{0,1\}^{*} يمكن اختصارها بوقت حدودي للغة  B\subseteq \{0,1\}^{*} ويُرمز اليه ب-  A\leq _{p}B إذا يوجد دالة يمكن حسابها بوقت حدودي  f:\{0,1\}^{*}\to \{0,1\}^{*} بحيث انه لكل  x\in \{0,1\}^{*} ,  x\in A وفقط إذا  f(x)\in B
اختصارات ليفين: فليكن f و- g دالتين يمكن حسابهما بوقت حدودي، حينها يمكن تسميتهما اختصار ليفين من اللغة R للغة 'R إذا كانت f اختصار كارب من  S_{R}=\{x:\exists y,(x,y)\in R\} للغة  S_{R}'=\{x:\exists y,(x,y)\in R'\} ولكل  x\in S_{R} وكذلك  y'\in R'(f(x)) حينها  (x,g(x,y'))\in R في حين أن  R'(x')=\{y':(x',y')\in R'\} .
اختصارات سعة مواردها لُغَرِتمية: نبدأ أولا بتعريف نوع خاص من الدوال والتي هي يمكن حسابها بسعة موارد لغرتمية:
فلتكن  f:\{0,1\}^{*}\to \{0,1\}^{*} دالة محدودة حدوديا بمعنى انه يوجد ثابت  c>0 بحيث أن  f(x)\leq |x|^{c} . ونقول أن f يمكن حسابها بسعة موارد لغرتمية إذا يمكن حساب اللغتين  L_{f}=\{\langle x,i\rangle |f(x)_{i}=1\} وكذلك  L'_{f}=\{\langle x,i\rangle |i\leq |f(x)|\} يمكن حسابها بسعة موارد لغرتمية.
والان نعرف اختصارات سعة مواردها لغرتمية بالشكل التالي: نقول أن لغة  A\subseteq \{0,1\}^{*} يمكن اختصارها بسعة موارد حدودية للغة  B\subseteq \{0,1\}^{*} ويُرمز اليه ب-  A\leq _{l}B إذا يوجد دالة يمكن حسابها بسعة موارد لغرتمية  f:\{0,1\}^{*}\to \{0,1\}^{*} بحيث انه لكل  x\in \{0,1\}^{*} ,  x\in A وفقط إذا  f(x)\in B
مسائل غير محلولة

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