سوالات

اگر x جواب محاسبه شده برای جواب دستگاه Ax=b ، عدد حالت A برابر با ۱۰^۳ و دقت نسبی درایه‌های A و b تقریباً برابر با ۱۰^(-۱۰) و روند عدد یک در ماشین محاسبه مورد استفاده برای محاسبه x برابر با ۱۰^(-۱۴)…

با توجه به نمودار ساقه و برگ، میانگین کدام است؟

در بسط (x+y+z+u)^5 ضریب x^2 z^2 u کدام است؟

یک نمونه تصادفی شامل ۳۰ دانشجو از دانشگاه‌های مختلف کشور انتخاب کرده و از آن‌ها سوال شده است که آیا از رشته تحصیلی خود راضی‌اند یا خیر. ۷ نفر جواب منفی داده‌اند. اگر افراد x، y و z در بین…

فرض کنید A و B دو پیشامد مستقل و P(B)=۳/۴ , P(A)=۱/۳ باشد. مقدار احتمال شرطی A به شرط A∪ B کدام گزینه است؟

فرض کنید ′A و ′B بیانگر متمم پیشامدهای A و B و A∆B نشان‌دهندهٔ تفاضل متقارن این دو پیشامد باشند. اگر ۰٫۳ = (′P(A′∩B، ۰٫۱ = P(A) و ۰٫۲ = (P(A∩B، آن‌گاه مقدار (P(A∆B کدام است؟

خروجی الگوریتم زیر از چه مرتبه‌ای است؟ j = ۰ i = ۱ while(i ≤ n) j = j + ۲i i = ۴i print j

با توجه به رابطه بازگشتی زیر، (T(n از چه مرتبه‌ای است؟ T(۲^n) = T(۲^(n-1)) + Θ(n^۲) ; T(۱) = Θ(۱)

هنگامی‌که می‌خواهیم نشان دهیم زمان یا حافظه یک الگوریتم، حداقل از مرتبه تابعی مانند f : N → R^(+) است، از کدام نماد باید استفاده کنیم؟

کدام گزاره یا گزاره‌ها درست است؟ الف) سومین بزرگ‌ترین کلید در یک MAX heap با کلیدهای متمایز می‌توان با اندیس ۲ باشد در درایه. ب) سومین بزرگ‌ترین کلید در یک MAX heap با کلیدهای متمایز می‌توان با اندیس…

کدام درخت یا درخت‌ها را می‌توان با یک چرخش (rotation) به درخت AVL تبدیل کرد؟ درخت AVL، درختی است که در آن برای هر رأس، قدر مطلق اختلاف ارتفاع زیر درخت‌های راست و چپ، حداکثر یک است. همچنین چرخش…

الگوریتم مرتب‌سازی سریع (Quick sort) را روی آرایه‌ای شامل ۴ عدد اجرا می‌کنیم. تعداد مقایسه‌ها چه عددی نمی‌تواند باشد؟

حداقل حافظه کمکی لازم برای دو عمل زیر، به‌ترتیب از چپ به راست از چه مرتبه‌ای است؟ برعکس کردن یک لیست پیوندی (linked list) یک طرفه n عضوی برعکس کردن یک لیست پیوندی (linked list) دو طرفه n عضوی

دو الگوریتم BFS (جستجوی اول سطح) و DFS (جستجوی اول عمق) را روی گراف زیر و با شروع از رأس S اجرا می‌کنیم. در هر گام از BFS یا DFS اگر چند رأس برای انتخاب وجود داشت، رأسی را انتخاب می‌کنیم که از نظر…

پیاده‌سازی معمولی کدام مورد با داده ساختار پشته (stack) انجام می‌شود؟

کدام گزاره یا گزاره‌ها درست است؟ الف) ارتفاع یک درخت جستجوی دودویی (binary search tree) با ۱۰ کلید می‌تواند ۹ باشد. ب) اگر داده‌های کلیدی اعداد ۷،...،۲،۱ باشند فقط یک درخت جستجوی دودویی به ارتفاع ۲…

G یک گراف همبند با n رأس و e یال است. همچنین می‌دانیم که وزن همه یال‌های G یکسان است. بهترین زمان برای یافتن یک زیردرخت فراگیر (پوشای) کمینه G از چه مرتبه‌ای است؟

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

الگوریتم دایکسترا را روی گراف زیر و با شروع از رأس s اجرا می‌کنیم. فاصله a از s در ابتدا ∞+ در نظر گرفته می‌شود. هنگام اجرای الگوریتم، فاصله a از s چند بار تغییر می‌کند؟

کدام مسئله یا مسائل از ۳ مسئله زیر دارای الگوریتم حریصانه (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 یک زیردنبالهٔ…

فرض کنیم زبان L گرامر زیر باشد (S متغیر شروع): S → aSaa B B → bB λ به‌ازای کدام مقدار برای x رشته‌ی aaa x b aaa a a a عضو L است؟

فرض کنیم L_1 و L_2 به‌ترتیب زبان دو گرامر G_1 و G_2 باشد ( S متغیر شروع): G_1 : S → aSbS bSaS λ G_2 : S → aSa bSb λ کدام‌یک از این دو زبان منظم هستند؟

دو عبارت زیر را درنظر بگیرید: الف) فرض کنیم M یک NFA (اتوماتای متناهی نامعین) باشد و ′M یک NFA کاملاً شبیه M با این تفاوت که حالت‌های پایانی (پذیرش) ′M غیرپایانی و حالت‌های غیرپایانی ′M در M حالت‌های…

فرض کنیم L زبان گرامر زیر باشد (S متغیر شروع): S → aA bB A → aB bS λ B → bA aS کدام‌یک از دو رشته x = a^۱۲ b^۶ a^۶ و y = b^۱۵ a^۱۰ b^۸ در L قرار دارد؟

به‌ازای کدام مقدار x عبارت b^7a^5b^3xa^5 در زبان عبارت منظم r = b^()ab^()(b^()ab^()ab^()ab^()ab^()ab^())^() قرار می‌گیرد؟

فرض کنیم L زبان NFA زیر باشد. با قراردادن کدام‌یک از دو مقدار ۰ و ۱ به‌جای x در عبارت ۱۱۱۱۰۰۱۰x۱۰۰۰۱۱ عبارت حاصل در L قرار می‌گیرد؟

کدام‌یک از دو زبان زیر مستقل از متن است؟ L_1 = a^n c^m b^n n > m ≥ 0 L_2 = a^n b^m c^k k ≠ n + m, n, m, k ≥ 0

می‌توان با شرایط گفته شده در لم تزریق تجزیه کرد. مقدار p منحصر به فرد نیست چون اگر p طول تزریق L باشد، هر عدد بزرگ‌تر از p نیز هست. همواره می‌توان کوچک‌ترین طول تزریق را یافت. کوچک‌ترین طول تزریق…

فرض کنید M ماشین تورینگ زیر باشد: اگر ‫α = ۰^۱۶‬ و ‫β = ۰^۱۷‬ کدام‌یک از این دو رشته توسط M پذیرفته می‌شود؟

الف) یک Mid PDA یک PDA توسعه‌یافته است که می‌تواند وسط پشته را بخواند. در واقع تابع انتقال در Mid PDA تابع چهار چیز است: نماد ورودی، نماد بالایی پشته، حالت فعلی ماشین و نماد وسط پشته. ( اگر پشته k…

کدام‌یک از استدلال‌های زیر معتبر است؟ ( ∴ نماد نتیجه‌گیری است.) (الف) ¬ a ∧ (a → b) ∴ b (ب) p → q q → r ∴ p → r

فرض کنیم زبانی، شامل شش ثابت c_۱, c_۲, …, c_۶ ، نمادهای محمولی دو موضعی O_۱, O_۲ ، نمادهای محمولی یک‌موضعی F_۱, F_۲ باشد. با فرض متمایز بودن b_i ‌ها، تعبیر زیر را در نظر می‌گیریم: I(C_i) = b_i ۱ ≤ i…

در استدلال زیر در سیستم استنتاج طبیعی، (∃ x A(x) → ∀ x B(x) (A(x))/(∃ x A(x)))/(((∀ x B(x))/(B(x)))/((A(x)→ B(x))/(∀ x (A(x)→ B(x))))) کدام گزینه در مورد قانون‌های معرفی سور عمومی (forallI) و معرفی…

دو فرمول زیر در منطق گزاره‌ها را درنظر بگیرید: α ≡ ¬ A_1 ∧ A_2 ∧ (¬ A_2 ∨ A_3) ∧ (A_1 ∨ ¬ A_2 ∨ A_3) β ≡ A_2 ∧ (¬ A_3 ∨ A_1) ∧ (¬ A_1 ∨ A_3) ∧ (¬ A_1) ∧ (¬ A_2 ∨ A_3) برای کدام فرمول یک ارزش‌دهی به…