حل تشریحی سوالات حل مسئله - کنکور دکتری مهندسی فناوری اطلاعات (IT) 1403

حداقل تعداد مقایسه‌های لازم برای یافتن کوچکترین و بزرگترین عنصر در یک آرایه عنصری کدام است؟

آرایه نامرتب $T\left[\mathrm{1..}n\right]$ از اعداد مفروض است. یک پنجره به‌طول $\sqrt{n}$ داریم که آن را با $\text{window(}\sqrt{n}\text{)}$ نشان می‌دهیم. این پنجره اگر روی آرایه $T\left[\mathrm{1..}n\right]$ از اندیس iام باز شود، آن‌گاه زیر آرایه $T\left[i..i+\sqrt{n}-1\right]$ مرتب خواهد شد. با یک الگوریتم کارا، حداکثر با چند بار فراخوانی این پنجره می‌توان آرایه T را مرتب کرد؟

مرتبه جواب رابطه بازگشتی $T\left(n\right)=T\left(\frac{n}{9}\right)+T\left(\frac{7n}{9}\right)+1$ ، کدام است؟

فرض کنید یک کاهش چند جمله ای از مسئله A به مسئله B از کلاس NP داشته باشیم. کدام مورد درست است؟

تابع بازگشتی زیر را در نظر بگیرید. تابع g با تعریف g(x,y) برای درج y تا علامت 0 در محل x استفاده می‌شود. خروجی تابع f برای f(0,8,3) کدام مورد است؟

f (int a, int b, int c)

{

int m = (a +b)/2;

if(c>0);

{

g(m, c);

f(a, m, c-1);

f(m, b, c-1);

}

}

یک مجتمع آموزشی تصمیم دارد برای برگزاری کلاسهای درسی یک روز معین از کمترین کلاس فیزیکی استفاده کند. برنامه درسی یک روز معین شامل n درس متمایز موجود است زمان شروع و خاتمه هر درس از قبل مشخص شده است. سریع‌ترین الگوریتم برای تعیین حداقل تعداد کلاس‌های فیزیکی اختصاص داده شده از چه ساختمان داده و مرتبه زمانی برخوردار است؟

چه تعداد از موارد زیر درست است؟

از یک آرایه دلخواه می توان در مرتبه $O\left(n\right)$ یک هرم دودویی مینیمم تولید کرد.

بهترین مرتبه زمان اجرا برای پیاده‌سازی الگوریتم پریم جهت تعیین درخت پوشای کمینه یک گراف استفاده از ساختمان داده هرم فیبوناچی مینیمم است.

اگر یک درخت AVL با ارتفاع h، حداقل دارای T(h) گره باشد، آنگاه T(h)=T(h-1)+T(h-2)+1

