«Информатиканың теориялық негіздері»

Тақырып 6. Алгоритмдердің асимтотикалық күрделілігі

жүктеу/скачать 0,6 Mb. бет 78/80 Дата 07.01.2022 өлшемі 0,6 Mb. #20727

Бұл бет үшін навигация:

• Тақырып 7. Рекурсия және итерация
• Тапсырмалар

Тақырып 6. Алгоритмдердің асимтотикалық күрделілігі. Жұмыстың мақсаты: есептің күрделілігі ұғымын қарастыру, қиын есеп ұғымын меңгеру. Рефератқа арналған тақырыптар: Есепттің күрделілігінің негізгі ұғымдары Асатолтыру есебі ұғымы. Тану есебі ұғымы. Полиномиалды үйлестіру ұғымы. NP есептер күрделілігінің класы. ОРЫНДАЛУШЫЛЫҚ есебінің NP күрделілігі класына жатуы туралы теорема. P және NP класстары арасындағы байланыс. P, NP, NPI, NPC күрделілік класы. Тақырып 7. Рекурсия және итерация Жұмыстың мақсаты: рекурсия және итерация ұғымдарын қарастыру. Рекурсивті алгоритмдер мен есептеу итерациясын құрастыру машықтарын және олардың тиімділігін бағалауды меңгеру. Есептелінетін функция ұғымы. Бөлікті функциялардың суперпозициясы. Примитивті рекурсиялы функциялар. Негізгі қасиеттері. Ауыстыру амалының негізгі қасиеттері. Примитивті рекурсияның негізгі қасиеттері. Шекті қосу және көбейту амалдары Рекурсия және итерация Рекурсия және итерация арасындағы байланыс. Рекурсия механизмін жүзеге асыру. Тақырып 8. Желілерде және графтардағы оптимизация алгоритмдері Жұмыстың мақсаты: Коммивояжер есебі туралы ұғым, Коммивояжер есебінің эвристикалық алгоритмі. Тапсырмалар: 6 қалалар арасындағы қашықтық матрицасы берілген. Барлық қалаларды аралап шығудың ең қысқа жолын эвристикалық алгоритмді пайдаланып тап. жүктеу/скачать 0,6 Mb. Достарыңызбен бөлісу: