Э. А. Абдыкеримова
жүктеу/скачать 1,31 Mb. Pdf көрінісі
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
|
Дәріс №12. Алгоритмдердің тиімділігі мен кҥрделілігіне анализ жасау Алгоритмдер математикалық логика – алгоритмдер теориясына жалғасатын ғылыми пәндер математика мен информатика арасындағы шектеулерді жҥйелі зерделеу объектісі болып табылады. Жағдайдың ерекшелігі мынада, ЭЕМ-да іске асыру ҥшін алгоритмдер әзірлеуге ҧйғарылған практикалық міндеттерді шешу кезінде және сонымен қатар практикада ақпараттық технологияларды пайдалану кезінде, негізінен бҧл ҧғымның жоғары формальдылығына сҥйенбеген жӛн. Сондықтан алгоритм ҧғымының мәнін мазмҧнды тҥсіндіру және оның негізгі қасиеттерін қарастыру негізінде алгоритмдермен және алгоритмдеумен танысқан дҧрыс болады. Мҧндай тәсіл кезінде алгоритмдеу берілген тілдік қҧралдар шеңберінде белгілі бір практикалық тәсілдердің, ҧтымды ойлаудың ерекше ӛзіндік дағдыларының жиынтығы ретінде алға шығады. Ақпаратты ӛлшеуде мҧндай жағдай мен жоғарыда қарастырылған тәсілдің арасында ҧқсастықты жҥргізуге болады: ―кибернетикалық‖ тәсіл кезіндегі жіңішке математикалық қҧрулар компьютермен практикалық жҧмыс кезінде барынша қарапайым ―кӛлемді‖ тәсілді қолдану кезінде аса қажет емес. ―Алгоритм‖ сӛзінің ӛзі ІХ ғасырдың ҧлы математигі Әл-Хорезмидің атының латын тіліндегі algorіthmі жазылуынан шыққан, ол арифметикалық амалдарды орындау ережесін қалыптастырған. Бастапқыда алгоритм ретінде кӛп мәнді санды тӛрт арифметикалық амалды орындау ережесі арқылы тҥсінді. Мысалы, кӛпразрядты екі бҥтін санды қосу ҥшін мынадай ережені орындау керек: 1) екі кӛпразрядты бҥтін сандардың мәнін анықтау; 2) осы екі санды бірінің астына бірін разрядтарын сәйкестендіріп жазу; 90 3) егер осы сандардың біреуінің ҥлкен разрядтары жетіспесе, оны нӛлдермен толтыру; 4) ең кіші разрядқа қосу амалын орындау және келесі разрядты қарастыруға кӛшу; Бҧл жағдайда, келесі ҥлкен разрядқа ӛтетін бірлік пайда болса, онда оны еске сақтап қою керек; 5) барлық разрядтар біткенше оңнан жылжи қарастырып, есте сақталған бірлікті ескеріп және пайда болған жаңа ҥлкен разрядқа ӛтетін бірлікті қайтадан еске сақтай отырып әрбір разрядқа қосу амалын орындау; 6) нәтиже ретінде барлық разрядтарда қосу амалы орындалғаннан кейін, шыққан санды аламыз және есте сақталған бірлік болса, онда оны нәтиженің ең ҥлкен разрядының мәні ретінде есептейміз. Бҧл жазылған ережемен екі кӛпразрядты бҥтін санды қосу ҥшін орындаушының қазақ тілін білуі және бір разрядты сандарды қосатын қабілеті қажет. Енді ондық сан деген ҧғымды білетін, екі кӛп разрядты бҥтін санды кӛбейте алатын және қазақ тілін тҥсінетін қабілеті бар деп есептеп, кез келген екі ондық санды кӛбейтуге болатын ережені қҧрастырайық. 1. Екі ондық санның мәндерін анықтау; 2. Осы сандардың ондық белгісін кӛрсететін ҥтірді ескермей, оларды бірінің астына бірін бҥтін кӛбейткіштер ретінде жазу; 3. Кӛбейткіштерді кӛбейтіп, кӛбейтіндіні табу; 4. Берілген екі ондық сандардағы ҥтірдің оң жағындағы таңбалардың санын қосу; 5. Нәтиже ретінде ҥтірден кейінгі таңбалардың саны 4-қадамнан шыққан санға тең болатындай етіп жазылған 3-қадамнан шыққан кӛбейтіндіні аламыз. Осындай арифметикалық амалдарды орындау ережелерін алгоритм деп тҥсінсе, кейін келе ―алгоритм‖ деген сӛз тҥрлі математикалық есептерді шешу ережелерін белгілеуге қолданыла бастады. Мысалы, грек ғалымы Евклид қҧрастырған екі натурал санның ең ҥлкен ортақ бӛлгішін табатын тӛмендегі ережені Евклид алгоритмі деп атайды. 1) екі натурал санды алып, олардың мәндерін анықтау; 2) егер екі сан ӛзара тең болса, онда нәтиже ретінде осы сандардың кез келгенін алу керек немесе осы сандардың ҥлкенін анықтау қажет; 3) ҥлкен санды ҥлкен сан мен кіші санның айырмасына алмастыру керек; 4) 2-қадамнан бастап, қайталау. ―Алгоритм‖ ҧғымын нақтылаудың бірнеше тәсілдері белгілі: - ақырлы және ақырсыз автоматтар теориясы; - есептелетін (рекурсивті) функциялар теориясы; - Черчтің λ есептеуі. жүктеу/скачать 1,31 Mb. Достарыңызбен бөлісу:
|