3-طراحی الگوریتم

[powerboy2988]

این تاپیک برای بحث و گفتگو درباره درس طراحی الگوریتم می باشد.

از دوستانی که مشکلی با درس طراحی الگوریتم دارند تقاضا می شود که در اینجا مطرح کنند.

[powerboy2988]

سلام به دوستان
من واسه ارشد دارم از کتاب نیپولیتان می خونم . کتاب جالبی . استادمون هم داره از همین کتاب درس میده.

مشکلی که تو این کتاب بهش برخوردم اینکه نمی تونم الگوریتم استراسن رو پیاده سازی کنم. کسی میتونه کمک کنه؟

[kanan]

سلام به دوستان
من واسه ارشد دارم از کتاب نیپولیتان می خونم . کتاب جالبی . استادمون هم داره از همین کتاب درس میده.

مشکلی که تو این کتاب بهش برخوردم اینکه نمی تونم الگوریتم استراسن رو پیاده سازی کنم. کسی میتونه کمک کنه؟

مشكل اصلي اين كتاب ترجمشه كه واقعا افتضاح هستش اصلا تابلو كه جعفرنژاد داده دانشجوهاش ترجمه كردن من از روي ترجمه جليلي ميخونه
راستي هر هفته استاد ما تمرين ميده كه اونارو اينجا ميزارم ببينين شما ميتونين حل كنين هر كي تونست جوابشو بزاره منم بدم به استاد ثواب داره ها كمي تا نيمه ابري سخت هستش هنوز هيچ كدوم نتونستم حل كنم

[kanan]

با سلام
استادمون جواب اين سوالات گذاشت ولي تا حالا كه بيش 2 ساعت گذشته سر در نميارم
آخه چرا راديكال همين توري حذف كرده يعني چه چون N بزرگه راديكال حذف كرده
به خدا استاد به من يه 12 بده برام كافي هستش هيچي سر در نميارم

[sh]

سلام
بچه ها اگه مي تونيد تمام سوالاتي که استادتون ميگه رو اينجا بزاريد.

[kanan]

با سلام
سوالات اين هفته كه استادمون بهمون گفته حل كنيم

[naser.g]

سلام
چند سوال طراحی الگوریتم دارم
دوستان سری یه کمکی برسونن که چند نمرم در گرو این سوالاست
لطفا سریییییییییییییییییییییییییییییییییییییییییی
مرسی موفق باشید

[musicjet]

دوستان سلام.
من دنبال الگوریتم مثلث بندی بهینه ی چند ضلعی محدب میگردم.
ممنون میشم اگه توی جزوه هاتون دارید برام بذارید.
ایشالا به هر چی دوست دارین برسین.

[sh]

با استفااده از الگوريتم عقبگرد چطوري مي تونيم با سه رنگ گراف رو رنگ اميزي کنيم؟اينم شکل گراف



0----0-----0
| | |
0 ---0-----0

[rosa_127]

دوست عزيز شكل گرافي كه گذاشتين واضح نيست؛ پيشنهاد مي كنم از ترجمه كتاب neapolitan صفحات
193 -197 رو مطالعه كنيد؛ علاوه بر روش دستي مي تونيد در الگوريتم m_coloring با قرار دادن مقدار 3 به
جاي m گراف رو رنگ آميزي كنيد.

امتحان ميان ترم :
http://www.adeli.ir/courses/algorithms_ ... y-87-9.pdf

رفرنسها و اسلايدهاي طراحي الگوريتم:
http://www.adeli.ir/courses/algorithms_fall2008

همانطوريكه مي دونيد كتابهاي CLRS , Neapolitan هرسال مدنظر طراحان ارشد براي دروس طراحي الگوريتم و ساختمان داده هست؛ و معمولا اساتيد تمرينات اين كتابها رو به عنوان homework به دانشجوها مي دن؛ براي نمونه لينك زير كه يكي از تمرينات دكتر قدسي به دانشجويان شريف هست:

http://mehr.sharif.edu/%7Ece354/assigns/hw1-84.pdf
http://mehr.sharif.edu/%7Ece354/assigns/hw5-84.pdf

اكثر تمرينات CLRS رو مي تونيد از لينكهاي زير دانلود كنيد:

http://rapidshare.com/files/182351485/C ... s.rar.html
http://rapidshare.com/files/182358238/I ... n.rar.html

براي باقي مسائل مي تونيد از سايت زير كمك بگيريد:

http://cs.cramster.com/introduction-to- ... 6-337.aspx

و همين طور براي كتاب Algorithms (by Kenneth A. Berman):

http://cs.cramster.com/algorithms-1st-16-411.aspx

البته توي تعدادي از دانشگاهها مثل دانشكده شريعتي علاوه بر تمرينات دو كتاب گفته شده سوالات مسابقات ACM هم به عنوان تكليف داده مي شه:

