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