دانلود کتاب محاسبات عددی

دانلود کتاب محاسبات عددی بصورت 4 فصل

قسمت 1 (2,689 KB)

قسمت 2 (3,126 KB)

قسمت 3 (3,146 KB)

قسمت 4 (3,956 KB)

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

یعنی فاقد سایر قسمت های جزوه می باشد

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

قسمت اول :

قسمت دوم : 

قسمت سوم : 

قسمت جزوه های بخش آمار :

قسمت اول

قسمت دوم

قسمت سوم

قسمت چهارم

قسمت پنجم

قسمت ششم

قسمت هفتم

قسمت هشتم

قسمت نهم

قسمت دهم

قسمت یازدهم

قسمت دوازدهم

قسمت سیزدهم

شما از کامپایلرها ( Compilers )چه می دانید؟

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

 اگر بپذیرید که کامپیوتر تنها قادر به درک مفهوم سیگنال های پذیرش و عدم پذیرش و یا همان سیگنال ها و اعداد صفر و یک است می توانید راحت تر به جواب برسید درواقع سیستم کامپیوتر شامل مدارهایی است که این مدارها فقط به دو سیگنال صفر و یک و یا فعال و غیر فعال و یا روشن و خاموش حساس است  و به هیچ وجه قادر به درک الفاظ و زبان طبیعی نمی باشد و حتی از کاری که قرار است انجام بدهد نیز خبر ندارد و مدارهای الکتریکی بر اساس کدهایی که در حافظه قرار می گیرد ( کلمات حافظه ) و در نهایت پردازش هایی که توسط پردازنده در واحد کنترل و ALU بر روی آن ها صورت می دهد اعمالی انجام می شود . اما ان چه که در این جا مورد توجه است همان شکل گیری صفر و یک ها در نتیجه یک برنامه به زبان فرضا C# می باشد . این کاری است که کامپایلرها انجام می دهند .

مکانیسم کلی کار کامپایلرها به این صورت است که برنامه مبدا را خوانده و یک شکل میانی از آن ایجاد نموده و سرانجام آن را به زبان دیگری مانند اسمبلی تبدیل می کند و زبان اسمبلی نیز از شکل میانی برنامه شکل قابل فهم سیستم و یا همان صفر و یک ها را ایجاد و آن ها را در قالب Memory Word برای سیستم و سخت افزار مهیا می نماید . لذا تبدیل شکل ابتدایی برنامه مقصد به یک شکل اجرایی سیستمی از وظایف کامپایلر ها می باشد . البته باید توجه کنیم که کامپایلرها بر اساس قواعد و گرامر زبان مبدا اقدام به تولید زبان مقصد می نمایند .

کامپایلر نویسان برای سهولت در طراحی ، اجزای کامپایلر را به بخش های زیر تقسیم بندی می کنند که هر یک عملی را انجام می دهد :

الف) تحلیل گر لغوی ( Lexer ) :

در واقع طولانی ترین پروسه را انجام می دهد ، با زبان مبدا مستثقیما در تعامل بوده و مستقل از زبان مقصد می باشد . تحلیل گر لغوی با خواندن زبان ورودی ان را به مجموعه ای از نشانه های قابل فهم برای تجزیه کننده تقسیم بندی می کند . میدانیم که جملات یک زبان از رشته هایی از نشانه ها تشکیل شده است و دنباله ای از این کاراکترهای ورودی که یک نشانه را تشکیل می دهند یک لغت ( Lexeme ) نامیده می شوند .

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

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

ب)تحلیل گر ساختار دستور (Parser) :

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

ج ) تحلیل گر معنایی (Syntax Analyzer ) :

فاز تحلیل معنایی برنامه مبدا را برای پیدا کردن خطاهای معنایی بررسی کرده و اطلاعات مربوط به نوع داده ها را در درخت تجزیه حاشیه نویسی می کند مثلا بررسی می کند که یک رشته حرفی با یک عدد جمع نزده شده باشد و مانند آن . مجاز بودن نوع داده ها نیز در این بخش بررسی می شود. در واقع در زمان تحلیل معنایی ، کامپایلر ساختارهایی را کشف می کند که از نظر ساختار دستوری صحیح هستند اما در رابطه با عملی که انجام می دهند بی معنی هستند .

