حل یک تست بدون دسترسی به پاسخ تشریحی ناممکن است. ازاین‌رو، شما باید به جواب تشریحی تمامی تستهای کنکور برای هر درس دسترسی داشته باشید. این مقاله به بررسی روش‌هایی می‌پردازد که می‌توانید به پاسخ تشریحی کنکور ارشد فناوری اطلاعات ۱۴۰۰ دسترسی داشته باشید.
روش های دسترسی به پاسخ نامه تشریحی تست های کنکور ارشد فناوری اطلاعات ۱۴۰۰
مؤسسه کنکور کامپیوتر دو روش برای دسترسی به پاسخ نامه تشریحی تست های کنکور ارشد آیتی ۱۴۰۰ برایتان فراهم کرده است:
روش اول: استفاده از پلتفرم آزمون کنکور کامپیوتر
پلتفرم آزمون با گردآوری جواب تشریحی تمامی تستهای کنکور برای تمامی درس‌ها، یک منبع جامع برای دانشجویان است که آنها را از کتاب‌های درسی بی‌نیاز می‌کند. همچنین امکان ایجاد آزمون، رقابت با دیگر دانشجویان و… نیز از دیگر مزایای این محیط است. برای کسب اطلاعات بیشتر می‌توانید به صفحه پلتفرم آزمون مراجعه کنید.
برای آشنایی شما کیفیت پاسخ‌نامه‌های تشریحی این پلتفرم، پاسخ تشریحی تستهای کنکور فناوری اطلاعات ۱۴۰۰ برای درس‌‌های ساختمان داده و الگوریتم، هوش مصنوعی، پایگاه داده و ریاضیات گسسته و ... در زیر آورده شده است:
پاسخ نامه تشریحی تست های درس پایگاه داده کنکور فناوری اطلاعات ۱۴۰۰
دشوار
در رابطه $R = (A,B,C,D,E,F)$ وابستگی‌های زیر برقرار است.
طراحی پایگاه داده
$A \to F$
$B \to C$
$ABC \to E$
در این رابطه چند سوپر کلید وجود دارد؟
گزینه 4 صحیح است.
D، B، A در سمت راست رابطه وجود ندارد (نمی‌توان به آنها رسید) بنابراین قطعاً جزئی از کلید کاندید می‌باشند.
$\left. \begin{array}{c}
\text{جزء}\mathrm{\ }\text{کلید}\ A\to F \\
\text{جزء}\text{کلید}\ B\to C \end{array}
\right\}\Rightarrow ABC\to E\Rightarrow
$ کلید اصلی است ABD پوشش داده شد، بنابراین A، B، C ،F، E تمام خصیصه‌های
\text{جزء}\mathrm{\ }\text{کلید}\ A\to F \\
\text{جزء}\text{کلید}\ B\to C \end{array}
\right\}\Rightarrow ABC\to E\Rightarrow
$ کلید اصلی است ABD پوشش داده شد، بنابراین A، B، C ،F، E تمام خصیصه‌های
برای تعداد ابرکلید، خصیصه‌های کلید اصلی یعنی D, B, A که کلید اصلی است حتماً باید در کلید باشند و دیگر خصیصه‌ها می‌توانند باشند یا نباشند پس برای هر خصیصه 2 حالت وجود دارد.
$
ABD\left(2^{\mathrm{\ }\text{تعداد}\mathrm{\ }\text{ستونهای}\mathrm{\ }\text{دیگر}}\right)=2^3=8
$
ABD\left(2^{\mathrm{\ }\text{تعداد}\mathrm{\ }\text{ستونهای}\mathrm{\ }\text{دیگر}}\right)=2^3=8
$
آسان
کدام مورد در خصوص رابطه درست است؟
طراحی پایگاه داده
گزینه 4 صحیح است.
گزینه 1: رابطه‌ی نرمال نباید صفات چندمقداری داشته باشد اما لزوماً رابطه‌ای که صفات چندمقداری ندارد نرمال نیست. پس این گزینه غلط است.
گزینه 2: کلید کاندید، کلید کمینه است و با حذف هرجزء آن خاصیت کلیدی‌اش را از دست می‌دهد. پس این گزینه غلط است.
توجه: ابرکلید می‌تواند کاهش‌پذیر باشد.
توجه: ابرکلید می‌تواند کاهش‌پذیر باشد.
گزینه 3: ترتیب و جابجایی تاپل‌ها دررابطه اهمیتی ندارد، این گزینه غلط است.
گزینه 4: صحیح است.
متوسط
فرض کنید در یک جدول $N \ge 3$ خصیصه داریم. در این جدول دو کلید کاندید وجود دارد. یک کلید کاندید دارای دو خصیصه است و یک کلید کاندید دیگر دارای یک خصیصه. بین خصیصه‌های این دو کلید هم‌پوشانی وجود ندارد. تعداد کل سوپر کلیدها در این جدول کدام است؟
پایگاه داده رابطه‌ای
گزینه 3 صحیح است.
باتوجه به شرایط سؤال فرض می‌کنیم 2 کلید کاندید یکی A و دیگری BC را داریم.
$
\text{تعداد}\mathrm{\ }\text{سوپر کلید}\mathrm{\ }\text{جدول}=\left[\mathrm{A\ }\text{تعداد}\mathrm{\ }\text{سوپر کلید}\mathrm{\ }\text{ترکیب}\mathrm{\ }\text{با}+\mathrm{BC}\mathrm{\ }\text{تعداد}\mathrm{\ }\text{سوپر کلید}\mathrm{\ }\text{ترکیب}\mathrm{\ }\text{با}\right]-\mathrm{ABC}\mathrm{\ }\text{تعداد}\mathrm{\ }\text{سوپر کلید}\mathrm{\ }\text{ترکیب}\mathrm{\ }\text{با}
$
\text{تعداد}\mathrm{\ }\text{سوپر کلید}\mathrm{\ }\text{جدول}=\left[\mathrm{A\ }\text{تعداد}\mathrm{\ }\text{سوپر کلید}\mathrm{\ }\text{ترکیب}\mathrm{\ }\text{با}+\mathrm{BC}\mathrm{\ }\text{تعداد}\mathrm{\ }\text{سوپر کلید}\mathrm{\ }\text{ترکیب}\mathrm{\ }\text{با}\right]-\mathrm{ABC}\mathrm{\ }\text{تعداد}\mathrm{\ }\text{سوپر کلید}\mathrm{\ }\text{ترکیب}\mathrm{\ }\text{با}
$
* توجه داشته باشید سوپرکلیدهای ترکیبی با ABC بین سوپرکلیدهای با BC و سوپرکلیدهای با A مشترک است و 2 بار حساب شده‌اند بنابراین لازم است یکبار آنها را کم کنیم.
$\mathrm{A}\mathrm{\ }\text{ستون}\mathrm{\ }\text{دیگر}\mathrm{\ }\text{با}\mathrm{\ n-1}\mathrm{\ }\text{ترکیب}\mathrm{\ =\ }{\mathrm{2}}^{\mathrm{n-1}}$
$\mathrm{BC}\mathrm{\ }\text{ستون}\mathrm{\ }\text{دیگر}\mathrm{\ }\text{با}\mathrm{\ n-2}\mathrm{\ }\text{ترکیب}\mathrm{\ =\ }{\mathrm{2}}^{\mathrm{n-2}}
$
$
$\mathrm{ABC}\mathrm{\ }\text{ستون}\mathrm{\ }\text{دیگر}\mathrm{\ }\text{با}\mathrm{\ n-3}\mathrm{\ }\text{ترکیب}\mathrm{\ =\ }{\mathrm{2}}^{\mathrm{n-3}}
$
$
در سوپرکلید، کلید کاندید حتماً باید باشند و برای بقیه ستون‌ها 2 حالت وجود دارد. می‌توانند باشند یا نباشند بنابراین $
{\mathrm{2}}^{\mathrm{(}\text{تعداد}\mathrm{\ }\text{ستون های}\mathrm{\ }\text{غیر از}\mathrm{\ }\text{کلید}\mathrm{\ }\text{کاندید}\mathrm{)}}
$ حالت برای سوپرکلید داریم.
{\mathrm{2}}^{\mathrm{(}\text{تعداد}\mathrm{\ }\text{ستون های}\mathrm{\ }\text{غیر از}\mathrm{\ }\text{کلید}\mathrm{\ }\text{کاندید}\mathrm{)}}
$ حالت برای سوپرکلید داریم.
تعداد سوپر کلید جدول $=\ 2^{n-1}+2^{n-2}-2^{n-3}=2^{n-3}\left(2^2+2-1\right)=5\times2^{n-3}$
دشوار
رابطه $R = (A,B,C,D,E,F)$ را در نظر بگیرید. اگر مجموعه وابستگی‌های تابعی F روی R برقرار باشد، کدام‌یک از تجزیه‌های زیر دارای گمشدگی (lossless) است؟
طراحی پایگاه داده
$F = \{A \to BC , CD \to E , B \to D , E \to A\}$
در این سؤال خطای تایپی F در متن سؤال وجود دارد. همچنین طراح در متن سؤال دارای گمشدگی و در پرانتز (lossless) عدم گمشدگی را خواسته است و این سؤال حذف شد.
طبق قضیه ریسانن در تجزیه مطلوب برای نداشتن گمشدگی باید خصیصه مشترک در 2 رابطه حداقل در یکی از آنها کلید کاندید باشد.
متوسط
رابطه R=(a,b,c) و عبارات جبر رابطه ای زیر را در نظر بگیرید:
پایگاه داده رابطه‌ای
$Q1:P(S(a,b1,c1),R)$ $Q2:{\underset{b,c}{\prod}} {({\underset{b=c}{\sigma}} \ \ R})$
$P\left(T,S\bowtie R\right)$
${\underset{b1,c}{\prod}} ({\underset{b1=c}{\sigma}} \ \ T)$
گزینه 3 صحیح است. در پرس‌و‌جوی اول یک جدول $R$ را تغییرنام داده به $S$ که ستونهای $a$ همان $a$ ولی $b,c$ را به $b_1,c_1$ تغییرنام داده و در خط بعدی با پیوند داخلی $R\infty S$ یک جدول جدید ایجاد می‌شود که به $T$ نام‌گذاری کرد. در پیوند داخلی براساس ستون مشترک $a$ ضرب انجام می‌شود. ادامه دستور مانند همان $Q_2$ است. دقت کنید پرس‌و‌جوی اول ضرب است و ستونهای بیشتری تولید می‌کند پس $Q_2$ زیرمجموعه‌ی $Q_1$ است.
دشوار
رابطه $R = (A,B,C,D,E,F,G)$ را با وابستگی‌های زیر در نظر بگیرید.
طراحی پایگاه داده
$AF \to BE$
$FC \to DE$
$F \to CD$
$D \to E$
$C \to A$
حاصل تجزیه 3NF این رابطه چند رابطه خواهد بود؟
در کلید نهایی سنجش گزینه 2 و3 را پاسخ اعلام کرد.
F ،G را سمت راست رابطه نداریم پس قطعاً جزئی از کلید می‌باشند.
$\left. \begin{array}{c}
\mathrm{(}\text{جزئی}\mathrm{\ }از\mathrm{\ }\text{کلید}\ G,\ F) \\
F\to CD \end{array}
\right\}\Rightarrow \left. \begin{array}{c}
\left(F,G,C,D\right) \\
FC\to CD \\
D\to E \\
C\to A \end{array}
\right\}\Rightarrow \left(F,G,C,D,E,A\right)
$
\mathrm{(}\text{جزئی}\mathrm{\ }از\mathrm{\ }\text{کلید}\ G,\ F) \\
F\to CD \end{array}
\right\}\Rightarrow \left. \begin{array}{c}
\left(F,G,C,D\right) \\
FC\to CD \\
D\to E \\
C\to A \end{array}
\right\}\Rightarrow \left(F,G,C,D,E,A\right)
$
به کل رابطه R رسیدیم پس FG کلید رابطه است.
در ساده‌سازی رابطه می‌توان A و C را از سمت چپ رابطه حذف کرد.
در ساده‌سازی رابطه می‌توان A و C را از سمت چپ رابطه حذف کرد.
$\left. \begin{array}{c}
F\to CD \\
C\to A \end{array}
\right\}\Rightarrow \left. \begin{array}{c}
\text{رسید}\mathrm{\ }\mathrm{A\ }\text{می توان}\mathrm{\ }\text{به}\mathrm{\ }\mathrm{F\ }از \\
AF\to BE \end{array}
\right\}{{\stackrel{\text{می توان}\mathrm{\ }\text{نوشت}}{\longrightarrow}F\to DE\Rightarrow \left\{ \begin{array}{c}
F\to D \\
F\to E \end{array}
\right.}}
$
F\to CD \\
C\to A \end{array}
\right\}\Rightarrow \left. \begin{array}{c}
\text{رسید}\mathrm{\ }\mathrm{A\ }\text{می توان}\mathrm{\ }\text{به}\mathrm{\ }\mathrm{F\ }از \\
AF\to BE \end{array}
\right\}{{\stackrel{\text{می توان}\mathrm{\ }\text{نوشت}}{\longrightarrow}F\to DE\Rightarrow \left\{ \begin{array}{c}
F\to D \\
F\to E \end{array}
\right.}}
$
$\left. \begin{array}{c}
FC\to DE \\
F\to CD \end{array}
\right\}\Rightarrow \text{حذف}\mathrm{\ }\text{کرد}\ FC\ را\mathrm{\ }در\ C\mathrm{\ }\text{طبق}\mathrm{\ }\text{بالا}\mathrm{\ }\text{می توان}\Rightarrow F\to DE\Rightarrow \left\{ \begin{array}{c}
F\to D \\
F\to E \end{array}
\right.
$
FC\to DE \\
F\to CD \end{array}
\right\}\Rightarrow \text{حذف}\mathrm{\ }\text{کرد}\ FC\ را\mathrm{\ }در\ C\mathrm{\ }\text{طبق}\mathrm{\ }\text{بالا}\mathrm{\ }\text{می توان}\Rightarrow F\to DE\Rightarrow \left\{ \begin{array}{c}
F\to D \\
F\to E \end{array}
\right.
$
بعد از ساده سازی داریم: $\begin{array}{c}
F\to B \\
F\to E \\
F\to C \\
F\to D \\
D\to E \\
C\to A \end{array}
$
F\to B \\
F\to E \\
F\to C \\
F\to D \\
D\to E \\
C\to A \end{array}
$
در این رابطه (B, E, C, D) غیرکلید $\rightarrow$ جزء کلید (F) داریم. پس رابطه نرمال سطح دو 2NF نیست. کافی است G را جدا کنیم تا F به‌تنهایی کلید باشد و دیگر جزئی از کلید نباشد.
داریم $R_2\left(F,G\right)$ و $R_1\left(A,B,C,D,E,F\right)$، $R_2$ نرمال 2NF و 3NF است ولی در $R_1$، [$\left(E,A\right)$ غیرکلید $\rightarrow$ غیرکلید $\left(C,D\right)$]داریم. پس باید به 3 رابطه‌ای $R_{11}\left(D,E\right)$، $R_{12}\left(A,C\right)$، $R_{13}\left(F,B,C,D\right)$ تجزیه کنیم تا 3NF شود. حاصل تجزیه 4 رابطه است.
$R\left(A,B,C,D,E,F,G\right)\left\{ \begin{array}{c}
R_1\left(A,B,C,D,E\right)\left\{ \begin{array}{c}
R_{11}\left(D,E\right)\ \ \ \ \ \ \ \ \ \ \\
R_{12}\left(C,A\right)\ \ \ \ \ \ \ \ \ \ \\
R_{13}\left(F,B,C,D\right) \end{array}
\right. \\
R_2\left(F,G\right)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{array}
\right.
$
R_1\left(A,B,C,D,E\right)\left\{ \begin{array}{c}
R_{11}\left(D,E\right)\ \ \ \ \ \ \ \ \ \ \\
R_{12}\left(C,A\right)\ \ \ \ \ \ \ \ \ \ \\
R_{13}\left(F,B,C,D\right) \end{array}
\right. \\
R_2\left(F,G\right)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{array}
\right.
$
پاسخ نامه تشریحی تست های درس هوش مصنوعی کنکور فناوری اطلاعات ۱۴۰۰
دشوار
فرض کنید که پایگاه دانشی به فرم زیر در دسترس است.
منطق مرتبه اول
| $\mathrm{\ \ }\mathrm{\forall }\mathrm{A,B:\ \ \ T}\left(\mathrm{A\ ,\ B}\right)\Rightarrow \neg \mathrm{T}\left(\mathrm{B\ ,\ A}\right)$ | (1) |
| $\mathrm{\forall }\mathrm{A,B,C:\ \ \ T}\left(\mathrm{A\ ,\ B}\right)\wedge \mathrm{T}\left(\mathrm{B\ ,\ C}\right)\Rightarrow \mathrm{T}\left(\mathrm{A\ ,\ C}\right)$ | (2) |
| $T(x , y)$ | (3) |
| $T( y , z)$ | (4) |
حال فرض کنید می‌خواهیم پرسش $(5)\ \alpha = T(x,z)$ را با استفاده از روش تجزیه، استنتاج کنیم. کدام ترتیب بر روی گزاره‌های پایگاه دانش برای این استنتاج می‌تواند استفاده شود؟ (از راست به چپ)
گزینه صحیح 2 است.
برای استنتاج عبارت داده شده ابتدا نقیض آن را به پایگاه دانش اضافه کرده و سعی می‌کنیم به تناقض برسیم. درخت زیر مراحل استنتاج متغیر خواسته شده در صورت سوال را نشان می‌دهد که با توجه به شکل زیر و اینکه از قانون شماره یک در استنتاج استفاده نشده است می‌توان گفت بهترین گزینه برای این سوال گزینه شماره ۲ است.
دشوار
دنیای مکعب‌ها (شامل سه مکعب $A$، $B$ و $C$) را درنظر بگیرید. $P(x , y)$ نشان می‌دهد که مکعب $x$ جزء یکی از مکعب‌های بالای مکعب $y$ است، از بین جملات زیر کدام گزینه فقط شامل جملات درست است؟
منطق مرتبه اول
$α\mathrm{:\ }\mathrm{\forall }\mathrm{x\ }\mathrm{\forall }\mathrm{y\ P}\left(\mathrm{x\ ,\ y}\right)\mathrm{\Rightarrow }\mathrm{\neg P}\left(\mathrm{y\ ,\ x}\right)\mathrm{\ }$
$β\mathrm{:\ }\mathrm{\forall }\mathrm{x\ }\mathrm{\forall }\mathrm{y\ }\mathrm{\forall }\mathrm{z\ P}\left(\mathrm{x\ ,\ y}\right)\mathrm{\wedge }\mathrm{\ P}\left(\mathrm{y\ ,\ z}\right)\mathrm{\Rightarrow }\mathrm{\ P}\left(\mathrm{x\ ,\ z}\right)$
$γ\mathrm{:\ }\mathrm{\exists }\mathrm{x\ }\mathrm{\forall }\mathrm{y\ \neg P}\left(\mathrm{y\ ,\ x}\right)$
$δ\mathrm{:\ }\mathrm{\forall }\mathrm{x\ }\mathrm{\exists }\mathrm{y\ P}\left(\mathrm{y\ ,\ x}\right)$
گزینه 1 صحیح است.
$\alpha$ : این عبارت بیانگر این است که اگر به ازای هر مکعب x و x ، y یکی از مکعب‌های بالایی y باشد آنگاه y نمی‌تواند جز مکعب‌هایی بالایی x باشد چون میدانیم x بالای y است و این عبارت درست است.
$\beta$ : این عبارت می‌گوید به ازای هر سه مکعب اگر x بالای y باشد و y هم بالای z باشد می‌توان گفت x بالای z نیز هست که عبارتی درست است.
$\gamma$ : این عبارت می‌گوید مکعبی وجود دارد که هیچ مکعب دیگری روی آن نیست و این عبارت نیز درست است چرا که همواره این شرط برای بالاترین مکعب برقرار است.
$\delta$ : این عبارت می‌گوید برای همه مکعب‌ها یک مکعب وجود دارد که روی آن قرار گرفته است و این عبارت نادرست است چرا که برای بالاترین مکعب این شرط برقرار نیست.
دشوار
کدام گزاره درست است؟
منطق گزاره‌ای
گزینه 1 صحیح است.
گزینه ۱ : این گزینه درست است زیرا در صورتی که سمت چپ یک استنتاج False باشد مستقل از اینکه سمت راست آن چه ارزشی دارد می‌توان ارزش کل گزاره را درست در نظر گرفت در نتیجه این گزاره همواره درست است.
گزینه ۲ : در صورتی که یک جمله برقرار باشد نقیض آن همواره نادرست است و نقیض عبارت $KB\ \models \ \alpha $ برابر $KB \ \wedge \ \neg \alpha$ می‌باشد نه $\neg KB\ \vee \ \ \alpha $.
گزینه ۳ : از آن جایی که گفته شده است $KB=\alpha$ است می‌توان عبارت $KB \ \wedge \ \neg \alpha$ را به صورت $\alpha \ \wedge \ \neg \alpha$ نوشت که میدانیم عبارتی ارضاناپذیر است.
گزینه ۴ : در این صورت می‌توان گفت $M(\alpha) \subseteq M(\beta)$ یا همان $\alpha \models \beta $ برقرار است.
دشوار
مسئله CSP شامل سه متغیر بولین A, B, C و عبارت‌های زیر که نشان‌دهنده‌ی محدودیت‌ها روی مقدار این متغیر‌هاست را درنظر بگیرید:
مسائل ارضای محدودیت
$\mathrm{A\ }\mathrm{\vee }\mathrm{\ B}$
$\mathrm{A\ }\mathrm{\vee }\mathrm{\ C}$
$\mathrm{\neg }\mathrm{B}\mathrm{\ }\mathrm{\vee }\mathrm{\ \neg C}$
$\mathrm{B}\mathrm{\ }\mathrm{\vee }\mathrm{\ \neg C}$
فرض کنید هنگام جستجو در مقداردهی‌ها، ترتیب متغیرها به ترتیب الفبایی و ترتیب مقادیر به‌صورت اول F و بعد T درنظر گرفته شود. ترتیب مقداردهی‌هایی که (از چپ به راست) به متغیرها توسط الگوریتم DFS با عقب‌گرد (backtrack) و استفاده از forward checking برای رسیدن به اولین جواب صورت می‌گیرد، کدام است؟
گزینه 3 صحیح است.
با توجه به ترتیب انتخاب متغیرها و ترتیب مقادیر به‌صورت اول F و بعد T ، درخت حاصل از اجرای این الگوریتم با توجه به محدودیت‌های در نظر گرفته شده در ادامه نشان داده شده است.
محدودیت‌ها :
1- A ∨ B
2- A ∨ C
3- ¬B ∨ ¬C
4- B ∨ ¬C
در این روش ابتدا متغیر A را انتخاب کرده و مقدار آن را به F تنظیم می‌کنیم در نتیجه با توجه به محدودیت شماره یک مقدار F از دامنه B و C حذف می‌شود. پس از آن متغیر B انتخاب می‌شود و مقدار آن را T در نظر می‌گیریم اما در این حالت با توجه به محدویت‌های شماره ۳ و ۴ دامنه مربوط به متغیر C تهی می‌شود و مجبور می‌شویم که عقب‌گرد انجام دهیم. در نتیجه به متغیر A که می‌تواند در این مرحله مقدار T بگیرد باز می‌گردیم. با این مقداردهی هیچ تغییر در دامنه متغیرها ایجاد نمی‌شود و در مرحله بعد متغیر B را انتخاب کرده و مقدار F را برای آن تنظیم می‌کنیم. در این حالت مقدار T از دامنه مقادیر C حذف می‌شود ولی هم‌چنان مقدار F برای آن معتبر است و پس از آن متغیر C انتخاب شده و مقدار آن را F در نظر گرفته و به پاسخ می‌رسیم.
دشوار
مسئله برج هانوی را درنظر بگیرید که در آن قرار است دیسک‌هایی که در شروع به ترتیب بزرگ به کوچک روی میله‌ی شماره 1 قرار گرفته‌اند، در انتها به همین ترتیب روی میله‌ی شماره 3 قرار گرفته باشند. کنش‌ها در این محیط می‌توانند دیسکی را که روی آن چیزی قرار نگرفته (یا به عبارت دیگر بالاترین دیسک روی یک میله است) را به یک میله خالی یا روی یک دیسک بزرگ‌تر منتقل کند. فرض کنید دیسک با کوچک‌ترین اندازه 1 واحد، دیسک متوسط 2 واحد و دیسک بزرگ 3 واحد وزن داشته باشد و هزینه‌ی انتقال هر واحد وزن بین دو میله با فاصله 1 برابر 1 واحد ولی بین دو میله با فاصله 2 به واسطه نداشتن استراحت برابر 3 واحد باشد. اگر هزینه‌ی کلی انتقال هر دیسک ضرب تعداد واحد وزن آن در هزینه جابه‌جایی هر واحد وزن باشد، کدام گزینه میزان هزینه‌ی کلی (یا مقدار تابع g(n)) برای 3 گره اولی که توسط الگوریتم UCS با فرض جستجوی گرافی گسترش می‌یابند (یا به عبارت دیگر از صف برداشته می‌شوند) را به درستی نشان می‌دهد و همچنین از بین توابع ابتکاری (heuristic) زیر کدام موارد قابل قبول (admissible) هستند؟ (قاعدتاً در تمام فضای جستجو)
الگوریتم های جستجوی آگاهانه
\( {h}_1 \) : سه برابر جمع وزن دیسک‌های روی میله‌ی اول
\( {h}_2 \) : جمع وزن دیسک‌های روی میله‌ی دوم
گزینه 3 صحیح است.
در ابتدا الگوریتم UCS را در مسئله داده شده اجرا می‌کنیم. در مرحله ابتدایی این الگوریتم دو انتخاب دارد که در شکل زیر نشان داده شده است و یکی هزینه ۳ و دیگری هزینه ۱ دارد. با توجه به این روش گره با هزینه ۱ انتخاب می‌شود. پس از آن با توجه به اینکه در صورت سوال گفته شده است که روش جستجو گرافی است از این گره به دو گره دیگر می‌توان رفت که در شکل زیر مشخص شده‌اند و یکی از این گره‌ها مشابه یکی از گره‌ها قبلی موجود در صف است و از آن‌جایی که g(n) کمتری دارد باعث بروزرسانی گره قبلی می‌شود (به این معنی که گره قبلی حذف و گره جدید جایگزین آن می‌شود). با توجه به شکل گره سوم برای بسط با توجه به مقادیر g(n) که در کنار هر شکل مشخص شده است، گره با g(n) برابر ۴ می‌باشد و تا به اینجا یکی از گزینه‌های ۳ یا ۴ درست هستند.
در مورد قابل قبول بودن توابع ابتکاری داده شده نیز تابع $h_1$ با توجه به مثال زیر قابل قبول نیست چرا که در این مثال می‌توان طی دو مرحله با انتقال دیسک با وزن یک به میله دوم و سپس میله سوم با هزینه ۲ به هدف رسید در صورتی که مقدار هیوریستیک در این حالت برابر ۳ می‌باشد.
اما تابع $h_2$ قابل قبول است چرا که برای انتقال دیسک‌های روی میله دوم و رسیدن به هدف باید هر کدام از آنها را حداقل یکبار و به میله با حداقل یک فاصله انتقال دهیم پس در هر صورت اندازه جمع وزن دیسک‌های روی میله دوم از هزینه واقعی رسیدن به هدف کمتر مساوی می‌باشد.
متوسط
فرض کنید می‌خواهیم در یک مسئله جستجو از روش \( {A}^* \) استفاده کنیم. در این مسئله دو تابع مکاشفه قابل قبول \( {h}_1 \) و \( {h}_2 \) تعریف شده‌اند. کدام یک از روش‌های زیر حالت بهینه هدف را پیدا می‌کند؟
الگوریتم های جستجوی آگاهانه
گزینه 4 صحیح است.
ابتدا دو نکته را یادآوری می‌کنیم :
۱- در روش جستجوی A* :
- در حالت جستجوی درختی در صورتی که تابع هیوریستیک قابل قبول باشد، الگوریتم A* پاسخ بهینه را تضمین می‌کند .
- در حالت جستجوی گرافی در صورتی که تابع هیوریستیک سازگار باشد، الگوریتم A* پاسخ بهینه را تضمین می‌کند.
۲- در صورتی که چند تابع هیوریستیک قابل قبول داشته باشیم، میانگین حسابی و هندسی ،max و min آنها نیز قابل قبول هستند چرا که در این توابع نیز هیچگاه مقدار h(n) تخمین زده شده برای یک گره بیشتر از مقدار اصلی هزینه مسیر آن گره تا گره هدف نمی‌شود.
گزینه ۱ : مجموع دو تابع هیوریستک قابل قبول لزوما یک تابع هیوریستیک قابل قبول نیست در نتیجه در این حالت تضمینی برای یافتن حالت بهینه نداریم.
گزینه ۲ : حاصلضرب دو تابع هیوریستک قابل قبول لزوما یک تابع هیوریستیک قابل قبول نیست در نتیجه در این حالت تضمینی برای یافتن حالت بهینه نداریم.
گزینه ۳ : min دو تابع هیوریسیتک قابل قبول، باز هم تابعی قابل قبول است اما در روش A* برای اینکه بخواهیم الگوریتم پاسخ بهینه را تضمین کند در حالتی که تابع هیوریستیک قابل قبول است نیاز به جستجو درختی داریم نه گرافی.
گزینه ۴ : تابع داده شده در این گزینه قابل قبول است و اثبات آن در ادامه آمده است از طرفی طبق نکته اول جستجوی اشاره شده در این گزینه درختی است پس می‌توان تضمین کرد که پاسخ بهینه در این شرایط یافت می‌شود.
$\forall n\ \ \ h_1(n)\ \le \ h^*(n)\ \ \ \ \ \ $
$\forall n\ \ \ h_2(n)\ \le \ h^*(n)$
$\forall n\ h_2\left(n\right)+2h_1\left(n\right)\le 3h^*\left(n\right)$
$\forall n\frac{\ h_2\left(n\right)+2h_1\left(n\right)}{3}\le h^*\left(n\right)\ \ \ \ \ \ \ $
آسان
کدام یک از موارد زیر در خصوص الگوریتم عمیق‌سازی تکرارشونده (iterative deepening) درست است؟
الگوریتم های جستجوی ناآگاهانه
گزینه 4 صحیح است.
یادآوری :
الگوریتم DFS یک الگوریتم جستجو ناآگاهانه است که ممکن است در عمق نامتناهی بیفتد به همین دلیل در یک نوع آن که DLS (Depth Limited Search) نام دارد این الگوریتم را فقط تا عمق معینی اجرا می‌کنیم اما بسته به اینکه هدف در عمق بیشتر یا کمتر از عمق تعیین شده باشد ممکن است نتوانیم به هدف برسیم و به طور کلی به دلیل اینکه عمق جواب را نمی‌دانیم، تعیین پارامتر عمق برای این روش سخت است. روش دیگری که برای رفع این مشکل ارائه شد IDS (Iterative Deepening Search) است. در این الگوریتم ، در یک حلقه عمق را از صفر تا بی‌نهایت یکی یکی زیاد می‌کنیم و در هر مرحله الگوریتم DLS را با آن اجرا می کنیم. کد زیر پیاده‌سازی این الگوریتم را نشان می‌دهد.
function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure
for depth = 0 to ∞ do
result ← DEPTH-LIMITED-SEARCH(problem, depth)
if result ≠ cutoff then return result
for depth = 0 to ∞ do
result ← DEPTH-LIMITED-SEARCH(problem, depth)
if result ≠ cutoff then return result
گزینه ۱ : نادرست است چرا که مثلا ریشه در هر تکرار ملاقات می‌شود اما گره هدف فقط در تکرار آخر ملاقات می‌شود.
گزینه ۲ : مرتبه زمانی هر دو الگوریتم $O(b^d)$ می‌باشد اما تعداد گره‌هایی که در روش IDS تولید می‌شود بیشتر است.
گزینه ۳ : میزان حافظه مورد استفاده این روش از مرتبه O(bd) است و در صورتی که از روش عقب‌گرد استفاده شود به O(d) قابل کاهش است.
گزینه ۴ : پاسخ این گزینه است.
پاسخ نامه تشریحی تست های درس شبکه های کامپیوتری کنکور فناوری اطلاعات ۱۴۰۰
آسان
روتری را در نظر بگیرید که سه زیر شبکه X و Y و Z را به هم متصل می‌کند. فرض کنید که همه واسط‌ها در این سه زیر شبکه باید پیشوند 0/21، 80، 2، 13 داشته باشند. فرض کنید زیر شبکه X باید از 1000 واسط پشتیبانی کند و هر کدام از زیر شبکه‌های Yو Z باید 500 واسط را آدرس‌دهی کنند. کدام مجموعه از آدرس‌های زیر این شرایط را برآورده می‌سازد؟
لایه شبکه
IP های در دسترس در این شبکه به‌صورت زیر است: (X به معنای این است که این قسمت فیکس نشده و می‌تواند صفر یا یک باشد):
IP: 13.2.01010XXX.XXXXXXXX اولیه موجود
ما در اینجا 11 جای خالی داریم که می‌توان$2^{11}$ یا 2048 آدرس تولید کرد. ابتدا چون برای زیرشبکه X، 1000 IP می‌خواهیم 1024 تای آن را به X اختصاص میدهیم. سپس از آدرس‌های باقی‌مانده، 512 تا را به زیرشبکه Z، Y میدهیم:
13.2.80.0/22 یا : 13.2.010100XX.XXXXXXXX زیرشبکه X
13.2.84.0/23 یا : 13.2.0101010X.XXXXXXXX زیرشبکه Y
13.2.86.0/23 یا : 13.2.0101011X.XXXXXXXX زیرشبکه Z
متوسط
یک کنترل کننده SDN با استفاده از APIهای شمالی و جنوبی اقدام به تبادل پیام می‌کند. کنترلر به API جنوبی چه پیام‌هایی می‌فرستد و مقصد این پیام‌ها کدامند؟ کنترلر از طریق API شمالی چه پیام‌هایی را و از کجا دریافت می‌کند؟
لایه شبکه
به‌طور کلی در SDN، پیام‌ها از طریق API جنوبی با سوئیچ‌ها در ارتباط‌اند و از طریق API شمالی با برنامه‌ها
آسان
برای این که یک صفحه وب شامل یک فایل GIF را از یک سرور HTTP1.0 که آدرس IP آن را نمی‌دانیم بازیابی کنیم، علاوه بر HTTP از کدام پروتکل‌های لایه کاربرد و انتقال باید استفاده کنیم؟ (فایل GIF روی همان سرور وب قرار دارد.)
لایه کاربرد
ما میدانیم که برای اینکه اسم یک سرور را به آدرس یا یک IP مشخص ترجمه کنیم، از DNS استفاده می‌کنیم که به ما به‌ازای هرسرور، یک IP یکتا می‌دهد. زمانی که ما IP سروری را نداریم مشخص است که باید از پروتکل DNS استفاده کنیم.
متوسط
توپولوژی زیر را در نظر بگیرید که در آن هاست S قصد دارد یک فایل بسیار بزرگ چند گیگابایتی را برای R بفرستد. تاخیر انتشار و ارسال لینک‌ها بر روی آنها نوشته شده است. فرستنده از پروتکل پنجره لغزان با اندازه پنجره 10 بسته استفاده می‌کند. فرض کنید که حداکثر اندازه صف ارسال در لینک متصل از سوئیچ به R برابر 30 بسته است. اندازه هر بسته داده 1000 بایت و اندازه هر بسته ack برابر 40 بایت است. فرض کنید که هیچ جریان ترافیکی دیگری در شبکه وجود ندارد. نرخ تقریبی ارسال از S به R کدام است؟ در شکل B بیانگر بایت است.
اصول و مقدمات شبکه‌های کامپیوتری
در این‌گونه سؤالات باید ببینیم که از زمانی‌که بسته اول ارسال می‌شود تا زمانی‌که اولین ACK برمی‌گردد، ما چند بسته می‌توانیم ارسال کنیم و بعد با یک تناسب ساده پاسخ‌را به‌دست آوریم. ابتدا زمان ارسال هربسته و ACK را طبق داده‌های مسئله حساب می‌کنیم:
$\frac {1000\times 8}{10^8 \times 8}=10^{-5}=0.01ms$ = زمان ارسال هربسته از S به روتر
$\frac {1000\times 8}{10^6 \times 8}=1ms$ = زمان ارسال هربسته از روتر به R
توجه: چون حجم بسته‌های ACK کم است و سوال از ما پاسخ تقریبی خواسته، می‌توان از زمان ارسال ACK صرف نظر کرد. حال باید حساب کنیم از زمانی که بسته اول شروع به ارسال می‌کند تا زمانی که اولین ACK به ما برمی‌گردد چقدر طول می‌کشد:
تاخیر انتشار از R به روتر مربوط به ACK + تأخیر انتشار از روتر به R + زمان ارسال بسته اول از روتر به R + زمان
ارسال بسته اول از S به روتر = زمان مورد نظر
| زمان | بسته |
تناسب
$\to$
|
| 21.01ms | 10 | |
| ms1000 | x |
=0.01+1+10+10=21.01ms
$\to x=\frac {10\times 100}{21.01}\approx476$
$\to x=\frac {10\times 100}{21.01}\approx476$
نکته قابل توجه در حل این سوال: ما از زمان ارسال بسته‌های ACK صرف نظر کردیم، همچنین طبق صورت مسئله تأخیر انتشار در لینک‌های S به روتر و برعکس را صفر در نظر گرفتیم. همچنین طبق گفته صورت سوال پنجره ارسال 10 بسته گنجایش دارد و اگر محدودیت پنجره ارسال ذکر نمی‌شد، باید حساب می‌کردیم با توجه به زمان ارسال بسته‌ها روی لینک از S به روتر و زمانی که طول می‌کشد تا اولین ACK به S برسد، ما چند بسته می‌توانستیم ارسال کنیم که مطابق محاسبات روبرو است: بسته $\frac {21.01}{0.01}=2101$
همانطور که محاسبه شد، اگر محدودیت پنجره امسال وجود نداشت، تعداد بسته‌هایی که در تناسب برای محاسبه جواب باید استفاده می‌شد، به جای 10 عدد، 2101 عدد می‌بود. همچنین اگر در مسئله‌ای این عدد از محدودیت پنجره ارسال کمتر بود، باید این عدد را به‌عنوان بسته‌های ارسالی در نظر گرفت. به‌طور کلی برای جایگذاری تعداد بسته‌ها در تناسب ذکر شد، ما باید مینیمم ظرفیت پنجره و تعداد بسته‌های قابل ارسال در مدت زمان فرستادن اولین بسته تا رسیدن اولین ACK قرار داده شود.
آسان
در شبکه زیر چند IP subnet وجود دارد؟
لایه شبکه
زیرشبکه‌های موجود به شرح روبه‌رو هستند: 1- زیرشبکه بین روتر 1 و 2 2- زیرشبکه سمت راست روتر 1 3- زیرشبکه سمت چپ روتر 1 4- زیرشبکه متصل به روتر 2
نکته: باید توجه داشت که سوئیچ‌ها سطح دو هستند و با IP کاری ندارند.
آسان
چند مورد از عبارات زیر در مورد فاز AIMD در پروتکل TCP درست هستند؟
لایه انتقال
- از کمک ادوات داخل شبکه برای کنترل ازدحام بهره می‌برد.
- وقتی Timeout رخ دهد اندازه پنجره ازدحام را برابر 1 می‌کند.
- تاخیر ارسال بسته‌ها را اندازه می‌گیرد و با استفاده از آن ازدحام را کنترل می‌کند.
- هر زمان که اتلاف یک بسته شناسایی شود اندازه پنجره ازدحام را نصف می‌کند.
گزاره اول: میدانیم ادوات داخل شبکه در کنترل ازدحام دخالتی ندارند و ما از طریق Loss، که به دو صورت timeout و یا دریافت ACK 3 تکراری تشخیص داده می‌شود، برای کنترل ازدحام تصمیم می‌گیریم و با تغییر پنجره ارسال این کار را می‌کنیم.
گزاره دوم: در کنترل ازدحام ما دو روش Reno و Tahoe داشتیم که در هردو روش با timeout، پنجره ارسال 1 می‌شد. پس این گزاره درست است.
گزاره سوم: همانطور که در گزاره اول اشاره شد، معیار ما برای کنترل ازدحام، Loss است و کاری به تأخیر ارسال بسته نداریم.
گزاره چهارم: میدانیم در روش Reno، با دریافت نسخه ACK تکراری، پنجره ارسال نصف می‌شود، اما در Tahoe، پنجره ارسال 1 می‌شود.
روش دوم: استفاده از دوره های نکته و تست درس های کنکور فناوری اطلاعات
دوره های نکته و تست علاوه بر حل و بررسی تمامی تستهای کنکور، نکاتی بیان می‌کنند که به درک بهتر و حل سریع‌تر تست‌ها کمک می‌کند. برای آشنایی بیشتر با هر دوره نکته و تست از لینک‌های زیر استفاده کنید.
- دوره نکته و تست ساختمان داده و طراحی الگوریتم
- دوره نکته و تست هوش مصنوعی
- دوره نکته و تست درس پایگاه داده
- دوره نکته و تست سیستم عامل
- دوره نکته و تست شبکه های کامپیوتری
- دوره نکته و تست ریاضیات گسسته
پاسخ نامه کنکور ارشد فناوری اطلاعات
اگر می‌خواهید کلید نهایی کنکور ارشد فناوری اطلاعات ۱۴۰۰ یا سایر کنکور‌ها را داشته باشید، می‌توانید به صفحه دفترچه سوالات کنکور ارشد فناوری اطلاعات مراجعه کنید و آنها را به‌صورت رایگان دانلود کنید.
کلید کنکور ارشد مهندسی فناوری اطلاعات ۱۴۰۰
شما می‌توانید کلید کنکور ارشد آیتی ۱۴۰۰ را در تصویر زیر مشاهده کنید. اگر می‌خواهید به‌تمامی پاسخ‌نامه های کلیدی کنکورهای مهندسی فناوری اطلاعات دسترسی داشته باشید، تمامی آنها در صفحه دفترچه سوالات کنکور ارشد فناوری اطلاعات قرار گرفته است.
جمع‌بندی
آزمون کارشناسی ارشد مهندسی فناوری اطلاعات شامل سؤالات متنوعی از جمله ساختمان داده و الگوریتم، هوش مصنوعی، پایگاه داده و... است. داوطلبان برای پاسخگویی به این سؤالات نیاز به دانش عمیق و تسلط بر مباحث موردنظر دارند و لازم است که از منابع مناسبی مانند دوره نکته و تست و پلتفرم آزمون استفاده کنند.
چگونه میتوانم به پاسخ تشریحی کنکور فناوری اطلاعات ۱۴۰۰ دسترسی داشته باشم؟
دو روش برای این کار در نظر گرفته شده است: 1-پلتفرم آزمون 2-دوره‌های نکته‌وتست
آیا منابعی برای دروس کنکور فناوری اطلاعات وجود دارد؟
بله می‌توانید از دوره‌های درس کنکور فناوری اطلاعات استفاده کنید.
چگونه میتوانم به پاسخ‌های کلیدی کنکورهای آیتی دسترسی داشته باشم؟
تمامی کلید‌های کنکور فناوری اطلاعات در صفحه دفترچه‌های کنکور آیتی موجود است.
