Реферат пән бойынша Информатиканың теориялық негіздері
жүктеу/скачать 26,22 Kb.
|
|
ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ «Семей қаласының Шәкәрім атындағы университеті» КЕАҚ Физика-математика ғылымдары және информатика кафедрасы РЕФЕРАТ Пән бойынша Информатиканың теориялық негіздері (пәннің атауы) БББ ЖАРАТЫЛЫСТАНУ–МАТЕМАТИКА ФАКУЛЬТЕТІ 6В01503 (БББ коды және атауы) Орындалды:Серікқалиев Н.Е. (Т. А. Ә.) Курс, топ студенті: ДМИ-301в Оқытушы: Умирбаева С.Т. (Т. А. Ә.) Семей, 2023 Марковтың нормальды алгоритмдері. Бірінен-бірі тәуелсіз тарихи пайда болған бұл тәсілдер, соңыра өзара эквивалентті болып шықты. Алгоритм ұғымын тұрпаттандырудың негізгі мақсаты мынада: әртүрлі математикалық есептердің алгоритмдік шешімділігі мәселесін шешуге жол ашу, яғни есеп шешіміне әкелетін алгоритм құруға бола ма?- деген сұраққа жауап беру. Біз осы мәселенің қойылуын және есептердің алгоритмдік шешімділігі теориясының кейбір нәтижелерін қарастырамыз, бірақ алдымен Пост, Тьюринг машиналары және Марковтың нормалы алгоритмдері мысалында автоматтар теориясындағы алгоритм ұғымын тұлғатандыруды, сонан соң рекурсивті функциялар теориясы негіздерін талқылаймыз. Өздеріне арналған программалардың қасиеттері туралы әртүрлі тұжырымдауды дәлелдеуге арналған абстракты ( яғни шын емес, тек қиялда ғана бар) Пост пен Тьюринг машиналарын американдық математик Эмил Пост пен ағылшын математигі Аллан Тьюринг бірінен-бірі тәуелсіз (және іс жүзінде бір уақытта) 1936 ж. ұсынды. Бұл машиналар бастапқы мәліметтерді “енгізіп”, программалар орындалғаннан соң нәтижені оқуға мүмкіндік беретін, толығымен анықталған әмбебап орындаушылар болып табылады. Пост машинасы аса танымал емес, бірақ Тьюринг машинасына қарағанда әлдеқайда қарапайым. Жергілікті компьютерлік желілер мына компоненттерден құралады: - компьютерлер (жұмыс стансалары немесе серверлер); - кабельдік жүйе; - желілік адаптерлер; - қосымша желілік қондырғылар. Қазіргі кезде компьютерлік желілерге қосу үшін кабельдерді қолданады. Желінің жұмысын қанағаттандыруына байланысты кабельдер үш түрге бөлінеді. Оларды компьютерлер арасында сигнал түрінде жібереді. Көптеген желілерде кабельдің үш түрі пайдаланылады: - коаксиалды (coaxsial cable); - есулі қос өткізгіш (twisted pair): экрандалмаған (unshielded) және экрандалған (shielded); 75 - оптикалы талшықты. Коаксиалды кабел кеңінен қолданылады. Бұл екі себеппен түсіндіріледі. Біріншіден, ол жеңіл және пайдалануға ыңғайлы, екіншіден, орнату өте қауіпсіз және қарапайым. Ең қарапайым коаксиалды кабель мыс сымнан (соrе), қабықшадан, оны қоршайтын сыртқы темір тоқыма экраннан және қабықшадан құрастырылады. Егер кабельде темір тоқымаман (тормен) қатар фольга қабаты болса, онда кабель қос экранды деп аталады. Күшті бөгеттер орын алатын жағдайда қос торды және екі қабат фольгалы кабельді пайдаланады. Есулі өткізгішке қарағанда коаксиалды кабель электрмагниттік бөгеттерге төзімді, сигналдардың өшуі де аздау болады. Сигналдың өшуі (attenuation) дегеніміз – сигналдың кішіреюі. Коаксиалды кабелдің екі түрі бар: - жіңішке; - жуан. Жіңішке (thin) – диаметрі 0,5 см болатын иілгіш кабель. Ол қолдануда қарапайым және желінің кез келген түріне сәйкес келеді, компьютердің желілік тақшасына тікелей қосылады. Жіңішке коаксиалды кабел 185 м-ге дейін қашықтықта сигнал бере алады. Жіңішке кабель ұшында орналасқан Тконнекторы арқылы BNC-коннекторына қосылады да, желілік тақшағаадаптерге жалғанады. Жіңішке кабельде сигнал өткізу жылдамдығы 10 Мбит/с артық болмайды. Жуан (thick) – диаметрі 1 см болатын қатты кабель. Ethernet – әйгілі желілік архитектурада пайдаланылған кабельдің бірінші түрі болғандықтан, оны кейде «стандартты Ethernet» деп атайды. Кабельдердің ток өткізгіш бөлігі не бірнеше мыс сымдардан, не бір мыс сымнан тұрады. Кабельдің ток өткізгіш бөлігі неғұрлым жуан болса, соғұрлым сигнал үлкен қашықтықты қамтиды. Жуан кабель 500 м-ге дейін сигналдарды жеткізеді. Сондықтан жуан коаксиалды және жіңішке коаксиалды кабельден құрылған кішкене желілерді біріктіретін негізгі кабель магистраль (backbone) ретінде пайдаланылады. Жуан коаксиалды кабельге қосу үшін арнайы құрылғы – трансивер (transceiver) пайдаланылады... Сымсыз желіні мына жағдайларда қолдану тиімді: - адамдарға толы мекемелерде; - бір орындарда жұмыс істемейтін адамдарға; - оңашаланған мекемелерде; - жоспарлау үнемі ауысып отыратын мекемелерде; - құрылыста, қазба жұмысы жүріп жатқан жерлерде және т.с.с. Сымсыз желі кабельді желі сияқты қызмет атқарады. Сымсыз адаптер тақшасы трансивермен әрбір компьютерге орнатылады, пайдаланушы компьютер кабельмен жалғанғандай жұмыс істей береді. 76 Кабельді пайдаланбай-ақ сымсыз көпір деп аталатын компонент көмегімен ЖЕЖ-ді көбейтуге болады. Ол 40 км қашықтықтағы мекемелер арасында байланысты қамтамасыздандырады. Кабельді желі мен спутниктік станса сигналдарды дестелі радионы біріктіру көмегімен береді және қабылдайды. Технологияға байланысты сымсыз желіні үш түрге бөлуге болады: - жергілікті есептеуіш желі; - кеңейтілген жергілікті есептеуіш желі; - ұтқыр (мобильді) желі (тасымалданатын компьютер). Бұл желі түрлерінің арасындағы негізгі ерекшелік беру параметрі. Жергілікті және кеңейтілген жергілікті есептеуіш желілер желі қызмет ететін ұйымдарға жататын қабылдағыш пен хабарлағыштарды қолданады. Есептеуіш желі. Типті сымсыз желінің жай желіден айырмашылығы тек беру ортасы ғана болады. Сымсыз трансиверлі желілік адаптер әрбір компьютерге орнатылғандықтан, пайдаланушылар компьютерлер кабельмен жалғанғандай жұмыс істейді. Трансивер қалған желімен сымсыз қосылған компьютерлер арасында сигналдар ауысуын қамтамасыз етеді, кейде қатынау нүктесі (access point) деп аталады. Сымсыз ЖЕЖ-де үлкен емес қабырғалы трансивер пайдаланылады. Олар тасымалданатын құрылғылар арасында радиоконтакт орнатады. Осы трансиверлерді қолданғандықтан, мұндай желіні толық сымсыз желі деп атауға болмайды. Сымсыз жергілікті желі мәліметтерді берудің төрт әдісін пайдаланады: - инфрақызыл сәуле; - лазер; - тар спектрдегі радиохабар (бір жиілікті беру); - бытыраңқы спектрдегі радиохабар. Барлық инфрақызылды сымсыз желілер мәліметтер беруде инфрақызыл сәулені пайдаланады. Осындай жүйеде өте күшті сигнал беру қажет, әйтпесе оған басқа да көздер әсер етеді, мысалы, терезе. Инфрақызыл түс жиілігі кең ауқымды болғандықтан, осы тәсіл сигналдарды жоғары жылдамдықпен беруге мүмкіндік береді. Инфрақызылды желі төрт түрге бөлінеді: 1) Тікелей көрінетін желі. Аты айтып тұрғандай, хабарлағыш пен қабылдағыш арасында тікелей көрінетін жағдайда ғана беру мүмкін болады. 2) Бытыраңқы радиоқызыл сәуле. Мұндай технологияда сигналдар төбе мен қабырғаларға шағылысып, аяғында қабылдағышқа жетеді. Тиімді аймақ 30 м (100 фут) шектеледі және беру жылдамдығы үлкен емес (барлық сигналдар шағылысады). 3) Шағылысқан инфрақызыл сәуле. Бұл желіде компьютер жанына орналасқан оптикалық трансиверлер сигналдарды белгілі бір орынға береді, одан олар сәйкес компьютерге қайта жолданады. 77 4) Кеңжолақты оптикалық желі. Бұл инфрақызылды сымсыз желі кеңжолақты қызмет атқарады. Олар мультимедия ортасының қатаң талаптарына сәйкес келеді және кабельді желі сияқты болады. Инфрақызыл желілерді пайдаланған өте қолайлы және жылдам болғанымен, сигналдарды 30 м-ден артық қашықтыққа беру кезінде қиындықтар туындайды. Осындай желі көптеген ұйымдарда болатын күшті көздерден шығатын бөгеттерге жиі соқтығысады. Алгоритмдерді сипаттау әдістері Құрастырылған алгоритмді жүзеге асыру үшін немесе берілген есептің шешімін табу үшін алгоритмді орындаушы туралы түсінік пайда болады. Себебі алгоритм құрастырылғанда оны орындаушы немесе жүзеге асырушы белгілі болуы тиіс. Алгоритмді орындаушы ретінде адам мен адамдар ұжымы, компьютер мен есептеу жүйелері, станок пен әртүрлі «ақылды машиналар», манипуляторлар мен роботтар, өндіріс технологиясы және т.б. объектілер қарастырылады. Орындаушының ерекшелігіне байланысты есептің алгоритмін құрастыру да әртүрлі тәсілмен орындалады. Олардың ең көп тарағандары: сөзбен сипаттау (вербальді), графикалық бейнелеу (граф-схема, блок-схема түрінде), алгоритмдік тілде формулалар тізбегі түрінде жазу, компьютердің командалар жиыны ретінде және т.б. Мысалы, алгоритмді орындаушы ретінде компьютер қарастырылатын болса, онда оған түсінікті тілде жазылған бағдарлама құрастырылуы тиіс немесе алгоритм компьютерге берілген командалар тізбегі түрінде бейнеленуі керек. Сонымен, алгоритм белгілі бір тілде жазылуы және ол орындаушыға түсінікті болуы тиіс. Бұл жерде тіл туралы түсінік енгізіледі. Тіл туралы түсінікті келесі түрде беруге болады: Тіл – адам өмірінде танымдық және коммуникативтік (қарымқатынас) функцияларын орындайтын, табиғаты кез келген белгілеулердің (таңбалар мен ережелердің) жүйесі. Тіл табиғи және жасанды болуы мүмкін. Табиғи тіл – адамдардың ойларын жеткізу және олардың бір-бірімен қарым-қатынас жасау формасы болса, ал жасанды тіл – белгілі бір жеке мақсатты жүзеге асыру үшін табиғи тіл негізінде құрастырылған белгілеулердің жүйесі. Мысалы, алгоритмдерді ЭЕМ-ге түсінікті тілде құрастыру мақсатында жасанды тілдер – алгоритмдік тілдер пайда болды. Қазіргі кезде олардың саны жүздеп саналады. Алгоритмдер теориясында алгоритмді жалпы түрде бейнелеуге көп көңіл бөлінеді немесе алгоритмнің әмбебап болуын қамтамасыз етуге тырысады. Алгоритмді жалпы түрде бейнелеу тәсілін алгоритмдік жүйе деп атайды. Алгоритмдік жүйелерді сипаттауда арнайы формальді түрдегі құралдар қолданылады. Олар «алгебралық» және «геометриялық» болып екі түрлі жүйеге бөлінеді. Алгебралық теория бойынша алгоритм белгілі бір нақты символдардың мәтіні ретінде құрастырылады. Ал геометриялық 78 жүйелерде объектілердің бір-бірімен байланысқан граф түріндегі геометриялық сипаттамалар қолданылады. Бірінші бағытқа рекурсивті функцияларды, Тьюринг машинасын, А.А. Ляпуновтың операторлық жүйесін және т.б., ал екіншісіне – А.А. Марковтың қалыпты алгоритмдерін, графсхемалар мен блок-схемаларды жатқызуға болады. Алгоритмді сипаттау әдістері құрастырылатын алгоритмнің программа құрастырушыға түсінікті болуын қамтамасыз етуі тиіс. Іс жүзінде алгоритм сөздер арқылы (вербальді сипаттау) және блок-схема күйінде бейнеленеді. Алгоритмді осылайша сипаттау оны түсінікті әрі көрнекті етеді. Марковтың нормальды алгоритмдері Алгоритм ұғымын тұрпаттандыру үшін Россия математигі А.А. Марков ассоциативтік қисапты пайдалануды ұсынды. Ассоциативтік қисаптың кейбір ұғымдарын қарастырайық. Әріппе (әртүрлі таңбалардың ақырлы жиынтығы) бар болсын. Оны құраушы таңбаларды әріптер деп атаймыз. Әріппе әріптерінің кез келген ақырлы тізбегі (олардың сызықты қатары) осы әріппедегі сөз деп аталады. Әлдебір А әріппесіндегі N және M екі сөзін қарастырайық. Егер N M-нің бөлігі болса, онда M-ге енеді дейді. Әлдебір әріппеде алмастырулардың ақырлы жүйесі берілсін: N-M, S-Т, ..., мұндағы N, M, S, T,... – осы әріппедегі сөздер. Кез келген N-M алмастыруын әлдебір К сөзіне былай қолдануға болады: егер К-да N-сөзінің бір немесе бірнеше кірістері болса, онда олардың кез келгенін М-мен алмастыруға болады және керісінше, егер М-нің кірісі бар болса, онда оны N-мен алмастыруға болады. Р1 және Р2 сөздері әлдебір ассоциативтік қисапта сыбайлас аталады, егер олардың біреуі екіншісінен мүмкін алмастыруды бір ғана қолданғанда түрлендірілетін болса. Р, Р1, Р2,..., М cөздерінің тізбегі Р сөзінен М сөзіне әкелетін дедуктивті тізбек аталады, егер осы тізбектің қатар тұрған екі сөзінің әрқайсысы сыбайлас болса. Егер Р-дан М-ге тізбек және кері тізбек бар болса, онда Р және М сөздері эквивалентті аталады. Қазіргі кезде көпшілікке үйреншікті болған компьютерлердің пайда болуының, оның аппараттық және бағдарламалық жабдығының дамуына әсер етуші негізгі фактор – ғылыми зерттеулердің нәтижелері. Өткен ғасырдың 30- жылдарында ағылшын математигі А. Тьюринг пен америкалық математик Э. Пост алгоритм туралы түсінік пен абстракт машина немесе абстракт автомат туралы идеясын жариялаған болатын. Олардың идеялары бір-біріне өте жақын және ол идея бойынша алгоритмдік үдеріс дегеніміз арнайы құрастырылған «машина» орындайтын амалдардың тізбегі. Осының негізінде алгоритмдік процестер математикалық терминдермен сипатталына бастады. Кейіннен, ғылыми әдебиетте, ол «машина» Тьюринг машинасы деп аталынды. Осы идея бойынша Тьюринг машинасы келесі бөлімдерден тұрады: - ұяшықтарға бөлінген бағдарламалық лента; әрбір ұяшыққа бір таңбаны жазуға болады; - «оқитын бас» - арнайы сезімтал элемент; ол ұяшыққа жазылған информацияны оқи алады; лента екі бағыт бойынша қозғала алады; әрбір сәтте сезімтал элемент бір ұяшыққа орналасады; - басқару құрылғысы, ол әрбір сәтте белгілі бір күйде болады; ол бірнеше жағдайда болу мүмкіншілігі бар; оның бірінде машинаның жұмыс істеуі тоқтатылады. Егер қазіргі кездегі электронды есептегіш машиналардың фон Нейман ұсынған жұмыс істеу принциптерін қарастыратын болса, онда Тьюринг машинасымен ұқсас екендігіне көз жеткізуге болады. ЭЕМ-дерде информация енгізу, оны компьютердің «оқуы» дәл осы принциптерге негізделген. Тьюринг пен Пост ұсынған алгоритмдік жүйе бойынша, ақпарат екілік жүйеде бейнеленеді немесе әрбір ұяшыққа 0 немесе 1 жазылады. Алгоритм бұйрық түрінде берілетін реттелінген ережелерден тұрады. Алгоритмнің орындалуы бірінші бұйрыққа сәйкес бастапқы ұяшықтан басталады. Машина сыртқы және ішкі әліппе деп аталынатын символдардың жиындарымен жұмыс істейді. Сыртқы әліппеге машина жұмыс істейтін 80 символдар жататын болса, ал ішкі әліппеге оның басқару құрылғысының жағдайларының жиыны жатады. Тьюринг машинасы қабылдай алатын сыртқы әліппенің символдары енгізілетін ақпаратты белгілейді. Ол символдардың саны шектелген және олардың әрқайсысының кодтары болуы тиіс. Мысал: Әріппе Алмастырулар {а,в,с,d,e} ac-ca; abac-abace аd-da; eca-ae bc-cb; eda-be bd-db; edb-be abcde және acbde сөздері-сыбайлас (bc-cb алмастыру) abcde-cadbe сөздері эквивалентті. Алмастырулары бағытталған болып келетін: N M (жебеше алмастыруды солдан оңға қарай жүргізуге рұқсат етілетіндігін білдіреді) ассоциативтік қисаптың арнайы түрін қарастыруға болады. Әрбір ассоциативтік қисап үшін мынадай есеп бар: кезкелген екі сөз үшін олардың эквивалентті немесе емес екендігін анықтау керек. Формулаларды шығарудың кез келген үрдісі, математикалық есептеулер мен түрлендірулер де әлдебір ассоциативтік қисапта дедуктивті тізбектер болып табылады. Ассоциативтік қисапты құру ақпаратты анықталған қайта 39 өңдеудің әмбебап әдісі болып табылады және алгоритм ұғымын тұрпаттандыруға мүмкіндік береді. Ассоциативтік қисап негізінде алгоритм ұғымын енгізейік: А әріппесінде Алгоритм деп, А-дағы сөздерге үрдіс анықтайтын және бастапқы сөз ретінде кез келген сөзді мақұлдайтын түсінікті дәл ұйғарым. А әріппесінде алгоритм мақұл алмастыруларды қай тәртіппен қолдануға болатындығы және қашан тоқтайтындығы туралы дәл ұйғарыммен толықтырылған мақұл алмастырулар жүйесі түрінде беріледі. Мысал: Әріппе В алмастырулар жүйесі А={a,b,c} cb-cc cca-ab ab-bca Алмастыруларды қолдану туралы ұйғарым: кез келген Р сөзінде алмастырулардың сол жағын оң жағына ауыстырып, мүмкін алмастырулар жасау керек; жаңа алынған сөзбен үрдісті қайталау керек. Осылай, қарастырылған мысалдағы алмастырулар жүйесін ваваас және всасавс сөздеріне қолданып, мынаны аламыз:
bcacabc bcacbcac bcacccac bcacabc ақырсыз үрдіс (тоқтау жоқ), осымен біз бастапқы сөзді алдық.
1 1
P сөзі: 11+11=111 40 сөзін Марковтың қалыпты алгоритмі арқылы біртіндеп қайта өңдеу мына кезеңдер арқылы өтеді: Р=11+11+111P5=+1+111111 P1=1+11+111Р6=++1111111
Марковтың қалыпты алгоритмін кез келген алгоритм берілуінің әмбебап түрі ретінде қарастыруға болады. Қалыпты алгоритмдер әмбебаптығы қалыптастыру принципі арқылы жарияланады: кез келген ақырлы А әріппесінде кез келген алгоритм үшін оған пара-пар А әріппесі бойынша қалыпты алгоритм құруға болады. Соңғы тұжырымды түсіндірейік. Кейбір жағдайларда алмастыруларында тек А әріппесінің әріптерін пайдаланатын болсақ, А әріппесінде берілген алгоритмге эквивалент қалыпты алгоритм құрылмайды. Дегенмен А әріппесін кеңейту арқылы (оған жаңа әріптерді қосу арқылы) қажетті, қалыпты алгоритм құруға болады. Бұл жағдайда, бастапқы А әріппесіндегі сөздерге ғана қолданы-латын болса да құрылған алгоритмді А әріппесі бойынша алгоритм дейді. Егер N алгоритмі А әріппесінің кейбір кеңейімінде берілген болса, онда N А әріппесі бойынша қалыпты алгоритм дейді. Тьюринг машиналарының композициясы Осы уақытқа дейін әртүрлі алгоритмдер командалар жиыны мен ішкі және сыртқы әріппелерімен өзгешеленетін әртүрлі Тьюринг машиналарында орындалады деп келді. Дегенмен, кез келген Тьюринг машинасының кез келген алгоритмін орындауға қабілетті әмбебап Тьюринг машинасын жасауға болады. Бұған әмбебап машинаның сырт әріппесіндегі кез келген берілген Тьюринг машинасының конфигурациясы мен программасын кодтау арқылы қол жеткізуге болады. Кодтаудың өзі былай орындалуға тиіс: а) әртүрлі таңбалар әртүрлі кодтық топтармен алмастырылуы қажет, бірақ бір таңба қай жерде кездескеніне қарамай, бір ғана кодтық топпен жаппай ауыстырылуы қажет; б) кодтық жазба жолдары жеке кодтық топтарға бірмәнді бөлшектенуге тиіс с) А,П,С командаларына сәйкес кодтық топтардытану, сыртқы әріппеге және іш күйлеріне сәйкес кодтық топтарды ажырату. Қорытынды: Тьюринг машинасы – белгілі бір есептерді шығаруға арналған қатаң математикалық құрылым, математикалық аппарат. Бұл аппарат машина деп аталу себебі оның құрамдас бөлігінің және функцияларының есептеу техникасына ұқсауында. Тьюринг машинасының есептеу техникасынан ерекшелігі оның еске сақтау құрылғысы шексіз лентадан тұруында, ал есептеу техникасының еске сақтау құрылғысы қаншалықты үлкен көлемді болса да шектеулі. Сондықтан Тьюринг машинасын лентасы шексіз болғандықтан есептеу техникасы түрінде қолдануға болмайды. Марковтың нормальды алгоритміне қойылатын талаптар: алгоритм қарапайым орындалатын саны шектеулі ережелерден тұруы тиіс, яғни жазбалардың шектеулі болуы талабын қанағаттандыруы тиіс; алгоритм шектеулі қадамнан соң есепті шешуі тиіс, яғни әрекеттердің шектеулі болу талабын қанағаттандыруы тиіс; алгоритм барлық мүмкін болатын бастапқы деректер үшін біреу ғана болуы керек, яғни әмбебаптық талабын қанағаттандыруы тиіс; алгоритм қойылған есептің дұрыс шешімін табуы керек, яғни дұрыс болу талабын қанағаттандыруы тиіс. Бұл анықтамаларда әрекетті орындаушы көрсетілуі тиіс және ол орындайтын «қарапайым» операцияларға не жататыны нақтылануы тиіс. Алгоритмді әртүрлі формада бейнелеуге , яғни беруге болады. жүктеу/скачать 26,22 Kb. Достарыңызбен бөлісу:
|