مدار (علوم کامپیوتر)

در علوم نظری رایانه، مدار یک مدل محاسباتی است که در آن مقادیر ورودی از طریق دنباله‌ای از دروازه‌ها ادامه می‌یابد که هر کدام یک تابع را محاسبه می‌کنند. مدارهایی از این نوع یک تعمیم از مدارهای بولی و یک مدل ریاضی برای مدارهای منطقی دیجیتال ارائه می‌دهند. مدارها توسط دروازه‌هایی که در آن‌ها وجود دارد و مقادیری که دروازه‌ها می‌توانند تولید کنند تعریف می‌شوند. به عنوان مثال، مقادیر در یک مدار بولی مقادیر بولی هستند و مدار شامل اتصال، جدایی و دروازه‌های نفی است. مقادیر در یک مدار صحیح مجموعه ای از اعداد صحیح هستند و دروازه‌ها اتحاد مجموعه، تقاطع مجموعه و مجموعه مکمل و همچنین جمع و ضرب عملیات حسابی را محاسبه می‌کنند.

ک مدار یک سه‌گانه است ${\displaystyle (M,L,G)}$ ، جایی که

• ${\displaystyle M}$ مجموعه‌ای از مقادیر است،
• ${\displaystyle L}$ مجموعه‌ای از برچسب‌های دروازه است که هر کدام تابعی از ${\displaystyle M^{i}}$ به ${\displaystyle M}$ برای برخی از اعداد صحیح غیر منفی ${\displaystyle i}$ (جایی که ${\displaystyle i}$ نشان دهنده تعداد ورودی‌های گیت)
• یک گراف جهت‌دار غیرمدور با برچسب از ${\displaystyle L}$ .

به گیت‌های درجه صفر ورودی یا برگ می‌گویند. به گیت‌های خارج از درجه ۰ خروجی می‌گویند. اگر لبه ای از دروازه وجود داشته باشد ${\displaystyle g}$ بسوی دروازه ${\displaystyle h}$ در نمودار ${\displaystyle G}$ سپس ${\displaystyle h}$ فرزند ان نامیده می‌شود ${\displaystyle g}$ . ما فرض می‌کنیم که نظمی در رئوس نمودار وجود دارد، بنابراین می‌توانیم از آن صحبت کنیم ${\displaystyle k}$ فرزند یک دروازه وقتی ${\displaystyle k}$ کمتر از درجه بیرونی دروازه است.

اندازه یک مدار تعداد گره‌های یک مدار است. عمق یک دروازه ${\displaystyle g}$ طول طولانی‌ترین مسیر در ${\displaystyle G}$ است شروع در ${\displaystyle g}$ تا یک دروازه خروجی به‌طور خاص، دروازه‌های خارج از درجه ۰ تنها دروازه‌های عمق ۱ هستند. عمق یک مدار حداکثر عمق هر دروازه است.

ارزش دقیق ${\displaystyle V(g)}$ از یک دروازه ${\displaystyle g}$ با درجهٔ ${\displaystyle i}$ و برچسب زدن ${\displaystyle l}$ به صورت بازگشتی برای همه گیت‌ها تعریف می‌شود ${\displaystyle g}$ .

${\displaystyle V(g)={\begin{cases}l&{\text{if }}g{\text{ is an input}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{otherwise,}}\end{cases}}}$

مقدار مدار مقدار هر یک از دروازه‌های خروجی است.

• مدار بولی
• پیچیدگی مدار
• کلاس پیچیدگی

• مشارکت‌کنندگان ویکی‌پدیا. «Circuit (computer science)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۵ ژانویه ۲۰۱۸.