د) تولید کننده کد میانی : 

در این بخش یک شکل میانی قابل فهم اسمبلر و یا یک نمایش میانی صریح از برنامه مبدا تولید می کند که می توان آن را برنامه ای برای یک ماشین انتزاعی در نظر گرفت ( مفهوم انتزاعی به معنای قابل فهم بودن برای انسان است نه ماشین . ) و باید دارای دو ویژگی سهولت تولید و سهولت تبدیل به برنامه مقصد باشد .

نمایش میانی می تواند شکل های گوناگونی داشته باشد مانند صفر ، یک ، دو ، سه و چهار آدرسه .در ساختار فرضا سه ادرسه در هر ثبات می توان سه ادرس را شامل عملگر  ، عملوند اول و عملوند دوم قرار داد . محاسبه عبارات ، نظارت بر ساختارهای جریان کنترلی و احضار رویه ها نیز در این بخش توسط مولد کد میانی صورت می گیرد .

ه) بهینه ساز کد(Optimizer) :

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

و) تولید کد :

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

یک نمونه : عبارت  Statement :=initial + rate * 60 را در نظر بگیرید . داریم :

Statement: =initial + rate * 60àid₁:=id₂ + id₃ *60

حال کد نهایی را می توان به فرم زیر در نظر گرفت که سرانجام در اسمبلر تبدیل به کد قابل فهم ماشین خواهد شد :

MOVE    id₃, R2                                                                                                  

Mul          #60.0, R2

MOVE     id₂, R1

MOVE   R2, R1

الگوریتم هایی برای تبدیل عبارت های میانوندی ، پسوندی و پیشوندی به یکدیگر

1- تبدیل عبارت میانوندی به پسوندی

الگوریتمی را که در زیر می بینید برای تبدیل یک عبارت میانوندی به یک عبارت پسوندی به کمک پشته و به زبان  C++نوشته شده است . این برنامه به این صورت عمل می کند که ابتدا عبارت را پرانتز گذاری می کند و سپس از سمت چپ به راست شروع به پردازش رشته می کند و اپرندها(عملوند) را به خروجی می فرستد اما اپراتورها(عملگر) و پرانتز باز را وارد پشته می کند . اما اگر اپراتوری را وارد پشته نمود اما اپراتوری با اولویت بالاتر یا هم اولویت با آن در پشته قرار داشت ، ابتدا آن اپراتور را از پشته خارج می کند . اگر به پرانتز بسته رسیدیم تمام اپراتورهای تا اولین پرانتز باز را از پشته خارج می کند .

در الگوریتم زیر isp اولویت در پشته و icp اولویت ورودی را نشان می دهند . # نیز نماینده سمت چپ ترین نشانه می باشد . e معرف رشته ای است که آن را پردازش می کنیم و x وy هم نشانه ها و یا لیترال ها می باشند.

Void postfix (exp e)

{

Stackstack;

Token y;

Stack.Add ("#");

For (token x=NextToken (e); x! ="#"; x=NextToken (e))

{

If(x is an operand)

Cout<

Else if (x= = ")")

For (y=*stack.Delete(y); y! ="("; y=*stack.Delete(y))     

Cout << y;     

//x is an operator

Else

{

For(y=*stack.Delete(y); ISP(y) <=icp(x); y=*stack.Delete(y))

Cout<

Stack.Add(y);

Stack.Add(x);

}

}

While (! stack.isEmpty ())

Cout<<*stack.Delete(y);

}

سایر الگوریتم ها نیز به همین ترتیب به دست می آیند .  

تبدیلات زیر را در نظر بگیرید :

Infix :(     (     (     (   A   *    B    )    /     C     )    -    D    )   +     E      )

Post:  (     (     (     (   A   B    *    )   C     /      )   D    -     )   E     +      )