فرض کنید (G=(V,E یک گراف همبند وزن‌دار باشد که وزن تمام یالهای آن برابر مقدار ثابت C است. چند مورد از گزاره‌های زیر در مورد این گراف درست است؟

• درخت پوشای کمینه (MST) این گراف را می توان در مرتبه $O\left(\left|E\right|\right)$ محاسبه کرد.
• می‌توان طول کوتاه‌ترین مسیر از یک رأس تا تمام رئوس را در مرتبه $O\left(\left|V\right|\right)$، نه در مرتبه $O\left(\left|E\right|\right)$ محاسبه کرد.
• می‌توان تعداد مؤلفه‌های هم بند گراف را در مرتبه $\theta \left(\left|V\right|+\left|E\right|\right)$ محاسبه کرد.

فرض کنید بخواهیم عدد n را به k جمعوند طبیعی تبدیل کنیم رابطه بازگشتی که تعداد حالات ممکن را مشخص می‌کند، کدام است؟ (تعداد حالات مورد نظر را با $P\left(n,k\right)$ نشان می‌دهیم)

به عنوان مثال عدد ۶ را می‌توان به صورت‌های زیر به ۳ جمعوند طبیعی تبدیل کرد

6=1+1+4

6=2+2+2

6=3+1+2

آرایه A به طول n مفروض است. می‌دانیم عنصری در این آرایه بیش از $\frac{2n}{3}$ بار، تکرار شده است. بهترین الگوریتم برای یافتن این عنصر از چه مرتبه زمانی است؟

یک جدول در هم‌ساز داریم فرض کنید برای رفع مشکل تصادم از روش وارسی خطی استفاده شده است. با در نظر گرفتن فرض یکنواختی تابع در هم ساز کلید بعدی با چه احتمالی در خانه چهارم قرار می‌گیرد؟

چند مورد از عبارات زیر درست است؟

برای مرتب‌سازی توپولوژیکال رأس‌ها در گراف جهت دار حتماً باید از دو بار الگوریتم DFS استفاده شود.

برای محاسبه قطر یک گراف غیر جهت دار ساده بدون دور از دوبار الگوریتم BFS استفاده می‌کنیم.

هرگاه G یک گراف غیر جهت دار ساده باشد، مسئله تشخیص دور در این گراف را می‌توان در مرتبه زمانی $O\left(\left|V\right|\right)$ پاسخ داد. $\left|V\right|$ تعداد رئوس گراف G است.

در یک شبکه که حداکثر اندازه TPDU در آن ۱۲۸ بایت، حداکثر عمر TPDU برابر با ۳۰ ثانیه و دارای یک شماره توالی ۸ بیتی باشد، حداکثر نرخ داده در هر اتصال چند کیلوبیت بر ثانیه خواهد بود؟

یک اتصال TCP برقرار شده است که در آن، MISS = 1KB و RTT = 100 ms است. وقتی اندازه پنجره فرستنده برابر ۳۲ کیلوبایت است، یک timeout تشخیص داده می‌شود. چند میلی ثانیه طول می‌کشد که اندازه پنجره فرستنده برابر ۲۲ کیلوبایت شود؟

در شبکه خطی زیر که شامل روترهای A تا E است، از روش بردار فاصله برای مسیریابی استفاده می‌شود. تأخیر لینک بین هر دو روتر را یک واحد در نظر بگیرید. تأخیر همه روترها تا روتر A، قبل از خرابی روتر A در سطر اول و پس از خرابی روتر A را پس از اولین دور مبادله اطلاعات روترها به هم در سطر دوم مشاهده می‌کنید. کدام یک از موارد زیر در خصوص تأخیر روترها به روتر A پس از دور ششم مبادله اطلاعات درست است؟

یک کانال دارای نرخ ارسال ۴ کیلوبیت بر ثانیه و تأخیر انتشار ۲۰ میلی ثانیه است. فریم‌ها چند بیت باید باشند تا بازدهی روش توقف و انتظار حداقل ۵۰ درصد باشد؟

دو ایستگاه، از یک کانال بی‌سیم با پهنای باند $10\frac{Mbit}{\sec }$ به شکل مشترک، با استفاده از پروتکل Slotted ALOHA بهره برداری می‌کنند. هر دو ایستگاه همواره داده برای ارسال دارند و ایستگاه اول با احتمال فریم‌های خود را ارسال می‌کند. اگر ایستگاه دوم بخواهد گذردهی داشته باشد، با چه احتمالی باید ارسال کند؟

کدام حالت های زنجیره بلوکی رمز می‌تواند در حالت موازی پیاده‌سازی شده و کارآیی را افزایش دهد؟

حمله SYN Flooding، به کدام مورد اشاره دارد؟

فرایند توزیع کلید در شبکه های بی‌سیم 802.11i (مثلاً در WPA2)، از دو بخش Pairwise key Distribution (که گاهی به آن 4-way handshake هم می‌گویند) و Group Key Distribution تشکیل شده است. با توجه به اطلاعات داده شده کدام مورد درست است؟

PMK= Pairwise Master Key

PTK=Pairwise transient Key

GTK= Group Temporal Key

AP=Access Point

STA= Station

شکل زیر تابع چگالی احتمال پروفایل رفتاری کاربر عادی (authorized user) را در کنار تابع چگالی احتمال پروفایل رفتاری نفوذی (Intruder) نشان می‌دهد. در حال حاضر در سیستم تشخیص نفوذی که ساخته‌ایم مرز تصمیم‌گیری را در وسط دو پروفایل و در نقطه T گذاشته‌ایم. حال اگر مقدار را در راستای محور x افزایش دهیم به‌ترتیب False positive و False negative چه تغییری را نشان می‌دهد؟ (Positive=Intrusion)

در خصوص پروتکل تبادل کلید زیر بین دو طرف A و B کدام مورد درست است؟

$P{U}_A$: کلید عمومی A $P{R}_A$: کلید خصوصی A $P{U}_B$: کلید عمومی B

$K_{AB}$: کلید مشترک متقارن بین A و B(که قرار است طی این پروتکل تبادل شود)

$N_B$: مقدار تصادفی یکبار مصرف (nonce) تولید شده توسط B

$H\left(0\right)$: تابع چکیده ساز

$E_P\left(K,\left[X\right]\right)$: رمز محتوای X با کلید K و الگوریتم P

$A\to B:E_{RSA}\left(P{U}_B\left[I{D}_A,K_{AB}\right]\right)$

$B\to A:E_{RSA}\left(P{U}_A\left[I{D}_B,K_{AB},N_B\right]\right)$

$A\to B:E_{RSA}\left(P{R}_A,\left[H\left(N_B\right)\right]\right)$