مطالعه با حل تمرین و تست تکمیل می‌شود. دانشجویان پس از حل تست باید به رفع اشکال آن بپردازند. ازاین‌رو، در اختیار داشتن پاسخنامه تشریحی تست‌ها بسیاری مهم است. این مقاله به بررسی پاسخ تشریحی کنکور ارشد کامپیوتر ۱۴۰۰ می‌پردازد. در انتهای مقاله نحوه دسترسی به پاسخ کلیدی کنکور کامپیوتر ۱۴۰۰ را نیز بیان خواهیم کرد.
روش های دسترسی به پاسخ تشریحی تست های کنکور ارشد کامپیوتر ۱۴۰۰
شما می‌توانید به یک از دو روش زیر به پاسخ تشریحی تست های کنکور ارشد ۱۴۰۰ دسترسی داشته باشید:
روش اول: استفاده از پلتفرم آزمون کنکور کامپیوتر
پلتفرم آزمون نه‌تنها پاسخنامه تشریحی تمامی تستهای کنکور ارشد کامپیوترمعرفی ارشد کامپیوتر
ارشد کامپیوتر چیست؟
این مقاله عالی به معرفی ارشد کامپیوتر می‌پردازد و درباره آینده رشته کامپیوتر و نحوه اپلای کردن توضیح می‌دهد و آی‌تیمعرفی فناوری اطلاعات (IT) - 7 دلیل برای انتخاب رشته آی تی در دانشگاه
آی تی چیست و چگونه پس از ظهور توانست در مدت فقط 20 سال تمام دنیا را فرا بگیرد و اکثر پول دنیا را ببلعد و پرطرفدارترین و پر درآمدترین مشاغل دنیا را در بر گیرد، در این صفحه به بررسی این موضوعات پرداخته شده برای هر درس را شامل می‌شود، بلکه محیطی برای ایجاد آزمون‌های شبیه‌سازی شده، رقابت با دیگر دانشجویان و… فراهم می‌آورد. برای کسب اطلاعات بیشتر درباره این پلتفرم می‌توانید به صفحه پلتفرم آزمون مراجعه کنید.
در زیر پاسخ تشریحی تست های کنکور کامپیوتر ۱۴۰۰ برای درس‌های هوش مصنوعی، سیستم عامل، پایگاه داده و نظریه زبانها و ماشین‌ها به همراه پاسخ تشریحی آمده است:
جواب تشریحی تستهای درس هوش مصنوعی کنکور کامپیوتر ۱۴۰۰
متوسط در حل یک مسئله ارضای قیود، از الگوریتم AC-3 استفاده شده است. فرض کنید هر قید شامل دو متغیر است و اندازه دامنه متغیرها، یکسان و برابر با d است. همین‌طور تعداد متغیرها برابر با n است. هر یال گراف قیود حداکثر چندبار نیاز به سازگار شدن دارد؟ مسائل ارضای محدودیت
گزینه 2 صحیح است.
در این روش تعداد دفعاتی که یک یال نیاز به سازگار شدن دارد برابر همان دامنه متغیرهاست چرا که در صورتی که تغییری در دامنه یکی از این متغیرها ایجاد شود همه یال‌های وارد شونده به آن دوباره به صف وارد می‌شوند و این تغییرات برای یک یال حداکثر برابر تعداد مقادیر دامنه متغیر یعنی d است.
متوسط محیط زیر با کنش‌های (action) بالا U، پایین D، چپ L و راست R را در نظر بگیرید. کنش‌هایی که باعث ورود به خانه S5 می‌شوند پاداش برابر با 10 دارند و خود S5 خانه وضعیت پایان است. سایر کنش‌ها پاداش $-1$ دارند. مقدار ضریب تخفیف (discount factor) برابر γ=0.9 را در نظر بگیرید. کدام گزینه صحیح است؟ عدم قطعیت
| $s3$ | $s2$ | $s1$ |
| $s6$ | $s5$ | $s4$ |
| $s9$ | $s8$ | $s7$ |
گزینه ۱ صحیح است.
مقادیر V و Q خواسته شده در این سؤال برابر تابع سیاست بهینه می‌باشند. (علامت ستاره بالای هر کدام بیانگر این موضوع است.)
تابع سیاست بهینه با شروع از حالت S1 ابتدا به یکی از حالات S2 یا S4 می‌رود و سپس به حالت نهایی S5 می‌رود. پاداش حرکت اول برابر -1و پاداش حرکت دوم برابر ۱۰ است که با احتساب ضریب تخفیف داریم:
$V^*(s1) = R_1 + \gamma R_2 = -1 + 0.9 \times 10 = 8$
مقدار Q خواسته شده چون براساس تابع سیاست بهینه می‌باشد، به صورت زیر محاسبه می‌شود:
$Q^*(s4) = R_D + \gamma V^*(s7) = -1 + \gamma V^*(s7)$
حالت s7 وضعیتی مشابه حالت s1 دارد، بنابراین مقدار V آن برابر با V حالت s1 می‌باشد:
$Q^*(s4) = R_D + \gamma V^*(s7) = -1 + 0.9 \times 8 = 6.2$
متوسط محیط زیر با وضعیت شروع S و وضعیت هدف G را در نظر بگیرید. فرض کنید خانه‌های خاکستری مسدود هستند و نمی‌توان به آنها وارد شد. همچنین در هر وضعیت چهار کنش بالا U، راست R، پایین D و چپ L با هزینه برابر قابل انجام هستند. اولویت انتخاب کنش‌ها هم در شرایط یکسان به ترتیب از راست به چپ D، R، U و L خواهد بود. اگر کنشی منجر به برخورد به خانه‌های مسدود یا دیوارها شود، عامل (agent) سر جایش می‌ماند. اگر جستجو گرافی (graph search) انجام شود، خانه A در شکل زیر چندمین گره برداشته شده از صف برای گسترش در روش‌های DFS و BFS خواهد بود؟ الگوریتم های جستجوی ناآگاهانه
| A | ||||||
| S | G | |||||
گزینه 2 صحیح است.
شکل زیر را در نظر بگیرید :
روش BFS :
درخت حاصل از جستجو به این روش و ترتیب بسط گره‌ها در ادامه نمایش داده شده است. همانطور که در شکل زیر مشخص است پس از S تمامی فرزندان آن بسط داده می‌شوند و درنهایت نوبت به فرزندان گره C می‌رسد و گره A از فرزندان این گره چون کنش UP اولویت بیشتر دارد زودتر به صف اضافه شده و در نتیجه زودتر هم نوبت به بسط آن می‌رسد و به عنوان گره ۶ ام بسط داده می‌شود.
روش DFS :
درخت حاصل از جستجو به این روش و ترتیب بسط گره‌ها در ادامه نمایش داده شده است. همانطور که در شکل زیر مشخص است پس از S فرزند اول آن یعنی C و پس از آن گره A بسط پیدا میکند و در واقع گره A به عنوان گره ۳ ام بسط داده می‌شود.
اعداد بدست آمده در هیچکدام از گزینه‌ها موجود نیستند اما می‌توان با اغماض گزینه دوم را بعنوان پاسخ سوال در نظر گرفت.
متوسط محیط زیر با وضعیت شروع S و وضعیت هدف G را درنظر بگیرید. فرض کنید خانه‌های خاکستری مسدود هستند و نمی‌توان به آنها وارد شد. همچنین در هر وضعیت چهار کنش بالا U، راست R، پایین D و چپ L با هزینه برابر واحد قابل انجام هستند. اولویت انتخاب کنش‌ها هم در شرایط یکسان به ترتیب از راست به چپ U ،L ،D و R خواهد بود و برای برداشته شدن از صف هم در شرایط کاملاً یکسان از نظر معیار صف اولویت گره‌ای که زودتر در صف گذاشته شده برداشته می‌شود. اگر کنشی منجر به برخورد به خانه‌های مسدود یا دیوارها شود، عامل (agent) سر جایش می‌ماند. اگر جستجو گرافی (graph search) با روش \( {A}^* \) با تابع ابتکاری (heuristic) فاصله‌ی منهتن تا هدف انجام شود، کدام ترتیب در برداشته شدن از صف جهت گسترش گره‌های مشخص B ،A و C (از چپ به راست) درست است؟ الگوریتم های جستجوی آگاهانه
| C | ||||||
| G | A | S | ||||
| B | ||||||
گزینه 1 صحیح است.
با توجه به شکل زیر درخت حاصل از جستجو A* در این سوال در ادامه رسم شده است. برای اجرای این روش در این مسئله باید توجه داشت که اولویت انتخاب کنش‌ها در شرایط یکسان به ترتیب از راست به چپ U ،L ،D و R خواهد بود و برای برداشته شدن از صف هم در شرایط کاملاً یکسان از نظر معیار صف اولویت گره‌ای که زودتر در صف گذاشته شده برداشته می‌شود. همچنین در محاسبه فاصله منهتن برای خانه‌ها به عنوان تابع ابتکاری دیوار را در نظر نمی‌گیریم.
در مرحله اول از بین فرزندان خانه S، به خانه A می‌رویم که f(n) کمتری دارد (در هر گره در درخت زیر مقدار f(n) در کنار نام گره نوشته شده است). پس از آن فرزندان گره A نیز به صف اضافه می‌شوند و در این مرحله از آن‌جایی که مقدار f(n) برای تمامی گره‌ها یکسان است گره‌ای که زودتر در صف قرار داده شده است یعنی گره B انتخاب می‌شود. پس در کل ابتدا گره A و سپس گره B انتخاب شد و پاسخ سوال گزینه ۱ می‌باشد.
متوسط در کدام یک از گراف‌های قیود زیر با n رأس، الزاماً می‌توان مسئله ارضای قیود را در زمان چندجمله‌ای نسبت به تعداد متغیرها و اندازه‌ی مجموعه مقادیر مجاز متغیرها حل کرد؟ مسائل ارضای محدودیت
گزینه 2 صحیح است.
پیچیدگی محاسباتی مسئله ارضا محدودیت در صورتی که گراف مسئله به شکل درخت باشد از مرتبه $O(nd^2)$ که برحسب تعداد رئوس و دامنه مقادیر مجاز چندجمله‌ای است اما در حالتی که گراف با فقط یک دور نیز داشته باشیم می‌توانیم از طریق حذف گره و با استفاده از روش cutset مسئله را حل کنیم. در این مسئله می‌توان با حذف یک گره که در دور گراف قرار دارد، یک درخت و یک مجموعه cutset ساخت و مرتبه زمانی حل این مسئله با این روش از مرتبه $O((n-c)d^{2+c})$ می‌باشد که در آن c تعداد اعضای cutset می‌باشد که در اینجا برابر با ۱ است و همچنین بخش $O((n-c)d^2)$ مرتبه زمانی حل درخت حاصل و $O(d^c)$ مرتبه زمانی مقداردهی به اعضای cutset می‌باشد.
دشوار برای حل یک مسئله‌ی جستجو، از روش‌های محلی تپه‌نوردی استفاده کرده‌ایم. فرض کنید احتمال موفقیت در جستجویی که از یک حالت تصادفی شروع می‌شود، برابر با 25 درصد است. زمانی که جستجو موفقیت‌آمیز باشد، به صورت متوسط نیاز به طی کردن 7 گام دارد و در صورتی که به یک کمینه محلی غیر بهینه همگرا شود، به صورت متوسط 9 گام طی می‌شود. به منظور حصول اطمینان از به جواب رسیدن روش، در صورت همگرایی به کمینه محلی غیر بهنیه، از حالت تصادفی اولیه دیگری جستجو را آغاز میکنیم. به صورت متوسط چند گام برای رسیدن به پاسخ بهینه سراسری باید طی شود؟ مسائل ارضای محدودیت
گزینه 3 صحیح است.
نکات :
اگر احتمال موفقیت الگوریتم جستجو محلی با شروع مجدد تصادفی در هر بار برابر p باشد آنگاه متوسط تعداد دفعات شروع مجدد برای رسیدن به پاسخ بهینه عمومی در این الگوریتم برابر $\frac{1}{p}$ می‌باشد.
(برای اثبات نکته بالا باید از تعریف امید ریاضی برای متغیر دارای توزیع هندسی کمک گرفت :
$E(X) = \sum_{k=1}^\infty k(1-p)^{k-1} p $
$ \ \ \ \ \ \ \ \ \ = p \sum_{k=1}^\infty k(1-p)^{k-1} $ $ \ \ \ \ \ \ \ \ \ = p(\sum_{k=1}^\infty k(1-p)^{k-1} + \sum_{k=2}^\infty k(1-p)^{k-1} + \sum_{k=3}^\infty k(1-p)^{k-1} + .... ) $ $ \ \ \ \ \ \ \ \ \ = p( \frac{1}{1-(1-p)} + \frac{1-p}{1-(1-p)} + \frac{(1-p)^2}{1-(1-p) } + ... $
$ \ \ \ \ \ \ \ \ \ = 1 + (1-p) + (1-p)^2 + ... $
$ \ \ \ \ \ \ \ \ \ = 1 + (1-p) + (1-p)^2 + ... $
$ \ \ \ \ \ \ \ \ \ = \frac{1}{1-(1-p)} $ $ \ \ \ \ \ \ \ \ \ = \frac{1}{p} $
اگر احتمال موفقیت الگوریتم جستجو محلی با شروع مجدد تصادفی در هر بار برابر p باشد آنگاه تعداد گام‌های مورد انتظار برای رسیدن به پاسخ بهینه برابر است با:
تعداد کل گام‌ها : ( تعداد گام‌ها در تپه‌نوردی در حالت موفق) + (تعداد گام‌ها در تپه‌نوردی در حالت ناموفق) $(\frac{1}{p}-1)$
پاسخ سوال :
احتمال موفقیت = 0.25= p
تعداد گام‌ها در تپه‌نوردی در حالت ناموفق = 9
تعداد گام‌ها در تپه‌نوردی در حالت موفق = 7
تعداد کل گام‌ها = $(4-1) × 9+7=34$
متوسط فرض کنید برای حل یک مسئله‌ی جستجوی خصمانه از روش درخت min-max با هرس α - β استفاده میکنیم. در یکی از مراحل میانی که مقدار max را تخمین می‌زنیم، مقدار α برابر با 4، مقدار β برابر با 3 و تخمین فعلی حالت max برابر با صفر است. فرض کنید در این مرحله، مقدار یکی از حالت‌های بعدی حالت max مذکور را به صورت بازگشتی محاسبه کرده‌ایم. به ازای کدام مقدار برای حالت بعدی، حالت max مذکور را هرس میکنیم؟ بازی های رقابتی
گزینه 4 صحیح است.
در این سوال گفته شده است که مقدار آلفا برابر ۴ و مقدار بتا برابر ۳ می‌باشد و این به این معنی است که در همین حالت نیز شرط هرس برقرار است و نیازی به بررسی حالات بعدی نیست و می‌توان حالت max مذکور را هرس کرد. اما بیاید فرض کنیم که در صورت سوال مقدار آلفا داده نشده است در این صورت برای اینکه بخواهیم شرط هرس برقرار شود باید مقدار تخمینی برای گره بعدی بیشتر مساوی ۳ باشد تا پس از بررسی این حالت مقدار آلفا برای حالت max برابر با این عدد شده و امکان هرس برای حالت max مذکور در شاخه‌ای که مقدار تخمینی آن صفر است اتفاق بیفتد.
دشوار کدام گزینه در مورد حل مسائل CSP درست است؟ مسائل ارضای محدودیت
گزینه 4 صحیح است.
گزینه ۱ : این گزینه نادرست است چرا که در AC سازگاری یال‌ها بررسی می‌شود در حالیکه در forward check در هر مرحله با مقداردهی به یکی از متغیرها، دامنه سایر متغیرها با توجه به این مقداردهی بروز شده و مقادیر متناقض حذف می‌شوند.
گزینه ۲ : این گزینه نادرست است و استفاده از این روش‌ها منجر به از دست رفتن راه‌حل‌ها نمی‌شود.
گزینه ۳ : ممکن است علت عدم وجود راه حل برای این نوع مسائل وجود محدودیت‌ها بیش از دوتایی باشد و این نوع محدودیت‌ها در روش AC3 کشف نمی‌شوند و نمی‌توان گفت در حالتی که راه‌حل وجود ندارد این الگوریتم آن را یافت میکند و به دامنه تهی می‌رسد.
گزینه ۴ : در مسائل ارضا محدودیت در حالتی که بدنبال تمام جواب‌های مسئله باشیم استفاده از تکنیک مشخص کننده ترتیب مقادیر تاثیر در بهبود جواب ندارد چرا که باید در نهایت همه مقادیر ممکن برای یک متغیر بررسی شوند اما تکنیک مشخص کننده ترتیب انتخاب متغیرها می‌تواند مفید باشد و باعث شود مسیر‌هایی که به جواب نمی‌رسند زودتر پیدا شده و حذف شوند.
توضیح: گزینه 4 در دفترچه بصورت زیر بوده است که ما برای درست شدن این تست گزینه 4 را تغییر داده‌ایم
اگر در یک مسئله CSP دنبال همه‌ی جواب‌ها باشیم، استفاده از تکنیک‌های مشخص‌کننده‌ی ترتیب متغیرها (variable ordering) و ترتیب مقادیر (value ordering) تأثیری در بهبود سرعت نخواهد داشت.
پاسخ این سوال در ابتدا گزینه ۱ اعلام شده بود و سپس این سوال حذف شد.
جواب تشریحی تستهای درس سیستم‌های عامل کنکور کامپیوتر ۱۴۰۰
آسان کدام سطح از RAID را Disk mirroring می‌گویند؟ مدیریت I/O و دیسک
گزینه 2 صحیح است.
RAID مخفف (redundant Array of Independent) است. از تکنیک RAID برای افزایش سرعت خواندن و نوشتن، افزایش تحمل‌پذیری در برابر خطا و افزایش فضای ذخیره‌سازی استفاده می‌شود. سطوح مختلفی از مکانیسم RAID وجود دارد که هفت سطح آن مورد توافق همه است. (از 0 تا 6)
در RAID چهار تکنیک (برای تحقق اهداف RAID) مورد استفاده قرار می‌گیرد و یکی از این تکنیک‌ها mirroring است. از این تکنیک برای افزایش قابلیت اطمینان استفاده می‌شود. به این صورت که داده‌های اصلی روی دو دیسک به طور یکسان نوشته می‌شوند. و در صورت خرابی یک دیسک، داده‌ها از بین نمی‌روند.
تکنیک‌های دیگر عبارت اند از: Striping, Parity, Hamming code
هریک از این تکنیک‌ها در سطوح مختلف مورد استفاده قرار می‌گیرند. Mirroring در RAID سطح 1 استفاده می‌شود.
دشوار کدام مورد سیستم‌عامل را مجبور میکند دستورات $s_4،~ s_3، ~ s_2،~ s_1$ که به ترتیب در پردازه‌های همروند $p_4، ~p_3، ~ p_2، ~p_1$ قرار دارند به همان ترتیب $s_4،~ s_3، ~ s_2،~ s_1$ اجرا کند؟ (مقدار اولیه سمافورها ∘ = a = b = c) انحصار متقابل
گزینه 1 صحیح است.
با توجه به مقادیر اولیه سمافورها ($a=b=c=0$) فقط دستور $S_1$ در ابتدا می‌تواند اجرا شود.
بررسی گزینه 1: این گزینه صحیح است. زیرا اجرای فرایندهای $P_3$ ، $P_2$ ، $P_1$ و $P_4$ فقط منجر به اجرای دستورات $S_3$ ، $S_2$ ، $S_1$ و $S_4$ به همین ترتیب می‌شود.
علت رد گزینه 2: می‌توان سناریویی را پیدا کرد که اجرای فرایندهای $P_3$ ، $P_2$ ، $P_1$ و $P_4$ منجر به اجرای دستورات به ترتیب $S_2$ ، $S_3$ ، $S_1$ و $S_4$ شود. (در صورتی که فرایندها به این ترتیب اجرا شوند: $P_2$ ، $P_3 $ ، $P_1$ و $P_4$)
علت رد گزینه 3: در این گزینه اجرای فرایندهای $P_3$ ، $P_2$ ، $P_1$ و $P_4$ می‌تواند منجر به اجرای دستورات $S_3$ ، $S_2$ ، $S_1$ و $S_4$ به همین ترتیب شود. اما سناریوی دیگری را می‌توان یافت که تمامی فرایندها پس از اجرای فرایند 1 به خواب ابدی بروند. (در صورتی که فرایند ها به این ترتیب اجرا شوند: $P_2$ ، $P_3$ ، $P_1$ و $P_4$)
علت رد گزینه 4: این گزینه نادرست است زیرا اجرای فرایندهای $P_3$ ، $P_2$ ، $P_1$ و $P_4$ منجر به خواب ابدی می‌شود.
متوسط فرض کنید که طول آدرس مجازی 47 بیت و اندازه صفحه 16KB و هر مدخل از جدول صفحه 8 بایت باشد. اگر بخواهیم هر جدول صفحه تنها در یک صفحه ذخیره شود، از جدول صفحه چند سطحی استفاده شود؟ حافظه مجازی
گزینه 2 صحیح است.
فرمت آدرس منطقی:
| $Offset$ | $PT_n$ | ... | $PT_2$ | $PT_1$ |
با توجه به صورت سوال هر جدول صفحه جزئی باید در یک قاب قرار گیرد. برای محاسبه تعداد سطرهای جدول صفحه جزئی باید اندازه قاب را (که برابر است با اندازه جدول صفحه جزئی) بر اندازه عرض جدول صفحه ($=e$ مدخل) تقسیم کنیم:
تعداد سطرهای جدول صفحه جزئی $=\frac{\text{اندازه }\ \text{قاب }\ }{\text{عرض }\ \text{جدول }\ \text{صفحه }\ }=\frac{2^4 × 2^{10}B}{2^3B}=2^{11}B$
حال لازم است تعداد بیت‌های offset را محاسبه کنیم تا بتوانیم فرمت آدرس منطقی را به دست آوریم:
$pageSize=16KB=2^4\times 2^{10}=2^{14}=2^x\to x=14=offset$
برای محاسبه تعداد سطوح جدول صفحه کافیست از سمت راست به اندازه تعداد بیت‌هایی که برای نشان دادن سطرهای جدول صفحه جزئی استفاده میکنیم (در اینجا 11 بیت با توجه به محاسبات بالا) جدا کنیم:
تعداد سطوح برابر با 3 است.
توجه: در مجموع طول آدرس منطقی با توجه به گفته سوال باید 47 بیت شود.
دشوار الگوریتم زیر برای حل مسئله ناحیه بحرانی (Critical-Problem) را در نظر بگیرید. در این الگوریتم، در حالتی که تنها دو پردازه ∘P و P1 وجود داشته باشد، متغیرهای flag و turn بین این دو پردازه مشترک هستند: انحصار متقابل
Boolean flag [2]:/*initially false*/
Int turn;
با فرض اینکه ساختار پردازه $(i=0\;\; OR\;\; 1) P_i$ به صورت زیر باشد، کدام گزینه صحیح است؟
|
do{
Flag[i]=true;
While (flag[j]) {
If (turn==j) {
flag[i]=false;
while (turn==j)
:/*do nothing*/
Flag[i]=true;
}
}
/*critical section*/
Turn = j;
flag[i]=false;
/*remainder section*/
} while (true);
|
گزینه 4 صحیح است.
این الگوریتم تلاش چهارم Dekker است. مراحل این الگوریتم به صورت زیر است:
1- Set کردن flag فرایند و کنترل flag فرایند مقابل.
2- اگر flag مقابل بالا بود به اندازه زمان تصادفی flag فرایند پایین می‌رود (false می‌شود) و مجدد بالا می‌رود.
3- در نهایت ورود به ناحیه بحرانی.
این الگوریتم تمامی شروط انحصار متقابل، انتظار محدود و پیشرفت را تضمین میکند.
آسان یک کامپیوتر دارای m چاپگر از یک نوع است. این چاپگرها به وسیله 3 پردازه A و B و C استفاده می‌شوند که در زمان بیشترین نیاز (حداکثر تقاضا) به ترتیب به 3 و 4 و 6 چاپگر نیاز دارند. کمترین مقدار m که برای آن هیچ وقت در این کامپیوتر بن بست پیش نیاید چند است؟ بن بست
گزینه 2 صحیح است.
راه حل بدون استفاده از فرمول:
فرض کنید همه فرآیندها منابع خود به جز یک منبع را در اختیار دارند یعنی فرایند A دو منبع، B سه منبع و C پنج منبع در اختیار دارند که جمعا 10 منبع می‌شود. اگر یک منبع دیگر اضافه شود یکی از فرایندها می‌تواند کار خود را به اتمام برساند و منابعی که در اختیار دارد را آزاد کند.
بنابراین حداقل 11 منبع نیاز است که بن‌بستی رخ ندهد.
راه حل با استفاده از فرمول:
در یک سیستم با n فرایند و m منبع از یک نوع، اگر شرط زیر برقرار باشد بن‌بست رخ نمی‌دهد:
$\sum^n_{i=1}{Request\left[i\right]\lt m+n}$ $3+4+6<m+3\ \to m>10\to m\ge 11$
آسان دو پردازه متناوب با مشخصات زیر مفروض است. کدام گزینه بزرگترین مقدار x را برای پردازه 2 نشان می‌دهد به نحوی که زمانبندی قبضه‌ای (نرخ یکنواخت) Rate Monotonic امکان پذیر باشد؟ فرآیندها و زمانبندی پردازنده‌ها
| Cpu Time | Period | |
| 25 | 50 | $P_1$ |
| x | 80 | $P_2$ |
گزینه 3 صحیح است.
زمانبندی تمام وقایع متناوب در یک سیستم بی‌درنگ بر اساس رابطه زیر ممکن است قابل انجام باشد:
$\sum^m_{i=1}{\frac{t_i}{p_i}}\le 1$
در این رابطه m تعداد فرایندها، $t_i$ مدت زمان اجرای فرایند و $p_i$ دوره تناوب فرایند است.
توجه: یک سیستم بی‌درنگ اگر با محاسبه این فرمول قابل زمانبندی نباشد به صورت عملی نیز قابل زمانبندی نیست. اما اگر در این فرمول صدق کند، به طور قطع نمی‌توان گفت که این سیستم قابل زمانبندی است و باید برای آن نمودار گانت بکشیم و بررسی کنیم.
در این سوال چون بزرگترین مقدار x را خواسته بهتر است از گزینه‌هایی که بیشترین مقدار را دارند بررسی را شروع کنیم.
بررسی گزینه 4:
$\sum^2_{i=1}{\frac{t_i}{p_i}}=\frac{25}{50}+\frac{35}{80}=0.94\le 1$
این مقادیر از لحاظ تئوری درست است. برای اینکه ببینیم از لحاظ عملی نیز قابل زمانبندی است یا خیر، نمودار گانت می‌کشیم.
با توجه به این نمودار واضح است که این زمانبندی قابل انجام نیست. زیرا فرایند p2 باید در لحظه 80 کار خود را به پایان می‌رساند، نه 85. (چون دوره تناوب این فرایند 80 ثانیه است و در لحظه 80 رویداد راه انداز p2 مجدد رخ می‌دهد)
بررسی گزینه 3:
$\sum^2_{i=1}{\frac{t_i}{p_i}}=\frac{25}{50}+\frac{30}{80}=0.875\le 1$
این مقادیر از لحاظ تئوری درست است. برای اینکه ببینیم از لحاظ عملی نیز قابل زمانبندی است یا خیر، نمودار گانت می‌کشیم.
با توجه به نمودار بالا مهلت‌های زمانی فرایندها برآورده شده است زیرا در لحظه 400 به تناوب رسیده‌اند و فرایندها مجدد یکدیگر را ملاقات کرده‌اند.
چون در صورت سوال بزرگترین x را خواسته و گزینه‌های دیگر از 30 کمترند، پس پاسخ سوال گزینه 3 است.
متوسط در یک الگوریتم برنامه ریزی اولویت‌دار که پنج پردازه و اولویت‌های آنها به صورت زیر است، وجود دارد. میانگین زمان انتظار چند میلی ثانیه است؟ فرآیندها و زمانبندی پردازنده‌ها
فرض کنید که هر چه مقدار اولویت کمتر باشد، اولویت پردازه بیشتر است. یعنی پردازه $P_4$ دارای کمترین اولویت و پردازه $P_2$ دارای بیشترین اولویت است.
| پردازه | زمان | اولویت |
| $P_1$ | $10_{ms}$ | 3 |
| $P_2$ | $1_{ms}$ | 1 |
| $P_3$ | $2_{ms}$ | 4 |
| $P_4$ | $1_{ms}$ | 5 |
| $P_5$ | $5_{ms}$ | 2 |
اگر زمان ورود فرایند ها را ندادند، صفر در نظر بگیرید.
نمودار گانت این فرایند به صورت زیر است:
میانگین زمان انتظار فرایندها $=\frac{\sum^n_1{\mathrm{(}\text{زمان}\mathrm{\ }\text{خروج}\mathrm{)-(}\text{زمان}\mathrm{\ }ورود\mathrm{)}-\mathrm{(}\text{زمان}\mathrm{\ }\text{پردازش}\mathrm{)}}}{n}$
میانگین زمان انتظار فرایندها $=\frac{\left(16-10-0\right)+\left(1-1-0\right)+\left(18-2-0\right)+\left(19-1-0\right)+(6-5-0)}{5}=\frac{6+0+16+18+1}{5}=8.2$
پاسخ تشریحی تستهای درس پایگاه داده کنکور کامپیوتر ۱۴۰۰
متوسط
هم ارزی‌های جبر رابطه‌ای زیر را در نظر بگیرید. این هم ارزی‌ها ممکن است همواره درست باشند، در بعضی شرایط درست باشند، یا همواره نادرست باشند. در این عبارت‌ها، R یک رابطه (Relation)، ci ها شرط‌هایی بر روی R و ai ها زیر مجموعه‌هایی از صفت‌های R هستند.
کدام هم ارزی همواره درست است؟ پایگاه داده رابطه‌ای
کدام هم ارزی همواره درست است؟ پایگاه داده رابطه‌ای
پاسخ گزینه 1 است.
گزینه 1: $\sigma$ خاصیت جابجایی دارد.
گزینه 2: $\pi$ خاصیت جابجایی ندارد و $\pi$ درونی به $\pi$ بیرونی وابسته است و در $\pi_{a_1}\left(\pi_{a_2}\left(R\right)\right)$ باید $a_1\subseteq a_2$ باشد. وگرنه تهی برمی‌گرداند.
بنابراین تنها درصورتی‌که
$\left\{ \begin{array}{c}
a_1\subseteq a_2 \\
a_2\subseteq a_1 \end{array}
\right.
$ $a_1=a_2\Leftarrow$ برقرار باشد این گزینه صحیح است.
a_1\subseteq a_2 \\
a_2\subseteq a_1 \end{array}
\right.
$ $a_1=a_2\Leftarrow$ برقرار باشد این گزینه صحیح است.
گزینه 3) مثال نقض:
همانطور که در مثال آمده دو جدول $R_2\neq R_1$
گزینه 4)
اگر $a_1$ شامل فقط ستون $B$ و بطور کلی $a_1\subseteq a_2$ بود آنگاه رابطه هم‌ارزی درست بود.
دشوار
رابطه $R(A,B,C,D)$ و این وابستگی‌های تابعی را در نظر بگیرید: $B \to C~ ;~CD \to B$
کدام گزینه در مورد رابطه R درست است؟ طراحی پایگاه داده
کدام گزینه در مورد رابطه R درست است؟ طراحی پایگاه داده
گزینه 4 صحیح است.
A و D در سمت راست رابطه وجود ندارند پس قطعا جزئی از کلید کاندید می‌باشند. با گسترش A و D به‌تنهایی نمی‌توان به R رسید بنابراین برای پیدا کردن کلید کاندید B و C را که در سمت چپ رابطه داریم را هرکدام به‌تنهایی به AD اضافه میکنیم. اگر به کل R رسیدیم کلید کاندید است.
A و D در سمت راست رابطه وجود ندارند پس قطعا جزئی از کلید کاندید می‌باشند. با گسترش A و D به‌تنهایی نمی‌توان به R رسید بنابراین برای پیدا کردن کلید کاندید B و C را که در سمت چپ رابطه داریم را هرکدام به‌تنهایی به AD اضافه میکنیم. اگر به کل R رسیدیم کلید کاندید است.
اضافه کردن B به D و A
$\left. \begin{array}{c}
B\to C \\
\text{جزء}\mathrm{\ }\text{کلید}\ A,B,D \end{array}
\right\}\Rightarrow\text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\ ABD
$
B\to C \\
\text{جزء}\mathrm{\ }\text{کلید}\ A,B,D \end{array}
\right\}\Rightarrow\text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\ ABD
$
$\left. \begin{array}{c}
\text{جزء}\mathrm{\ }\text{کلید}\ A,C,D \\
CD\to B \end{array}
\right\}\Rightarrow\text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\ \mathrm{ACD}
$
\text{جزء}\mathrm{\ }\text{کلید}\ A,C,D \\
CD\to B \end{array}
\right\}\Rightarrow\text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\ \mathrm{ACD}
$
این رابطه دو کلید کاندید ABD و ACD دارد.
[غیرکلید $\rightarrow$ جزء کلید] نداریم $\Leftarrow$ 2NF است.
* در این رابطه کلاً غیرکلید نداریم و A و B و C و D همگی جزء کلید هستند. B در کلید کاندید ABD و C در کلید کاندید ACD هردو جزء کلید محسوب می‌شوند.
[غیرکلید $\rightarrow$ غیر کلید] نداریم $\Leftarrow$ 3NF است.
[جزء کلید $\rightarrow$ جزء کلید] داریم $\Leftarrow$ BCNF نیست.
توجه: از همان ابتدا بعد از پیدا کردن کلیدهای کاندید با توجه به اینکه هیچ غیرکلیدی نداشتیم می‌توان فهمید رابطه 3NF و 2NF است.
دشوار
رابطه $R(A,B,C,D,E)$ و این وابستگی‌های تابعی را در نظر بگیرید : $AB \to CDE ~; ~E \to BC$
تعداد کلیدهای کاندید R چند تاست؟ طراحی پایگاه داده
تعداد کلیدهای کاندید R چند تاست؟ طراحی پایگاه داده
گزینه 2 صحیح است.
A سمت راست رایطه نداریم. بنابراین قطعا جزئی از کلید است. با گسترش A به تنهایی نمی‌توان به کل R رسید پس از سمت چپ R برای یافتن کلید کاندید B و E را امتحان میکنیم.
A سمت راست رایطه نداریم. بنابراین قطعا جزئی از کلید است. با گسترش A به تنهایی نمی‌توان به کل R رسید پس از سمت چپ R برای یافتن کلید کاندید B و E را امتحان میکنیم.
$\left. \begin{array}{c}
\text{جزء}\mathrm{\ }\text{کلید}\ A \\
\text{جزء}\mathrm{\ }\text{کلید}\ B \\
در\mathrm{\ }\text{رابطه}\mathrm{\ }AB\to CDE \end{array}
\right\}\Rightarrow \ \text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\ \mathrm{AB}
$
\text{جزء}\mathrm{\ }\text{کلید}\ A \\
\text{جزء}\mathrm{\ }\text{کلید}\ B \\
در\mathrm{\ }\text{رابطه}\mathrm{\ }AB\to CDE \end{array}
\right\}\Rightarrow \ \text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\ \mathrm{AB}
$
$\left. \begin{array}{c}
\text{جزء}\mathrm{\ }\text{کلید}\ A \\
\text{جزء}\mathrm{\ }\text{کلید}\ E \\
در\mathrm{\ }\text{رابطه}\mathrm{\ }E\to BC \end{array}
\right\}\Rightarrow \ \mathrm{AB}\mathrm{\to }\mathrm{CDE}\mathrm{\Rightarrow }\text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\mathrm{\ }AE
$
\text{جزء}\mathrm{\ }\text{کلید}\ A \\
\text{جزء}\mathrm{\ }\text{کلید}\ E \\
در\mathrm{\ }\text{رابطه}\mathrm{\ }E\to BC \end{array}
\right\}\Rightarrow \ \mathrm{AB}\mathrm{\to }\mathrm{CDE}\mathrm{\Rightarrow }\text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\mathrm{\ }AE
$
کلید کاندید باید کمینه باشد بنابراین این رابطه 2 کلید کاندید دارد.
دشوار
این شمای پایگاه داده را در نظر بگیرید:
زبان و پرس و جوی SQL
Student (sid, sname, age)
Course (cid, cname. credits)
Takes (sid ,cid, grade)
می‌خواهیم sid دانشجویانی را پیدا کنیم که هم در درس Database و هم در درس Math ثبت‌نام کرده‌اند. کدام پرس‌وجوی SQL برای این منظور مناسب است؟
I. SELECT T1.sid
FROM Course C1. Takes T1
WHERE C1.cid = T1.cid AND C1.cname = Database'
INTERSECT
SELECT T2.sid
FROM Course C2, Takes T2
WHERE C2.cid = T2.cid AND C2.cname = ‘Math’
II. SELECT T1.sid
FROM Course C1, Takes T1
WHERE C1.cid = T1.cid AND C1.cname = ‘Database’
AND T1.sid IN (SELECT T2.sid
FROM Course C2, Takes T2
WHERE C2.cid = T2.cid AND C2.cname = ‘Math’)
III. SELECT T1.sid
FROM Course C1. Takes T1
WHERE C1.cid = T1.cid AND C1.cname = ‘Database’
AND EXISTS (SELECT *
FROM Course C2, Takes T2
WHERE C2.cid = T2.cid AND C2.cname = ‘Math’ AND C2.sid = C1.sid)
گزینه 3 صحیح است.
I: اشتراک id دانشجویانی که درس Database را گرفتهاند با id دانشجویانی که درس Math را گرفتهاند برمی‌گرداند $\gets$ درست است.
II: از بین id هایی که درس ریاضی Math گرفته اند، id دانشجویانی که درس پایگاه داده Database را هم گرفته‌اتد برمی‌گرداند $\gets$ درست است.
III: در جدول Course ستونی به نام Sid وجود ندارد و بطور کلی C1.Sid و C2.Sid غلط می‌باشد.
دشوار
شمای رابطه‌ای زیر، پایگاه داده موسسات آموزش هنر است:
پایگاه داده رابطه‌ای
در این پایگاه داده اسامی هنرجویانی که در هر موسسه عضو هستد ذخیره شده است.
جدول هنرهای مورد علاقه نام رشته‌های هنری مورد علاقه هر هنرجو را نشان می‌دهد.
جدول دوره‌های هنری نشان می‌دهد در هر موسسه چه رشته‌های هنری‌ای ارائه می‌شود.
Studwnt(SID , Name)
Institute(IId , IName , IAddress)
Membership(SID , IId)
Faviorate Field (SID, Field)
Offered Field(IID , Field)
کدام جبر رابطه‌ای لیست تمام هنرجوها را می‌دهد که فقط در موسسه‌هایی عضوند که هیچ رشته هنری خارج از علاقه‌مندی آنها را ارائه نمی‌دهد؟
گزینه 4 صحیح است.
کاربر به تمام رشته‌هایی که مؤسسه‌ای که ثبت نام کرده است ارائه می‌دهد، علاقه دارد.
گزینه 1) id دانشجویانی را برمی‌گرداند که در مؤسسه ای که عضو هستند حداقل یک علاقه‌مندی دارند. (نادرست)
گزینه 2) id دانشجویانی را برمی‌گرداند که در مؤسسه ای که عضو هستند هیچ علاقه‌مندی ندارند. (نادرست)
گزینه 3) id دانشجویانی را برمی‌گرداند که در مؤسسه ای که عضو هستند حداقل یک علاقه‌مندی دارند. (نادرست)
گزینه 4) با توجه به رابطه‌ی تقسیم $A\div B=\pi_x\left(A\right)-\pi_x\left(\left(\pi_x\left(A\right)\times B\right)-A\right)$ این رابطه همان تقسیم است و id دانشجویانی که به همه دروس ارائه شده مؤسسه‌ای که عضو آن هستند را برمی‌گرداند.
دشوار
حاصل تجزیه رابطه زیر براساس 3NF چند رابطه خواهد بود؟
طراحی پایگاه داده
$R = (A,B,C,D,E)$
$A \to B,C$
$B,C \to A,D$
$D \to E$
گزینه 2 صحیح است.
E و D و C و B و A همگی در سمت راست رابطه وجود دارند. برای یافتن کلید از کمترین های سمت چپ مانند A امتحان میکنیم.
$\left. \begin{array}{c}
\text{فرض}\mathrm{\ }\text{میکنیم}\mathrm{:\ }\text{جزء}\mathrm{\ }\text{کلید}\ A \\
در\mathrm{\ }\text{رابطه}\ A\to B,C \end{array}
\right\}\to \left. \begin{array}{c}
\text{قبلا}\mathrm{\ }\text{رسیدیم}\mathrm{:}\ A,B,C \\
در\mathrm{\ }\text{رابطه}\mathrm{:}\ B,C\to A,D \end{array}
\right\}\to \left. \begin{array}{c}
\text{قبلا}\mathrm{\ }\text{رسیدیم}\mathrm{:}\ A,B,C,D \\
در\mathrm{\ }\text{رابطه}mathrm{:}\ D\to E \end{array}
\right\}\downarrow
$
\text{فرض}\mathrm{\ }\text{میکنیم}\mathrm{:\ }\text{جزء}\mathrm{\ }\text{کلید}\ A \\
در\mathrm{\ }\text{رابطه}\ A\to B,C \end{array}
\right\}\to \left. \begin{array}{c}
\text{قبلا}\mathrm{\ }\text{رسیدیم}\mathrm{:}\ A,B,C \\
در\mathrm{\ }\text{رابطه}\mathrm{:}\ B,C\to A,D \end{array}
\right\}\to \left. \begin{array}{c}
\text{قبلا}\mathrm{\ }\text{رسیدیم}\mathrm{:}\ A,B,C,D \\
در\mathrm{\ }\text{رابطه}mathrm{:}\ D\to E \end{array}
\right\}\downarrow
$
$\rightarrow$$\text{رسیدیم}\ R(A,B,C,D,E)\ \text{کلید}\mathrm{\ }\text{کاندید}\mathrm{\ }\text{است}\mathrm{\ }\mathrm{\ }\rightarrow\mathrm{\ }\text{به}\mathrm{\ }\text{کل}\mathrm{\ }\mathrm{A}$
صفت چند مقداری و مرکب و جدول تودرتو نداریم پس 1NF است.
غیرکلید $\rightarrow$ جزء کلید هم نداریم پس 2NF هم هست ولی (غیرکلید) $D\rightarrow E$ (غیرکلید) داریم و 3NF نیست.
برای نرمال‌سازی رابطه را به دو رابطه‌ی مجزای $R_1$ که $D$ درآن کلید خارجی و $R_2$ که $D$ درآن کلید اصلی می‌باشد تبدیل میکنیم.
$R_1:A\rightarrow B,C$ $R_2:D\rightarrow E$ $B,C\rightarrow A,D$
جواب تشریحی تستهای درس نظریه زبانها و ماشین‌ها کنکور کامپیوتر ۱۴۰۰
متوسط
کدام‌یک از گزاره‌های زیر درست است؟
خانواده زبان‌های بازگشتی و شمارش پذیر بازگشتی
گزینه 2 صحیح است.
مجموعه تمام ماشین‌های تورینگ شمارا هستند (حذف گزینه 1).
مجموعه تمام رشته‌های تعریف شده روی یک الفبا همان $\sum^\ast$ است و ما می‌دانیم که $\sum^\ast$ مجموعه‌ای شماراست (حذف گزینه 3).
کل زبان‌های قابل تعریف روی الفبا ناشمارا و زبان‌های منظم شمارا هستند. حال می‌دانیم که اگر یک مجموعه شمارا را از یک مجموعه ناشمارا کم کنیم، مجموعه حاصل همچنان ناشمارا خواهد بود. اگر از مجموعه کل زبانها، مجموعه زبان‌های منظم را کم کنیم، مجموعه حاصل شامل کلیه زبان‌های نامنظم است که ناشمارا نیز هست (حذف گزینه 4)
دشوار
سه زبان $L_3$, $L_2$, $L_1$ با تعاریف زیر مفروضند. کدام گزاره صحیح است؟
خصوصیات زبان‌های مستقل از متن
${\mathrm{L}}_{\mathrm{1}}\mathrm{=}\left\{\mathrm{w}o^{\mathrm{n}}\mathrm{\ |\ w}\mathrm{\in }{\left\{\mathrm{a,b}\right\}}^{\mathrm{*}},{\mathrm{n}}_{\mathrm{a}}\left(\mathrm{w}\right)\mathrm{=}{\mathrm{n}}_{\mathrm{b}}\left(\mathrm{w}\right)\mathrm{=n,\ }\left|\mathrm{w}\right|\mathrm{=}\mathrm{2}\mathrm{n}\right\}$
${\mathrm{L}}_{\mathrm{2}}\mathrm{=}\left\{\mathrm{w}o^{\mathrm{n}}\mathrm{\ |\ w}\mathrm{\in }{\left\{\mathrm{a,b}\right\}}^{\mathrm{*}}\mathrm{,\ }\left|\mathrm{w}\right|\mathrm{=n}\right\}$
${\mathrm{L}}_{\mathrm{3}}\mathrm{=}\left\{\mathrm{w}o^{\mathrm{n}}\mathrm{\ |\ w}\mathrm{\in }{\left\{\mathrm{a,b}\right\}}^{\mathrm{*}}\mathrm{,\ }{\mathrm{n}}_{\mathrm{a}}\left(\mathrm{w}\right)\mathrm{=n\ }یا\mathrm{\ }\left|\mathrm{w}\right|\mathrm{=n}\right\}$
گزینه 3 صحیح است.
بررسی زبان ${L}_\mathbf{1}$:
در قسمت w اگر بخواهیم تعداد a و b برابری داشته باشیم باید به ازای هر a که می‌خوانیم، b نیز وجود داشته باشد تا به این طریق بتوانیم مستقل از متن بودن آن را تشخیص دهیم اما پس از w رشته $o^n$ آمده است. ما اکنون معیاری جهت سنجش تعداد nتا o که برابر تعداد a یا b هست نداریم زیرا این معیار را جهت برابری تعداد a و b به اندازه n، مصرف کردیم در نتیجه زبان داده شده مستقل از متن نیست (حذف گزینه 2 و 4).
بررسی زبان ${L}_\mathbf{2}$:
برای اینکه بفهمیم این زبان مستقل از متن هست یا خیر یک روش این است که سعی کنیم ماشین پشته‌ای آن را بکشیم. اکنون همین کار را میکنیم.
همانطور که مشاهده می‌کنید می‌توان به صورت فوق ماشین را به راحتی کشید. اگر دقت کنید می‌بینید که ماشین رسم شده DPDA است در نتیجه این زبان مستقل از متن قطعی است.
بررسی زبان ${L}_\mathbf{3}$:
روش دیگر تشخیص مستقل از متن بودن یک زبان، نوشتن گرامر مستقل از متن برای آن زبان است. اکنون همین کار را میکنیم.
1) $S\rightarrow S_1|S_2$
2) $S_1\to aS_1o\left|bS_1o\right|\varepsilon \Longrightarrow \left|w\right|=n\ در\mathrm{\ }\text{حالتی}\mathrm{\ }\text{که}$
3) $S_2\to B\underbrace{aS_2o}_{n_o(wo^n)=n_a(w)=n}|B\ \Longrightarrow \ n_a(w)=n\ در\mathrm{\ }\text{حالتی}\mathrm{\ }\text{که}$
4) $B\rightarrow bB|\varepsilon$
2) $S_1\to aS_1o\left|bS_1o\right|\varepsilon \Longrightarrow \left|w\right|=n\ در\mathrm{\ }\text{حالتی}\mathrm{\ }\text{که}$
3) $S_2\to B\underbrace{aS_2o}_{n_o(wo^n)=n_a(w)=n}|B\ \Longrightarrow \ n_a(w)=n\ در\mathrm{\ }\text{حالتی}\mathrm{\ }\text{که}$
4) $B\rightarrow bB|\varepsilon$
در نتیجه متوجه می‌شویم که زبان داده شده مستقل از متن است. اما به دلیل وجود قاعده $S\rightarrow S_1|S_2$ که عدم قطعیت به وجود می‌آورد، می‌توان گفت که این زبان غیرقطعی است (حذف گزینه 1).
متوسط
گرامر زیر چه زبانی را تولید میکند؟ ($\varepsilon$ بیانگر رشته تهی است.)
ماشین‌های تورینگ
${G:S}\mathrm{\to }{\mathrm{S}}_{\mathrm{1}}\mathrm{\ B}$
$~~~~~~~{\mathrm{S}}_{\mathrm{1}}\mathrm{\to }\mathrm{a}{\mathrm{S}}_{\mathrm{1}\mathrm{\ }}\mathrm{b}$
$~~~~~~~\mathrm{bB}\mathrm{\to }\mathrm{bbb\ B}$
$~~~~~~~\mathrm{a}{\mathrm{S}}_{\mathrm{1}}\mathrm{b}\mathrm{\to }\mathrm{aa}$
$~~~~~~~\mathrm{B\to\varepsilon}$
گزینه 1 صحیح است.
برای حل این سوال بهتر است رشته‌های کف متعلق به گرامر G را بررسی کنیم و ببینیم این رشته‌ها به کدام گزینه تعلق ندارند و سپس آن گزینه را حذف کنیم.
1) $S\Rightarrow S_1B\Rightarrow aS_1bB\Rightarrow aaB\Rightarrow aa\equiv a^2\notin~\text{زبان}\mathrm{\ }\text{گزینه}\mathrm{\ 2\ }و\mathrm{\ 3}$
2) $S\Rightarrow S_1B\Rightarrow aS_1bB\Rightarrow aS_1bbbB\Rightarrow aabbB\Rightarrow aabb\equiv a^2b^2\in~ \text{زبان}\mathrm{\ }\text{هر}\mathrm{\ }\text{چهار}\mathrm{\ }\text{گزینه}$
3) $S\Rightarrow S_1B\Rightarrow aS_1bB\Rightarrow aS_1bbbB\Rightarrow aabbB\Rightarrow aabbbbB\Rightarrow aabbbb\equiv a^2b^4\in~\text{زبان}\mathrm{\ }\text{هر}\mathrm{\ }\text{چهار}\text{گزینه}$
4) $a^2b\in ~\text{زبان}\mathrm{\ }\text{گزینه}\mathrm{\ 4}\mathrm{\ }{{\stackrel{در\mathrm{\ }\text{حالی}\mathrm{\ }\text{که}}{\Longrightarrow}}}a^2b\notin L\left(G\right)$
با استفاده از 4 مثال فوق متوجه شدیم که تنها زبان گزینه 1 می‌توان معادل $L\left(G\right)$ باشد.
دشوار
از میان چهار جملۀ زیر، چه تعداد از آنها صحیح است؟
خانواده زبان‌های بازگشتی و شمارش پذیر بازگشتی
الف- اشتراک دو زبان بازگشتی، لزوماً یک زبان بازگشتی است.
ب- اگر $h(L)$ (تصویر همومورفیک $L$) منظم باشد می‌توان نتیجه گرفت خود $L$ نیز منظم است.
ج- اجتماع دو زبان مستقل از متن قطعی، خود یک زبان مستقل از متن قطعی است.
د- زبان‌های شمارش پذیر بازگشتی تحت عملیات مکمل‌گیری بسته هستند.
گزینه 1 صحیح است.
بررسی گزاره الف:
زبان‌های بازگشتی نسبت به عمل اشتراک بسته هستند پس این گزاره صحیح است.
بررسی گزاره ب:
اگر h(L) منظم باشد، لزوماً L منظم نیست. در نتیجه این گزاره غلط است. به مثال نقض زیر توجه کنید.
$L=a^nb^n\notin Reg{{\stackrel{If\ h(a)=a\ \&\ h(b)=a}{\Longrightarrow}}}h\left(L\right)=a^{2n}\in Reg$
بررسی گزاره ج:
بر اساس متن درس می‌دانیم که زبان‌های مستقل از متن قطعی تحت اجتماع بسته نیستند در نتیجه این گزاره غلط است.
بررسی گزاره د:
بر اساس متن درس می‌دانیم که زبان‌های شمارش پذیر بازگشتی (RE) تحت مکمل گیری بسته نیستند. در نتیجه این گزاره غلط است.
آسان
اگر M یک ماشین حالت متناهی قطعی (DFA) باشد، می‌گوییم دو رشته x و y نسبت به M با هم معادلند، هرگاه $\left(\mathrm{s,y}\right) \begin{array}{c}\mathrm{*} \\ {{\mathop{\longrightarrow}\limits_{\mathrm{\ \ \ M\ \ \ \ }}}} \end{array}\mathrm{q}\mathrm{\Leftrightarrow }\left(\mathrm{s,x}\right) \begin{array}{c}\mathrm{*} \\ {{\mathop{\longrightarrow}\limits_{\mathrm{\ \ \ \ M\ \ \ \ }}}} \end{array}{q}$، که در آن s حالت شروع و q یک حالت دلخواه ماشین است. کلاس‌های هم‌ارزی رشته‌ها نسبت به ماشین روبه‌رو کدام است؟
ماشین‌های متناهی
گزینه 4 صحیح است.
اگر حالات مشابهی در ماشین نباشد (حالاتی که با ورودی‌های یکسان به حالات مشابه می‌روند) آنگاه کوتاه‌ترین رشته‌ای که به وسیله آن وارد یک state می‌شویم، نماینده کلاس هم‌ارزی آن state خواهد بود.
هیچ‌یک از حالت‌های 1 و 2 و 3 و 4 باهم معادل نیستند زیرا به ازای ورودی‌های یکسان، حالت بعدی یکسانی ندارند، در نتیجه ماشین داده شده ساده نمی‌شود و این بدان معناست که کلاس‌های هم‌ارزی هر حالت به صورت زیر می‌باشد:
| Q4 | Q3 | Q2 | Q1 | Q0 |
| $[aa]$ | $[ab]$ | $[b]$ | $[a]$ | $[\varepsilon]$ |
روش دوم: استفاده از دوره های نکته و تست درس های کنکور کامپیوتر
دوره های نکته و تست درس‌های کنکور کامپیوتر برای آشنایی و تسلط بر تستهای کنکور تهیه شده‌اند. دوره نکته و تست هر درس شامل تمامی تستهای کنکور آن درس به همراه پاسخ تشریحی است. برای آشنایی بیشتر با هر دوره می‌توانید از لینک‌های زیر استفاده کنید.
- دوره نکته و تست ساختمان داده و طراحی الگوریتمخرید نکته و تست ساختمان داده و طراحی الگوریتم
از نگاه دانشجویان، قدرت بیان فوق العاده استاد رضوی و پوشش ۱۰۰ درصدی تمامی سرفصل‌ها، نکات و تست‌ها، ویدیوهای حل تست ساختمان داده و طراحی الگوریتم را به بهترین ویدیو حل تست کشور در درس ساختمان و الگوریتم تبدیل کرده است. این فیلم پرطرفدارترین و پرفروش‌ترین فیلم حل تست ساختمان داده و الگوریتم کشور است و هر سال بیش از ۶۰۰۰ نفر این فیلم را تهیه می‌کنند
- دوره نکته و تست هوش مصنوعینکته و تست هوش مصنوعی
بهترین دوره نکته و تست هوش مصنوعی کشور در این صفحه معرفی و ویژگی‌ها و اهمیت دوره نکته و تست هوش و نحوه استفاده از نکته و تست هوش مصنوعی گفته شده
- دوره نکته و تست درس پایگاه دادهدوره نکته و تست درس پایگاه داده
دوره نکته و تست پایگاه داده و ویژگی‌ها و اهمیت دوره نکته و تست پایگاه داده و نحوه استفاده صحیح از نکته و تست پایگاه داده کنکور ارشد کامپیوتر و آیتی در این صفحه عالی توضیح داده شده است
- دوره نکته و تست سیستم عاملدوره نکته و تست سیستم عامل
بهترین دوره نکته و تست سیستم عامل در این صفحه معرفی و ویژگی‌ها و اهمیت دوره نکته و تست سیستم های عامل و نحوه استفاده از نکته و تست سیستم عامل گفته شده
- دوره نکته و تست شبکه های کامپیوترینکته و تست شبکه
بهترین دوره نکته و تست شبکه کشور در این صفحه معرفی و ویژگی‌ها و اهمیت دوره نکته و تست شبکه های کامپیوتری و نحوه استفاده از نکته و تست شبکه گفته شده
- دوره نکته و تست نظریه زبان ها و ماشین هادوره نکته و تست نظریه زبان ها و ماشین ها
دوره نکته و تست نظریه زبان ها و ماشین ها در این صفحه قرار گرفته و ویژگی ها و اهمیت دوره نکته و تست نظریه زبان ها و ماشین ها بررسی شده است
- دوره نکته و تست درس سیگنال ها و سیستم هادوره نکته و تست درس سیگنال ها و سیستم ها
دوره نکته و تست سیگنال و سیستم و ویژگی‌های نکته و تست سیگنال و نحوه استفاده صحیح از نکته و تست سیگنال کنکور ارشد کامپیوتر در این صفحه عالی توضیح داده شده
- دوره نکته و تست معماری کامپیوتر
- دوره نکته و تست مدار منطقینکته و تست مدار منطقی
بهترین دوره نکته و تست مدار منطقی کشور در این صفحه معرفی و ویژگی‌ها و اهمیت دوره نکته و تست مدار منطقی و نحوه استفاده از نکته و تست مدار منطقی گفته شده
- دوره نکته و تست الکترونیک دیجیتالدوره نکته و تست الکترونیک دیجیتال
بهترین دوره نکته و تست الکترونیک دیجیتال کشور در این صفحه معرفی شده و اهمیت دوره نکته و تست الکترونیک دیجیتال و نحوه استفاده صحیح از دوره بیان شده است
- دوره نکته و تست ریاضیات گسسته نکته و تست ریاضیات گسسته کنکور ارشد کامپیوتر
بهترین دوره نکته و تست ریاضیات گسسته کشور در این صفحه معرفی و ویژگی‌ها و اهمیت دوره نکته و تست گسسته و نحوه استفاده از نکته و تست گسسته گفته شده
پاسخنامه کنکور ارشد کامپیوتر ۱۴۰۰
برای دسترسی به پاسخ های کلیدی کنکورهای کامپیوتر می‌توانید از دفترچه‌های کنکور کامپیوتر استفاده کنید. در صفحه دفترچه سوالات کنکور ارشد مهندسی کامپیوتردانلود سوالات کنکور ارشد کامپیوتر
دفترچه سوالات کنکورهای ارشد کامپیوتر از اولین سال برگزاری تا کنکور 1403 به همراه کلید نهایی سازمان سنجش در این صفحه بصورت رایگان قرار داده شده است تا بتوانید به راحتی و بدون صرف زمان زیاد برای جستجو در اینترنت، از دفترچه سوالات سال‌های گذشته استفاده نمایند می‌توانید تمامی آنها را به‌صورت رایگان دانلود کنید.
کلید کنکور ارشد کامپیوتر ۱۴۰۰
تصویر زیر کلید کنکور ارشد کامپیوتر ۱۴۰۰ را نشان می‌دهد که همان پاسخ نهایی سازمان سنجش است. برای دانلود کلید کنکور ارشد کامپیوتر سال‌های دیگر می‌توانید از به صفحه دفترچه سوالات کنکور ارشد مهندسی کامپیوتردانلود سوالات کنکور ارشد کامپیوتردفترچه سوالات کنکورهای ارشد کامپیوتر از اولین سال برگزاری تا کنکور 1403 به همراه کلید نهایی سازمان سنجش در این صفحه بصورت رایگان قرار داده شده است تا بتوانید به راحتی و بدون صرف زمان زیاد برای جستجو در اینترنت، از دفترچه سوالات سال‌های گذشته استفاده نمایند مراجعه کنید.
جمع‌بندی
آزمون کارشناسی ارشد کامپیوتر شامل سوالات متنوعی از جمله طراحی الگوریتمآموزش طراحی الگوریتم به زبان ساده
درس طراحی الگوریتم یکی از مهم‌ترین و بنیادیترین دروس رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. و ساختمان دادهآموزش ساختمان داده و الگوریتم
هر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم میکند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است، شبکهجامع‌ترین آموزش درس شبکه های کامپیوتری
درس شبکه های کامپیوتری یکی از مهم‌ترین و بنیادیترین دروس رشته کامپیوتر است، با توجه به اینکه اینترنت امروزی بزرگترین سیستم مهندسی ساخت دست بشر در تمام طول تاریخ است، آشنایی با شبکه‌های کامپیوتری برای تمامی علاقه‌مندان و دانشجویان رشته کامپیوتر الزامی است، در این راستا در این صفحه به معرفی شبکه‌های کامپیوتری پرداخته شده است، هوش مصنوعیدرس هوش مصنوعی
این صفحه عالی به معرفی درس هوش مصنوعی از جمله پیش نیازهای درس هوش مصنوعی، سرفصل و منابع درس هوش مصنوعی و فیلم‌های آموزشی درس هوش مصنوعی پرداخته شده و ... است. داوطلبان برای پاسخگویی به این سوالات نیاز به دانش عمیق و تسلط بر مباحث مورد نظر دارند و لازم است که از منابع مناسبی استفاده کنند پس استفاده از دوره نکته و تست و پلتفرم آزمون را به شما پیشنهاد میکنیم.
چگونه می توانم به جواب تشریحی کنکور کامپیوتر ۱۴۰۰ دسترسی داشته باشم؟
دو روش: (۱) پلتفرم آزمون (۲) دوره‌های نکته و تست
آیا منابعی برای دروس کنکور کامپیوتر وجود دارد؟
بله می‌توانید از دوره‌های درس کنکور کامپیوتر استفاده کنید.
چگونه می توانم کلید کنکور ارشد کامپیوتر ۱۴۰۰ را داشته باشم؟
شما با مراجعه به صفحه دفترچه‌های کنکور کامپیوتر می‌توانید به پاسخ کلیدی تمامی کنکورهای کامپیوتر دسترسی رایگان داشته باشید.
