سوالات

کدام مسئله یا مسائل از ۳ مسئله زیر دارای الگوریتم حریصانه (greedy) با زمان چندجمله‌ای است؟ کوله‌پشتی ۰ و ۱ / کوله‌پشتی کسری / زیردرخت فراگیر (پوشای) کمینه (MST)

بهترین زمان برای تعیین دوبخشی بودن و نبودن یک گراف با n رأس و e یال از چه مرتبه زمانی است؟ (گراف دوبخشی یعنی گرافی که بتوان رأس‌های آن را به دو بخش A و B افراز کرد بطوریکه هر یال G یک سر در A و یک سر…

کدام گزاره یا گزاره‌ها در مورد مسئله جریان (شار) در شبکه‌ها (Network Flow) درست است؟ الف) اگر ظرفیت هر یال مضرب 1/2 باشد، مقدار جریان (شار) بیشینه نیز مضرب 1/2 است. ب) دقیقاً یک برش (cut) وجود دارد…

کدام گزاره یا گزاره‌ها در مورد کلاس P درست است؟ الف) L ∈ P اگر و تنها اگر الگوریتم A موجود باشد که برای هر ورودی به طول n بیت، عدد ثابت c > 0 موجود باشد که A در زمان O(n^c) پاسخ درست را بدهد. ب) L ∈…

G یک گراف وزن‌دار با وزن‌های مثبت و با n رأس است؛ به‌طوری‌که بیشترین درجه رأس‌ها lgn است. کدام الگوریتم برای محاسبه فاصله هر دو رأس از همدیگر مرتبه زمانی بهتری دارد؟ (فرض کنید n به اندازه کافی بزرگ…

فرض کنید f:NtoN یک تابع باشد که برای هر i ، محاسبه f(i) در زمان Θ(√i) ممکن باشد. همچنین برای هر i و j که 1≤ i≤ j≤ n تعریف می‌کنیم: g(i,j)= f(i), اگر i=j ; max_(i<k≤ j) g(i,k-1)+g(k,j) , اگر i<j…

فرض کنید b = b_1 b_2 ⋯ b_n یک رشته n حرفی با یک الفبای Σ باشد. منظور از یک دنبالهٔ b ، یک رشتهٔ حاصل از حذف برخی حرف‌های b است (بنابراین b دارای 2^n زیردنباله است)؛ به‌عنوان مثال xyy یک زیردنبالهٔ…

کدام گزاره‌های زیر درست است؟ (الف) برای هر تابع f : N → N داریم f = O(3f) . (ب) برای هر دو تابع g : N → N و f داریم f = O(f+g) .

پس از اجرای قطعه کد زیر، k از چه مرتبه‌ای است؟ k = 0; for (i = 0; i < n; i = i + 1) for (j = 1; j < n; j = j + i) k = k + 1;

پس از اجرای قطعه‌ای که زیر، k از چه مرتبه‌ای است؟ k = 0; for (i = 1; i < n; i = i + 1) for (j = 1; j < i; j = j + 1) k = k + i + j;

با اجرای الگوریتم کروسکال روی گراف زیر، وزن آخرین یال انتخاب شونده چند است؟

در جستجوی DFS بر روی یک گراف جهت‌دار بدون دور، در مورد هر رأس v، رأس‌های دیگر بلافاصله روی رأس v چند بار در پشته (Stack) قرار می‌گیرند؟

با مرتب‌سازی حبابی داده‌های مقابل را از بالا به پایین صعودی می‌کنیم. چند بار جابه‌جایی دو عنصر انجام می‌شود؟ آرایه (از بالا به پایین): ۴، ۲، ۳، ۱

مرتبه زمانی الگوریتم‌های مرتب‌سازی حبابی روی یک آرایه تصادفی و مرتب‌سازی انتخابی روی یک آرایه تصادفی به‌ترتیب از راست به چپ برابر است با:

هنگام اجرای الگوریتم دایکسترا روی گراف مقابل و با فراخوانی از رأس a یک درخت فراگیر مانند T ایجاد می‌شود. فاصله b از c در T چند است؟

زمان متوسط و زمان بدترین حالت برای Quick Sort بهترتیب از راست به چپ از چه مرتبههایی است؟

برای تعیین این که یک گراف جهت‌دار با n رأس دارای دور جهت‌دار است یا نه، حداقل چند بار باید حلقه اصلی الگوریتم بلمن ـ فورد را اجرا کرد؟

کدام مسأله دارای الگوریتم حل و تقسیم (با زمان چندجمله‌ای) نیست؟

کدام‌یک از مسائل زیر دارای الگوریتم پویا (dynamic) (با زمان چندجمله‌ای) است؟ (الف) یافتن فاصله هر دو رأس در یک گراف وزن‌دار جهت‌دار (ب) یافتن طولانی‌ترین زیردنباله مشترک دو رشته

در پیاده‌سازی کدام موارد به‌ترتیب از راست به چپ از صف و پشته (Stack) استفاده می‌شود؟

جریان بیشینه از s به t در شبکه مقابل چند است؟

چند تا از مسائل زیر روی گراف‌های وزن‌دار و همبند، عضو کلاس P است؟ (مسائل دارای زمان چندجمله‌ای) I) فاصله دو رأس خاص II) فاصله هر دو رأس III) سبک‌ترین زیردرخت فراگیر

