سوالات

مسئله ضرب زنجیره‌ای ماتریس‌ها (Matrix Chain Multiplication) را در روش شاخه و حد (Branch and Bound) برای پیدا کردن ترتیب بهینه ضرب ماتریس‌ها استفاده می‌شود. کدام‌یک از گزینه‌های زیر به‌درستی مفهوم حد…

آرایه A حاوی n بیت است. فرض کنید A یکی از دو گونه زیر است: گونه ۱: نیمی از درایه‌های A حاوی بیت صفر و نیم دیگر حاوی بیت ۱ (بدون ترتیب) است. گونه ۲: A در مجموع ۲/۳n صفر و ۱/۳n یک دارد. به‌شما آرایه A…

فرض کنید G یک گراف بدون جهت وزن‌دار و e یالی با حداکثر وزن در G باشد. فرض کنید یک درخت پوشای با حداقل وزن در G وجود دارد که شامل یال e است. کدام‌یک از عبارات زیر همواره درست است؟

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

پیچیدگی زمانی الگوریتم زیر را بیابید؟ Void func(int n) if (n <= 1) return; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) Printf(""); func(n/2); func(n/2);

الگوریتم عقب‌گرد برای تعیین همهٔ دورهای هامیلتونی در یک گراف همبند و بدون جهت G با n رأس را درنظربگیرید. تعداد گره‌ها در درخت فضای حالت این الگوریتم کدام است؟

منابع شما هم به‌میزان محدود R = ۵۰ می‌باشد. اطلاعات این پروژه‌ها در جدول زیر داده شده است. اگر از الگوریتم حریصانه براساس نسبت بیشترین سود به منابع استفاده کنیم کدام پروژه‌ها انتخاب و سود کل چقدر…

تعداد (۹) فایل مرتب‌شده با اندازه‌های ۳ و ۷ و ۸ و ۹ و ۱۵ و ۱۶ و ۱۷ و ۲۰ و ۲۳ مفروض است. می‌خواهیم این ۹ فایل را سه‌به‌سه با هم ادغام کرده و فایل مرتب‌شده واحدی به‌دست آوریم. حداقل تعداد جابه‌جایی‌ها…

کدام مورد درخصوص الگوریتم عقب‌گرد درست نیست؟

الگوریتم زیر، اندیس بزرگ‌ترین عنصر آرایه A را توسط j برمی‌گرداند. با فرض آن که عناصر آرایه A ، اعداد صحیح متمایز و متساوی‌الاحتمال باشند در این صورت میانگین زمان اجرای دستورالعمل d یعنی j = i کدام…

چند تا از گزاره‌های زیر درست است؟ الف) f(n) = o(g(n)) اگر و تنها اگر g(n) = ω(f(n)) ب) f(n) = O(g(n)) اگر و تنها اگر g(n) = Ω(f(n)) ج) n = ω(log n) د) dfrac n^۳ log n = θ(n^۲)

فرض کنید الگوریتم DFS روی گراف ارائه شده اجرا شده و همیشه راس‌ها به‌ترتیب الفبایی انتخاب می‌شوند. در پایان اجرای الگوریتم DFS زودترین خروج تا دیرترین خروج کدام است؟ (منظور از خروج، اتمام ملاقات راس…

مسئله زمان‌بندی فعالیت‌ها با مهلت که در آن n فعالیت داریم را درنظربگیرید. برای فعالیت i یک مهلت d_i و یک ارزش P_i منصوب است. برای فعالیت i ارزش P_i زمانی حاصل می‌شود که این فعالیت در مهلت d_i به…

اگر در روش کدگذاری هافمن، فراوانی داده اول از مجموع فراوانی n-1 داده دیگر بیشتر بوده و فراوانی n-1 عضو ذکر شده با هم برابر باشند، آنگاه طول کد تولید شده حداکثر چقدر است؟