Практикум павлодар 2014 удк



жүктеу/скачать 1,42 Mb.
бет11/20
Дата07.01.2022
өлшемі1,42 Mb.
#16918
түріПрактикум
1   ...   7   8   9   10   11   12   13   14   ...   20
Жауаптар және шешімдер


  • 3.1. в.




  • 3.2. б.

  • 3.3. а.


Шешім. 1) Рқар = Kқар/N = 10/20 = 1/2 — қара шарды алу ықтималдығы;

    1. Рақ = Kақ/N = 5/20 = 1/4 — ақ шарды алу ықтималдығы;

    2. Рсар = Kсар/N = 4/20 = 1/5 — сары шарды алу ықтималдығы;

    3. Рқыз = Kқыз/N = 1/20 — қызыл шарды алу ықтималдығы;

    4. Нқар = log2(l/(l/2)) = 1 бит;




    1. Нақ = log2(l/(l /4)) = 2 бит;

    2. Нсар = log2(l/(l/5)) = 2,236 бит;




    1. Нқыз = log2(l/(l/20)) = 4,47213 бит.




  • 3.4. б.




  • 3.5. б.


Шешім. 1) Көлдегі жалпы балықтар саны:


    • = 12500 + 25000 + 2•6250 = 50000;




  1. әрбір балықтың қармаққа түсу ықтималдығы:


Ра = 12500/50000 = 0,25; Рт = 25000/50000 = 0,5;

Рм = 6250/50000 = 0,125; Рш = 6250/50000 = 0,125;


    1. ақпарат көлемі:




  • = -(0,25•log20,25 + 0,5•log20,5 + 0,125•log20,125 + 0,125•log20,125) = 1,75 бит.


T 3.6. в.

  • 3.7. б.

  • 3.8. б.

  • 3.9. б.

32


  • 3.10. г.

  1. 3.11. а) 6065,5248, С35,АА16; б) 34131,41248, 3859,85416.

  • 3.12. а) 10010,01012; б) 107,48; в) 7С,416.




  • 3.13. а) 11010110001112; б) 11111010110011002.




  • 3.14. a) 1FA; б) 1В5. Түсініктеме: алдымен сегіздік жүйесінен екілік жүйесіне ауыстырыңыз, сосын он алтылық санау жүйесіне.




  • 3.15. б.




  • 3.16. а. Түсініктеме: осы есепті шешкен кезде тізбектік (жүйелі) кодтау принципін пайдалану керек.




  • 3.17. а.

  • 3.18. г.

Шешім. 1) N = 2i, 256 = 2i, i = 8 бит — бірінші бейненің түс тереңдігі;

    1. 640•480•8 = 2 457 600 бит — видеожад көлемі;

    2. 512 = 2i, i = 9 бит — екінші бейненің түс тереңдігі;

    3. 2 457 600 : 9 = 273 066 нүкте — екінші бейненің мөлшері.

  • 3.19. г.

Шешім. 1) N1 = 2i, 256 = 2i, i1 = 8;

    1. N2 = 2i, 65536 = 2i, i2 = 16;

    2. i1/i2 = 8/16 = 0,5 есе.

  • 3.20. г.




  • 3.21. б.

  • 3.22. в.

  • 3.23. б.

  • 3.24. а.

33


  1. АҚПАРАТТЫҚ ҮДЕРІСТЕРДІ АВТОМАТТАНДЫРУ. АБСТРАКТІЛІ АВТОМАТТАР

Абстрактілі (яғни тек адам қиялында ғана болатын) Пост және Тьюринг машиналары бағдарламалардың қасиеттері туралы әр түрлі тұжырымдарды дәлелдеу үшін ойлап шығарылды. Бұл бір-біріне тәуелсіз екі есептеу машиналарының моделін (практикада бір уақытта) 1937 жылы Алан Тьюринг ұсынды. Бұл машиналар толық детерминделген әмбебап орындаушылар болып табылады. Олар алғашқы деректерді енгізіп, бағдарлама орындалғаннан кейін нәтижені оқуға мүмкіндік береді. Тьюринг машинасына қарағанда Пост машинасы қарапайым болғанымен кең таралмаған.


