الگوریتم امروز

پارامتر k را می توان از روی الگوریتم های جستجوی محلی (local search) به سادگی فهمید. اینها همان پارامتری هستند که با جا به جا کردن دو چیز آن را بهبود می دهیم.

۰ نظر

۰ ۱۸ اسفند ۹۲ ، ۱۵:۳۰

سپیده آقاملائی

اگر پارامتر k را هم به ازای ورودی ها داشته باشیم (به جز n که سایز ورودی است) می توانیم الگوریتم هایی با زمان O(f(k)n^c) بدهیم که در آنها c ثابت است. به چنین الگوریتمی پارامتر ثابت (fixed parameter) می گویند. در الگوریتم k را ثابت فرض می کنیم.

http://www.cs.bme.hu/~dmarx/papers/marx-tractability-slides.pdf

اگر برای مساله ی np-complete بتوانیم پارامتر ثابت k تعیین کنیم که به ازای آن الگوریتم بر حسب k نمایی باشد و برحسب n چند جمله ای باشد به آن FPC می گویند. (مخفف fixed parameter tractable)

http://en.wikipedia.org/wiki/Parameterized_complexity

۰ نظر

۰ ۱۸ اسفند ۹۲ ، ۱۵:۲۰

سپیده آقاملائی

صورت سوالهای تمرین موازی

تمرین ها دو تصویر هستند. :) برای اینکه نیاز به گشتن در کتاب نباشد همه را یکجا گذاشتم.

شکلها و سوالاتی که در تمرین ها به آنها ارجاع داده شده است:

۰ نظر

۰ ۱۷ اسفند ۹۲ ، ۱۱:۰۸

سپیده آقاملائی

تمرین های موازی

From Leighton:

1.3

1.11

1.26

1.32

1.34

1.51

1.60

1.65

1.84

1.85

1.112

1.117

1.118

1.119

1.127

1.142

1.161

1.160

1.154

1.152

۰ نظر

۰ ۱۷ اسفند ۹۲ ، ۱۰:۴۷

سپیده آقاملائی

جواب تمرین های هندسه پیشرفته

جواب تمرین ها تو خود کتاب هست! (ته کتاب)

۰ نظر

۰ ۱۷ اسفند ۹۲ ، ۰۸:۴۰

سپیده آقاملائی

قدیمی ترین مطالب مطالب قدیمی تر جدیدترین مطالب مطالب جدید تر