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

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

تعریف رسمی

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

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

واژه شناسی

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

اندازه یک مدار تعداد گره های یک مدار است. عمق یک دروازه $g$ طول طولانی ترین مسیر در $G$ است شروع در $g$ تا یک دروازه خروجی به طور خاص، دروازه های خارج از درجه 0 تنها دروازه های عمق 1 هستند. عمق یک مدار حداکثر عمق هر دروازه است.

ارزیابی

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

$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)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۵ ژانویه ۲۰۱۸.