4.1 Тьюринг машинасы
Бұл елестегі машина - яғни ― «қағаз бетіндегі» машина немесе машинаның математикалық моделі.
Тьюринг машинасы - таза абстракция және ешқашан жасалмаған. Оның пайдасы түрлі есептер шешімінің алгоритмі бар немесе жоқ екендігін дәлелдеуге болады. Машина белгілі бір алгоритмді орындайтын болғандықтан, бұл машинаға алгоритмнің қасиеттерінен талаптар қойылады. Біріншіден, машина толықтай детерминенделген (есептеулер нақты және жалпы түсінікті) болуы қажет және тапсырылған ережелер жүйесі негізінде әрекет етуі керек. Екіншіден, - бастапқы мәліметтерді енгізуге мүмкіндік беруі қажет. Үшіншіден, берілген машинаның жұмыс жасау ережелерінің жүйесі және шешілетін есептердің класы машина жұмысы нәтижесін оқи алатындай болып келістірілуі керек.
Тьюринг тезисі кез келген алгоритмді Тьюринг машинасына салып шешуге болатынға негізделген.
Тьюринг машинасының жұмыс істеу принципі, сипаттамасы.
Бір ленталы Тьюринг машинасын кибернетикалық құрылғы ретінде қарастырады және ол келесі элементтерден тұрады:
– ұяшықтарға бөлінген шексіз лента;
– лента ұяшықтарында болатын символдарды оқи алатын басқарушы головка;
– Тьюринг машинасының жағдайын көрсететін ішкі алфавит символы бар жадының ұяшығы.
– лента бойымен головканың қозғалысын қамтамасыз ететін басқарудың механикалық құрылғысы
– тек оқуға болатын Тьюринг машинасының бұйрықтарынан тұратын функционалды схема - жады аймағы.
Әдетте, Тьюринг машинасы схемалық түрде мынадай түрде көрсетіледі:



34


Лентаны магниттік жол немесе баспаның қағаз лентасы деп қарастырайық, ол бірнеше ұяшыққа бөлінген. Жұмыс барысында машина бар ұяшықтарға жаңа ұяшықтарды қоса алады, сондықтан лента екі жағынан да шексіз деп айтуға болады. Лентаның әрбір ұяшығы көп жағдайдың бірінде болуы мүмкін. Бұл жағдайларды біз а0, а1,...,а m символдарымен немесе басқа символдармен белгілейміз. Осы символдар лента ұяшықтарында жазылған. Мұндай символдардың жиынтығы машинаның сыртқы алфавиті деп, ал лентаның өзі машинаның сыртқы жадысы деп аталады. Егер ұяшық бос болса, ол жерде  шарты символы орналасқан деп есептейміз. Машинаның жұмысы кезінде лентаның ұяшықтары өздерінің жағдайын өзгертуі де, өзгертпеуі де мүмкін. Жаңа қосылатын барлық ұяшықтар бос болады. Сонымен, егер қандай да бір уақытта лентаның r ұяшығы болса және машинаның сыртқы алфавиті мынадай символдардан тұрса а0, а1,...,аm, онда лентаның жағдайы былай жазылады:
аi0, аi1,...,аim.
аi1 - солдан бастап орналасқан бірінші ұяшықтың жағдайы, аi2 - екіншісінің жағдайы, т.с.с.
Басқару головкасы. Бұл лентаның бетімен қозғалатын және белгілі бір уақытта лентаның белгілі бір ұяшығында тұрады. Кейде керісінше басқару головкасы қозғалмайды, оған сәйкес лента қозғалады деп есептеледі. Ондай кезде головкаға лентаның ұяшығының біреуі әлде келесісі кіреді деп есептеледі. Егер лентаның ұяшығы головкада болса, машина бұл ұяшықты оқып немесе қабылдап жатыр деп есептеледі.
Машинаның ішкі жадысы - әрбір қараған уақытта белгілі бір жағдайда болатын құрылғы. Ішкі жадының жағдайының саны машинамен есептеліп отырады. Ішкі жадының жағдайын мынадай символдармен көрсетеміз S0, S1,…, Sn, олар машинаның сыртқы алфавитіне кірмейді. Ішкі жадының жағдайының символдарының жиынтығы машинаның ішкі алфавиті деп аталады.
Ішкі жадының жағдайын көбінесе машинаның ішкі жағдайлары деп атайды. Бұл жағдайлардың біреуі бастапқы деп аталады, бұл жағдайдан машина өз жұмысын бастайды, ол S0 жағдайы болсын. Тағы да бір арнайы жағдай - аяқтаушы соңғы жағдай. Соңғы жағдайды көрсететін символ стоп-символ деп аталады. Стоп-символ  өрнектеледі. Егер қандай да бір уақытта машинаның ішкі жадысы  келсе, ол жұмысын тоқтатқан болып есептеледі. Машинаның Sі қандай да бір ішкі жағдайында ешқандай өзгеріс болмауы мүмкін, олай болса, машина шексіз жасайды деп есептеледі.
Машина ерекше механизммен жабдықталған деп есептеледі. Ол қабылданатын ұяшық пен ішкі жады жағдайына қарай ішкі жады жағдайын, ұяшық орнын өзгерте алады деп есептеледі.
Машинаның (Тьюринг) ағымдағы жағдайы немесе оның конфигурациясы деп ағымдағы ұяшық аj және ішкі жады S1 жағдайларының жиынтығын айтамыз.
Тьюринг машинасының командасы, яғни машина жұмысы бір жағдайдан белгілі бір уақытта механикалық құрылғының бір такті жұмысынан соң жаңа

