سوالات

فرض کنید می‌خواهیم یک داده‌ساختار طراحی کنیم که هم‌زمان قابلیت‌های یک صف معمولی و یک صف اولویت (Priority Queue) را داشته باشد. این داده‌ساختار باید بتواند عملیات‌های زیر را انجام دهد: افزودن یک عنصر…

فرض کنید می‌خواهیم یک عبارت ریاضی را که شامل پرانتزهای باز و بسته، عملگرهای ریاضی (+, -, ×, div) و اعداد است، به یک عبارت پسوندی (Postfix) تبدیل کنیم و برای این کار از ترکیبی از پشته و صف استفاده…

کدام‌یک از الگوریتم‌های مرتب‌سازی زیر پایدار (Stable) است؟

در مورد الگوریتم هافمن کدام مورد درست است؟

مرتبه زمانی T(n) کدام است؟ T(۱) = ۵ ; T(n) = n + ۱ + T (n/۲)

n عدد صحیح k رقمی داریم ( k ثابت و مستقل از n هست) کدام مورد دقیق‌تر است؟

فرض کنید T(x) = ۱/۲T(x/۲) + θ(۱/x) . پیچیدگی رابطه T کدام است؟

فرض کنید L_n زیرمجموعه‌ای از ZtimesZ به‌صورت زیر باشد: L_n= (i,j) middle i+j≤ n, i≥ ∘, j≥ ∘ همچنین برای هر (i,j) در L_n مجموعه همسایه‌های (i,j) را به‌صورت زیر تعریف کنیم: N_n(i,j)= (k,m)∈ L_n: ۱≤ i-k…

یک گراف جهت‌دار G=(V,E) مدلی برای یک شبکه کامپیوتری با n رأس است. وزن w(u,v) روی یال (u,v) ، احتمال خراب‌نبودن (سالم‌بودن) لینک (u,v) است. فرض کنید لینک‌ها مستقل از یکدیگر خراب می‌شوند، بنابراین…

n فایل داریم که طول فایل i اُم L_i و احتمال دسترسی به آن P_i است که به ما داده شده است. می‌خواهیم این فایل‌ها را طوری پشت سرهم قرار دهیم که میانگین زمان دسترسی به فایل‌ها کمینه شود. به عبارت دیگر…

چند تا از گزاره‌های زیر صحیح است؟ اگر g(n) = o(f(n)) (نماد o کوچک) آنگاه f(n) = ω(g(n)) . اگر lim_(n → +∞) (f(n))/(g(n)) = ∘ آنگاه f(n) = o(g(n)) . برای هر ثابت c > ∘ و هر ثابت a > ۱ و هر تابع صعودی…

فرض کنید آرایه‌ای از n عنصر داده شده است و می‌خواهیم میانه (Median) آن را با استفاده از روش تقسیم و حل (Divide and Conquer) پیدا کنیم. کدام‌یک از گزینه‌های زیر درباره الگوریتمی که این مسئله را…

فرض کنید نتیجه یک ماتریس ریشه R از درخت جستجوی دودویی بهینه به‌صورت جدول زیر حاصل شده است و I_۱ < I_۲ < I_۳ < I_۴ کلیدها و p_۱ = p_۳ = ۳/۸ و p_۲ = p_۴ = ۱/۸ احتمال جستجوی این درخت دودویی هستند. کدام…

برای کدام‌یک از مسائل زیر، الگوریتم با زمان چندجمله‌ای پیدا شده است؟ الف ــ کوله‌پشتی کسری ب ــ تعیین نزدیک‌ترین زوج نقطه بین چند نقطه داده شده در صفحه

فرض کنید یک جدول n × n دارید و می‌خواهید در هر خانه از این جدول یک عدد بین ۱ تا k قرار دهید، به‌طوری‌که: هر عدد در هر سطر و هر ستون منحصربه‌فرد باشد (مانند جداول سودوکو). برخی خانه‌ها از قبل پر…

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

فرض کنید L زبان عبارت منظم r = (0+1)^() 0 (0+1)(0+1) باشد. از دو عبارت α = ۱۱۰۱۰۱۱۰۱۰۱۱۰۰۰۱۰۰ و β = ۰۱۰۱۱۱۰۱۱۱۰۱۰۱۱ ، کدام عضو زبان L است؟

فرض کنید L زبان گرامر زیر باشد: S → TbT T → aTb bTa TT λ از دو عبارت α = b aa bb a bb a bb aa bb و β = bbb ab aa b aaa b b ، کدام عضو زبان L است؟

فرض کنید L زبان گرامر زیر باشد: S → BA A → ∘∘ A1 ∘ B → ∘ B ∘ از دو عبارت α = ∘^(1∘)1^21 و β = ∘^221^(1∘) کدام عضو زبان L هست؟

فرض کنید: L_1 = w ∈ a, b ^ w = w^R L_2 = w ∈ a, b ^ n_ab(w) = n_aa(w) از این دو زبان کدام منظم است؟

از دو عبارت زیر کدام صحیح است؟ I: اگر تعدادی متناهی رشته از یک زبان منظم حذف کنیم حاصل یک زبان منظم خواهد بود. II: اگر تعدادی متناهی رشته به یک زبان غیرمنظم اضافه کنیم حاصل یک زبان غیرمنظم خواهد بود.

فرض کنید L زبان گرامر زیر با متغیر شروع S باشد: S → aAS S → a A → SbA A → SS A → ba از دو عبارت زیر کدام صحیح است؟ I: برای هر w ∈ L ، پنج رشته u, v, x, y, z وجود دارند که w = uvxyz و vy ≥ ۱ و برای هر…