Pre :  (     +    (      -   (    /      (    *   A    B     )   C    )     D   )     E      )

2- تبدیل عبارت پسوندی به پیشوندی:

الف) روش مستقیم :عبارت پسوندی را از چپ به راست به صورت (عملگر  -   عملوند   -   عملوند) پرانتز گذاری کرده و سپس عملگر را به قبل از پرانتز باز آن عبارت منتقل می کنیم .

ب) ابتدا آن را به فرم میانوندی تبدیل نموده و سپس از میانوندی به پیشوندی می بریم . برای نوشتن الگوریتم ، این روش ساده تر است .

3- تبدیل عبارت پیشوندی به پسوندی:

الف ) روش مستقیم : عبارت پسوندی را از راست به چپ به صورت (عملوند -  عملوند  -   عملگر  ) پرانتز گذاری کرده و سپس عملگر را به بعد از پرانتز بسته آن عبارت منتقل می کنیم .

ب) ابتدا آن را به فرم میانوندی برده و سپس از میانوندی به پسوندی تبدیل می کنیم . برای نوشتن الگوریتم ، این روش ساده تر است .

4- تبدیل عبارت پسوندی به میانوندی

از یک پشته استفاده می کنیم . از چپ به راست عبارت را ارزیابی نموده و عملگرها را در پشته قرار می دهیم و اگر به عملوندی رسیدیم آن را بر دو عبارت بالای پشته اعمال کرده و نتیجه را در پشته قرار می دهیم . ( دقت کنید که پایینی بر بالایی اعمال می شود . )

5- تبدیل عبارت پیشوندی به میانوندی

از یک پشته استفاده می کنیم . از راست به چپ عبارت را ارزیابی نموده و عملگرها را در پشته قرار می دهیم و اگر به عملوندی رسیدیم آن را بر دو عبارت بالای پشته اعمال کرده و نتیجه را در پشته قرار می دهیم . ( دقت کنید که عملوند بالایی بر عملوند پایینی اعمال می شود . )

6- تبدیل عبارت میانوندی به پیشوندی

عبارت را کاملا پرانتز گذاری کرده و سپس از چپ به راست هر عملگر را به فبل از پرانتز بسته شامل دو عملوندش منتقل می کنیم .

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

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

روش های گوناگون طراحی یک الگوریتم

الگوریتم ها بر دو مبنای صرفه جویی در زمان و صرفه جویی در هزینه استفاده از حافظه استوارند که اولی تحت عنوان پیچیدگی زمانی و دومی تحت عنوان پیچیدگی حافظه از آن یاد می شود که به ترتیب

هر دو مستقل از سخت افزار و نوع زبان برنامه نویسی است و بر این اصل استوار است که دستور کلیدی الگوریتم ( دستوری که در تمام تکرار های الگوریتم وجود دارد ) به ازای مقادیر گوناگون پارامتر ورودی در بدترین حالت ، بهترین حالت و حالت میانگین حداقل و یا حداکثر و یا به طور متوسط چندبار اجرا می شوند و یا چه میزان حافظه را به خود تخصیص می دهند .

پنج نماد O (ا ُی بزرگ) ،  o(ا ُی کوچک ) ، Ω ( امگا ) ، w (دبلیوی کوچک ) و Ө ( تتا) به ترتیب حد بالای پیچیدگی به ازای حداقل یک مقدار ، حدبالای پیچیدگی به ازای تمام مقادیر ممکن ، حد پایین پیچیدگی به ازای حداقل یک مقدار ، حد پایین پیچیدگی به ازای تمام مقادیر ممکن ، و حد متعارف ( حدی که هم در بالاترین و هم پایین ترین حدود بگنجد و در واقع اشتراک آن ها باشد ) را نشان می دهند و شامل تمام توابعی هستند که در آن حدود قرار می گیرند و برای تعریف آن می توان از این روابط کمک گرفت :