35


бір жағдайға өтуіне негізделген, содан соң тағы бір такті жұмысынан жаңа бір жағдайға өтуі т.с.с. Егер машина Sі ішкі жағдайында аі символды лентаның ұяшығын қабылдап, ішкі жады жағдайын келесіге Sb аударып сонымен бірге қабылданған ұяшықтың мазмұнын аr символына аударып, ал басқару головкасы


  1. орнында тұрып, бір ұяшыққа оңға қарай (R), солға қарай (L) қозғалса, онда машина мынадай команда орындап жатыр деп айтады:

Sі аіаs Sb H

Sі аіаs Sb R

Sі аіаs Sb L


Машина орындай алатын барлық командалардың жиынтығы бағдарлама деп аталады. Машина жұмысы шарт бойынша толықтай оның ішкі жадысының S және қабылданатын ұяшықтың aj жағдайымен анықталатын болғандықтан, барлық Sі aj (і=1,…, n; j=0, 1,…, m) үшін машина бағдарламасы тек қана бір aіaj сөзінен басталатын командадан тұруы қажет. Сонымен {a0, a1,…, a n} символды және {S0, S1,…, Sm} жағдайдағы машина бағдарламасы максимум (n+1)(m+1) командаларынан тұрады. Бағдарламада мынадай жолдардың өңделуі мүмкін емес, бірақ формалды түрде олардың болуы қате болып саналмайды.
Тьюринг машинасының қарапайым түрінде кейбір алгоритмдерді құру қиындық туғызады. Мысалы, аралық мәліметтерді бір жерде сақтау немесе бірнеше элемент топтарының символын салыстыру және т.б. Кей жағдайда қосымша лентаның болуы немесе сөздерді бірнеше лентаға орналастыру дұрыс шешім қабылдауға көмектеседі.
Көпленталы машина әрбір лентаға арналған алфавитке ие. Машинадағы ленталар бір-бірінен тәуелсіз қозғалады. Алайда машина лентасының жағдайы бірдей, ол жағдай басқару механизмі болып табылады. Бір ленталы машинаны қарастырғанда лента қозғалмайды, ал головка берілген бағытта қозғалады деп есептелді. Бірақ көп ленталы машинаны қарастырғанда бұл жағдай ыңғайлы емес. Себебі ленталар бір-бірінен тәуелсіз, ал бір басқару механизмінде түрлі бағыттағы қозғалысты көрсету қиын. Сонымен басқару механизмі қозғалмайды, ал ленталар оңға, солға бір-бірінен тәуелсіз қозғалады деп есептеледі.
Көп ленталы машинаның бағдарламасы - шешімге қарай келесі жазба тәртібі қолданылады: Sі{a,b,c}→{a',b',c'}{R,L,H}Sj
Тьюринг белгілі бір U есептеу машинасының құрылысының мүмкіндігін көрсетті, U машинасы универсалды деп аталу себебі онда түрлі есептеулерді жасауға болады.
Тьюринг машинасының ерекшелігі сәйкес келетін кодтау жолымен кез келген есептеуді берілген Тьюринг машинасында орындай алуында. Кодтау жеңіл болуы керек.
Тьюринг машинасының бағдарламасының кодталуы.
Тьюрингтің универсалды машинасы (ТУМ) лентасында берілген Тьюринг машинасының (ТМ) код номері жазылады. ТУМ осы код номерін оқып, оның лентасында бағдарламасы жазылған машинаның барлық жұмысын атқаруы қажет. Осыған сәйкес мұндай машиналарға белгілі бір әдіспен жазылған кіріспе

36


сөз қажет. Мүмкін белгілердің саны көп болғандықтан, барлық символдар басқа белгілердің ретімен кодталады. Егер А машинасы m символға ие Aі және n ішкі жағдайға Sj ие болса, кодты былай көрсету керек:

Aі = 1…1 (A1=1, A2=11, A3=111 және т.б.)

Sj = 2…2 (S1=2, S2=22, S3=222 және т.б.)

R = 3


L=33
H=333
Мұндай жағдайда машина жұмысының бағдарламасын белгілі бір санмен жазуға болады. Жазбаның екі нұсқасы бар:


  1. Команданың бөлу белгісі болмайды. Мұндай жағдайда командаларды мынадай форматта жазу қажет Aold Sold Anew R Snew сонда бірінен соң бірі орналасқан екі командалар элементар анализатормен бөлінеді.




  1. Команда бөлгіші бар. Мысалы Х саны оны 4 саны кодтаймыз.



жүктеу/скачать 1,42 Mb.

Достарыңызбен бөлісу:
1   ...   7   8   9   10   11   12   13   14   ...   20



©emirsaba.org 2024
әкімшілігінің қараңыз
    Басты бет
Lessons
Curriculum vitae
Documents