کمک برای یادگیری طراحی الگوریتم

[adel1368]

با سلام:

 من این طراحی الگوریتم رو نمی تونم خوب یاد بگیرم دوستان میتونن مرجعی

رومعرفی کنن برای یادگیریش 


 بجز این کتاب
طراحی الگوریتم ها

تالیف :
ریچارد نپولیتان
کیمرث  نعیمی پور


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

[کیان]

زبان غیرمادری مسلطی؟

[adel1368]

منظورتون انگلیسی باشه

آره میتونم بخونم

[不眠症]

به زبان مادری این سایت خوبه
http://www.algorithmha.ir/

به غیر از خواندن نوشتن مساله و توضیح برای خود(راه حل به صورت قدم به قدم) با صدای بلند راه‌گشاست (جدی)
بیشتر از تئوری میخوای یادبگیری پیاده سازی مساله و دیدن نتیجه(خروجی) و متغییرها به اصطلاح بازی بازی شود تا منطق کار درک شود. خوبی این کار اینه که با پیچاندن مسئله پیچش نمیخوری چون قبلش پیچش دادی یعنی بازی بازی کردی

به زبان غیر مادری
 یه کتاب خوب هست ولی چون وقت نداری توصیه نمی‌کنم
http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1849967202/ref=sr_1_1?ie=UTF8&qid=1354961883&sr=8-1&keywords=algorithm+design+manual

اگر بیشتر نیاز داشتی بعضی سایتها هستند که به صورت پراکنده الگوریتم های مختلفی رو شرح می‌دهند بگو تا به اونها هم لینک بدم

[adel1368]

به زبان مادری این سایت خوبه

زبان مادری من یه زبان دیگه ست

ممنون به خاطر معرفی سایت

[doomhammer65ir]

بهترین راه آموختن یک خوارزمی ، پیاده سازی آن به زبانیست که بر ان چیره و مسلط استید.
این ترم بنده هم  این درس را دارم ، هر جا مشکل داشتید بفرمایید

[adel1368]

مشکل اصلی من محاسبه پیچیدگی بازگشتی هاست
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0

میشه روش حل کردنش رو بگین

[امین - am1n]

مشکل اصلی من محاسبه پیچیدگی بازگشتی هاست
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0

میشه روش حل کردنش رو بگین

درختش رو باید رسم کنی دیگه. آسونه ... حالا من کاغذ و مداد ندارم الان 

       t (n)          ->>>  n
   t(n/2)      t(n/2)      ->>> n/2 + n/2 = n

t(n/4)   t(n/4)      ......      ->>> n/4 + n/4 + n/4 + n/4 =n

بعدش کل n هارو با هم جمع میکنی. که میشه D تا n . که D همون عمق درخته . ینی به اندازه ی D   این n ها با هم جمع میشن ... واضح بود ؟

[سید مسعود امامیان]

مشکل اصلی من محاسبه پیچیدگی بازگشتی هاست
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0

میشه روش حل کردنش رو بگین

به نظرم باید ابتدا روش رو فهمید ! مثلاً عدد گذاری تا چند رقم بعد ...

کتاب زیر کتاب خیلی خوبیه (فقط 1313 صفحه است ) :

t._cormen_-_introduction_to_algorithms_3rd_edition

دریافت :

http://uplod.ir/zpstrn5ce7jz/t._cormen_-_introduction_to_algorithms_3rd_edition.pdf.htm

خیلی مضحک هس که این انجمن قابلیت " اتصال فایل ضمیمه " نداره !

[adel1368]

ممنون بخاطر کتاب




با تشکر از همه دوستان

[doomhammer65ir]

مشکل اصلی من محاسبه پیچیدگی بازگشتی هاست
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0

میشه روش حل کردنش رو بگین

این الگوریتم به اصطلاح از گونه ی تقسیم و غلبه (  divide and conquer )  است . برای این الگوریتم ها میانگین مرتبه را از روی فرمول زیر بدست می آوریم :
نخست فرمول را به شکل استاندارد زیر میگیریم :

کد: [انتخاب]