فرض کنید زبان L با PDA به شکل زیر باشد که Σ = a,b الفبای ورودی و Γ = x , z الفبای پشته و z نماد بالایی پشته است. با قرار گرفتن کدام‌یک از دو مقدار a یا b به جای y در w = a^۱۴۰۴y b^۲۱۰۵ ، رشته w حاصل…

فرض کنید L زبان ماشین تورینگ زیر باشد: (نمودار حالت‌ها با حالت آغازین q_۱ و حالت‌های q_۲,…,q_۶,q_accept,q_reject روی الفبای نوار ∘, x, sqcup . ماشین نخستین ∘ را حذف می‌کند و سپس به‌طور مکرر نوار را…

فرض کنید M یک ماشین تورینگ معمولی است با این تفاوت که امکان حرکت به چپ را ندارد اما می‌تواند در همان خانه بماند. کدام مورد درخصوص M درست است؟

فرض کنید زبان L، زبان dfa زیر باشد: (در نمودار: حالت آغازین q_1 است؛ گذارها: q_1xrightarrow a q_2 ، q_1xrightarrow b q_3 ، q_2xrightarrow a q_2 ، q_2xrightarrow b q_3 ، q_3xrightarrow a q_4…

چه تعداد از گزاره‌های زیر، با گزاره‌ی ¬ ∀ x ∃ y P(x,y) ، معادل منطقی هستند؟ (a) ∃ x ¬ ∀ y P(x,y) (b) ∃ x ∃ y ¬ P(x,y) (c) ∃ x ¬ ∃ y P(x,y) (d) ∃ x ∀ y ¬ P(x,y)

از دو استدلال زیر کدام معتبر است؟ الف ــ چنین نیست که (همه دانش‌آموزان باهوش و همه معلم‌ها توانمند باشند.) اگر منابع مالی به‌اندازه کافی وجود داشته باشد، آن‌گاه همه معلم‌ها توانمند هستند. بنابراین…

از دو عبارت α ≡ ¬ P → (r ∨ q) β ≡ ¬ r → (¬ p → q) کدام‌یک مستلزم منطقی دیگری است؟ ( X را مستلزم منطقی Y گوییم هرگاه Y ⇒ X .)

کدام مورد بهترین ترجمه برای عبارت زیر در منطق گزاره‌ها است؟ اگر آفتاب طلوع کند «به دوچرخه‌سواری می‌روم فقط اگر دوچرخه خراب باشد.» T : آفتاب طلوع می‌کند D : به دوچرخه‌سواری می‌روم K : دوچرخه خراب است

فرض کنید: A(x) : x یک کاربر است C(x) : x به سرور وصل شده است R(x,y) : x، y را دریافت می‌کند k(x) : x پیام کدگذاری شده است کدام مورد بهترین ترجمه برای عبارت زیر در منطق سورها است؟ «کاربرانی که به سرور…

فرض کنید L = R, C زبان مرتبه اول باشد که در آن R نماد معمولی دوموضعی و C ثابت است. دو L -ساختار M = (Z, <_m, -1) و N = (N, <, ۰) را درنظر می‌گیریم، به‌طوری‌که N مجموعه اعداد صحیح نامنفی، Z مجموعه…

با درنظرگرفتن فرضیات سؤال ۹۶، اگر α ≡ ∀ x (R(x,C) → ∃ y R(y,x)) کدام مورد درست است؟

فرض کنید α یک فرمول در منطق گزاره‌ها شامل سه گزاره اتمی p ، q و r باشد، که در جدول ارزش آن تنها سه سطر با ارزش ۰ مطابق جدول زیر وجود دارد: p q r α :---: :---: :---: :---: ۱ ۰ ۱ ۰ ۱ ۰ ۰ ۰ ۰ ۰ ۱ ۰ در…

فرض کنید رابط گزاره‌ای با جدول ارزش زیر داده شده است. A B A B --- --- --- ۱ ۱ ۰ ۱ ۰ ۱ ۰ ۱ ۱ ۰ ۰ ۱ یک مجموعه از رابط‌های گزاره‌ای را کامل گوییم، هرگاه هر فرمول در منطق گزاره‌ها دارای معادلی باشد که…

فرض کنید زبان مرتبه اول شامل یک نماد معمولی دو موضعی P باشد. سه جمله a، b و c زیر را در نظر بگیرید: (a) ∀ x ∀ y ∀ z (P(x,y) → (P(y,z) → P(x,z))) (b) ∀ x ∀ y (P(x,y) → (P(y,x) → x = y)) (c) ∀ x ∃ y…

کدام مورد، درخصوص مجموعه تمام زیردنباله‌های دنباله ۱/n _(n=۱)^(∞) درست است؟

مجموعه a + b√۲ : a,b ∈ Q با چه تعدادی از مجموعه‌های [۰ , √۲] ، C و N هم‌توان است؟ ( N مجموعه اعداد طبیعی، Q مجموعه اعداد گویا و C مجموعه اعداد مختلط است.)

فرض کنید A = N^N مجموعه همه توابع از N به N باشد. رابطه R = (f,g) ∈ N^N × N^N f(∘) = g(∘) را بر A در نظر بگیرید. اگر A/R مجموعه همه کلاس‌های هم‌ارزی رابطه R بر A باشد، کدام مورد برای مجموعه A/R درست…

فرض کنید N_e مجموعه اعداد طبیعی زوج و G : N → N_e^N با ضابطه G(n) = f_n چنان تعریف شود، که f_n : N → N_e و f_n(m) = ۲n . کدام مورد درست است؟ ( N_e^N یعنی مجموعه همه توابع از N به N_e )