کدام گزاره (گزاره‌ها) درست است؟ الف) اگر در الگوریتم فورد ـ فالکرسون مسیرهای افزایشی را به دلخواه انتخاب کنیم و نیز ظرفیت همه یال‌های شبکه عدد طبیعی باشد، حتماً الگوریتم پس از متناهی گام متوقف…

کدام گزینه درست است؟

فرض کنید در یک مسئله عدد α_ij به‌ازای هر i و j که 1 ≤ i ≤ j ≤ n تعریف شده است و همچنین داریم: (∀ i) α_ii = 1 (∀ i < j) α_ij = min_(i ≤ k ≤ j) α_ik + α_kj + f(i,j,k) که در آن f یک تابع است که برای هر…

زمان اجرای قطعه کد مقابل، از چه مرتبه‌ای است؟ i = 2; while(i <= n) write(); i = i i;

مرتبه زمانی الگوریتم f2 کدام است؟ f1(n) for(x = ۰ , i = ۰ ; i < n ; i++) x++ return(x) f2(n) if(n == ۰) return(۰) else return f2(n/۲) + f1(n) + f2(n/۲)

فرض کنید می‌خواهیم کمترین تعداد ضرب عددی ممکن برای محاسبه ضرب A_1 × A_2 × ⋯ × A_n را با استفاده از روش برنامه‌نویسی پویا (Dynamic programming) پیدا کنیم. برای این‌کار لازم است از یک جدول n × n…

فرض کنید می‌خواهیم یک آرایه ۱۰ عنصری را با استفاده از الگوریتم مرتب‌سازی ادغامی، مرتب کنیم. چند مورد از موارد زیر صحیح است؟ (I) تعداد فراخوانی تابع merge در این الگوریتم ۱۹ است. (II) تعداد…

الگوریتم زیر برای مرتب‌سازی یک آرایه n عنصری از اعداد ۱، ۰ و ۱- است. به‌جای ...... چه دستوری باید قرار گیرد؟ sort(A) i = ۰ ; j = ۰ ; h = n+۱ ; while(h != j+۱) if(A[j+۱] == -۱) A[j+۱] <-> A[i+۱]…

فرض کنید الگوریتم بلمن ـ فورد (Bellman-Ford) برای محاسبه کوتاه‌ترین مسیر تک منبعی در یک گراف وزن‌دار تقریباً کامل استفاده شده است. مرتبه زمانی آن چقدر است؟ (v نشان‌دهنده تعداد گره‌ها و e نشان‌دهنده…

مرتبه زمانی محاسبه رابطه روبه‌رو کدام است؟ ∑_(i=۱)^n frac ۱ i^۲

فرض کنید تمام توابع log در این سؤال بر مبنای ۲ هستند و تعریف تابع log^() به شرح زیر است: log^() n = min i ≥ 0 : log^((i)) n ≤ 1 ترتیب توابع زیر را براساس نرخ رشد (از کمترین نرخ رشد به بیشترین نرخ…

فرض کنید یک متن فارسی به شما داده شده است که فقط ۳۳ کاراکتر در آن ظاهر شده‌اند (۳۲ کاراکتر الفبای فارسی به‌علاوه کاراکتر فاصله). نتیجه شمارش فراوانی این ۳۳ کاراکتر در این متن نشان می‌دهد که فراوانی…

آرایه‌ای به طول n داریم که k − n عنصر آن مرتب و k عنصر آن نامرتب هستند. اگر k خیلی کوچک‌تر از n باشد آنگاه کدام الگوریتم مرتب‌سازی دارای بهترین کارایی برای مرتب کردن آن است؟

اگر هزینه‌ی f(m) و g(m) برابر θ(m) باشد، هزینه‌ی h(n) چقدر است؟ h(n) p = ۱ for(i = ۱ ; i <= n ; i++) f(i) if(i == p) g(n) p = p × ۲

فرض کنید تابعی برای محاسبه‌ی x^n (توان) ندارید و می‌توانید از چهار عنصر اصلی استفاده کنید. x یک عدد دلخواه و n یک عدد طبیعی است. بهترین زمانی که می‌توانید در آن، x^n را محاسبه کنید، کدام است؟

کدام‌یک از مسائل زیر دارای پیچیدگی محاسباتی چند جمله‌ای است؟

متنی شامل حروف f ,a, b, c, d, e با فراوانی‌های زیر داده شده است. اگر این حروف را طبق کد هافمن کدگذاری کنیم تعداد بیت‌های f و a به‌ترتیب از راست به چپ کدام است؟ حروف a b c d e f…

الگوریتم خرد کردن پول با روش حریصانه برای وقتی‌که بخواهیم ۱۴ واحد پول را از طریق سکه‌های ۱۰ ، ۷ ، ۲ ، ۱ واحد خرد کنیم، چند سکه به‌دست می‌دهد؟