افراز عددی مرتب و نامرتب (قسمت اول)
افراز عددی مرتب و نامرتب (قسمت دوم)
افراز عددی مرتب و نامرتب (قسمت سوم)
افراز عددی مرتب و نامرتب (قسمت چهارم)
افراز عددی مرتب و نامرتب (قسمت پنجم)
پیچیدگی
تمرین‌های هفتهٔ دوم
۱. فرض کنید \(a\) و \(b\) اعداد صحیحی باشند که \(0\leq a\leq b\) برقرار است. تعداد جواب‌های صحیح نامعادلهٔ
\[a\leq\big|x_1\big|+\dots+\big|x_r\big|<b\] را در هر یک از حالت زیر محاسبه کنید.
الف) \(x_i\)ها مخالف صفر باشند.
ب) \(x_i\)ها اعداد صحیح دلخواه باشند.
۲. ثابت کنید تعداد راههای نوشتن \(n\) به صورت مجموعی از جمع‌وندهای \(1\)، \(2\)، و \(3\) بدون مهم بودن ترتیب جمع‌وندها، به‌طوری که هر یک از این جمع‌وندها حداقل یک‌بار مورد استفاده قرار گیرند، برابر عبارت زیر است:
\[1+\Big\lfloor\frac{n(n-6)}{12}\Big\rfloor.\]
۳. ثابت کنید تعداد افرازهای \(n\) به حداکثر \(k\) جزء برابر با تعداد افرازهای \(n+k\) به دقیقاً \(k\) جزء است.
۴. فرض کنید هر کدام از گزاره‌ها، زمان اجرای یک الگوریتم از اندازهٔ ورودی \(n\) باشد. در هر مورد مشخص کنید که کوچک‌ترین کران بالا \((O)\) برای اجرای الگوریتم چیست و با آوردن استدلال آن را اثبات کنید.
\[\begin{aligned}a)\;&5+0.001n^3+0.025n\\b)\;&0.3n+5n^{1.5}+2.5n^{1.75}\\c)\;&n\log_3n+n\log_2n\\d)\;&3\log_8n+\log_2\log_2 \log_2n\\e)\;&2n+n^{0.5}+0.5n^{1.25}\\f)\;&100n\log_3n+n^3+100n\end{aligned}\]
۵. درستی یا نادرستی هر یک از گزاره‌های زیر را مشخص کنید و برای پاسخ‌تان دلیل بیاورید. در صورت غلط بودن، عبارتی صحیح پیشنهاد دهید.
\[\begin{aligned}a)\;&O(f+g)=O(f)+O(g)\\b)\;&O(f\cdot g)=O(f)\cdot O(g)\\c)\;&g=O(f)\;{\rm and}\;h=O(f)\Rightarrow g=O(h)\\d)\;&5n+8n^2+100n^3=O(n^4)\\e)\;&5n+8n^2+100n^3=O(n^2 log n)\end{aligned}\]
باسلام، یه سوال مدرس چه کسی هستن؟
از تیم خودتون (تکمیلی) هستن؟
سلام
مدرس آقای دکتر مرتضی محمدنوری، استاد دانشکدهٔ ریاضی و علوم کامپیوتر دانشگاه تهران هستند.