الدوائر (علوم الحاسوب)

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

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

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

الدائرة الكهربائية هي ثلاثية(م،ل،جي){\displaystyle (M,L,G)}، أين

  • م{\displaystyle M}هي مجموعة من القيم،
  • ل{\displaystyle L}هي مجموعة من علامات البوابات، كل منها عبارة عن دالة منمأنا{\displaystyle M^{i}}لم{\displaystyle M}لبعض الأعداد الصحيحة غير السالبةأنا{\displaystyle i}(أينأنا{\displaystyle i}يمثل عدد المدخلات إلى البوابة)، و
  • جي{\displaystyle G}هو رسم بياني موجه غير دوري مُصنَّف، مع تصنيفات منل{\displaystyle L}.

تُسمى رؤوس الرسم البياني بالبوابات . لكل بوابةز{\displaystyle g}درجة داخليةأنا{\displaystyle i}البوابةز{\displaystyle g}يمكن تصنيفها بواسطة عنصرℓ{\displaystyle \ell }لل{\displaystyle L}إذا وفقط إذاℓ{\displaystyle \ell }يتم تعريفها علىمأنا.{\displaystyle M^{i}.}

مصطلحات

تُسمى البوابات ذات درجة الدخول 0 مدخلات أو أوراق . وتُسمى البوابات ذات درجة الخروج 0 مخرجات . إذا كان هناك حافة من البوابةز{\displaystyle g}إلى البوابةح{\displaystyle h}في الرسم البيانيجي{\displaystyle G}ثمح{\displaystyle h}يُطلق عليه اسم ابنز{\displaystyle g}نفترض وجود ترتيب على رؤوس الرسم البياني، لذا يمكننا الحديث عنك{\displaystyle k}الطفل الثالث من البوابة عندماك{\displaystyle k}أقل من أو يساوي درجة الخروج للبوابة.

حجم الدائرة هو عدد عقدها. عمق البوابةز{\displaystyle g}يمثل طول أطول مسار فيجي{\displaystyle G}ابتداءً منز{\displaystyle g}حتى بوابة الإخراج. على وجه الخصوص، البوابات ذات درجة الإخراج 0 هي البوابات الوحيدة ذات العمق 1. عمق الدائرة هو أقصى عمق لأي بوابة.

مستوىأنا{\displaystyle i}هي مجموعة جميع بوابات العمقأنا{\displaystyle i}الدائرة المستوية هي دائرة تكون فيها حواف البوابات ذات عمقأنا{\displaystyle i}لا يأتي إلا من أبواب الأعماقأنا+1{\displaystyle i+1}أو من المدخلات. بعبارة أخرى، لا توجد حواف إلا بين المستويات المتجاورة للدائرة. عرض الدائرة المستوية هو أقصى حجم لأي مستوى.

تقييم

القيمة الدقيقةV(ز){\displaystyle V(g)}بوابةز{\displaystyle g}مع درجة داخليةأنا{\displaystyle i}ووضع ملصقل{\displaystyle l}يتم تعريفها بشكل متكرر لجميع البواباتز{\displaystyle g}.

V(ز)={للو ز هو مدخلل(V(ز1)،...،V(زأنا))خلاف ذلك،{\displaystyle V(g)={\begin{cases}l&{\text{إذا كان }}g{\text{ مدخلاً}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{فيما عدا ذلك،}}\end{cases}}}

حيث كلزج{\displaystyle g_{j}}هو أحد والديز{\displaystyle g}.

قيمة الدائرة هي قيمة كل بوابة من بوابات الإخراج.

الدوائر كوظائف

يمكن أن تكون تسميات الأوراق أيضًا متغيرات تأخذ قيمًا فيم{\displaystyle M}إذا كان هناكن{\displaystyle n}إذا كانت الأوراق، فيمكن اعتبار الدائرة بمثابة دالة من من{\displaystyle M^{n}}لم{\displaystyle M}ومن المعتاد حينها النظر في مجموعة من الدوائر(جن)ن∈شمال{\displaystyle (C_{n})_{n\in \mathbb {N} }}، سلسلة من الدوائر المفهرسة بالأعداد الصحيحة حيث الدائرةجن{\displaystyle C_{n}}لديهن{\displaystyle n}المتغيرات. وبالتالي، يمكن اعتبار عائلات الدوائر بمثابة دوال منم*{\displaystyle M^{*}}لم{\displaystyle M}.

يمكن توسيع مفاهيم الحجم والعمق والعرض بشكل طبيعي لتشمل عائلات من الدوال، لتصبح دوالًا منشمال{\displaystyle \mathbb {N} }لشمال{\displaystyle \mathbb {N} }؛ على سبيل المثال،sأناzهـ(ن){\displaystyle size(n)}حجم ن{\displaystyle n}الدائرة الثالثة من العائلة.

التعقيد والمشاكل الخوارزمية

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

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

انظر أيضاً

مراجع