الگوريتم ( Pass_Muraille (ACM 27th:
http://adeli.ir/courses/algorithms_fall2008/B.pdf

مراجع اعلام شده وزارت علوم:

1- Neapolitan, Foundations of Algorithms.
2- CLRS) Cormen, leisersen, Rivert, Introduction to Algorithms)
3- Horowitz, Sahni, Fundamental of Computer Algorithms.
4- Aho, Hopctoft, Data Structure & Algorithms.
5- Udi Manber, Introduction to Algorithms.
6- Brassard, Fundamentals of Algorithms.

[مهيار]

اينم قسمت اول از كتاب udi manber كه چند سالي به عنوان منبع كنكور بود و سئوالهاي كنكور از تمرين ها و مباحث اين كتاب ميومد

http://rapidshare.com/files/202546919/manber1.rar.html

سر اولين فرصت 8 قسمت ديگه اين كتاب رو واستون آپلود ميكنم

[مهيار]

اينم 8 پارت بعدي

http://rapidshare.com/files/202647994/manber2.rar.html
http://rapidshare.com/files/202647996/manber3.rar.html
http://rapidshare.com/files/202647997/manber4.rar.html
http://rapidshare.com/files/202647998/manber5.rar.html
http://rapidshare.com/files/202647999/manber6.rar.html
http://rapidshare.com/files/202648000/manber7.rar.html
http://rapidshare.com/files/202648001/manber8.rar.html
http://rapidshare.com/files/202648002/manber9.rar.html

[Evil Boy]

جوابم رو گرفتم.ممنون

[Sentiment]

سلام..
بچه ها استاد طراحي الگوريتممون 3 تا اثبات از ما خواسته که من اینجا میذارم..
خواهش میکنم اگه میتونید حتما طریقه اثبات این دو تا رو بگید، کتاب خونه دانشگامون در حال تغییر تحوله، و گرنه اول خودم میرفتم سراغش بعد اگه پیدا نمیکردم از شما کمک میخواستم که وقتتون رو نگیرم.

اولی تو کتاب نیپولیتان هست که گفته بگیریمش، متاسفانه هر جا رفتم تموم شده بود، برای همینم نتونستم گیرش بیارم.
سومی هم استادمون گفت توی کتاب نغیب زاده هست، حالا اگه این کتاب رو دارید از توش نگاه کنید.
دومی رو نمیدونم از کدوم کتابه، شاید از کتاب مقسمی باشه.

فردا کلاسش رو دارم، ممنون میشم تا اونموقع جواب بدید.
فقط دومی رو اگه اثباتش رو گفتید بگید از کدوم کتابه.

مرسی.

فعلا..

[مهيار]

خوب اگر درست ديده باشم اون بايد o كوچيك باشه .
همونطور كه 100% تو اين مدت بهتون گفته شده o كوچيك هميشه يه حد كاملا بزرگ رو بر ميگردونه و برخلاف O بزرگ كه هميشه يه حد بزرگتر و مساوي بر ميگردونه عمل ميكنه

در مورد سئوال اولتون بايد بگم كه چون !n بزرگترين مرتبه زماني رو داره و قبل اون o كوچيك اومده بنابراين ميشه گفت كه a به توان n كه يك تابع نمايي ( به عنوان مثال a ميتونه هر مقدار ثابتي مثه 2و3و4و... بگيره ) بنابراين درست گفته شده كه
a^n E o(!n)

به عنوان توضيح تكميلي بايد بگم كه توابعي كه با نماد o كوچيك بيان ميشه هميشه سمت راستش كه مرتبه زماني تابع قرار ميگيره بايد يه حد بزرگتر از مرتبه واقعي رو برگردونه
مثلا همين تابع a^n ميتونه از مرتبه زماني n^n هم باشه و يا از مرتبه !log n* n هم باشه ( اگه درست گفته باشم )

در مورد سئوال دوم هم به همين منواله

شما كافيه بدونيد كه ترتيب رشد توابع به چه صورته و بعد تابع رو با مرتبه زماني داده شده مقايسه كنيد اگه o كوچيك بود حد بزرگتر اگر o بزرگ بود حد بزرگتر مساوي و دقيقا اين مسئله اما تضادش براي نماد امگا هم صدق ميكنه

در مورد سئوال سومتون از تابع چند جمله اي داده شده كافيه كه بزرگترين درجه رو در نظر بگيريد ضمن اينكه اينجا ضريب a تاثيري نداره .
بزرگترين درجه همون n^m هست كه با توجه به تعاريفي كه گفتم چون با نماد O بزرگ اومده و گفته شده كه از مرتبه زماني n^m هست و با توجه به اينكه نماد O بزرگ يك حد بزرگتر و مساوي با تابع بر ميگردونه بنابراين درست گفته شده در اينجا مرتبه زماني تابع از نظر مقداري با نمودار تابع ( در صورت ترسيم ) مساوي و دقيقا هم رو به ازاي مقادير مختلف براي n قطع ميكنند .

ضمن اينكه توصيه من اينه كه اصلا خودتونو محدود به كتاب نكنيد تو اين درس چون كه باعث ميشه خيلي چيزها رو نتونيد متوجه بشيد .

اميدوارم تونسته باشم منظورمو بهتون رسونده باشم

موفق باشيد