سلام و عرض ادب خدمت دوستان و همراهان همیشگی وب سایت آموزش برنامه نویسی سورس باران. در این مطلب فیلم آموزش کلاس درس الگوریتم تقریبی – بخش دوم رو برای شما جهت دانلود قرار داده ایم. این دوره از کلاس درس دکتر حمید ضرابی زاده در دانشگاه صنعتی شریف ضبط شده است و توضیحات بیشتر آن در ادامه مطلب موجود می باشد. لطفا با ما همراه باشید…
فیلم آموزش کلاس درس الگوریتم تقریبی – بخش دوم
- آموزش درخت اشتاینر در الگوریتم تقریبی
- آموزش برش بیشینه (max cut) در الگورتیم تقریبی
- آموزش متصل کردن راس های مهم یک گراف با کمترین هزینه در الگوریتم تقریبی
- آموزش گراف های وزن دار متریک در الگوریتم تقریبی
- توضیح دو الگوریتم تقریبی برای مسئله ست کاور در الگوریتم تقریبی
- آموزش خوشه بندی در الگوریتم تقریبی
- آموزش قطر نقاط در فضای هندسی در الگوریتم تقریبی
نکته!!! لطفا توجه داشته باشید که این فیلم در خود کلاس ضبط شده است.
الگوریتم تقریبی
الگوریتم تقریبی چیست؟
الگوریتم تقریبی (Approximation Algorithms) در علوم رایانه و تحقیق عملیاتی، الگوریتمی برای پیداکردن راهحلهای تقریبی برای مسائل بهینهسازی است. این الگوریتمها اغلب برای حل تقریبی مسائل انپی سخت (به انگلیسی: NP-hard) بکار میروند زیرا بسیاری از مسائل بهینهسازی انپی سخت هستند (در واقع بررسی کردن درستی جواب اینگونه مسائل با حل کلی آنها معادل است) طبق نظریه پیچیدگی محاسباتی تا زمانیکه P ≠ NP، الگوریتمهای کارامد با زمان چندجملهای برای چنین مسائلی پیدا نخواهد شد مگر اینکه P = NP که چنین فرضی هم خیلی بعید است. برخلاف الگوریتم جستجوی کاشف که راهحلهایی بهینه، اغلب بدون اثبات و بدون کران برای جواب خود هستند؛ الگوریتمهای تقریبی راه حلهایی شبه بهینه همراه با ضریبی برای میزان تقریب جواب واقعی ارائه میدهند همچنین وجود جواب خود را در بازهٔ خطای اعلام شده تضمین میکنند. (مثلاً جواب آنها ۲ برابر جواب بهینه است) منتها جواب خود را در زمان چندجملهای تولید میکنند. الگوریتمهای تقریبی برای مسائل P نیز استفاده میشوند ولی به ازای ورودیهای بزرگ خوب عمل نمیکنند.
بسیاری از مسائل بهینهسازی در ریاضیات، علوم کامپیوتر، و مهندسی انپی-سخت هستند و بنابراین به دست آوردن جوابهای بهینه برای این مسائل در زمان چندجملهای غیرمحتمل است. الگوریتمهای تقریبی این امکان را فراهم میآورند که جوابهایی نزدیک به جواب بهینه با ضریب تقریب قابل اثبات برای این دسته از مسائل به دست آورد. هدف این درس، آشنایی با مفاهیم و تکنیکهای متداول در طراحی الگوریتمهای تقریبی حول محور مسائل بنیادی در بهینهسازی ترکیبیاتی، و نیز بررسی روشهای اثبات سختی تقریب برخی از این مسائل است. یکی از مثالهای معروف برای الگوریتمهای تقریبی، مسئله پوشش راسی (به انگلیسی: vertex cover) در گراف است: پیدا کردن یال پوشش داده نشده و اضافه کردن هر دو رأس آن به مجموعه پوشش رأسی تا زمانی که هیچ یال پوشش نیافته نماند.
واضح است که مجموعه جوابهای این الگوریتم دو برابر جوابهای بهینه یعنی مجموعه کمترین رأسها برای پوشش دادن همه یالها در یک گراف است؛ پس ضریب ثابت این الگوریتم ۲ است. الگوریتمهای تقریبی موجود برای مسائل ان پی-سخت با هم تفاوت بسیاری دارند؛ مثلاً مسئله بستهبندی (به انگلیسی: bin packing problem) را میتوان به ازای هر ضریب بزرگتر از یک تقریب زد، (اگر بتوانیم الگوریتمی تقریبی با ضریب یک برای چنین مسائلی ارائه دهیم P = NP میشود) به این خانواده از مسائل Polynomial time approximation scheme میگویند؛ درحالیکه ثابت شده است که برای برخی مسائل دیگر هیچ الگوریتم تقریبیای یافت نمیشود مگر آنکه P=NP شود مانند مسئله بزرگترین خوشه (به انگلیسی: maximum clique problem) (پیدا کردن بزرگترین زیرگراف کامل) مسائل ان پی-سخت را میتوان با برنامهریزی خطی (مسائل برنامهریزی خطیای که x i {\displaystyle x_{i}} x_iهای صحیح دارند) متناظر کرد و در نتیجه آنها را در زمانهای نمایی حل کرد. (مسائل IP در مرتبه زمانی نمایی حل میشوند)
شاید برایتان جذاب باشد: آموزش برنامه نویسی برای صفرکیلومترها
لیست جلسات قبل دوره الگوریتم تقریبی
معرفی مدرس حمید ضرابی زاده
تحصیلات :
راستی! برای دریافت مطالب جدید در کانال تلگرام یا پیج اینستاگرام سورس باران عضو شوید.
- جم فايل : 576 مگابایت
- منبع : سورس باران
- رمز فايل : www.sourcebaran.com
- انتشار: ۲۵ خرداد ۱۳۹۷
دسته بندی موضوعات
- آموزش برنامه نویسی
- آموزش کریپتو کارنسی (ارز دیجیتال)
- آموزش متنی برنامه نویسی
- پروژه برنامه نویسی
- فروشگاه
- فیلم های آموزشی
- #F
- ++C
- 3ds max
- Ada
- ADO.NET
- Adobe Flash
- Agile
- Ajax
- AngularJS
- Anime Studio
- apache
- ARM
- Asp.Net
- ASP.NET MVC
- assembly
- AVR
- Azure
- Bootstrap
- Cassandra
- CCNA
- CCNP
- CCSP
- ChatGPT
- Cisco
- CMD
- COBOL
- CSS
- Cython
- Django
- Dreameaver
- Elixir
- EntityFramework
- Erlang
- Flash
- Go
- Groovy
- Haskell
- Htaccess
- HTML
- IOS
- Jade
- jquery
- Kendo UI
- Linq
- Linux
- LUA
- MariaDB
- maya
- Meteor
- MongoDB
- Mono Android
- MonoGame
- Mysql
- NoSQL
- Oracle
- Orchard
- Perl
- php
- PHPMyAdmin
- R
- Rational Rose
- Ruby
- Rust
- Scala
- Scrum Master
- SFML
- SharePoint
- SignalR
- silver light
- SQL Server
- Stimulsoft Reports
- Telerik
- UML
- VB.NET&VB6
- Vue 3
- WPF
- Xml
- آردوینو
- آموزش های پروژه محور
- آیونیک
- اتوکد
- الگوریتم تقریبی
- الگوریتم نویسی و فلوچارت
- امنیت
- اندروید
- اندروید استودیو
- انیمیشن سازی
- بازی سازی با Scratch
- بک ترک
- بیسیک فور اندروید
- پایتون
- پرولوگ
- پریمیر
- جاوا
- جاوا اسکریپت
- جنگو
- جوملا
- دارت
- دلفی
- دوره های رایگان پیشنهادی
- زامارین
- سئو
- ساخت CMS
- ساخت اتوران
- ساختمان داده ها
- سی شارپ
- شبکه و مجازی سازی
- طراحی الگوریتم
- طراحی بازی
- طراحی وب
- فتوشاپ
- فریم ورک codeigniter
- فلاتر
- کاتلین
- کامپایلرها
- کانستراکت
- کریستال ریپورت
- کلوژر
- گوگل آنالیتیکس
- گیت
- لاراول
- مای بی بی
- مایکروسافت پروجکت
- متریال دیزاین
- متلب
- معماری کامپیوتر
- مهندسی اینترنت
- میکروتیک
- نود جی اس
- نیوک
- هوش مصنوعی
- ویبولوتین
- ویژوال استودیو
- یونیتی
- کتاب های آموزشی
- Ada
- Ajax
- Android
- ASP.NET
- ASP.NET Core
- AVR
- clips
- CNC
- COBOL
- CQRS
- Cython
- Dreamweaver
- Elixir
- Entity Framework 4.0
- Erlang
- Go
- Groovy
- Haskell
- LINQ
- Lua
- Matlab
- MFC
- Node.js
- PERL
- php
- PLC
- Prolog
- React
- Rust
- Scala
- SFML
- SharePoint
- silver light
- VHDL
- VMware
- WinJS
- Workflow
- WPF
- XHTML
- Yii Framework
- اتوکد
- اچ تی ام ال
- اسمبلی
- اکتیو ایکس
- الگوریتم و فلوچارت
- انگولار
- اوبونتو
- اوراکل
- بازی سازی
- بانک اطلاعاتی
- برنامه نویسی سوکت
- برنامه نویسی موبایل
- بک ترک
- پاسکال
- پایان نامه
- پایتون
- پرولوگ
- جاوا
- جاوا اسکریپت
- جی کوئری
- حوملا
- داده کاوی
- دلفی
- رباتیک
- روبی
- زبان ماشین
- سئو
- ساختمان داده ها
- سایر کتاب ها
- سخت افزار
- سوئیفت
- سی اس اس
- سی پلاس پلاس
- سی شارپ
- سیستم عامل
- سیستم های خبره
- شبکه و مجازی سازی
- شبیه سازی کامپیوتر
- طراحی الگوریتم
- فتوشاپ
- فریم ورک گتنا
- کاتلین
- کالی لینوکس
- کریستال ریپورت
- گزارش کارآموزی
- گوگل
- لیسپ
- متلب
- مقاله
- مهندسی نرم افزار
- نیوک
- هوش مصنوعی
- وب مستر
- ویژوال بیسیک
- نرم افزار و ابزار برنامه نویسی
- وردپرس