داوطلبان با استفاده از آخرین کنکورهای برگزار شده می‌توانند شبیه‌سازی انجام دهند و عملکرد خودشان را ارزیابی کنند. دسترسی به پاسخ تشریحی این کنکورها برای مقایسه جواب دانشجو با پاسخ مرجع ضروری است. در این مقاله به روش‌هایی برای دسترسی به پاسخ تشریحی سوالات کنکور ارشد کامپیوتر ۱۴۰۲ اشاره خواهیم کرد.
روش های دسترسی به پاسخ تشریحی کنکور ارشد کامپیوتر ۱۴۰۲
در ادامه مقاله دو روش برای دسترسی به جواب تشریحی تست های کنکور کامپیوتر ۱۴۰۲ بیان خواهیم کرد.
روش اول: استفاده از پلتفرم آزمون کنکور کامپیوتر
پلتفرم آزمون و بانک تست و مجموعه سوالات کنکور ارشد کامپیوتر، آیتی و علوم کامپیوتر
سیستم قدرتمند آزمون کنکور کامپیوتر - اولین و تنها سیستم آزمون رشته کامپیوتر
داوطلبین کنکور ارشد کامپیوتر، آیتی و علوم کامپیوتر، با این پلتفرم نیازی به تهیه هیچ کتابی ندارید، بهتر از هر کتاب مجموعه سوالات
پلتفرم آزمون کنکور کامپیوتر یک سرویس است که دانشجویان با استفاده از آن می‌توانند به پاسخ تشریحی تمامی تستهای کنکور دسترسی داشته باشند، آزمون شخصی‌سازی‌شده بسازند، با دیگر دانشجویان رقابت کنند و…. برای آشنایی بیشتر با این پلتفرم پیشنهاد می‌کنیم از صفحه پلتفرم آزمون دیدن فرمایید.
در ادامه به‌عنوان نمونهای از پاسخ‌های تشریحی پلتفرم آزمون، جواب تشریحی تستهای کنکور کامپیوتر ۱۴۰۲ برای درس‌های ساختمان داده و طراحی الگوریتم، پایگاه داده، مدار‌های منطقی و معماری کامپیوتری ارائه شده است.
تستهای درس ساختمان داده و طراحی الگوریتم کنکور کامپیوتر ۱۴۰۲ به همراه جواب تشریحی
دشوار در مسئلۀ یافتن پوسته محدب، تعدادی نقطه در صفحه داده شده است. هدف پیدا کردن کوچکترین (کمترین محیط) چندضلعی محدب است که شامل همه نقاط باشد. بهترین الگوریتم ممکن برای یافتن این چندضلعی، چه مرتبه زمانی خواهد داشت؟ تقسیم و غلبه
یکسری نقاط در صفحه داده شده است و هدف ما یافتن چند ضلعی است با کمترین محیط که همه نقاط را شامل شود که این نقاط یا روی محیط این چند ضلعی باشند یا داخل این چند ضلعی.
یافتن convex hull با استفاده از الگوریتم Garham scan برای n نقطه دارای مرتبه $\theta\left(n\log{n}\right)$ است.
نکته) یافتن 2 نقطه از بین n نقطه در صفحه که در بین همه نقاط از هم دورتر هستند یا نزدیکتر هستند نیز از مرتبه $\theta\left(n\log{n}\right)$ است.
به عنوان مثال برای یافتن 2 نقطه که از همه نسبت به هم دورتر هستند، می‌آییم و convex hull این n نقطه را با مرتبه $\theta\left(n\log{n}\right)$ بدست می آوریم و سپس 2 نقطه‌ی که نسبت به هم از هر 2 نقطه ای دیگری دورتر هستند روی محیط پوسته محدب هستند که می توانیم با مرتبه $\theta\left(n\right)$ آن را پیدا کنیم و بنابراین مرتبه کلی $\theta\left(n\log{n}\right)$ می شود.
متوسط مرتبه زمانی الگوریتم زیر کدام است؟ به دست آوردن مرتبه زمانی شبه کدها
for(i = 1; i <= n; i++)
for(j = 1; j <= $\left\lfloor\frac{n}{i}\right\rfloor$; j++)
;S.O
for(j = 1; j <= $\left\lfloor\frac{n}{i}\right\rfloor$; j++)
;S.O
اگر به حلقه داخلی توجه کنیم، در زمانی که $i=1$ است این حلقه $⌊n⌋=n$ بار اجرا می‌شود و در زمانی که $i=2$ است حلقه $⌊\frac{n}{2}⌋$ بار اجرا می‌شود و این روند ادامه می‌یابد تا زمانی که i به عدد n می‌رسد در آن حالت یکبار دیگر کد داخلی اجرا شده دیگر اجرا نمی‌شود. در نتیجه مجموع اجرای برنامه به صورت زیر است:
$n+\left\lfloor \frac{n}{2}\right\rfloor +\left\lfloor \frac{n}{3}\right\rfloor +\left\lfloor \frac{n}{4}\right\rfloor +\dots +\left\lfloor \frac{n}{n}\right\rfloor $
نکته: اگر از ما در مسئله‌ای تنها مرتبه زمانی خواسته شده و تعداد دقیق اجرای کد مد نظر نمی‌باشد می‌توان از براکت‌ها صرف نظر کرد و عباراتی مانند $⌊\frac{n}{a}⌋$ و $⌊\frac{n}{a}⌋$ را معادل $\frac{n}{2}$ در نظر گرفت. زیرا در به دست آوردن جواب نهایی تاثیری ندارند.
بنابراین داریم:
$n+\frac{n}{2}+\frac{n}{3}+\frac{n}{4}+\dots +\frac{n}{n}=n(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots +\frac{1}{n})$
همچنین می‌دانیم:
۱- $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots +\frac{1}{n}\approx \mathrm{ln}\mathrm{}(n)$
۲- مرتبه زمانی عبارات لگاریتمی که مقادیر جلوی آنها یکسان بوده و پایه‌ثابتی دارند با هم برابر است.
در نتیجه:
$n\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots +\frac{1}{n}\right)\approx nln(n)\in \theta (nlog\left(n\right))$
اثبات $\sum^{\boldsymbol{n}}_{\boldsymbol{i}\boldsymbol{=}\boldsymbol{1}}{\frac{\boldsymbol{1}}{\boldsymbol{i}}}\boldsymbol{\in }\boldsymbol{\theta }\boldsymbol{(}\boldsymbol{\mathrm{ln}}\boldsymbol{\mathrm{}}\boldsymbol{(}\boldsymbol{n}\boldsymbol{))}$
به شکل زیر توجه کنید:
با توجه به این شکل می‌توان نتیجه گرفت که:
$\int^{n+1}_1{\frac{1}{x}dx}<\sum^n_{i=1\ }{\frac{1}{i}}$
حال اگر مستطیل‌های داده شده در شکل را به اندازه یک واحد به چپ شیفت بدهیم و از مستطیل اول (مقدار ۱) صرف نظر کنیم داریم:
$\sum^n_{i=1\ }{\frac{1}{i}}-1<\int^n_1{\frac{1}{x}dx}\to \sum^n_{i=1\ }{\frac{1}{i}}<\int^n_1{\frac{1}{x}dx}+1$
همچنین می‌دانیم $\int^n_1{\frac{1}{x}dx}=\mathrm{ln}\mathrm{}(n)$ است. بنابراین:
${\mathrm{ln} \left(n+1\right)\ }<\sum^n_{i=1\ }{\frac{1}{i}}<{\mathrm{ln} \left(n\right)\ }+1$
و چون $ln(n+1)∈θ(ln(n))$ و $ln(n)+1∈θ(ln(n))$ داریم:
$\sum^n_{i=1\ }{\frac{1}{i}}\in \mathrm{\Omega }\left({\mathrm{ln} \left(n\right)\ }\right)\ \&\ \sum^n_{i=1\ }{\frac{1}{i}}\in O\left({\mathrm{ln} \left(n\right)\ }\right)\to \sum^n_{i=1\ }{\frac{1}{i}}\in \theta ({\mathrm{ln} \left(n\right)\ })$
به غیر از اثبات بالا در حالت کلی می‌توانید در سوالاتی که مرتبه زمانی به رابطه‌ای مانند $\sum^n_{i=1}{f(i)}$ ختم می‌شود به جای علامت جمع، انتگرال گذاشته و سپس مرتبه زمانی را محاسبه کنید.
مثال:
$\sum^n_{i=1}{i}=\frac{n\left(n+1\right)}{2}\approx \int^n_1{i}di=\frac{1}{2}(n^2-1)\in \theta (n^2)$
$\sum^n_{i=1}{i^2}=\frac{n\left(n+1\right)\left(2n+1\right)}{6}\approx \int^n_1{i^2}di=\frac{1}{3}(n^3-1)\in \theta (n^3)$
$\sum^n_{i=1}{\frac{1}{i}}\approx \int^n_1{\frac{1}{i}}di=\mathrm{ln}\mathrm{}(n)\in \theta (\mathrm{ln}\mathrm{}(n))$
آسان کدام‌یک از عبارات زیر درست است؟ نظریه Np، شار، مجموعه‌های مجزا
الف- هر مسئله‌ای NP – کامل یک مسئله‌ای NP – سخت است.
ب- هر مسئله‌ای NP – سخت یک مسئله‌ای NP – کامل است.
ج- هر مسئله‌ای P (چندجمله‌ای) یک مسئله‌ای NP هم هست.
ب- هر مسئله‌ای NP – سخت یک مسئله‌ای NP – کامل است.
ج- هر مسئله‌ای P (چندجمله‌ای) یک مسئله‌ای NP هم هست.
در حالت کلی می‌توان روابط میان مسائل P، NP، NP کامل (NPc) و NP سخت (NPh) را با استفاده از نمودار وَن زیر نمایش داد:
بنابراین:
الف- صحیح
ب- هر مسئله NP سخت نمی‌تواند NP کامل باشد، زیرا هر مسئله NP کامل باید NP باشد اما یک مسئله NP سخت می‌تواند NP نباشد.
ج- صحیح
متوسط فرض کنید که یک مسئله را به‌صورت بهینه به توان هم با روش تقسیم و حل، هم با روش برنامه‌ریزی پویا و هم با روش حریصانه حل کرد. در این‌صورت از لحاظ پیچیدگی زمانی کدام‌یک ارجحیت دارد؟ سوالات ترکیبی
در صورت سوال گفته شده است که امکان حل مسئله به صورت بهینه برای هر سه روش ممکن است. این جمله ممکن است این ابهام را بوجود بیاورد که هر سه راه حل از نظر زمانی بهینه بوده و پیچیدگی زمانی یکسانی دارند. اما اگر به جواب‌ها دقت شود گزینه‌ای که بگوید هرسه پیچیدگی زمانی یکسانی دارند وجود ندارد. بنابراین منظور طراح در این سوال این است که هر روش جواب بهینه و مدنظر مسئله را به ما می‌دهد اما ممکن است هر روش پیچیدگی زمانی متفاوتی داشته باشد.
در حل این سوال درک کافی از نحوه عملکرد و اولویت‌های هر الگوریتم لازم می‌باشد، به همین دلیل به توضیح مختصری از عملکرد سه روش دقت کنید:
الگوریتم حریصانه: این روش در هر مرحله از بین انتخاب‌های ممکن، گزینه‌ای را انتخاب می‌کند که در همان لحظه بهترین انتخاب به نظر می‌رسد و در انتخاب‌ها به عواقب کار اندیشیده نمی‌شود. این الگوریتم در حل مسائل به دنبال بهترین جواب در سریعترین زمان می‌باشد برای همین معمولا بهینه‌ترین جواب مسئله را از دست می‌دهد.
الگوریتم تقسیم و حل: این روش یک روش بالا به پایین (Top-Down) است به این معنا که مسئله اصلی را به مسائل کوچکتر (و قابل حل) تقسیم می‌کند و سپس با ادغام کردن جواب مسائل کوچکتر سعی در بدست آوردن جواب مسئله اصلی می‌نماید. اصولاً این روش به یک الگوریتم بازگشتی منجر می‌شود.
الگوریتم برنامه‌ریزی پویا: روش برنامه‌ریزی پویا در مقایسه با روش تقسیم و حل مسائل را معمولا از پایین به بالا (Down-Top) حل می‌کند. در این روش حل زیر مسأله‌ها ذخیره می‌شود تا در صورت برخورد دوباره با آنها دیگر نیازی به حل مجدد نداشته باشند و از جواب‌های ذخیره شده استفاده شود. این روش مانند روش تقسیم و حل در نهایت با ترکیب حل زیرمسئله‌ها، مسئله اصلی را حل می‌کند. اصولاً این روش هم به یک الگوریتم بازگشتی منجر می‌شود.
با توجه به این توضیحات مشخص است که اولویت الگوریتم حریصانه حل مسئله در سریعترین و آسان‌ترین حالت ممکن است و به بهینه بودن حل مسئله توجه زیادی ندارد. درحالیکه دو الگوریتم دیگر با ایجاد یک الگوریتم بازگشتی (که می‌تواند از لحاظ زمانی هزینه‌بر باشد) سعی در حل دقیق و بهینه مسئله می‌کنند.
و چون سوال در اینجا بهینه بودن جواب را تضمین کرده است بهترین روش، روش حریصانه می‌باشد.
برای مقایسه بیشتر میان الگوریتم حریصانه و دو الگوریتم دیگر می‌توانید به لینک‌های زیر مراجعه کنید:
متوسط کدام‌یک از مسائل زیر در زمان خطی برحسب تعداد رئوس و یال‌های گراف ورودی قابل حل نیست؟ گراف
پیدا کردن درخت پوشای کمینه با الگوریتم‌های پریم و کروسکال ممکن است که مرتبه زمانی این الگوریتم‌ها در بهترین حالت از نوع O(nlog(n)) می‌باشد که n تعداد رئوس و یال‌ها می‌باشد.
حل خطی سه گزینه دیگر: (در پرانتز پیچیدگی زمانی هر بخش آمده است)
V: تعداد رئوس، E: تعداد یال‌ها
گزینه ۱: ابتدا تمام رئوس را به حالت ملاقات نشده علامت می‌زنیم (O(V)). سپس برروی یکی از رأس‌ها یکی از دو الگوریتم BFS یا DFS را یکبار اجرا می‌کنیم و در زمان اجرا رئوس ملاقات شده را علامت می‌زنیم (O(V+E)). در پایان این الگوریتم تمام رئوس را چک می‌کنیم اگر رأسی علامت ملاقات شده را نداشت گراف غیر همبند و در غیر این صورت همبند است O(V).
پیچیدگی زمانی:
$O(V)+O(V+E)+O(V)∈O(V+E)$
گزینه ۲: ابتدا تمام رئوس را به حالت ملاقات نشده علامت می‌زنیم (O(V)). الگوریتم DFS یا BFS را یکبار برروی یکی از رأس‌ها اجرا می‌کنیم و رئوس ملاقات شده را علامت می‌زنیم (O(V+E)). تمام رئوس را چک می‌کنیم تا رأسی که ملاقات نشده است را پیدا کنیم (O(V))، توجه شود اگر رأسی پیدا نشد گراف دوبخشی نبوده و مسئله به پایان می‌رسد. دوباره یکی از دو الگوریتم DFS یا BFS را مانند قبل اجرا می‌کنیم (O(V+E)). در نهایت تمام رئوس را چک می‌کنیم، اگر رأس ملاقات نشده‌ای باقی‌مانده باشد گراف دوبخشی نبوده و در غیر این صورت دوبخشی است (O(V)).
پیچیدگی زمانی:
$O(V)+O(V+E)+O(V)+O(V+E)+O(V)∈O(V+E)$
گزینه ۴:
یادآوری:
درخت پوشای کمینه گراف وزن‌دار، درختی می‌باشد که تمام رئوس گراف را به یکدیگر متصل می‌کند در حالیکه مجموع وزن یال‌ها کمینه باشد.
گراف DAG (Directed Acyclic Graph) گراف جهت‌داری است که دور یا حلقه‌ای در آن وجود نداشته باشد.
ترکیب توپولوژیکی رئوس گراف جهت‌دار آرایه‌ای مرتب از رئوس گراف است به طوریکه رئوسی که در ابتدای یال‌ها قرار دارند قبل از رئوسی که در انتهای یال‌ها (جهت کمانه) قرار دارند آمده باشند.
برای مثال در ترکیب توپولوژیکی گراف زیر باید رأس ۳ قبل از ۱ و رأس ۲ قبل از ۳ آمده باشد.
چند نمونه از ترکیب توپولوژیکی گراف بالا:
4 5 0 2 3 1
4 5 2 0 3 1
4 5 2 3 0 1
برای مطالعه بیشتر به لینک‌های زیر مراجعه کنید:
https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/
https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/
دشوار برای پیاده‌سازی مؤثر کدام‌یک از الگوریتم‌های زیر، ساختمان داده heap لازم نیست؟ درخت‌ها
گزینه 4 صحیح است.
پریم و دایجسترا مانند هم هستند و هر 2 از هیپ استفاده می‌کنند و minها را با استفاده از minheap انتخاب می‌کردند.
در روش هافمن هم با فراوانی‌ها یک minheap می ساختیم و سپس در هر مرحله 2 عنصر min ام را از minheap خارج می‌کردیم و با استفاده از این 2 درخت هافمن را می‌ساختیم و سپس جمع این 2 عنصر min ام را به درخت minheap اضافه می‌کردیم و این کار را n-1 بار انجام می‌دادیم.
اما کراسکال کارش با استفاده از مجموعه‌های مجزا انجام می‌داد.
دشوار یک آرایه دوبعدی $n\times n$ از اعداد داده شده است که هر سطر به‌صورت صعودی از چپ به راست و هر ستون به‌صورت صعودی از بالا به پایین مرتب شده است. کمترین پیچیدگی زمانی برای پیدا کردن یک عدد داده شده در این آرایه دوبعدی کدام است؟ آرایه، جستجو در آرایه، لیست پیوندی، پشته، صف
ایده حل مسئله به این گونه است که در هر مرحله مقایسه عدد داده شده با هر المان آرایه یک ردیف یا یک ستون حذف شود تا زمانی که عدد مورد نظر پیدا شود. مقایسه را با المان گوشه بالا سمت راست شروع می‌کنیم. با انجام این مقایسه سه حالت پیش می‌آید:
۱- عدد داده شده از المان فعلی بزرگتر است: در این صورت تمام اعداد موجود در آن ردیف حذف می‌شوند و ما برای ادامه جست‌وجو به ردیف بعدی (همان ستون) می‌رویم.
۲- عدد داده شده از المان فعلی کوچکتر است: در این صورت تمام اعداد موجود در آن ستون حذف می‌شوند و ما برای ادامه جست‌وجو به ستون قبلی (همان ردیف) می‌رویم.
۳- عدد داده شده از المان فعلی بزرگتر است: الگوریتم به پایان می‌رسد.
گام‌های حل مسئله به ترتیب:
$\bullet$ دو متغیر $j=n-1,i=0$ را به ترتیب برای ذخیره مختصات ردیف و ستون فعلی تعریف می‌کنیم. و در ابتدا مختصات المان گوشه بالا سمت راست را به آنها می‌دهیم.
$\bullet$ المان فعلی را با عدد داده شده مقایسه می‌کنیم.
o اگر عدد بزرگتر بود: $i=i+1$
o اگر عدد کوچکتر بود: $i=i-1$
o اگر دو عدد برابر بودند: جست‌وجو به پایان می‌رسد.
$\bullet$ گام بالا را تا زمانی که $i≥n$ یا $j≤0$ نیستند ادامه می‌دهیم.
$\bullet$ اگر حلقه بالا جست‌وجو را به پایان نرساند، گزارش عدم وجود عدد در آرایه را بازمی‌گردانیم.
مثال:
با استفاده از الگوریتم بالا در آرایه زیر به دنبال عدد ۱۶ می‌گردیم:
مرتبه زمانی الگوریتم:
در این الگوریتم یک حلقه وجود دارد که بیشترین رشد را دارد نسبت به دستورات دیگر دارد (باقی کد به تعداد ورودی بستگی نداشته و از مرتبه $O(1)$ می‌باشد).
کد داخل حلقه به اندازه ورودی بستگی ندارد برای همین از مرتبه $O(1)$ است.
این حلقه زمانی به پایان می‌رسد که $i=n$ یا $j=0$ شوند. در بدترین حالت با توجه به این که مقادیر اولیه به صورت $j=n-1,i=0$ می‌باشند و در هر مرحله ۱ واحد کم یا زیاد می‌شود حلقه به تعداد اجرا می‌شود.
بنابراین مرتبه حلقه و مرتبه الگوریتم برابر است با:
$O(1)+2n×O(1)∈O(n)$
آسان یک الگوریتم یک آرایه دوبعدی $n\times n$ را به‌عنوان ورودی دریافت می‌کند و زمان اجرای آن برحسب $n$ عبارت است از $T\left(n\right)=O\left(n\log{n}\right)$، زمان الگوریتم برحسب اندازه ورودی $m=n^2$ کدام است؟ رشد توابع
در سوال گفته شده الگوریتم آرایه دوبعدی با اندازه $n×n$ دریافت می‌کند، بنابراین اندازه ورودی $n^2$ می‌باشد. سپس گفته شده زمان اجرا به ازای این ورودی عبارت است از: $T(n)=O(nlog(n))$.
حال از ما زمان اجرا به ازای اندازه ورودی m که همان $n^2$ است خواسته شده‌است. در اینجا تنها کاری که باید کرد این است که مقدار n را بر حسب m بدست آوریم و در عبارت زمان اجرا جایگزین کنیم.
$m=n^2=>n=\sqrt{m}$
$T\left(n\right)=O\left(nlog\left(n\right)\right)\to T\left(m\right)=O\left(\sqrt{m}{\mathrm{log} \left(\sqrt{m}\right)\ }\right)$
$=O(\frac{1}{2}\sqrt{m}{\mathrm{log} \left(m\right)\ }=O\left(\sqrt{m}{\mathrm{log} \left(m\right)\ }\right)$
نکته: ضریب ثابت در داخل O(..) اثری ندارد.
متوسط فرض کنید برای حل یک مسئله باید از بین چهار الگوریتم انتخاب کنید. کدام‌یک ارجحیت دارد؟ روابط بازگشتی
پیچیدگی زمانی هر روش را حساب کرده و بهترین را انتخاب می‌کنیم.
گزینه ۱:
$T(n)=20T(\frac{n}{3})+O(n^2 )$
با استفاده از قضیه اصلی (Master):
$n^{{{\mathrm{log}}_3 20\ }}\approx n^{2.7}\in O\left(n^{{{\mathrm{log}}_3 20\ }}\approx n^{2.7}\right)>O\left(n^2\right)\to T\left(n\right)\in O\left(n^{{{\mathrm{log}}_3 20\ }}\approx n^{2.7}\right)$
گزینه ۲:
$T\left(n\right)=8T\left(\frac{n}{2}\right)+O\left(n^3\right)$
با استفاده از قضیه اصلی (Master):
$n^{{{\mathrm{log}}_2 8\ }}=n^3\in O\left(n^3\right)\to T\left(n\right)\in O(n^3{\mathrm{log} \left(n\right)\ })$
گزینه ۳:
$T\left(n\right)=2T\left(2n\right)+O\left(n\right)$
این راه‌حل به جواب نمی‌رسد، زیرا در هر مرحله به ازای هر تعداد ورودی اولیه تعداد ورودی‌ها در هر مرحله افزایش یافته و تا بینهایت ادامه می‌یابد، وچون زمان با تعداد ورودی‌ها رابطه مستقیم دارد زمان حل مسئله به بینهایت می‌رود و حل ناممکن است.
گزینه ۴:
$T(n)=2T(n-1)+O(1)$
$T(n)=4T(n-2)+3×O(1)$
$T(n)=8T(n-3)+7×O(1)$
:
$T(n)=2^n T(0)+(1+2+2^2+⋯+2^{n-1} )×O(1)$
$→T(n)=(1+2+2^2+⋯+2^{n-1} )×O(1)=\frac{1(1-2^n )}{1-2}×O(1)=(2^n-1)×O(1)=2^n×O(1)=O(2^n )$
$→T(n)∈O(2^n)$
به روش ساده‌تر می‌توان با نکته زیر مرتبه زمانی را محاسبه کرد.
نکته: مرتبه روابط بازگشتی به فرم $T(n)=aT(n-b)+c$ که در آن a, b, c اعداد ثابت هستند به صورت زیر بدست می‌آید:
$T\left(n\right)=\left\{ \begin{array}{c} O\left(a^{\frac{n}{b}}\right)\ \ \ \ \ :a>1 \\ O\left(n\right)\ \ \ \ \ :a=1,\ c\neq 0 \\ O\left(1\right)\ \ \ \ \ :a=1,\ c=0 \end{array} \right.$
$a=2,\ b=1,\ c=1\to T\left(n\right)=O(2^{\frac{n}{1}})$
مقایسه پیچیدگی زمانی گزینه‌ها:
$O\left(2^n\right)>O\left(n^3{\mathrm{log} \left(n\right)\ }\right)>O\left(n^{{{\mathrm{log}}_3 20\ }}\approx n^{2.7}\right)\to \mathrm{\ \text{گزینه1}}$
یادآوری قضیه اصلی (Master):
برای رابطه بازگشتی $T\left(n\right)=aT\left(\frac{n}{b}\right)+f(n)$ که در آن a, b ثابت بوده و $a≥1,b>1$ است، قضیه اصلی دارای سه حالت گوناگون زیر است که برای حل هر مسئله یکی از این سه حالت انتخاب می‌شود:
حالت اول: اگر معادله $f\left(n\right)=O(n^{{{\mathrm{log}}_b a-\epsilon \ }})$ برای $ϵ>0$ برقرار باشد، آن‌گاه زمان زیر برای رابطه برقرار است:
$T\left(n\right)=\theta (n^{{{\mathrm{log}}_b a\ }})$
حالت دوم: اگر معادله $f\left(n\right)=\theta (n^{{{\mathrm{log}}_b a\ }})$ برقرار باشد، آن‌گاه زمان زیر برای رابطه برقرار است:
$T\left(n\right)=\theta (n^{{{\mathrm{log}}_b a\ }})$
حالت سوم: اگر معادله $f\left(n\right)=\mathrm{\Omega }(n^{{{\mathrm{log}}_b a-\epsilon \ }})$ برای $ϵ>0$ و اگر $af\left(\frac{n}{b}\right)\le cf(n)$ برای $c<1$ و n های بزرگ برقرار باشند، آن‌گاه زمان زیر برای رابطه برقرار است:
$T\left(n\right)=\theta (f\left(n\right))$
متوسط فرض کنید $A=\left[a_1,a_2,\ldots,a_n\right]$ آرایه‌ای از اعداد صحیح متمایز باشد و k یک عدد صحیح داده شده باشد. هدف این است که دو عدد متمایز از A را پیدا کند که مجموع آنها دقیقاً k باشد، یا گزارش دهید که چنین عناصری وجود ندارد. یک الگوریتم کارا برای حل این مسئله چه زمانی خواهد داشت؟ سوالات ترکیبی
روش اول: (روش مرتب کردن و استفاده از دو اشاره‌گر)
- مرتب کردن آرایه به صورت صعودی (آرایه مرتب شده $A'$). $O(nlog(n))$
- استفاده از دو اشاره‌گر p, q در آرای مرتب شده. یکی به ابتدای آرایه (p) و دیگری به انتهای آن (q) اشاره می‌کند. $O(1)$
- اجرای حلقه زیر: ($O(n)$)
while $q > p$ :
If $(A' [p]+A' [q]==k)$
return $A' [p],A' [q]$
else
{
if ( $ A' [p]+A' [q]
$p=p+1$
else
$p=p-1$
}
- اگر حلقه بالا به جواب نرسد، مسئله جواب ندارد بنابراین گزارش آن ارسال می‌شود. $O(1)$
پیچیدگی زمانی:
$O(nlog(n))+O(1)+O(n)+O(1)∈O(nlog(n))$
روش دوم: (روش مرتب کردن و جست‌وجوی دودویی (باینری))
- مرتب کردن آرایه به صورت صعودی (آرایه مرتب شده $A'$). $O(nlog(n))$
- گردش در تمام المان‌های آرایه جدید و تلاش برای یافتن عدد $k-a$ (a عدد فعلی اشاره شده) با استفاده از الگوریتم جست‌وجوی دودویی. اگر به ازای عددی جست‌وجو موفقیت‌آمیز بود، دو عدد به عنوان جواب مسئله بازگردانده می‌شوند. $O(nlog(n))$
- در صورت نیافتن دو عدد، گزارش عدم موفقیت. $O(1)$
پیچیدگی زمانی:
$O(nlog(n))+O(nlog(n))+O(1)∈O(nlog(n))$
نکته: مرتبه زمانی الگوریتم جست‌وجوی دودویی (باینری) برابر با $θ(log(n))$ است.
دشوار الگوریتم مرتب‌سازی ادغام (Mergesort) را درنظر بگیرید. به‌جای اینکه آرایه ورودی را به دو قسمت تقریباً مساوی تقسیم کنیم، آن‌را به m بخش تقسیم می‌کنیم که لزوماً مساوی نیستند (m یک ثابت است.) سپس به‌صورت بازگشتی الگوریتم ادغام اصلاح شده را روی هر قسمت اجرا می‌کنیم و m آرایه مرتب‌شده را ادغام می‌کنیم. زمان اجرای الگوریتم ادغام اصلاح شده در حالتی که $m\gt2$ کدام است؟ مرتب‌سازی
گزینه 4 صحیح است.
$\frac{n}{K_1}+\frac{n}{K_2}+\ldots+\frac{n}{K_m}=n\Rightarrow n\left(\frac{1}{K_1}+\frac{1}{K_2}+\ldots+\frac{1}{K_m}\right)=n\Rightarrow\frac{1}{K_1}+\frac{1}{K_2}+\ldots+\frac{1}{K_m}=1$
| n عنصر $\overbrace{}$ |
|||
| $\frac{n}{K_m} $ | $\frac{n}{K_2}$ | ... | $\frac{n}{K_1}$ |
حالا روی هر‌یک از قسمت‌های $\frac{n}{K_i}$ الگوریتم مرتب‌سازی ادغامی را به‌صورت بازگشتی فراخوانی می‌کنیم و درنهایت که مرتب شدند پاسخ‌ها را باهم ادغام (merge) می‌کنیم بنابراین زمان اجرا برابر است با:
| $T\left(m\right)=T\left(\frac{n}{K_1}\right)+T\left(\frac{n}{K_2}\right)+\ldots+T\left(\frac{n}{K_m}\right)+θ(n)∈θ(nlogn)$ |
| $\downarrow$ |
| زمان Merge |
طبق نکاتی که در مورد حل روابط بازگشتی بلد هستیم چون مجموع ضرایب n درون 4T برابر 1 شده $(\frac{1}{K_1}+\frac{1}{K_2}+\ldots+\frac{1}{K_m}=1)$ و در انتهای رابطه بازگشتی هم $\theta\left(n\right)$ داریم، مرتبه $T\left(n\right)$ برابر $\theta\left(n\log{n}\right)$ است.
متوسط کدام‌یک از روابط بازگشتی زیر را نمی‌توان مستقیماً با قضیه اصلی حل کرد؟ روابط بازگشتی
گزینه 4 صحیح است.
برای حل این سوال نباید از روش‌های ابتکاری که برای حل روابط بازگشتی به این فرم وجود دارد استفاده کنید و فقط باید قضیه Master ساده را درنظر بگیرید.
در رابطه بازگشتی $T\left(n\right)=aT\left(\frac{n}{b}\right)+f\left(n\right)$ اگر در حاصل تقسیم $f\left(n\right)$ بر $n^{\log_b{a}}$ یا بالعکس فقط لگاریتم n مشاهده کنیم (حالا با هر توانی = $\log^K{n}$) قضیه Master جواب نمی‌دهد. توجه کنید که اگر $\log^K{n}$ در یک n ای ضرب بشود، قضیه Master جواب می‌دهد. بررسی گزینه 1) $\frac{n^{\log_4{16}}}{n}=\frac{n^2}{n}=n$ : لگاریتم تنها نشد پس Master جواب می‌دهد بررسی گزینه 2) $\frac{n^{\log_5{1}}}{20}=\frac{n^0}{20}=\frac{1}{20}$ : لگاریتم تنها نشد پس Master جواب می‌دهد. بررسی گزینه 3) $\frac{n\log{n}}{n^{\log_4{3}}}=\frac{n\log{n}}{n^{0.8}}=n^{0.2}\log{n}$ : در اینجا $f\left(n\right)$ را بر $n^{\log_b{a}}$ تقسیم کردیم، چون با این مقادیر این کار راحت‌تر است، توجه کنید که تفاوتی ندارد که $f\left(n\right)$ را بر $n^{\log_b{a}}$ تقسیم کنیم یا بالعکس لگاریتم تنها نشد پس Master جواب می‌دهد. بررسی گزینه 4) $\frac{n\log{n}}{n^{\log_2{2}}}=\frac{n\log{n}}{n}=\log{n}$ : لگاریتم تنها نشد پس Master جواب نمی‌دهد.
در رابطه بازگشتی $T\left(n\right)=aT\left(\frac{n}{b}\right)+f\left(n\right)$ اگر در حاصل تقسیم $f\left(n\right)$ بر $n^{\log_b{a}}$ یا بالعکس فقط لگاریتم n مشاهده کنیم (حالا با هر توانی = $\log^K{n}$) قضیه Master جواب نمی‌دهد. توجه کنید که اگر $\log^K{n}$ در یک n ای ضرب بشود، قضیه Master جواب می‌دهد. بررسی گزینه 1) $\frac{n^{\log_4{16}}}{n}=\frac{n^2}{n}=n$ : لگاریتم تنها نشد پس Master جواب می‌دهد بررسی گزینه 2) $\frac{n^{\log_5{1}}}{20}=\frac{n^0}{20}=\frac{1}{20}$ : لگاریتم تنها نشد پس Master جواب می‌دهد. بررسی گزینه 3) $\frac{n\log{n}}{n^{\log_4{3}}}=\frac{n\log{n}}{n^{0.8}}=n^{0.2}\log{n}$ : در اینجا $f\left(n\right)$ را بر $n^{\log_b{a}}$ تقسیم کردیم، چون با این مقادیر این کار راحت‌تر است، توجه کنید که تفاوتی ندارد که $f\left(n\right)$ را بر $n^{\log_b{a}}$ تقسیم کنیم یا بالعکس لگاریتم تنها نشد پس Master جواب می‌دهد. بررسی گزینه 4) $\frac{n\log{n}}{n^{\log_2{2}}}=\frac{n\log{n}}{n}=\log{n}$ : لگاریتم تنها نشد پس Master جواب نمی‌دهد.
تستهای درس پایگاه داده کنکور کامپیوتر ۱۴۰۲ به همراه جواب تشریحی
آسان کدام مورد یک طراحی منطقی درست برای نمودار EER زیر است؟
[توجه: در نمودار EER، از خط ممتد در زیر صفت برای نمایش کلید کاندیدا و از خط‌چین زیر صفت برای نمایش صفت ممیزه یا کلید جزئی موجودیت ضعیف استفاده شده است. در طراحی جداول، از خط ممتد در زیر صفت(ها) برای نمایش کلید اصلی و از خط‌چین برای نمایش کلید خارجی استفاده شده است.] طراحی پایگاه داده
[توجه: در نمودار EER، از خط ممتد در زیر صفت برای نمایش کلید کاندیدا و از خط‌چین زیر صفت برای نمایش صفت ممیزه یا کلید جزئی موجودیت ضعیف استفاده شده است. در طراحی جداول، از خط ممتد در زیر صفت(ها) برای نمایش کلید اصلی و از خط‌چین برای نمایش کلید خارجی استفاده شده است.] طراحی پایگاه داده
از موجودیت A شروع می‌کنیم:
A یک موجودیت ساده است، موجودیت‌های ساده برای خود یک رابطه تشکیل می‌دهند و تمام صفات ساده خود را شامل می‌شوند. A صفت AID را به عنوان کلید اصلی می‌گیرد (چون روی شکل تنها کلید کاندید است.).
A(AID, A1)
در موجودیت B:
B یک موجودیت ضعیف است، موجودیت‌های ضعیف برای خود یک رابطه دارند که کلید این رابطه ترکیبی از کلید اصلی موجودیتی که به آن وابسته هستند و کلید جزئی خود می‌باشد. بنابراین کلید B ترکیب AID, BID می‌شود. صفت B1 متعلق به این موجودیت است برای همین در رابطه آن قرار می‌گیرد.
B در یک ارتباط N:1 با موجودیت Y قرار دارد، در اینگونه ارتباط‌ها صفات و کلید اصلی طرف ۱ ارتباط در رابطه طرف N قرار می‌گیرند. بنابراین در اینجا RA به عنوان یک صفت دیگر B قرار می‌گیرد و کلید Y که در ادامه مشخص می‌شود برابر XID است، به عنوان کلید خارجی در رابطه B قرار می‌گیرد.
B(AID, BID, B1, XID, RA)
موجودیت‌های X و Y:
موجودیت Y یک subclass بوده که superclass Xآن است. در نگاشت generalizationها و specializationها از EER به مدل رابطه‌ای چندین روش وجود دارد:
۱- برای هر یک از subclassها و superclass یک رابطه درست کنیم، رابطه superclass شامل تنها صفات خود می‌باشد و subclassها علاوه بر صفات خود کلید اصلی superclass را نیز به عنوان کلید اصلی خود دارند.
۲- تنها برای هر یک از subclassها رابطه تشکیل دهیم، در اینجا هر رابطه subclass شامل صفات خود و صفات موجود متناظرش در superclass است و کلید این رابطه کلید اصلی superclass می‌باشد. این روش زمانی می‌تواند به کار رود که subclassها به صورت disjoint یعنی جدا از هم باشند. در موارد overlap کارایی ندارد.
علاوه‌بر دو روش بالا دو روش دیگر هم وجود دارند که به جای ایجاد چندین رابطه تنها یک رابطه ایجاد می‌کنند و تمام صفات superclass و subclassها را در آن قرار می‌دهند. (توضیحات این دو روش خارج از محدوده کنکور است.)
حال اگر به گزینه‌ها دقت کنید هم برای X و هم برای Y رابطه تشکیل شده است بنابراین اینجا از روش ۱ استفاده شده است.
موجودیت X تمام صفات خود را دارد و XID چون تنها کلید کاندید است به عنوان کلید اصلی استفاده می‌شود:
X(XID, X1)
موجودیت Y تمام صفات خود را دارد و از XID که کلید X است به عنوان کلید استفاده می‌کند. در شکل نشان داده شده که Y صفت Y2 را نیز دارد امّا اگر دقت کنید این صفت از نوع صفت مشتق است و صفت‌های مشتق در مدل رابطه‌ای وارد نمی‌شوند. بنابراین در نهایت مدل رابطه‌ای Y به صورت زیر می‌شود:
Y(XID, Y1)
متوسط جداول زیر برای یک باشگاه قایق‌سواری طراحی شده است که در آن قایق‌های فراهم‌شده توسط تعدادی از شرکت‌ها به اعضای باشگاه اجاره داده می‌شوند. پایگاه داده رابطه‌ای
Member (MID, MName, MDate, MType) اطلاعات اعضا شامل شمارۀ عضویت، نام، تاریخ عضویت، نوع عضویت
Boat (BID, Capacity, BType, Company) اطلاعات قایق‌ها شامل شمارۀ قایق، ظرفیت، نوع، شرکت
Rent (MID, BID, Date, Duration) اطلاعات اجاره قایق شامل شماره عضو، شماره قایق، تاریخ اجاره، مدت اجاره به ساعت
Boat (BID, Capacity, BType, Company) اطلاعات قایق‌ها شامل شمارۀ قایق، ظرفیت، نوع، شرکت
Rent (MID, BID, Date, Duration) اطلاعات اجاره قایق شامل شماره عضو، شماره قایق، تاریخ اجاره، مدت اجاره به ساعت
کدام مورد، جبر رابطه‌ای معادل شماره اعضایی است که همه قایق‌های از نوع Jet، شرکت Yamaha را برای حداقل 2 ساعت متوالی اجاره کرده‌اند؟
بررسی گزینه‌ها:
گزینه ۱:
$\prod_{}(\sigma_{(Duration \ge 2\ AND\ Company='Yamaha'\ AND\ BType='Jet')}(Rent\ \Join \ Boat))$
این گزینه شماره عضویت افرادی را برمی‌گرداند که یکی از قایق‌های Jet شرکت Yamaha را به مدت بیش از ۲ ساعت اجاره کرده‌اند. این گزینه می‌تواند از هر شماره عضویت چندین نمونه داشته باشد که تعدادشان برابر تعداد قایق‌ها و دفعات اجاره آنها توسط یک فرد می‌باشند.
سؤال از ما شماره عضویت افرادی که تمام قایق‌ها را اجاره کرده‌اند میخواهد بنابراین این گزینه غلط است.
گزینه ۲:
$\prod_{}(\sigma_{(Duration \ge 2)}(Rent)) \div \prod _{}(\sigma_{(Company='Yamaha'\ AND\ BType='Jet')}( Boat))$
عبارت $\prod_{}{({\sigma }_{Duration\ge 2}(Rent))}$ شماره قایق و شماره عضویت مربوط به اطلاعات تمام اجاره‌هایی که مدتشان بیش از ۲ ساعت هستند را برمی‌گرداند.
عبارت $\prod_{}{({\sigma }_{Company='Yamaha'AND\ BType='Jet'}\left(Boat\right))}$ شماره تمام قایق‌هایی را برمی‌گرداند که از نوع Jet شرکت Yamaha باشند.
حال تقسیم عبارت اول بر دوم شماره عضویت کسانی را برمی‌گرداند که تمام BIDها را شامل شده باشند. به عبارتی دیگر شماره عضویت کسانی برگردانده می‌شود که تمام قایق‌های از نوع Jet شرکت Yamaha را اجاره کرده باشند، همچنین با توجه به رابطه اول این افراد همگی قایق‌ها را به مدت بیش از ۲ ساعت اجاره کرده‌اند.
این گزینه صحیح است.
گزینه ۳:
$\prod_{}(\sigma_{(Duration \ge 2)}\ (Rent))-\prod_{}\ (\sigma_{Company!='Yamaha'\ OR \ BType!='Jet')}(Rent\ \Join \ Boat))$
عبارت $\prod_{}{({\sigma }_{Duration\ge 2}\left(Rent\right))}$ شماره عضویت افرادی را بازمیگرداند که هر قایقی را به مدت دو ساعت اجاره کرده باشند.
عبارت $\prod_{}{\left({\sigma }_{Compan!='Yamaha'OR\ BType!='Jet'}\left(Rent\infty Boat\right)\right)}$ شماره عضویت کسانی را بازمیگرداند که قایق‌هایی که از نوع Jet و یا از شرکت Yamaha نباشند را اجاره کرده‌اند.
تفریق رابطه دوم از رابطه اوّل شماره عضویت کسانی را برمی‌گرداند که به هیچ عنوان قایقی غیر از نوع Jet شرکت Yamaha به مدت بیش از ۲ ساعت اجاره نکرده باشند. یعنی ممکن است کسی باشد که تنها یک قایق از این نوع اجاره کرده باشد و در جواب نهایی بیاید و یا ممکن کسی باشد که تمام قایق‌ها از جمله قایق‌های خواسته سؤال را اجاره کرده باشد ولی در جواب نهایی نیاید. بنابراین این گزینه غلط است.
گزینه ۴:
$\prod_{}(\sigma_{(Duration \ge 2)}\ (Member \Join \ Rent))\cap \prod_{}\ (\sigma_{Company='Yamaha'\ AND \ BType='Jet')}(Rent\ \Join \ Boat))$
عبارت $\prod_{}{({\sigma }_{Duration\ge 2}\left(Member\infty Rent\right))}$ شماره عضویت افرادی که قایق به مدت بیش از دو ساعت اجاره کرده باشند برمی‌گرداند.
عبارت $\prod_{}{({\sigma }_{Company='Yamaha'\ AND\ BType='Jet'}\left(Rent\infty Boat\right))}$ شماره عضویت افرادی که قایق از نوع Jet شرکت Yamaha را اجاره کرده باشند برمی‌گرداند.
اشتراک دو عبارت بالا شماره عضویت افرادی که یک یا چند قایق Jet شرکت Yamaha را به مدت ۲ ساعت و یا بیشتر اجاره کرده باشند برمی‌گرداند. نتیجه مشابه با گزینه ۱ است. این گزینه نیز غلط است.
متوسط یک سیستم مدیریت کتابخانه براساس جداول زیر طراحی شده است. زبان و پرس و جوی SQL
Member (MemID, Name, Age, MemType) اطلاعات اعضا شامل شناسه، نام، سن، نوع عضویت
Book (ISBN, Title, Author, Publisher) اطلاعات کتاب شامل کد شابک، عنوان، نویسنده، ناشر
Borrowed (MemID, ISBN, BorrowDate, ReturnDate) ،اطلاعات امانت‌گیری شامل شناسه عضو، شابک
Book (ISBN, Title, Author, Publisher) اطلاعات کتاب شامل کد شابک، عنوان، نویسنده، ناشر
Borrowed (MemID, ISBN, BorrowDate, ReturnDate) ،اطلاعات امانت‌گیری شامل شناسه عضو، شابک
تاریخ امانت‌گیری، تاریخ بازگشت
کدام مورد، این محدودیت که «هر فرد با نوع عضویت عادی (Regular) نمی‌تواند بیش از 2 بار یک کتاب را به امانت ببرد» را با استفاده از اظهار (Assertion) به‌درستی توصیف می‌نماید؟
کدام مورد، این محدودیت که «هر فرد با نوع عضویت عادی (Regular) نمی‌تواند بیش از 2 بار یک کتاب را به امانت ببرد» را با استفاده از اظهار (Assertion) به‌درستی توصیف می‌نماید؟
گزینه 4 با تاثیر مثبت توسط سنجش اعلام شد. بررسی گزینه‌ها:
گزینه ۱:
در اینجا دو شرط لازم است True باشند تا محدودیت اعمال شده عمل کند.
۱- عضوی از نوع ‘Regular’ داشته باشیم
۲- با توجه به عبارات پرانتز سوم و دستور Exists قبل از آن، زمانی شرط دوم برقرار است که کتابی با ISBN مشخص در دو تاریخ متفاوت قرض گرفته شده باشد. اینکه کتاب توسط یکنفر یا چند نفر متفاوت قرض گرفته شده باشد و یا نوع عضویت افراد Regular بوده باشد در اینجا چک نمی‌شود.
بنابراین این گزینه غلط است.
به عنوان مثال: اگر دو شخص متفاوت که هر دو از نوع Regular هم هستند، کتاب یکسانی را در دو تاریخ متفاوت فقط برای یکبار قرض گرفته باشند، سیستم خطا اعلام می‌کند و محدودیت اعمال می‌شود.
گزینه ۲:
دستور Select ISBN From Book … می‌گوید ISBN تمام کتاب‌های جدول Book را برگردان اگر شرط زیر برقرار باشد. علت اینکه تمام کتاب‌ها برگردانده می‌شود این است که در شرط آمده مقادیر رکورد‌های Book تأثیری روی شرط ندارند. در کل به دلیل دستور Not Exists اگر شرط زیر برقرار باشد محدودیت عمل می‌کند و سیستم خطای Assertion می‌دهد.
شرط (select count(*) …) > 2 می‌گوید بررسی کن اگر کتابی توسط فرد یکسان با نوع Regular بیش از دو بار در تاریخ یکسان و برگشت یکسان قرض گرفته شده‌است عبارت True را برگردان. به عبارتی این شرط بررسی می‌کند که آیا بیش از دو رکورد کاملا مشابه در جداول وجود دارد یا خیر.
برای مثال: اگر فردی با نوع عضویت Regular یک کتاب را در بیش از دو تاریخ قرض گرفته باشد این محدودیت عمل نمی‌کند.
گزینه ۳:
این گزینه می‌توانست کاملا درست باشد اگر به جای Not Exists پس از عبارت MemType=’rgular’ And از دستور Exists استفاده شده بود.
در این گزینه ابتدا چک می‌شود که عضو داده شده از نوع Regular باشد سپس این عضو یک کتاب با ISBN مشخص را بیش از دو بار قرض نگرفته باشد. (در حالیکه ما اعضایی را می‌خواهیم که قرض گرفته باشند.)
گزینه ۴:
این گزینه دقیقا خواسته مسئله می‌باشد.
عبارات جلوی Not Exists شماره کتاب و عضوهایی را برمی‌گرداند که عضو داده شده از نوع Regular باشد و آن شخص کتابی با ISBN مشخص را بیش از دو بار قرض گرفته باشد.
آسان در رابطه R(A, B, C, D, E) با وجود وابستگی تابعی $\left(C,D\right)\rightarrow E$، کدام‌یک از تجزیه‌های زیر برای این رابطه، یک تجزیه بی‌کاست (Lossless, Nonless) است؟ طراحی پایگاه داده
سنجش این سوال را از کلید نهایی حذف کرد.
شرط تجزیه بی‌کاست یک رابطه R به چندین رابطه $R_1, R_2, \dots , R_n$ این است که پیوند طبیعی تمام این رابطه‌ها دقیقا رابطه R را ایجاد کنند.
اگر رابطه R به دو رابطه تجزیه شود این تجزیه زمانی بی‌کاست است که صفت یا صفت‌هایی مشترک در دو رابطه وجود داشته باشند که این صفت یا صفتها حداقل در یکی از دو رابطه کلید کاندید یا سوپرکلید باشد.
به عبارت دیگر باید یکی از دو عبارت زیر برقرار باشند:
$R_1\cap R_2\to (R_1-R_2)\ or\ R_1\cap R_2\to (R_2-R_1)$
بررسی گزینه‌ها:
گزینه ۱:
اشتراک دو رابطه صفت D است، این صفت با توجه به وابستگی تابعی داده شده نمی‌تواند کلید هیچ‌کدام از دو رابطه باشد.
$D\to \left(A,\ B,\ C\right)$$\ Flase$$,\ \ \ \ \ \ D\to \left(E\right)$$\ False$
گزینه ۲:
اشتراک دو رابطه دو صفت (A, B) است، این صفتها با توجه به وابستگی تابعی داده شده نمی‌توانند سوپرکلید هیچ‌کدام از دو رابطه باشد.
$\left(A,\ B\right)\to \left(D\right)$$\ False$$,\ \ \ \ \ \ \left(A,\ B\right)\to \left(\ C,\ E\right)$$\ False$
گزینه ۳:
اشتراک دو رابطه سه صفت (C, D) است، این صفتها با توجه به وابستگی تابعی داده شده می‌توانند کلید رابطه دوم باشند:
$\left(C,\ D\right)\to E$
$\Rightarrow \left(A,\ C,\ D\right)\to AE \Rightarrow \left(A,\ C,\ D\right)\to E$
$\Rightarrow \left(A,\ C,\ D\right)=R_1\cap R_2\to R_2-R_1=E$$\ \ True$
گزینه ۴:
اشتراک دو رابطه هیچ صفتی نمی‌شود. این گزینه مشخصاً غلط است.
دشوار چند عبارت از عبارات زیر درست است؟ اصول و مفاهیم پایه
• زبان سطح پایین دستکاری داده‌ها (Low Level DML) باید در یک زبان برنامه همه منظوره (General Purpose Language) نهفته شود.
• مدل داده‌ای فیزیکی (Physical Data Model) مفاهیمی را فراهم می‌کند که توسط کاربران نهایی (End Users) به‌راحتی قابل فهم باشند.
• مدل داده‌ای (Data Model) ابزاری برای حصول تجرید داده‌ها (Data Abstraction) است.
• DBMS مسئولیت کامل اینکه در هر لحظه پایگاه داده‌ها در وضعیت معتبر (Valid State) باشد را برعهده دارد. لازم به ذکر است وضعیت معتبر وضعیتی است که تمام محدودیت‌ها و شرایط و ساختارهای تعریف شده در شمای پایگاه داده را ارضاء کند.
• مدل داده‌ای فیزیکی (Physical Data Model) مفاهیمی را فراهم می‌کند که توسط کاربران نهایی (End Users) به‌راحتی قابل فهم باشند.
• مدل داده‌ای (Data Model) ابزاری برای حصول تجرید داده‌ها (Data Abstraction) است.
• DBMS مسئولیت کامل اینکه در هر لحظه پایگاه داده‌ها در وضعیت معتبر (Valid State) باشد را برعهده دارد. لازم به ذکر است وضعیت معتبر وضعیتی است که تمام محدودیت‌ها و شرایط و ساختارهای تعریف شده در شمای پایگاه داده را ارضاء کند.
گزینه 3 صحیح است. بررسی عبارات:
عبارت اول:
این عبارت درست است.
در زبان سطح پایین دستکاری داده‌های باید روند تغییرات داده‌ها برخلاف زبان سطح بالا قدم به قدم مشخص شوند. زبان سطح پایین باید حتما در یک زبان برنامه‌نویسی همه منظوره باشد اما زبان DML سطح بالا لازم نیست.
عبارت دوم:
این عبارت نادرست است.
مدل داده‌ای فیزیکی جزئیاتی را فراهم می‌کند که از نحوه ذخیره داده‌های برروی محیط فیزیکی اطلاع می‌دهند. مفاهیم فراهم شده در این مدل سطح پایین به طور کلی برای متخصصان کامپیوتر می‌باشند و نه کاربران نهایی (End Users).
عبارت سوم:
این عبارت کاملا درست است.
به طور کلی Data abstraction به معنی مخفی کردن جزئیات ذخیره‌سازی و سازمان‌دهی داده‌ها و تنها نمایش جزئیات منطقی مثل موجودیت‌‌ها و روابط می‌باشد.
Data Model که مجموعه‌ای از مفاهیم برای بیان ساختار یک پایگاه داده‌است، ابزارهای لازم برای رسیدن به این abstraction را در اختیار قرار می‌دهد.
عبارت چهارم:
این عبارت نادرست است.
DBMS به طور کامل نه بلکه فقط تا حدی مسئول نگه داشتن پایگاه‌داده در حالت valid است.
آسان کدام نمودار بهترین توصیف برای عبارت زیر را نشان می‌دهد؟ طراحی پایگاه داده
«در اسناد تحلیل مربوط به امور تغذیه دانشجویان نوشته شده است: تمام غذاها این قابلیت را دارند که به‌عنوان پیش‌غذای دیگر نیز استفاده شوند. به‌عنوان مثال الویه که خود می‌تواند غذای مستقلی باشد، می‌تواند به‌عنوان پیش‌غذای چلوخورشت قیمه به دانشجو داده شود. همچنین همراه با پیش‌غذا یک نوشیدنی یا ترشی (و نه هر دو با هم) به دانشجو داده می‌شود»
1 
2 
3 
4 
گزینه 4 صحیح است. بررسی اشکال:
شکل ۱:
در این شکل پیش‌غذا و غذا به عنوان دو موجودیت جداگانه معرفی شده‌اند درحالیکه لازم به اینکار نیست زیرا همانطور که در پاراگراف آمده ذکر شده پیش‌غذا از میان همان غذاها انتخاب می‌شود بنابراین بودن یک موجودیت غذا کافیست.
همچنین در اینجا هم نوشیدنی و هم ترشی هر دو با هم در رابطه شرکت کرده‌اند امّا مطابق آنچه ذکر شده این دو همزمان با هم سرو نمی‌شوند، بنابراین بودنشان همزمان در رابطه درست نیست.
شکل ۲:
اجتماع نوشیدنی و ترشی باید موجودیت همراه غذا را تشکیل دهد نه پیش‌غذا.
پیش‌غذا همان غذاها هستند و نیازی به داشتن موجودیت جداگانه نمی‌باشند.
شکل ۳:
اینجا فقط مشکل وجود موجودیت پیش‌غذا است، زیرا پیش‌غذاها از همان موجودیت غذا می‌توانند انتخاب شوند و نیاز به موجودیت جداگانه ندارند.
شکل ۴:
این شکل بهترین شکل برای توصیف پاراگراف آمده است.
به وضوح مشخص است که همراه غذا از اجتماع نوشیدنی و ترشی بدست می‌آید.
در هر سرو یک همراه غذا از نوشیدنی و یا ترشی سرو می‌شود که در این شکل به خوبی نمایش داده‌شده‌است.
غذا و پیش‌غذا هر دو می‌توانند از موجودیت غذا انتخاب شوند پس تعریف موجودیت دیگر لازم نیست و فقط کافیست که موجودیت غذا را دو بار در رابطه شرکت دهیم.
متوسط دو جدول زیر با وابستگی‌های تابعی نشان داده شده مفروض است. طراحی پایگاه داده
1) TblOne (A, B) , $\left\{A\to B\right\}$
2) TblTwo (A, C) , $\left\{A\to C\right\}$
حال اگر DE Normalization انجام دهیم، کدام مورد درست است؟
گزینه 2 با تاثیر مثبت در سنجش اعلام شد. گاهی اوقات دسترسی به برخی داده‌ها و انتخاب‌ها آنقدر پرکاربرد و زیاد می‌شوند که افزودن داده‌های اضافی و برگرداندن پایگاه داده به یک سطح نرمال پایین‌تر برای ما از لحاط هزینه بهینه‌تر می‌باشد. فرآیند Denormalization برای همین منظور استفاده می‌شود.
توجه کنید این فرآیند دقیقا برعکس عمل normalization نیست و فقط براساس کاربرد‌های مورد نیاز انجام می‌شود.
برای مثال: فرض کنید که ما دو جدول از اساتید و دوره‌ها داریم. در جدول دوره‌های ID اساتید ذخیره می‌شود امّا نام اساتید خیر. در اینجا ما اگر نیاز داشته باشیم که به دوره‌ها به همراه نام اساتید دسترسی داشته باشیم باید هر بار این دو جدول را با یکدیگر پیوند بزنیم.
از یک لحاظ اینکار خوب است زیرا اگر استادی تصمیم به تغییر نامش بگیرد ما فقط کافی است آن نام را در یکجا تغییر دهیم.
ولی از طرف دیگر اگر این جدول‌ها بزرگ باشند، ممکن است زمان‌های زیادی هر بار صرف پیوند این جدول بکنیم. در اینجا denormalization برای حل این مشکل می‌آید و با ایجاد یک جدول از پیوند این دو جدول سرعت را افزایش می‌دهد.
در این سؤال با توجه به جداول داده شده، عمل Denormalization یک جدول از پیوند طبیعی دو جدول آمده به ما می‌دهد:
$NewTbl\ \left(A,\ B,C\right),\ \left\{A\to B,\ A\to C\right\}$
جدول بدست آمده در سطح 2NF است زیرا صفات B و C با کل کلید جدول که A است رابطه کامل دارند.
جدول بدست آمده در سطح 3NF است زیرا هیچ وابستگی انتقالی در رابطه وجود ندارد، به عبارتی هیچ یک از صفتها با کلید به دلیل وجود واسطه وابستگی تابعی ندارند بلکه مستقیم با خود کلید یعنی A رابطه دارند.
جدول بدست آمده می‌تواند مشکل MVD داشته باشد و در سطح 4NF نباشد. این مشکل اجباری نیست فقط امکانش هست. علت آن هم پیوند دو جدول با صفتی مشترک است.
تستهای درس مدار‌های منطقی کنکور کامپیوتر ۱۴۰۲ به همراه جواب تشریحی
آسان ماشین حالت زیر چه رشته‌ای را نمی‌تواند تشخیص دهد؟ تحلیل مدارات ترتیبی و پارامترهای زمانی فلیپ فلاپ‌ها
به ترتیب گزینه‌ها را بررسی می‌کنیم:
گزینه ۱:
با ۲ تا صفر به S4 می‌رویم سپس هر مقدار صفر که دریافت کنیم در همان حالت می‌مانیم تا اینکه با دریافت یک ۱ به S5 می‌رویم که حالت هدف است. بنابراین تعدادی صفر و سپس یک قابل تشخیص است.
گزینه ۲:
با یک صفر به S2 رفته سپس با یک ۱ به S3 می‌رویم، در اینجا هر چه قدر که ۱ بگیریم در همان حالت می‌مانیم، تا زمانیکه یک صفر دریافت کرده و به S5 می‌رویم که حالت هدف است. بنابراین ابتدا صفر، تعدادی یک سپس صفر قابل تشخیص است.
گزینه ۳:
با دریافت یک ۱ به S1 می‌رویم و تا زمانی که ۱ دریافت کنیم در همانجا می‌مانیم تا اینکه یک صفر دریافت کنیم که به S3 می‌رویم، در اینجا براساس گزینه دیگر ورودی دریافت نمی‌کنیم و چون در S3 که حالت هدف نیست قرار گرفتیم می‌توانیم نتیجه بگیریم که این گزینه قابل تشخیص نیست.
گزینه ۴:
تعدادی یک ما را به S1 برده و در آنجا نگه می‌دارد، با دریافت یک صفر به S3 می‌رویم و با دریافت تعدادی یک همانجا می‌مانیم تا اینکه در نهایت با دریافت یک صفر به S5 رفته که حالت هدف است. بنابراین این گزینه قابل تشخیص است.
آسان شمارنده زیر چه ترتیبی را می‌شمارد؟ تحلیل مدارات ترتیبی و پارامترهای زمانی فلیپ فلاپ‌ها
به ورودی‌های counter توجه کنید.
ورودی clear یک ۱ است که چون not می‌شود می‌توان آن را صفر در نظر گرفت، بنابراین در این counter، clear عملی انجام نمی‌دهد.
حال به ورودی $I0$ تا $I3$ توجه کنید، این ورودی برابر عدد ۴ است.
در نهایت برای ورودی Load می‌توانیم عبارت زیر را بنویسیم:
$\overline{(\overline{Reset}.\overline{\left(Q_3.Q_2\right)})}=Reset+(Q_3.Q_2)$
براساس ورودی Load اگر Q2 و Q3 هر دو همزمان ۱ باشند، خروجی در کلاک بعدی برابر ۴ یعنی مقدار $I$ ها می‌شود. به عبارتی اگر خروجی ۱۲ باشد در کلاک بعدی ۴ می‌شود و دیگر بالا‌تر نمی‌رود. بنابراین بیشترین مقدار شمارش ۱۲ است و کمترین مقدار چون ورودی clear عمل نمی‌کند و Reset نیز به Load وصل است (که آن هم نهایت ۴ را خروجی می‌دهد) ۴ است.
شمارنده از ۴ تا ۱۲ می‌شمارد.
آسان عبارت ساده‌شدۀ تابع زیر کدام است؟ ساده سازی، جبر بول، گیت‌ها
$F\left(A,B,C,D\right)=\left(A+B+\bar{C}+\bar{D}\right)\left(\bar{A}+C+\bar{D}\right)\left(\bar{A}+B+\bar{C}+\bar{D}\right)\left(\bar{B}+C\right)\left(\bar{B}+\bar{C}\right)\left(A+\bar{B}\right)\left(\bar{B}+D\right)$
عبارت F داده شده به صورت product-of-sums است بنابراین سریعترین راه برای ساده کردن آن استفاده از جدول کارنو است.
فقط توجه کنید که در اینجا چون product-of-sums داریم باید برای هر پرانتز مکان‌هایی که در آن صفر می‌شود (به عبارتی ماکسترم‌ها) را پیدا کنید و علامت بزنید. این کار را با معکوس کردن هر پرانتز می‌توانید به راحتی انجام دهید. چگونه؟
برای مثال در ابتدا برای پرانتز اول معکوس آن می‌شود $(~\overline{A}.\overline{B}.C.D)$ حال باید مکان‌هایی که هر ۴ عبارت برقرار هستند را پیدا کرده و در آن صفر بگذارید.
به سراغ پرانتز بعدی می‌رویم و همین کار را تکرار می‌کنیم: $(\bar A +C+\bar D )→(A.\bar C .D)$
$(\bar A +B+\bar C +\bar D )→(A.\bar B .C.D)$
$(\bar B +C)→(B.\bar C )$
$(\bar B +\bar C)→(B.C)$
$(A+\bar B)→(\bar A.B)$
$(\bar B+\bar D )→(B.D)$
در نهایت جدول کارنو به صورت زیر در می‌آید که چون تعداد یک‌های آن کمتر از صفرهاست سعی می‌کنیم کوچکترین عبارت sum-of-products آن را بدست آوریم:
عبارت نهایی برابر است با:
$F\left(A,B,C,D\right)=\overline{B}\overline{D}+\overline{A}\overline{B}\overline{C}=\overline{B}\left(\overline{D}+\overline{A}\overline{C}\right)$
بنابراین گزینه ۱ صحیح است.
آسان در مدار زیر، حداقل تعداد سیکل‌های لازم جهت جابهجایی (Swap) محتوای ثبات‌های Reg1 و Reg4 کدام است؟ (فرض کنید که Select مالتی پلکسرها و Clock Enable (CE) ثبات‌ها توسط ماشین حالت مناسب تولید خواهد شد.) تحلیل مدارات ترتیبی و پارامترهای زمانی فلیپ فلاپ‌ها
نام‌های مشخص شده در شکل زیر را برای مالتی‌پلکسرها در نظر می‌گیریم و برای مشخص کردن کلید Enable هر رجیستر از حرف E و عدد هر رجیستر استفاده می‌کنیم.
در کلاک اول: مقادیر زیر را وارد مدار می‌کنیم (توجه مقادیر ورودی‌هایی که مشخص نشده‌اند همگی صفر است.):
$M_1=0,\ M_3=1,\ M_2=0,\ E_5=1,\ E_6=1$
در این کلاک مقدار رجیستر ۱ به رجیستر ۵ و مقدار رجیستر ۴ به رجیستر ۶ منتقل می‌شوند.
در کلاک دوم: (توجه مقادیر ورودی‌هایی که مشخص نشده‌اند همگی صفر است.)
$M_2=0,E_4=1$
در این کلاک مقدار رجیستر ۱ که در رجیستر ۵ هم قرار دارد به رجیستر ۴ منتقل می‌شود.
در کلاک سوم: (توجه مقادیر ورودی‌هایی که مشخص نشده‌اند همگی صفر است.)
$M_2=1,E_1=1$
در این کلاک مقدار رجیستر ۴ که در رجیستر ۶ هم قرار دارد به رجیستر ۱ منتقل می‌شود.
در این لحظه دو مقدار مطابق خواسته سؤال جابه‌جا شده‌اند بنابراین حداقل ۳ کلاک برای اینکار لازم است.
(توجه: اعمال دو کلاک دو و سه می‌توانند جابه‌جا نیز رخ دهند.)
متوسط با این فرض که سیگنال CLK فرکانس 160 MHz داشته باشد، فرکانس سیگنال $Z_3$ چند مگاهرتز است؟ تحلیل مدارات ترتیبی و پارامترهای زمانی فلیپ فلاپ‌ها
ابتدا ورودی D تمام فلیپ‌فلاپ‌ها را بدست می‌آوریم: (به یاد داشته باشید که در فلیپ‌فلاپ D خروجی Q در کلاک بعدی برابر مقدار D فعلی است.)
$D_1=\overline{Z_1},\ \ D_2=Z_1\bigoplus Z_2,\ \ D_3=Z_1.Z_2\bigoplus Z_3$
با شروع از $Z_3 Z_2 Z_1=000$ سعی می‌کنیم یک دوره کامل از تغییرات از این ۳ سیگنال را بیابیم. این کار را با توجه به ۳ عبارت بالا انجام می‌دهیم:
$000→001→010→011→100→101→110→111→000$
همانطور که می‌بینید پس از ۸ کلاک (تعداد پیکان‌ها) یک دوره کامل تغییرات ۳ سیگنال طی شده و دوباره به مقدار 000 می‌رسیم. چون فرکانس کلال 160MHz است فرکانس هر دوره برابر $\frac{160}{8}=20MHz$ می‌شود.
حال توجه کنید که در هر دوره مقدار $Z_3$ یکبار از صفر به ۱ و یکبار از ۱ به صفر می‌رود بنابراین در هر دوره تنها یک حلقه طی می‌کند و فرکانسش با دوره یکی است. یعنی فرکانس $Z_3$ نیز برابر 20MHz است.
متوسط مدار زیر به همراه سیگنال‌های کنترلی مشخص شده طی 5 سیکل داده شده است. مقدار ثبات $R_3$ پس از 5 سیکل کدام است؟ تحلیل مدارات ترتیبی و پارامترهای زمانی فلیپ فلاپ‌ها
سیکل 1: $Sel_0=0$، $LdR_0=1$، $LdR_1=1$
سیکل 2: $Sel_1=0$، $LdR_2=1$
سیکل 3: $Sel_0=1$، $LdR_0=1$، $Sel_1=1$، $Sel_2=0$، $LdR_3=1$
سیکل 4: $Sub = 1$، $LdR_3=1$، $Sel_2=1$، $Sel_1=0$، $LdR_2=1$
سیکل 5: $Add = 1$، $LdR_3=1$، $Sel_2=1$
سیکل 2: $Sel_1=0$، $LdR_2=1$
سیکل 3: $Sel_0=1$، $LdR_0=1$، $Sel_1=1$، $Sel_2=0$، $LdR_3=1$
سیکل 4: $Sub = 1$، $LdR_3=1$، $Sel_2=1$، $Sel_1=0$، $LdR_2=1$
سیکل 5: $Add = 1$، $LdR_3=1$، $Sel_2=1$
با توجه به دستورات در هر سیکل داریم.
در سیکل اول:
عدد ۵ به رجیستر صفر و عدد ۶ به رجیستر یک منتقل می‌شوند.
در سیکل دوم:
(توجه کنید $Sel_1$ به دو مالتی پلکسر که به ضرب‌کننده متصل هستند، وصل است)
مقدار ذخیره شده در رجیستر صفر در خودش ضرب شده و حاصل به رجیستری دو می‌رود. در نتیجه مقدار رجیستر دو برابر $5×5=25$ می‌شود.
در سیکل سوم:
در این سیکل دو اتفاق میافتد:
۱- مقدار ۱۰ به رجیستر صفر منتقل می‌شود.
۲- مقدار رجیستر یک در خودش ضرب شده و حاصل در رجیستر سه ذخیره می‌شوند. مقدار رجیستر یک برابر ۶ است بنابراین مقدار $6×6=36$ در رجیستر سه ذخیره می‌شود.
در سیکل چهارم:
در این سیکل دو اتفاق میافتد:
۱- مقادیر دو رجیستر دو و سه از هم کم شده و حاصل در رجیستر سه ذخیره می‌شود. مقدار رجیستر دو ۲۵ و رجیستر سه ۳۶ است بنابراین مقدار نهایی رجیتسر سه به $25-36=-11$ می‌رسد.
۲- مقدار فعلی رجیستر صفر که ۱۰ است در خودش ضرب شده و حاصل در رجیستر دو ذخیره می‌شود. بنابراین در انتهای این سیکل مقدار رجیستر دو برابر $10×10=100$ است.
در سیکل پنجم:
در این سیکل مقدار فعلی رجیستر دو که ۱۰۰ است با مقدار رجیستر سه که ۱۱- است جمع شده و حاصل به رجیستر سه منتقل می‌شود. بنابراین مقدار رجیستر سه به $100-11=89$ می‌رسد.
مقدار نهایی رجیستر سه برابر ۸۹ است.
متوسط کد Verilog/VHDL زیر را در نظر بگیرید. با توجه به مقادیر ورودی‌ها که به‌صورت شکل موج داده شده است، خروجی Q کدام است؟ تحلیل مدارات ترتیبی و پارامترهای زمانی فلیپ فلاپ‌ها
Verilog
Module ParReg(D, Id, clr, clk, Q);
input D, Id, clr, clk; output Q;
wire [7 : 0] D; wire Id, clr, clk;
reg [7 : 0] Q;
always@(posedge clk or negedge clr)
if (!clr) begin
Q = 0;
end else begin
if (Id) begin
Q = D;
end
end
end module;
input D, Id, clr, clk; output Q;
wire [7 : 0] D; wire Id, clr, clk;
reg [7 : 0] Q;
always@(posedge clk or negedge clr)
if (!clr) begin
Q = 0;
end else begin
if (Id) begin
Q = D;
end
end
end module;
VHDL
entity ParReg is
port (D: in bit_vector; clk, Id: in bit; Q: out bit_vector);
end entity ParReg;
architecture RTL of ParReg is
begin
L : Process (clk, clr)
begin
if (clr = ‘0’) then
Q <= (others => ‘0’)
elseif (clk ‘ event and clk = ‘1’) then
if (Id = ‘1’) then
Q <= D;
end if;
end if;
end process;
end architecture RTL;
port (D: in bit_vector; clk, Id: in bit; Q: out bit_vector);
end entity ParReg;
architecture RTL of ParReg is
begin
L : Process (clk, clr)
begin
if (clr = ‘0’) then
Q <= (others => ‘0’)
elseif (clk ‘ event and clk = ‘1’) then
if (Id = ‘1’) then
Q <= D;
end if;
end if;
end process;
end architecture RTL;
طبق کدها متوجه می‌شویم که clear پایه‌ی active low و آسنکرون با کلاک است، در لبه مثبت اول کلاک، کلیر 1 (غیر فعال) و لود نیز 1 (فعال) است. طبق کدها در این شرایط می‌توان ورودی D را به خروجی Q انتقال داد (که این مورد در همه گزینه‌ها رعایت شده). حال وقتی در خط‌چین دوم، لبه کلاک منفی می‌شود (پایین می‌رود) و کلیر صفر می‌شود، مقدار خروجی بدون توجه به سایر پایه‌ها صفر خواهد شد (چون کلیر آسنکرون تنظیم شده است) به این ترتیب گزینه‌های 1 و 4 رد می‌شوند چون مقدار خروجی را همچنان 10 نگه داشته‌اند. بین گزینه‌های 2 و 3 تفاوت وقتی دیده می‌شود که از لبه سوم کلاک عبور کرده‌ایم و clear = 0 می‌شود. در این لحظه با توجه به مقدار کلیر، باید Q = 0 شود که در هر 2 گزینه رعایت شده اما در گزینه سوم وقتی لبه بالارونده چهارم کلاک آمده و البته LD هم یک شده، مقدار D را به Q انتقال داده است که اشتباه است چون در این لحظه همچنان clear = 0 است و نمی‌توان خروجی را 1 کرد.
تستهای درس معماری کامپیوتری کنکور کامپیوتر ۱۴۰۲ به همراه جواب تشریحی
آسان اگر یک کامپیوتر از نمایش اعداد مکمل 2 و ثبات‌های 12 بیتی استفاده کند، دامنه نمایش اعداد صحیح در آن کدام است؟ محاسبات
از میان ۱۲ بیت، ۱ بیت به عنوان بیت علامت استفاده می‌شود و دیگر بیت‌ها برای مقادیر اعداد. با ۱۱ بیت می‌توان از 0 تا $2^{11}-1=2047$ را نمایش داد. توجه داشته باشید که در سیستم مکمل ۲ اعداد منفی قابل نمایش یکی بیشتر از مثبت‌ها است.
براساس این توضیحات دامنه نمایش اعداد برای اعداد مثبت حداکثر 247 و برای اعداد منفی حداقل عدد -248 است.
بنابراین گزینه ۱ صحیح است.
آسان در یک سامانه پردازشی، %40 زمان برای دسترسی به حافظه RAM و %30 زمان برای دسترسی به هارد دیسک صرف می‌شود. اگر سرعت دسترسی به حافظه RAM و دیسک را به‌ترتیب دو و سه برابر کنیم، تسریع چقدر می‌شود؟ ارزیابی کارایی
اگر T زمان کل مصرفی در سامانه پردازشی باشد داریم:
$T=T_R+T_H+T_O$
$T_R$ : زمان مصرف شده توسط RAM
$T_H$ : زمان مصرف شده توسط هارددیسک
$T_O$ : زمان مصرف شده توسط باقی اجزاء پردازش
براساس توضیحات سؤال داریم:
$T_R=0.4T,T_H=0.3T,T_O=0.3T$
پس از افزایش سرعت زمان مصرفی RAM نصف شده و زمان هارددیسک $\frac{1}{3}$ می‌شود. اگر $T'$ را به عنوان زمان مصرفی جدید بگیریم داریم:
$T'=\frac{T_R}{2}+\frac{T_H}{3}+T_O=0.2T+0.1T+0.3T=0.6T$
چون سرعت و زمان مصرف شده رابطه عکس با هم دارند، می‌توانیم نسبت سرعت‌ها را با محاسبه عکس نسبت زمان‌های مصرفی بدست آوریم:
$\frac{S'}{S}=\frac{T}{T'}=\frac{T}{0.6T}\approx 1.66$
متوسط می‌خواهیم برای یک بانک ثبات (Register File) شامل 4 ثبات 4 بیتی مداری طراحی کنیم که امکان انتخاب دو ثبات به‌عنوان ورودی به واحد ALU و یک ثبات به‌عنوان محل نگهداری خروجی ALU نیاز داشته باشد. برای طراحی این مدار (به‌غیر از ثبات‌ها) به کمک دیکودر و مالتی پلکسر به چه مشخصاتی نیاز است؟ طراحی کامپیوتر
چون باید ۳ ثبات برای ۲ ورودی و ۱ خروجی ALU انتخاب کنیم نیاز به سه decoder داریم که چون ۴ ثبات داریم decoderها باید 2x4 باشند.
خروجی ALU را به ورودی ۴ ثبات وصل می‌کنیم و ثباتی را که می‌خواهیم خروجی در آن ذخیره شود را بایک decoder مشخص می‌کنیم.
برای ورودی‌های ALU باید دو ثابت انتخاب کنیم برای اینکار به ۱۶ بافر سه حالته برای هر ورودی نیاز داریم. ۱۶ بافر برای این است که ثبات‌ها ۴ بیتی بوده و ما ۴ تا ثبات داریم و باید هر بیت خروجی ثبات را با یک بافر سه حالته کنترل کنیم (به یاد داشته باشید که بافر سه حالته یک ورودی کنترل دارد که اگر ۱ باشد خروجی برابر ورودی دیگر المان است و اگر صفر باشد خروجی high impedance است.)
بنابراین در کل به ۳ دیکدر و ۳۲ بافر سه حالته نیاز داریم.
آسان یک کامپیوتر دارای دستورات و حافظهای با کلمات 32 بیتی، 8 ثبات و 112 دستورالعمل است. هر دستورالعمل از یک بخش Opcode و دو میدان (Field) آدرس تشکیل شده است: یکی برای ثبات و یکی برای حافظه. می‌توان از حافظه در هر ثبات و یا بالعکس، از ثبات در خانه‌ای از حافظه نوشت. امکان جابهجایی مستقیم داده بین خانه‌های حافظه وجود ندارد. تعداد بیت‌های مورد نیاز برای میادین مختلف دستورات کدام است؟ (Opcode, RegAddr, MemAddr) طراحی کامپیوتر
برای RegAddr چون ۸ تا رجیستر داریم $log_2 \ 8=3$ بیت برای دسترسی به آنها کافی است.
برای Opcode نیز چون ۱۱۲ تا دستورالعمل داریم تعداد $⌈log_2\ 112 ⌉=7$ بیت برای مشخص کردن آنها کافی است.
توجه کنید حافظه کلمات ۳۲ بیتی دارد بنابراین هر دستور می‌تواند ۳۲ بیت باشد. ۱۰ بیت را برای دو قسمت قبل استفاده کردیم بنابراین می‌توان $32-10=22$ بیت باقی مانده را برای دسترسی به خانه‌های حافظه در نظر گرفت.
بنابراین جواب نهایی برابر (7,3,22) است.
آسان یک حافظه نهان (Cache) دارای نگاشت مستقیم (Direct Mapping) و ظرفیت 1 MB و حافظه اصلی دارای ظرفیت 512 MB است. بلوک‌های حافظه هرکدام 32 بایتی هستند. میادین مختلف آدرس (Tag, Block, Word Offset) چند بیتی هستند؟ حافظه ها
در روش Direct Mapping سه بخش آدرس به صورت زیر بدست می‌آیند:
Word offset به راحتی از روی گزینه‌های مشخص است که ۵ است، آن هم به دلیل ۳۲ بایتی بودن بلوک‌های حافظه است که از طریق $log_232=5$ بدست آمده است.
تعداد بیت‌های مورد نیاز Block با محاسبه $log_2$ تعداد Blockهایی که حافظه Cache می‌تواند ذخیره کند تعیین می‌شود. در این جا Cache ظرفیت $1MB=2^{20} B$ دارد و هر بلاک $32B=2^5 B$ حافظه نیاز دارد بنابراین:
$\frac{2^{20}}{2^5}=2^{15}\ Block\to {{\mathrm{log}}_2 2^{15}\ }=15\ bits\ for\ Block$
تعداد بیت‌های tag برابر اختلاف تعداد بیت‌های لازم برای آدرس‌دهی حافظه اصلی و Cache می‌باشد. تعداد بیت‌های لازم برای Cache برابر ۲۰ است که حاصل جمع Block و Word offset می‌باشد. تعداد بیت‌های لازم برای حافظه اصلی برابر $log_2512M=log_22^{29}=29$ است. در نتیجه تعداد بیت‌های tag برابر است با:
$29-20=9\ bits\ for\ Tag$
آسان با فرض اینکه X آدرس یک خانه در حافظه است، این برنامه RTL معادل اجرای کدام دستور است؟ RTL
t0: MAR <= X
t1: DR <= M[MAR]
t2: M[MAR] <= A
t3: A <= DR
t1: DR <= M[MAR]
t2: M[MAR] <= A
t3: A <= DR
به ترتیب خطوط دستورات را بررسی می‌کنیم:
در دستور اول، مقدار موجود در حافظه X به یک رجیستر به اسم MAR منتقل می‌شود.
در دستور دوم، از مقدار ذخیره شده در MAR به عنوان آدرس برای دسترسی به حافظه استفاده می‌شود و داده موجود در آن آدرس را در رجیستری به اسم DR می‌ریزد.
در دستور سوم، مقدار A در حافظهای با آدرسی که در MAR ذخیره شده است منتقل می‌شود. این خانه‌ی حافظه همان خانه حافظه در مرحله قبل است و MAR مقدارش برابر با X است. A یک رجیستر است.
در دستور چهارم، مقدار DR در A ریخته می‌شود. DR با توجه به دستورات قبل مقدارش برابر با M[MAR] است.
با توجه به این توضیحات، می‌توان گفت که این دستورات مقدار ذخیره شده در M[MAR] یا همان M[X] را با مقدار ذخیره شده در رجیستر A جابه‌جا می‌کنند. بنابراین گزینه جواب باید XCHG A, X باشد.
بررسی گزینه‌های دیگر:
گزینه ۱:
این گزینه مقدار A را در حافظه با آدرس X منتقل می‌کند.
گزینه ۲:
این دستور مقدار خانه حافظه به آدرس X را به A منتقل می‌کند.
گزینه ۳:
Comp->Compare
این گزینه گویا به مقایسه مقدار حافظه در آدرس X و مقدار A می‌پردازد.
آسان شکل زیر جزء i اُم یک واحد حسابی (Arithmetic Unit) n بیتی است که عملکرد آن با خطوط $S_1S_0$ برای ورودی‌های n بیتی A و B و تک بیت Cin، کنترل می‌شود. $FA_i$ یک تمام افزا (Full Adder) است. طراحی کامپیوتر
اگر $S_1=1$، کدام حالت مربوط به عملکرد این واحد حسابی است؟
وقتی $S_1=1$ است یعنی MUX بسته به مقدار $S_0$ تنها می‌تواند ۱ و $\overline{b_i}$ را خروجی دهد.
در اینجا به یک نکته توجه کنید شکل نمایش داده شده بیانگر یک بیت از دو ورودی و خروجی است، و وقتی با i آن را نمایش داده‌اند به معنی این است که برای تمام بیت‌ها عمل یکسانی صورت می‌گیرد. بنابراین وقتی ۱ به عنوان خروجی MUX انتخاب می‌شود به این معنی است که یک عدد با بیت‌های تمام ۱ با عدد A جمع می‌شود و ما می‌دانیم که جمع شدن با یک عدد تمام یک، معادل با جمع شدن با عدد ۱- است.
با این توضیحات داریم:
اگر $S_0=0$, $C_{in}=0$ باشد، خروجی MUX برابر ۱ است و ما چون carry نداریم Full adders جمع یک عدد تمام یک با A را محاسبه می‌کند که معادل A-1 است.
اگر $S_0=0$, $C_{in}=0$ باشد، مانند قبل اتفاق میافتد با این تفاوت که یک ۱ نیز بدلیل وجود carry به حاصل اضافه می‌شود که حاصل را برابر A می‌کند.
اگر $S_0=1$, $C_{in}=0$ باشد، عدد A با مکمل ۱ عدد B جمع می‌شود که جمع با مکمل یک معادل با $A-B-1$ است.
اگر $S_0=1$, $C_{in}=1$ باشد، مانند قبلی اتفاق میافتد با این تفاوت که یک ۱ نیز اضافه می‌شود $A-B$.
روش دوم: استفاده از دوره های نکته و تست درس های کنکور کامپیوتر
شما با تهیه دوره نکته و تست هر درس از دروس رشته مهندسی کامپیوتر می‌توانید به پاسخ تشریحی تمامی تستهای کنکور، از اولین سال برگزاری دسترسی داشته باشید. علاوه بر روش سنتی حل تستها، روش‌هایی بیان می‌شود که با استفاده از آنها می‌توان بسیاری از تستها را در زمان کمتری حل کرد.
- دوره نکته و تست ساختمان داده و طراحی الگوریتم
- دوره نکته و تست هوش مصنوعی
- دوره نکته و تست درس پایگاه داده
- دوره نکته و تست سیستم عامل
- دوره نکته و تست شبکه های کامپیوتری
- دوره نکته و تست نظریه زبان ها و ماشین ها
- دوره نکته و تست درس سیگنال ها و سیستم ها
- دوره نکته و تست معماری کامپیوتر
- دوره نکته و تست مدار منطقی
- دوره نکته و تست الکترونیک دیجیتال
- دوره نکته و تست ریاضیات گسسته
پاسخنامه کنکور ارشد کامپیوتر
روش دیگری که می‌توانید به پاسخ کلیدی (و نه تشریحی) تست های کنکور ارشد کامپیوتر ۱۴۰۲ دسترسی داشته باشید، استفاده از دفترچه کنکور کامپیوتر سال ۱۴۰۲ است. می‌توانید از صفحه دفترچه سوالات کنکور ارشد مهندسی کامپیوتر تمامی دفترچه‌های کنکور کامپیوتر را به‌صورت رایگان دانلود کنید.
کلید کنکور ارشد کامپیوتر ۱۴۰۲
در تصویر زیر می‌توانید کلید کنکور ارشد کامپیوتر ۱۴۰۲ را ملاحظه فرمایید. در واقع کلید کنکور ارشد همان پاسخ‌نامه‌ای است که توسط سازمان سنجش برای کنکور ارائه می‌شود.
جمع‌بندی
آزمون کارشناسی ارشد کامپیوتر شامل سوالات متنوعی از جمله طراحی الگوریتم و ساختمان داده، شبکه، هوش مصنوعی و ... است. داوطلبان برای پاسخگویی به این سوالات نیاز به دانش عمیق و تسلط بر مباحث مورد نظر دارند و لازم است که از منابع مناسبی مانند دوره نکته و تست و پلتفرم آزمون استفاده کنند.
چه روش‌هایی برای دسترسی به جواب تشریحی کنکور کامپیوتر ۱۴۰۲ وجود دارد؟
دو روش: (۱) پلتفرم آزمون (۲) دوره‌های نکته و تست
چگونه به کلید کنکور ارشد کامپیوتر ۱۴۰۲ دسترسی داشته باشم؟
می‌توانید کلید کنکور ارشد کامپیوتر ۱۴۰۲ و سایر کنکورها را از صفحه دفترچه‌های کنکور ارشد کامپیوتر که در بالا معرفی کردیم، دانلود نمایید.