الف ) وجود داشته باشد n و حداقل 0<c به طوری که برای تمامn>=N که در آن N>=0 داشته باشیم g(n)<=c*f(n) که در این صورت می گوییم : (f(n))  g(n)=O

ب ) وجود داشته باشد n و حداقل یک 0<c به طوری که برای تمامn>=N که در آن N>=0 داشته باشیم g(n)>=c*f(n) که در این صورت می گوییم : (f(n))Ω g(n)= .

ج ) وجود داشته باشد n و حداقل یک  0<d,c به طوری که برای تمامn>=N که در آن N>=0 داشته باشیم c*f(n)<=g(n)<=d*f(n) که در این صورت می گوییم : (f(n))Ω g(n)= .

د ) وجود داشته باشد n و 0<c به طوری که برای تمامn>=N و تمام مقادیر cکه در آن N>=0 داشته باشیم g(n)<=c*f(n) که در این صورت می گوییم : (f(n))  g(n)=o

ه ) وجود داشته باشد n و 0<c به طوری که برای تمامn>=N و تمام مقادیر cکه در آن N>=0 داشته باشیم g(n)>=c*f(n) که در این صورت می گوییم : (f(n)) g(n)=w

نکته : برای محاسبه پیچیدگی روابط می توانید از قضایای زیادی استفاده نمایید که مهم ترین آن ها قضیه Master می باشد که بسیار کاراست و در کتاب CLRS به وضوح توضیح داده شده است .

بنابراین روش های گوناگونی طراحی شده است تا به کمک آن ها الگوریتم هایی نوشته و براساس آن ها برنامه نویسی هایی انجام گیرد تا بهترین کارایی از لحاظ پیچیدگی زمانی و مکانی حاصل شود که روش های زیر از جمله مهم ترین آن ها بوده و در کتب طراحی الگوریتم مورد بحث قرار گرفته است :

الف)روش تقسیم و غلبه

ب ) برنامه نویسی پویا

ج) روش حریصانه

د) روش عقبگرد

ه) روش شاخه و حد

روش تقسیم و غلبه

این روش از این منطق کمک می گیرد که می توان مسئله را به زیر مسائلی تقسیم نمود به طوری که حل زیر مسائل مستقل از مسئله اصلی است  . مثلا فرض کنیم آرایه ای از اعداد مرتب را داریم که قصد داریم تا به کمک آن ها کلیدی را در آن جستجو کنیم . در هر مرحله آرایه را به دو زیر آرایه راست و چپ تقسیم می کنیم به طوری که زیر آرایه چپ دارای عناصر کوچکتر از زیر آرایه راست می باشند زیرا آرایه به صورت صعودی مرتب شده است . حال کلید را با عنصر میانی مقایسه می کنیم و اگر برابر نبود بررسی می کنیم که اگر بزرگتر از عنصر میانه بود در زیر آرایه راست و اگر کوچکتر از عنصر میانه بود در زیر آرایه چپ به دنبال آن می گردیم . حال فرض می کنیم آرایه ما آرایه سمت چپ و یا سمت راست است و بنابراین دوباره آن را به دو زیر آرایه تقسیم کرده و ادامه می دهیم . از آنجا که در هر مرحله آرایه نصف می شود لذا مرتبه آن O(log N)+1 می باشد که N اندازه ورودی است .

نمونه دیگر نیز الگوریتم مرتب سازی آرایه به روش ادغام است که از مرتبه O(N log N ) می باشد . الگوریتم مرتب سازی سریع نیز در بدترین حالت که آرایه به صورت نزولی مرتب شده باشد O(N^2) بوده و در حالت میانگین O(N log N ) می باشد .

نکته : این الگوریتم ها در کتب طراحی الگوریتم از جمله دو کتاب ریچارد نیپولیتان و CLRS بیان شده است  .

برنامه نویسی پویا