t(n)  = at(n/b)+C(n^k) سپس میانگین برابر است با :

کد: [انتخاب]

if a>b^k =>n^log(a,b)
if a=b^k =>(n^k)*log(n)
if a<b^k =>n^kچون در نمونه ای که دادید :

کد: [انتخاب]

a=2 b=2 k=1
a=b^k میانگین مرتبه از رده :

کد: [انتخاب]

(n^k) * log(n)است . که چون k=1 برابر است با nlogn  .

[adel1368]

مشکل اصلی من محاسبه پیچیدگی بازگشتی هاست
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0

میشه روش حل کردنش رو بگین

این الگوریتم به اصطلاح از گونه ی تقسیم و غلبه (  divide and conquer )  است . برای این الگوریتم ها میانگین مرتبه را از روی فرمول زیر بدست می آوریم :
نخست فرمول را به شکل استاندارد زیر میگیریم :

کد: [انتخاب]

t(n)  = at(n/b)+C(n^k) سپس میانگین برابر است با :

کد: [انتخاب]

if a>b^k =>n^log(a,b)
if a=b^k =>(n^k)*log(n)
if a<b^k =>n^kچون در نمونه ای که دادید :

کد: [انتخاب]

a=2 b=2 k=1
a=b^k میانگین مرتبه از رده :

کد: [انتخاب]

(n^k) * log(n)است . که چون k=1 برابر است با nlogn  .

استادمون این مسئله و حل کرده بود وجوابی شما آوردید اورده بود ولی روش حلش رو نگفته منم که زیادی باهوشم نمیتونستم حلش کنم ولی الان روش حلرو دونستم

اگه زحمتی نباشه میشه یک مثال دیگه حل کنید( )

[doomhammer65ir]

ببینید کلا این روش زمانی کاربرد داره که الگوریتم به همون شکل استانداردی که نوشتم باشه و نه شکل دیگه ای .
یعنی . این الگوریتم ها زمانی بدست میاد که توی الگوریتم ، پرسش رو بجای اینکه بیایم یکراست حل کنیم میایم یک دوم ، یک سوم ، یک دهم از اون پرسش رو حل میکنم ( بخش at(n/b) ) ، سپس میایم یک کارایی روی بخش هایی که حل کردیم و نکردیم انجام میدیم ( مثلا سرهم کردن merge ) که بخش ( C( n^K  رو میسازه . سپس میایم از روی سه شرطی که گفتم میانگین مرتبه رو بدست میاریم
الگوریتم های مرتب کردن ادغامی و سریع و اینها از این دسته است
اگر کتاب دم دستت داری بخش (( ضرب اعداد صحیح بزرگ از روش تقسیم و غلبه )) رو بخون
اونم یک نمونه از این دسته است

[doomhammer65ir]

حالا من یک الگوریتم مینویسم ( یافتن بزرگترین عدد در یک آرایه ) شما نخست t(n) رو براش بساز سپس بگو میانگین مرتبه اش چیه :

کد: [انتخاب]

function find_max ( T , low , high)
{
  if (low==high)
   return T[low]

  else
   if (high == low+1)
       if (T[high] > T [low])
           return T[high]
       else
           return T[low]

   else
       {
       mid=floor((high+low)/2)
       LMAX=find_max(T,low,mid)
       RMAX=find_max(T,mid+1,high)
       return MAXIMUM(LMAX,RMAX)
       }
}


[adel1368]

حالا من یک الگوریتم مینویسم ( یافتن بزرگترین عدد در یک آرایه ) شما نخست t(n) رو براش بساز سپس بگو میانگین مرتبه اش چیه :

کد: [انتخاب]

function find_max ( T , low , high)
{
  if (low==high)
   return T[low]

  else
   if (high == low+1)
       if (T[high] > T [low])
           return T[high]
       else
           return T[low]

   else
       {
       mid=floor((high+low)/2)
       LMAX=find_max(T,low,mid)
       RMAX=find_max(T,mid+1,high)
       return MAXIMUM(LMAX,RMAX)
       }
}


میشه روش حلش رو همبگید