چند مورد از گزارههای زیر درست است؟ I. هر الگوریتم که ضرب دو ماتریس را محاسبه کند، میتواند در همان مرتبه وارون یک ماتریس را محاسبه کند و بالعکس. II. برای محاسبه ضرب دو چندجملهای از درجه ۱۶ تعداد فراخوانیهای لازم با استفاده از الگوریتم تقسیم و حل، وقتی که چندجملهای حداکثر از درجه ۴، چندجملهای کوچک تلقی میشود برابر با ۱۳ است. III. در شبکه جریان داده شده شکل زیر اگر فقط مجاز به افزایش ظرفیت یک یال باشیم، حداکثر میتوان ۷ واحد به ظرفیت یک یال آن اضافه کرد تا شبکه حداکثر جریان عبوری را داشته باشیم. شبکه (جهتدار، ظرفیتها): s→ 2 با ظرفیت 5 ، s→ 3 با ظرفیت 9 ، 3→ 2 با ظرفیت 2 ، 2→ t با ظرفیت 14 ، 3→ t با ظرفیت 3 .

سوال ۶۷ کنکور ارشد مهندسی کامپیوتر ۱۴۰۳

اهمیت

۰/۵

چند مورد از گزاره‌های زیر درست است؟

I. هر الگوریتم که ضرب دو ماتریس را محاسبه کند، می‌تواند در همان مرتبه وارون یک ماتریس را محاسبه کند و بالعکس.
II. برای محاسبه ضرب دو چندجمله‌ای از درجه ۱۶ تعداد فراخوانی‌های لازم با استفاده از الگوریتم تقسیم و حل، وقتی که چندجمله‌ای حداکثر از درجه ۴، چندجمله‌ای کوچک تلقی می‌شود برابر با ۱۳ است.
III. در شبکه جریان داده شده شکل زیر اگر فقط مجاز به افزایش ظرفیت یک یال باشیم، حداکثر می‌توان ۷ واحد به ظرفیت یک یال آن اضافه کرد تا شبکه حداکثر جریان عبوری را داشته باشیم.

شبکه (جهت‌دار، ظرفیت‌ها): $s\to 2$ با ظرفیت $5$ ، $s\to 3$ با ظرفیت $9$ ، $3\to 2$ با ظرفیت $2$ ، $2\to t$ با ظرفیت $14$ ، $3\to t$ با ظرفیت $3$ .

#max-flow#min-cut#divide-and-conquer#polynomial-multiplication#matrix-inversion