مسئله را به زیر مسائلی تقسیم می کنیم به طوریکه میان مسئله nام و مسئله n-1)) ام رابطه ای وجود داشته باشد و سپس گام به گام از جمله اول شروع کرده و به سمت جلو حرکت می کنیم . مکانیسم آن نیز به این طریق است که فرضا اگر بخواهیم کوتاهترین مسیر میان I و j را پیدا کنیم آن را به دو زیر مسیر I تا k و k تا j تقسیم کرده و بررسی می کنیم که کوتاهترین مسیر در این سه گروه کدام  است (i…………k…………j )

به عنوان مثال برای این که تعداد ضرب های لازم برای ضرب ماتریس های A(i) تا A(j) را پیدا کنیم ، این رابطه میان زیر مسائل برقرار است :

M[i][j]=mim(M[i][k]+M[k+1][j]+d(i-1)*d(k)*d(j)                         I  

M[i][j]=0                                                                          i>=j  

که در آن d(i-1) و d(k) و d(j) تعداد سطر های ماتریس ها می باشند .

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

روش حریصانه

الگوریتمی است بر پایه انتخاب بهترین گزینه به طوری که هر انتخاب در هر مرحله شرطی را برآورده کند و مجموع انتخاب ها تا آن زمان از حدی تعیین شده فراتر نرود . الگوریتم های راشال ، پریم ، سولین و کوله پشتی صفر و یک از بهترین مواردی هستند که به کمک این روش قابل اجرا می باشند . در این جا الگوریتم پریم را توضیح می دهم .

الگوریتم پریم برای ساخت درخت پوشای کمینه از یک گراف به کار می رود . درخت پوشای کمینه ، زیر گرافی از یک گراف موزون  است که شامل تمام رئوس گراف و برخی یال های آن می باشد به طوری که مجموع اوزان آن درخت نسبت به سایر درخت های ممکن حداقل شود .( می دانیم که معادل عدد کاتالان می توان می توان با N راس درخت ایجاد کرد . )

الگوریتم پریم در هر مرحله : یالی با کمترین وزن را انتخاب می کند به طوری که الف ) کم ترین وزن را میان سایر یال ها داشته باشد ب) قبلا انتخاب نشده باشد  ج ) با یال های انتخابی قبلی تشکیل دور ندهد ( زیرا در این صورت درخت نیست . ) . این الگوریتم در هر مرحله یک درخت ایجاد می کند .

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

روش عقبگرد

این روش از درخت فضای حالت استفاده می کند به این صورت که هر کدام از گره های آن یک حالت ممکن را نشان می دهند و بنابراین هر مسیر از گره ریشه به برگ ، یک حل کاندید به شمار خواهد رفت . یکی از کاربردهای آن در مسئله n وزیر است یعنی چگونه n وزیر را روی یک صفحه شطرنجی n*n قرار بدهیم به طوری که همدیگر را گارد ندهند . در این صورت گره j ام سطح  iام درخت یعنی معرف وزیر ردیف iام و ستون jام صفحه شطرنج خواهد بود . حال از گره ریشه شروع کرده و با یک پیمایش پیشوندی اگر به گرهی غیر امیدبخش یعنی گرهی که باعث شود دو وزیر یکدیگر را گارد بدهند ، به عقب بر می گردیم و الا به سمت برگ ها حرکت می کنیم .

دو وزیر در ردیف I وk و ستون j زمانی یکدیگر را گارد می دهند که یا روی یک ردیف و یک ستون باشند و یا هم قطر باشند یعنی COL(i)-COL(j)=|i-k| برقرار باشد .

روش شاخه و حد

این روش ، شکل اصلاح شده روش عقبگرد می باشد زیرا در روش عقبگرد مجبور به پیمایش تمام گره ها هستیم که بسیاری از آن ها بی مورد است (در روش عقبگرد کل گره هایی که پیمایش می شوند برابرند با : ( [n^(n+1)-1]/[(n-1)] لذا در روش الگوریتم های شاخه و حد ، الگوریتمی پیمایش می شود که شرطی را برآورده سازد ، یعنی ابتدا محاسبه می کنیم که آیا گرهی امیدبخش است و در صورت امید بخش بودن ، آن را پیمایش می کنیم .

Password : www.electrobot.org