3-طراحی الگوریتم
مدیر انجمن: rosa_127
-
- کاربر ساده
- پست: 52
- تاریخ عضویت: یکشنبه 27 مرداد 1387, 4:10 pm
3-طراحی الگوریتم
این تاپیک برای بحث و گفتگو درباره درس طراحی الگوریتم می باشد.
از دوستانی که مشکلی با درس طراحی الگوریتم دارند تقاضا می شود که در اینجا مطرح کنند.
از دوستانی که مشکلی با درس طراحی الگوریتم دارند تقاضا می شود که در اینجا مطرح کنند.
چه کمکی به کشورم و مردم کشورم می تونم بکنم؟
-
- کاربر ساده
- پست: 52
- تاریخ عضویت: یکشنبه 27 مرداد 1387, 4:10 pm
Re: 3-طراحی الگوریتم
سلام به دوستان
من واسه ارشد دارم از کتاب نیپولیتان می خونم . کتاب جالبی . استادمون هم داره از همین کتاب درس میده.
مشکلی که تو این کتاب بهش برخوردم اینکه نمی تونم الگوریتم استراسن رو پیاده سازی کنم. کسی میتونه کمک کنه؟
من واسه ارشد دارم از کتاب نیپولیتان می خونم . کتاب جالبی . استادمون هم داره از همین کتاب درس میده.
مشکلی که تو این کتاب بهش برخوردم اینکه نمی تونم الگوریتم استراسن رو پیاده سازی کنم. کسی میتونه کمک کنه؟
چه کمکی به کشورم و مردم کشورم می تونم بکنم؟
Re: 3-طراحی الگوریتم
مشكل اصلي اين كتاب ترجمشه كه واقعا افتضاح هستش اصلا تابلو كه جعفرنژاد داده دانشجوهاش ترجمه كردن من از روي ترجمه جليلي ميخونهpowerboy2988 نوشته شده:سلام به دوستان
من واسه ارشد دارم از کتاب نیپولیتان می خونم . کتاب جالبی . استادمون هم داره از همین کتاب درس میده.
مشکلی که تو این کتاب بهش برخوردم اینکه نمی تونم الگوریتم استراسن رو پیاده سازی کنم. کسی میتونه کمک کنه؟
راستي هر هفته استاد ما تمرين ميده كه اونارو اينجا ميزارم ببينين شما ميتونين حل كنين هر كي تونست جوابشو بزاره منم بدم به استاد ثواب داره ها كمي تا نيمه ابري سخت هستش هنوز هيچ كدوم نتونستم حل كنم
- پیوستها
-
- untitled.JPG (64.87 KiB) مشاهده 15898 مرتبه
زندگي را مثل پيازي ديدم كه هر ورقشو باز كردم
اشك منو درآورد!!
خدا بگم چيكارت نكنه اون كسي كه منو معتاد سريال فرار از زندان كردي
گفتگو آنلاين اعضا انجمن
http://www.tinychat.com/6kclp
اشك منو درآورد!!
خدا بگم چيكارت نكنه اون كسي كه منو معتاد سريال فرار از زندان كردي
گفتگو آنلاين اعضا انجمن
http://www.tinychat.com/6kclp
Re: 3-طراحی الگوریتم
با سلام
استادمون جواب اين سوالات گذاشت ولي تا حالا كه بيش 2 ساعت گذشته سر در نميارم
آخه چرا راديكال همين توري حذف كرده يعني چه چون N بزرگه راديكال حذف كرده
به خدا استاد به من يه 12 بده برام كافي هستش هيچي سر در نميارم
استادمون جواب اين سوالات گذاشت ولي تا حالا كه بيش 2 ساعت گذشته سر در نميارم
آخه چرا راديكال همين توري حذف كرده يعني چه چون N بزرگه راديكال حذف كرده
به خدا استاد به من يه 12 بده برام كافي هستش هيچي سر در نميارم
- پیوستها
-
- untitled1.JPG (61.04 KiB) مشاهده 15690 مرتبه
زندگي را مثل پيازي ديدم كه هر ورقشو باز كردم
اشك منو درآورد!!
خدا بگم چيكارت نكنه اون كسي كه منو معتاد سريال فرار از زندان كردي
گفتگو آنلاين اعضا انجمن
http://www.tinychat.com/6kclp
اشك منو درآورد!!
خدا بگم چيكارت نكنه اون كسي كه منو معتاد سريال فرار از زندان كردي
گفتگو آنلاين اعضا انجمن
http://www.tinychat.com/6kclp
Re: 3-طراحی الگوریتم
سلام
بچه ها اگه مي تونيد تمام سوالاتي که استادتون ميگه رو اينجا بزاريد.
بچه ها اگه مي تونيد تمام سوالاتي که استادتون ميگه رو اينجا بزاريد.
Re: 3-طراحی الگوریتم
با سلام
سوالات اين هفته كه استادمون بهمون گفته حل كنيم
سوالات اين هفته كه استادمون بهمون گفته حل كنيم
- پیوستها
-
- untitled3.JPG (65.05 KiB) مشاهده 15651 مرتبه
-
- untitled2.JPG (49.32 KiB) مشاهده 15572 مرتبه
زندگي را مثل پيازي ديدم كه هر ورقشو باز كردم
اشك منو درآورد!!
خدا بگم چيكارت نكنه اون كسي كه منو معتاد سريال فرار از زندان كردي
گفتگو آنلاين اعضا انجمن
http://www.tinychat.com/6kclp
اشك منو درآورد!!
خدا بگم چيكارت نكنه اون كسي كه منو معتاد سريال فرار از زندان كردي
گفتگو آنلاين اعضا انجمن
http://www.tinychat.com/6kclp
Re: 3-طراحی الگوریتم
سلام
چند سوال طراحی الگوریتم دارم
دوستان سری یه کمکی برسونن که چند نمرم در گرو این سوالاست
لطفا سریییییییییییییییییییییییییییییییییییییییییی
مرسی موفق باشید
چند سوال طراحی الگوریتم دارم
دوستان سری یه کمکی برسونن که چند نمرم در گرو این سوالاست
لطفا سریییییییییییییییییییییییییییییییییییییییییی
مرسی موفق باشید
- پیوستها
-
- tarahi algo.rar
- (4.33 KiB) 595 مرتبه دانلود شده
Re: 3-طراحی الگوریتم
دوستان سلام.
من دنبال الگوریتم مثلث بندی بهینه ی چند ضلعی محدب میگردم.
ممنون میشم اگه توی جزوه هاتون دارید برام بذارید.
ایشالا به هر چی دوست دارین برسین.
من دنبال الگوریتم مثلث بندی بهینه ی چند ضلعی محدب میگردم.
ممنون میشم اگه توی جزوه هاتون دارید برام بذارید.
ایشالا به هر چی دوست دارین برسین.
Re: 3-طراحی الگوریتم
با استفااده از الگوريتم عقبگرد چطوري مي تونيم با سه رنگ گراف رو رنگ اميزي کنيم؟اينم شکل گراف
0----0-----0
| | |
0 ---0-----0
0----0-----0
| | |
0 ---0-----0
Re: 3-طراحی الگوریتم
دوست عزيز شكل گرافي كه گذاشتين واضح نيست؛ پيشنهاد مي كنم از ترجمه كتاب 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.
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.
مشاوره خصوصی کنکور 92 برای متقاضیان قبولی در سراسری تهران
Re: 3-طراحی الگوریتم
اينم قسمت اول از كتاب udi manber كه چند سالي به عنوان منبع كنكور بود و سئوالهاي كنكور از تمرين ها و مباحث اين كتاب ميومد
http://rapidshare.com/files/202546919/manber1.rar.html
سر اولين فرصت 8 قسمت ديگه اين كتاب رو واستون آپلود ميكنم
http://rapidshare.com/files/202546919/manber1.rar.html
سر اولين فرصت 8 قسمت ديگه اين كتاب رو واستون آپلود ميكنم
پيش از سحر تاريك است،اما تا كنون نشده که آفتاب طلوع نکند... به سحر اعتماد کنيد.
شکست وجود ندارد مگر در ذهن سازندهاش!
-------------------------------------------------------------------
بوي جوي موليان آيد همي
ياد يار مهربان آيد همي
ديگه آموي و درشتي هاي او
زير پايم پرنيان آيد همي
--------------------------------------------------------------------------
به سلامتي بچه هاي قديم که با ذغال واسه خودشون سيبيل ميذاشتن تا شبيه باباهاشون بشن نه بچه هاي الان که ابروهاشونو بر ميدارن تا شبيه مادراشون بشن
شکست وجود ندارد مگر در ذهن سازندهاش!
-------------------------------------------------------------------
بوي جوي موليان آيد همي
ياد يار مهربان آيد همي
ديگه آموي و درشتي هاي او
زير پايم پرنيان آيد همي
--------------------------------------------------------------------------
به سلامتي بچه هاي قديم که با ذغال واسه خودشون سيبيل ميذاشتن تا شبيه باباهاشون بشن نه بچه هاي الان که ابروهاشونو بر ميدارن تا شبيه مادراشون بشن
Re: 3-طراحی الگوریتم
اينم 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
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
پيش از سحر تاريك است،اما تا كنون نشده که آفتاب طلوع نکند... به سحر اعتماد کنيد.
شکست وجود ندارد مگر در ذهن سازندهاش!
-------------------------------------------------------------------
بوي جوي موليان آيد همي
ياد يار مهربان آيد همي
ديگه آموي و درشتي هاي او
زير پايم پرنيان آيد همي
--------------------------------------------------------------------------
به سلامتي بچه هاي قديم که با ذغال واسه خودشون سيبيل ميذاشتن تا شبيه باباهاشون بشن نه بچه هاي الان که ابروهاشونو بر ميدارن تا شبيه مادراشون بشن
شکست وجود ندارد مگر در ذهن سازندهاش!
-------------------------------------------------------------------
بوي جوي موليان آيد همي
ياد يار مهربان آيد همي
ديگه آموي و درشتي هاي او
زير پايم پرنيان آيد همي
--------------------------------------------------------------------------
به سلامتي بچه هاي قديم که با ذغال واسه خودشون سيبيل ميذاشتن تا شبيه باباهاشون بشن نه بچه هاي الان که ابروهاشونو بر ميدارن تا شبيه مادراشون بشن
نحوه اثبات؟
سلام..
بچه ها استاد طراحي الگوريتممون 3 تا اثبات از ما خواسته که من اینجا میذارم..
خواهش میکنم اگه میتونید حتما طریقه اثبات این دو تا رو بگید، کتاب خونه دانشگامون در حال تغییر تحوله، و گرنه اول خودم میرفتم سراغش بعد اگه پیدا نمیکردم از شما کمک میخواستم که وقتتون رو نگیرم.
اولی تو کتاب نیپولیتان هست که گفته بگیریمش، متاسفانه هر جا رفتم تموم شده بود، برای همینم نتونستم گیرش بیارم.
سومی هم استادمون گفت توی کتاب نغیب زاده هست، حالا اگه این کتاب رو دارید از توش نگاه کنید.
دومی رو نمیدونم از کدوم کتابه، شاید از کتاب مقسمی باشه.
فردا کلاسش رو دارم، ممنون میشم تا اونموقع جواب بدید.
فقط دومی رو اگه اثباتش رو گفتید بگید از کدوم کتابه.
مرسی.
فعلا..
بچه ها استاد طراحي الگوريتممون 3 تا اثبات از ما خواسته که من اینجا میذارم..
خواهش میکنم اگه میتونید حتما طریقه اثبات این دو تا رو بگید، کتاب خونه دانشگامون در حال تغییر تحوله، و گرنه اول خودم میرفتم سراغش بعد اگه پیدا نمیکردم از شما کمک میخواستم که وقتتون رو نگیرم.
اولی تو کتاب نیپولیتان هست که گفته بگیریمش، متاسفانه هر جا رفتم تموم شده بود، برای همینم نتونستم گیرش بیارم.
سومی هم استادمون گفت توی کتاب نغیب زاده هست، حالا اگه این کتاب رو دارید از توش نگاه کنید.
دومی رو نمیدونم از کدوم کتابه، شاید از کتاب مقسمی باشه.
فردا کلاسش رو دارم، ممنون میشم تا اونموقع جواب بدید.
فقط دومی رو اگه اثباتش رو گفتید بگید از کدوم کتابه.
مرسی.
فعلا..
- پیوستها
-
- mathematic.JPG (27.62 KiB) مشاهده 14278 مرتبه
بهارهای شگفتی در راهند، فردا گلی میشکفد که بادها را پرپر خواهد کرد.
اللهم صلی علی محمد و آل محمد و عجل فرجهم
اللهم صلی علی محمد و آل محمد و عجل فرجهم
Re: 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 قطع ميكنند .
ضمن اينكه توصيه من اينه كه اصلا خودتونو محدود به كتاب نكنيد تو اين درس چون كه باعث ميشه خيلي چيزها رو نتونيد متوجه بشيد .
اميدوارم تونسته باشم منظورمو بهتون رسونده باشم
موفق باشيد
همونطور كه 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 قطع ميكنند .
ضمن اينكه توصيه من اينه كه اصلا خودتونو محدود به كتاب نكنيد تو اين درس چون كه باعث ميشه خيلي چيزها رو نتونيد متوجه بشيد .
اميدوارم تونسته باشم منظورمو بهتون رسونده باشم
موفق باشيد
پيش از سحر تاريك است،اما تا كنون نشده که آفتاب طلوع نکند... به سحر اعتماد کنيد.
شکست وجود ندارد مگر در ذهن سازندهاش!
-------------------------------------------------------------------
بوي جوي موليان آيد همي
ياد يار مهربان آيد همي
ديگه آموي و درشتي هاي او
زير پايم پرنيان آيد همي
--------------------------------------------------------------------------
به سلامتي بچه هاي قديم که با ذغال واسه خودشون سيبيل ميذاشتن تا شبيه باباهاشون بشن نه بچه هاي الان که ابروهاشونو بر ميدارن تا شبيه مادراشون بشن
شکست وجود ندارد مگر در ذهن سازندهاش!
-------------------------------------------------------------------
بوي جوي موليان آيد همي
ياد يار مهربان آيد همي
ديگه آموي و درشتي هاي او
زير پايم پرنيان آيد همي
--------------------------------------------------------------------------
به سلامتي بچه هاي قديم که با ذغال واسه خودشون سيبيل ميذاشتن تا شبيه باباهاشون بشن نه بچه هاي الان که ابروهاشونو بر ميدارن تا شبيه مادراشون بشن