مرتب‌سازی توپولوژیکی، الگوریتم دکسترا و الگوریتم بلمن - فورد
توضیحات
در جلسه نوزدهم درس طراحی الگوریتم دکتر حمید حاج سیدجوادی که اهمیت به سزایی در کنکور ارشد کامپیوتر و کنکور ارشد آی تی و نیز کنکور دکتری کامپیوتر و کنکور دکتری آی تی دارد، مطالب مهمی در باره مرتب‌سازی توپولوژیکی، الگوریتم دکسترا و الگوریتم بلمن - فورد ارائه می‌شود. ابتدا مرتب‌سازی توپولوژیکی مطرح می‌شود و یک روش هوشمندانه برای چون گراف DAG(directed acyclic graph) ارائه می‌شود. سپس مرتب‌سازی توپولوژیکی با استفاده از DFS مطالعه شده و الگوریتم آن با یک مثال شرح داده می‌شود. آنگاه به مبحث مؤلفه‌های همبندی قوی پرداخته می‌شود. به عنوان یک کاربرد کلاسیک از جستجوی عمق-اول، تجزيه يک گراف جهت دار به اجزای مؤلفه‌های همبند قوی آن تدریس می‌شود. سپس مفهوم Relax كردن آموزش داده می‌شود. در ادامه دو الگوریتم مهم برای یافتن کوتاهترین مسیر در یک گراف وزن‌دار و جهت دار با جزئیات کامل و شبه کد های مربوطه آموزش داده می‌شود. اولین الگوریتم Shortest Path Algorithm طراحی شده توسط Dijkstra مورد بحث و بررسی دقیق قرار می‌گیرد. سپس قضیه درستی الگوریتم کوتاهترین مسیر دکسترا مطرح می‌شود. بعد از آن یک مثال در این مورد حل می‌شود. آنگاه چند نکته در این مورد مطرح شده و بعد از آن ویژگی های الگوریتم دکسترا مورد بحث قرار می‌گیرند. سپس Belman-ford Algorithm و مرتبه اجرایی آن با یک مثال آموزش داده شده و قضیه مربوط به آن مطرح می‌شود. در انتها 10 تست کنکور ارشد و دکترای طراحی الگوریتم در خصوص مطالب این جلسه مطرح و حل تشریحی آنها ارائه می‌گردد.