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



жүктеу/скачать 0,6 Mb.
бет67/80
Дата07.01.2022
өлшемі0,6 Mb.
#20727
1   ...   63   64   65   66   67   68   69   70   ...   80
Вариант 2

1. а) 285(10); б) 846(10); в) 163(10).

2. а) 000101010001(2-10); б) 010101010011(2-10); в) 011010001000(2-10).

3. Автоматизация.

4. 50 72 6F 67 72 61 6D.

5. а) 242(10); б) 135(10); в) 248(10).

6. а) 81(10); б) –40(10); в) –24(10).

7. а) 18509(10); б) 28180(10).

8. а) 28882(10); б) –19070(10).

9. а) 0110010010010101; б) 1000011111110001.

10. а) –363,15625; б) –487,15625.

11. а) C075228000000000; б) 408B9B0000000000.



Вариант 3

1. а) 905(10); б) 504(10); в) 515(10).

2. а) 010010010100(2-10); б) 001000000100(2-10); в) 01110000(2-10).

3. Информатика.

4. 50 72 6F 63 65 64 75 72 65.

5. а) 207(10); б) 210(10); в) 226(10).

6. а) 98(10); б) –111(10); в) –95(10).

7. а) 19835(10); б) 22248(10).

8. а) 18156(10); б) –28844(10).

9. а) 0111100011001000; б) 1111011101101101.

10. а) 334,15625; б) 367,15625.

11. а) C07C08C000000000; б) C0811B0000000000.



Вариант 4

1. а) 483(10); б) 412(10); в) 738(10).

2. а) 001101011000(2-10); б) 100010010010(2-10); в) 010101000110(2-10).

3. Computer.

4. 84 88 91 8A 8E 82 8E 84.

5. а) 185(10); б) 224(10); в) 193(10).

6. а) 89(10); б) –65(10); в) –8(10).

7. а) 29407(10); б) 25342(10).

8. а) 23641(10); б) –23070(10).

9. а) 0111011101000111; б) 1010110110101110.

10. а) 215,15625; б) –143,375.

11. а) C071760000000000; б) 407FF28000000000.



Вариант 5

1. а) 88(10); б) 153(10); в) 718(10).

2. а) 000110000100(2-10); б) 100110000111(2-10); в) 100100011000(2-10).

3. Printer.

4. 43 4F 4D 50 55 54 45 52.

5. а) 158(10); б) 134(10); в) 190(10).

6. а) 64(10); б) –104(10); в) –47(10).

7. а) 30539(10); б) 26147(10).

8. а) 22583(10); б) –28122(10).

9. а) 0100011011110111; б) 1011101001100000.

10. а) –900,546875; б) –834,5.

11. а) 407C060000000000; б) C0610C0000000000.



Вариант 6

1. а) 325(10); б) 112(10); в) 713(10).

2. а) 100101100010(2-10); б) 001001000110(2-10); в) 011100110110(2-10).

3. компьютеризация.

4. 50 52 49 4E 54.

5. а) 239(10); б) 160(10); в) 182(10).

6. а) 55(10); б) –89(10); в) –22(10).

7. а) 17863(10); б) 25893(10).

8. а) 24255(10); б) –26686(10).

9. а) 0000010101011010; б) 1001110100001011.

10. а) –969,15625; б) –434,15625.

11. а) C082B30000000000; б) C086EB0000000000.



Вариант 7

1. а) 464(10); б) 652(10); в) 93(10).

2. а) 000110010010(2-10); б) 001100011000(2-10); в) 011000010000(2-10).

3. YAMAHA.

4. 4D 4F 44 45 4D.

5. а) 237(10); б) 236(10); в) 240(10).

6. а) 95(10); б) –68(10); в) –77(10).

7. а) 28658(10); б) 29614(10).

8. а) 31014(10); б) –24013(10).

9. а) 0001101111111001; б) 1011101101001101.

10. а) –802,15625; б) –172,375.

11. а) C085EB0000000000; б) C07D428000000000.



Вариант 8

1. а) 342(10); б) 758(10); в) 430(10).

2. а) 010110010000(2-10); б) 011101100101(2-10); в) 011100010111(2-10).

3. световое перо.

4. 4C 61 73 65 72

5. а) 136(10); б) 130(10); в) 239(10).

6. а) 82(10); б) –13(10); в) –77(10).

7. а) 27898(10); б) 24268(10).

8. а) 19518(10); б) –16334(10).

9. а) 0000110100001001; б) 1001110011000000.

10. а) 635,5; б) –555,15625.

11. а) C07848C000000000; б) C085394000000000.



Вариант 9

1. а) 749(10); б) 691(10); в) 1039(10).

2. а) 100100010001(2-10); б) 001000111001(2-10); в) 001101100011(2-10).

3. Микропроцессор.

4. 88 AD E4 AE E0 AC A0 E2 A8 AA A0.

5. а) 230(10); б) 150(10); в) 155(10).

6. а) 74(10); б) –43(10); в) –21(10).

7. а) 18346(10); б) 25688(10).

8. а) 31397(10); б) –21029(10).

9. а) 0110101101111000; б) 1110100100110101.

10. а) 110,546875; б) –743,375.

11. а) C08B794000000000; б) 407CB28000000000.



Вариант 10

1. а) 817(10); б) 661(10); в) 491(10).

2. а) 100001010001(2-10); б) 010000000111(2-10); в) 001001110001(2-10).

3. Принтер.

4. 42 69 6E 61 72 79.

5. а) 219(10); б) 240(10); в) 202(10).

6. а) 44(10); б) –43(10); в) –94(10).

7. а) 23359(10); б) 27428(10).

8. а) 21481(10); б) –20704(10).

9. а) 0001101010101010; б) 1011110111001011.

10. а) –141,375; б) 145,375.

11. а) 408EA14000000000; б) C07B128000000000.



Вариант 11

1. а) 596(10); б) 300(10); в) 515(10).

2. а) 001100100110(2-10); б) 001000010110(2-10); в) 010100010010(2-10).

3. Дисковод.

4. 49 6E 66 6F 72 6D 61 74 69 6F 6E.

5. а) 237(10); б) 160(10); в) 253(10).

6. а) 122(10); б) –97(10); в) –82(10).

7. а) 30469(10); б) 21517(10).

8. а) 23008(10); б) –23156(10).

9. а) 0010111101000000; б) 1011001101110001.

10. а) 576,375; б) –99,375.

11. а) 40864B0000000000; б) C047140000000000.



Вариант 12

1. а) 322(10); б) 320(10); в) 738(10).

2. а) 000110000000(2-10); б) 100101010110(2-10); в) 011101100001(2-10).

3. Pentium 100.

4. 91 A8 E1 E2 A5 AC A0 20 E1 E7 A8 E1 AB A5 AD A8 EF.

5. а) 201(10); б) 135(10); в) 198(10).

6. а) 91(10); б) –7(10); в) –95(10).

7. а) 29234(10); б) 19909(10).

8. а) 25879(10); б) –27169(10).

9. а) 0001111001010100; б) 1011010001110010.

10. а) –796,15625; б) 325,15625.

11. а) 4060B00000000000; б) C0846C6000000000.



Вариант 13

1. а) 780(10); б) 949(10); в) 718(10).

2. а) 0001000000010101(2-10); б) 100110011001(2-10); в) 001101100001(2-10).

3. Арифмометр.

4. AC AE A4 A5 AB A8 E0 AE A2 A0 AD A8 A5.

5. а) 188(10); б) 213(10); в) 217(10).

6. а) 89(10); б) –90(10); в) –34(10).

7. а) 25173(10); б) 25416(10).

8. а) 27435(10); б) –22433(10).

9. а) 0111110101101100; б) 1111011001100010.

10. а) –142,375; б) 565,15625.

11. а) C086494000000000; б) C083DC6000000000.



Вариант 14

1. а) 164(10); б) 1020(10); в) 713(10).

2. а) 011110000100(2-10); б) 001100010001(2-10); в) 100101010001(2-10).

3. Сканер.

4. A2 EB E7 A8 E1 AB A8 E2 A5 AB EC AD EB A9 20 ED AA E1 AF A5 E0 A8 AC A5 AD E2.

5. а) 127(10); б) 199(10); в) 187(10).

6. а) 57(10); б) –31(10); в) –109(10).

7. а) 17689(10); б) 20461(10).

8. а) 26493(10); б) –30785(10).

9. а) 0010110001100110; б) 1010001111010000.

10. а) –550,15625; б) 616,15625.

11. а) 407C360000000000; б) 408B594000000000.



Вариант 15

1. а) 280(10); б) 700(10); в) 464(10).

2. а) 010100110011(2-10); б) 100100100101(2-10); в) 100010010001(2-10).

3. ВИНЧЕСТЕР.

4. 43 6F 6D 70 75 74 65 72 20 49 42 4D 20 50 43.

5. а) 217(10); б) 161(10); в) 232(10).

6. а) 53(10); б) –24(10); в) –110(10).

7. а) 23380(10); б) 22620(10).

8. а) 24236(10); б) –30388(10).

9. а) 0100101101100011; б) 1001001000101100.

10. а) 84,15625; б) –681,375.

11. а) 4075E28000000000; б) C07E980000000000.



Вариант 16

1. а) 728(10); б) 383(10); в) 202(10).

2. а) 001100110011(2-10); б) 001101100010(2-10); в) 010001000100(2-10).

3. IBM PC.

4. 8A AE AC AF EC EE E2 A5 E0.

5. а) 170(10); б) 242(10); в) 158(10).

6. а) 70(10); б) –50(10); в) –90(10).

7. а) 21581(10); б) 31014(10).

8. а) 19903(10); б) –17431(10).

9. а) 0011111110001000; б) 1001011111011111.

10. а) 650,375; б) –974,5.

11. а) C05DCA0000000000; б) 408E5B0000000000.



Вариант 17

1. а) 158(10); б) 177(10); в) 439(10).

2. а) 000100110101(2-10); б) 001010010011(2-10); в) 0001000000100100(2-10).

3. Автоматизация.

4. 50 72 6F 67 72 61 6D.

5. а) 172(10); б) 247(10); в) 216(10).

6. а) 104(10); б) –67(10); в) –88(10).

7. а) 17134(10); б) 17996(10).

8. а) 24197(10); б) –19851(10).

9. а) 0001010110011011; б) 1001010000111010.

10. а) 423,15625; б) 835,15625.

11. а) 4089794000000000; б) 408B414000000000.



Вариант 18

1. а) 328(10); б) 537(10); в) 634(10).

2. а) 000100000100(2-10); б) 010110011001(2-10); в) 100000110111(2-10).

3. Информатика.

4. 50 72 6F 63 65 64 75 72 65.

5. а) 203(10); б) 199(10); в) 214(10).

6. а) 87(10); б) –50(10); в) –31(10).

7. а) 17130(10); б) 27910(10).

8. а) 26837(10); б) –17264(10).

9. а) 0100011000011101; б) 1101001111000101.

10. а) –197,15625; б) –341,375.

11. а) C057D80000000000; б) 406F0C0000000000.



Вариант 19

1. а) 1026(10); б) 725(10); в) 100(10).

2. а) 100110010110(2-10); б) 100100110010(2-10); в) 000110010000(2-10).

3. Computer.

4. 84 88 91 8A 8E 82 8E 84.

5. а) 173(10); б) 149(10); в) 129(10).

6. а) 73(10); б) –117(10); в) –39(10).

7. а) 24335(10); б) 28591(10).

8. а) 19650(10); б) –27052(10).

9. а) 0110010000000000; б) 1111111001010100.

10. а) 612,15625; б) –652,546875.

11. а) 40664C0000000000; б) 40684C0000000000.



Вариант 20

1. а) 853(10); б) 135(10); в) 66(10).

2. а) 100001111001(2-10); б) 100000010000(2-10); в) 001101000100(2-10).

3. Printer.

4. 43 4F 4D 50 55 54 45 52.

5. а) 178(10); б) 240(10); в) 152(10).

6. а) 54(10); б) –10(10); в) –43(10).

7. а) 18083(10); б) 19157(10).

8. а) 18477(10); б) –28803(10).

9. а) 0101010001100111; б) 1110101001001100.

10. а) 575,375; б) 983,375.

11. а) C088440000000000; б) C0696C0000000000.



Вариант 21

1. а) 206(10); б) 382(10); в) 277(10).

2. а) 011101100101(2-10); б) 010001110111(2-10); в) 011101010000(2-10).

3. компьютеризация.

4. 50 52 49 4E 54.

5. а) 234(10); б) 254(10); в) 192(10).

6. а) 120(10); б) –110(10); в) –112(10).

7. а) 19743(10); б) 30381(10).

8. а) 30643(10); б) –23233(10).

9. а) 0111100111001110; б) 1001100000100111.

10. а) –503,15625; б) 339,375.

11. а) C06EA50000000000; б) C08E230000000000.



Вариант 22

1. а) 692(10); б) 844(10); в) 1014(10).

2. а) 010101100010(2-10); б) 100100100111(2-10); в) 001001000101(2-10).

3. YAMAHA.

4. 4D 4F 44 45 4D.

5. а) 215(10); б) 229(10); в) 241(10).

6. а) 101(10); б) –34(10); в) –56(10).

7. а) 23242(10); б) 17599(10).

8. а) 25657(10); б) –29323(10).

9. а) 0010101000011001; б) 1011000010001010.

10. а) 654,546875; б) 494,375.

11. а) C0642C0000000000; б) C082F14000000000.



Вариант 23

1. а) 707(10); б) 133(10); в) 1023(10).

2. а) 001010000011(2-10); б) 010000000011(2-10); в) 001010000001(2-10).

3. световое перо.

4. 4C 61 73 65 72.

5. а) 136(10); б) 202(10); в) 207(10).

6. а) 85(10); б) –44(10); в) –66(10).

7. а) 17949(10); б) 27584(10).

8. а) 27445(10); б) –31187(10).

9. а) 0100011111000100; б) 1011001111110000.

10. а) 446,15625; б) –455,375.

11. а) 408B894000000000; б) C089930000000000.



Вариант 24

1. а) 585(10); б) 239(10); в) 361(10).

2. а) 011010000001(2-10); б) 100001010001(2-10); в) 001110000111(2-10).

3. Микропроцессор.

4. 88 AD E4 AE E0 AC A0 E2 A8 AA A0.

5. а) 162(10); б) 224(10); в) 206(10).

6. а) 73(10); б) –111(10); в) –66(10).

7. а) 17189(10); б) 22238(10).

8. а) 32549(10); б) –23508(10).

9. а) 0011100011010100; б) 1001010101100011.

10. а) –279,375; б) –838,15625.

11. а) 4081C94000000000; б) 403D800000000000.



Вариант 25

1. а) 382(10); б) 830(10); в) 512(10).

2. а) 100000100101(2-10); б) 010010010100(2-10); в) 011000000011(2-10).

3. Принтер.

4. 42 69 6E 61 72 79.

5. а) 136(10); б) 183(10); в) 162(10).

6. а) 111(10); б) –122(10); в) –61(10).

7. а) 21736(10); б) 22611(10).

8. а) 18894(10); б) –25174(10).

9. а) 0000111101011000; б) 1110000000001111.

10. а) 300,546875; б) –400,15625.

11. а) 408EFB0000000000; б) 4078D28000000000.




Зертханалық жұмыс №3 (2 сағат)

Тақырып: Шекті автомат туралы түсінік



  1. Шекті автоматтарды беру тәсілдері

  2. Логикалық элементтер мен бөгеттерден құрылған схемалар


ЕМЕС, ЖӘНЕ, НЕМЕСЕ үш логикалық функцияның жиынын XIX ғ. аяғында өмір сүрген, осы функцияларды зерттеген ағылшын математигі Джордж Бульдің қүрметіне Бульдік базис деп атаған. Осы үш функция арқылы әртүрлі логикалык функциялар өрнектелетін алгебраны Буль алгебрасы деп атайды.

ЕМЕС функциясы - бұл бір аргумент функциясы (басқа атаулары: теріске шығару, инверсия). Функция әдетте аргумент үстіндегі сызықшамен белгіленеді:

Y=a


Мүндағы Ү - логикалық функция; а - аргумент. Теріске шығару функциясы 1-ге тең, егер оның аргументі 0-ге тең болса және керісінше:

өшірілді =жанды.

Егер ЖАНДЫ айтылымы ақиқат болса, онда ӨШІРІЛДІ айтылымы жалған болады және керісінше. Терістеу аргументін теріске шығару аргументтің өзіне тең болады: (өшірілді ЕМЕС)ЕМЕС=өшірілді немесе егер

Ү=а, ОНДА Ү=а=а.

Тоқ немесе кернеудің белгілі деңгейі түрінде ЕМЕС функциясын жүзеге асыратын электронды логикалық элемент инвертор деп аталады. Инвертор функционалдық сүлбелерде төмендегідей бейнеленеді:


Кіріс – сол жақтан, шығыс – оң жақтан. Шығыс сызығында оның тіктөртбұрышпен қосылатын жерінде шеңбер – инверсия символы бейнеленген. Релелі-контактілі логикада ЕМЕС функциясын ағытылатын контакт жүзеге асырады (сур. 1.1), яғни реленің мұндай контактісі жүйеде тоқ күші а болған кезде ағытылып тұрады, ал а тоқ күшін берген кезде ағытылады.



ЖӘНЕ функциясы - бүл екі немесе одан да көп аргумент функциясы (Басқа атауы: конъкция, логикалық көбейту). Белгіленуі:

Ү=а&b, Ү=аb.

ЖӘНЕ функциясы 1-ге тең сонда және тек сонда, егер оның барлық аргументі 1-ге тең болса. Табиғи тілдегі «және» осы байланысты білдірері, мысалы: лифт жүреді, егер есік жабылса ЖӘНЕ кнопка басылса.



Релелі-контактілі техникада ЖӘНЕ функциясы сигнал-аргументтер басқаратын тұйықталған контактілерді тізбектей жалғау арқылы жүзеге асады (сур.1.2 а).





1

&

Барлық контактілер бірдей қалыпта болған жағдайда ған тоқ жүреді. Егер тым болмаса бір контакт нольдік күйде тұрса (ажыратылған), онда тоқ жүрмейді, функция 0-ге тең болады.

ЖӘНЕ функциясын жүзеге асыратын элементті ЖӘНЕ элементі немесе конъюктор деп атайды. ЖӘНЕ элементін көбінесе ақпарат ағынын басқару үшін пайдаланады. Мұнда оның бір кірісіне қандай-да бір ақпаратты әкелетін логикалық сигналдар келеді, ал басқасына басқарушы сигнал келеді: 1-өткізу, 0-өткізбеу. Осындай жолмен қолданылатын элементті вентиль деп атайды.

НЕМЕСЕ функциясы - бұл функция екі немесе одан да көп аргумент функциясы. НЕМЕСЕ функциясы 1-ге тең, егер оның ең болмағанда бір аргументі 1-ге тең болса (басқа атаулары: дизъюнкция). Белгіленуі: Ү=аЬ. Табиғи тілдерде дизъюнкция функциясы «немесе» шылауымен айтылып, мына түрдегі сөйлемдерде қолданылады: Біз келесі жағалауға өте аламыз, егер өзен таяз НЕМЕСЕ көпір бүтін болса.

Логикалық формула (логикалық өрнек) – логикалық шамалар мен логикалық амалдар таңбасынан тұратын формула.

Логикалық формуланың есептелуінің нәтижесі тек қана АҚИҚАТ немесе ЖАЛҒАН болады.

НЕМЕСЕ элементін жүзеге асыратын элемент – дизъюнктордың шартты белгісі төмендегідей.


Тапсырмалар:

1. Аргумент мәндерінің барлық комбинациялары үшін ЕМЕС функциясының ақиқаттық кестесін құр.

2. ЖӘНЕ және НЕМЕСЕ функциялары үшін аргументтердің барлық комбинациялары үшін ақиқаттық кесте құр.

3. ЕМЕС функциясын жүзеге асыратын логикалық элемент – инвертордың жұмысы мен функционалдық схемадағы шартты белгісін сипатта.

4. ЖӘНЕ функциясын жүзеге асыратын логикалық элемент – конъюктордың жұмысы мен функционалдық схемадағы шартты белгісін сипатта.

5. НЕМЕСЕ функциясын жүзеге асыратын логикалық элемент – дизъюнктордың жұмысы мен функционалдық схемадағы шартты белгісін сипатта.

Зертханалық жұмыс №4 (3 сағат)

Тақырып: Алгоритмдер теориясының негізгі ұғымдары



  1. Тьюринг және Пост машиналарының көмегімен алгоритмдерді есептеу.

  2. Марковтың қалыпты алгоритмдері.


Қысқаша мәлімет

(Алгоритм ұғымын формальдандыру)

Тьюринг машинасы туралы түсінік алгоритмге берілген ең ыңғайлы да қолайлы анықтама болды. Бұл түсінік ағылшын математигінің атымен аталды, 1937 жылы, яғни, ЭЕМ пайда болғаннан жыл бұрын берген болатын. Тьюринг машинасының анықтамасы:

Тьюринг машинасы математикалық машина, сонымен қатар Тьюринг машинасын мынандай математикалық объектілермен салыстыруға болады: топ, интеграл, функция, туынды т.с.с. Тьюринг машинасының автоматты түрде жұмыс істейтін құрал ретінде елестетуге болады. Тьюринг машинасы елес машина, ол қандай да бір көзге көрініп жұмыс атқарып тұрған құрылғы емес. Біз ол машинаны бар деп санаймыз. Белгілі бір жағдайда бір ұяшықты қарасытрады, ол ұяшықтар лента бойында орналсқан. Лентадағы ұяшықтар жағдай ауысқанда өзгеруі немесе сол қалпында қалуы мүмкін. Жағдай ауысып отырады. Тьюринг машинасы программамен жұмыс істейді. Екі алфавит бар: ішкі және сыртқы алфавиттер.

Мысалы, ішкі алфавит Машинаға берілген элементтер міндетті түрде ақырлы болуы керек. Жұмыс істеуге ыңғайлы болу үшін лента бойында бос ұяшық бар деп есептейміз. Сыртқы алфавит . Ішкі алфавит лента ішінде жазылған, сыртқы алфавит лента үстінде жазылған.

q0 – бастапқы жағдай

q1- соңғы жағдай.

Программа былай берілуі мүмкін:









Тьюринг машинасының командасының жалпы түрі:




  • Егер Х=С болса, онда aj тұрған ұяшықты қарастырамыз және соны өшіреміз. Содан кейн al элементін жазамыз. Жағдай qi -дан qk –ға өзгереді. Одан кейін ешқандай қадам жасамай орнымызда қаламыз. Яғни, al элементі тұрған және qk жағдайы бар ұяшық өз-өзін қарастырады.

  • Егер Х=П болса, онда бір қадам оңға (направо) ауысады.

  • Егер Х=Л болса, онда бір қадам солға (налево) ауысады.

Мысал:







q1
1

0

1







q1




1

0

1

0




q2




1

0

1

0

0

q0




1

0

1

0

1

Қортыа келе, бастпқы сөз 101 болса, программа бойынша Тьюринг машинасымен жұмыс істегенде 10101 сөзін алдық.


Тапсырмалар мен есептер

 


  1. Рекурсивті функцияларды қолдана отырып құр:

А) қосудың үшорынды функциясын;

Б) n-орынды қосу функциясын;



  1. Рекурсивті функцияларды қолдана отырып құр:

А) көбейтудің екіорынды функциясын;

Б) көбейтудің үшорынды функциясын;

В) n-орынды көбейтудің функциясын.


  1. Бөлудің бөлікті екіорынды функциясын құрастыр.

  2. Лентада бөлінегн екі санды қосатын Пост машинасының программасын құрып, өзбетіңмен орында;

А) бір бос орынмен;

Б) көп бос орынмен.



  1. Лентада бөлінегн екі санды азайтатын Пост машинасының программасын құрып, өзбетіңмен орында

А) бір бос орынмен;

Б) көп бос орынмен.



  1. Лентада бөлінегн екі санды көбейтетін Пост машинасының программасын құрып, өзбетіңмен орында

А) бір бос орынмен;

Б) көп бос орынмен.



  1. Қарапайым арифметикалық амалдарды орындайтын Тьюринг машинасын құрастыр.

  2. g және h функциясын есептейтін Тьюринг машиналары бар. Келесі есептеуді орындайтын машина құрастыр:

А) осы функциялардың суперпозициясын;

Б) g және h функцияларынан примитивті рекурсия арқылы алынатын.



  1. Кері функцияны тудыратын Тьюринг машинасын құрастыр.

  2. Келесілерді есептейтін Тьюринг машинасын құрастыр:

А) екі санның қосындысын;

Б) екі санның айырымын;

В) екі санның көбейтіндісін;


  1. 1 символдарымен көрсетілген екі бүтін сандарды азайтуды орындайтын Марковтың қалыпты алгоритмін құрастыр. Алгоритмнің жұмысын мысалдармен тексер.

  2. 1 символдарымен көрсетілген екі бүтін сандарды көбейтуді орындайтын Марковтың қалыпты алгоритмін құрастыр.


Бақылау сұрақтары

  1. Неге математикада алгоритм ұғымын формальдандыру қажет болды?

  2. Алгоритм ұғымын жетілдірудің қандай қырлары бар?

  3. Қандай функциялар есептелінетін функциялар деп аталады?

  4. Қандай функциялар бөлікті рекурсиялы функциялар деп аталады?

  5. рекурсивті функциялар теориясында қандай қарапайым функциялар мен амалдар жиынтығы қолданылады?

  6. Черч тезисінің формулировкасы қандай?

  7. Посттың абстрактілі машинасының құрылғылары қандай?

  8. Тъюрингтің абстрактілі машинасының құрылымы қандай?

  9. Тьюринг машинасы қалай сипатталады? Тьюринг машинасының схемаларына мысал келтір.

  10. Тьюринг машинасының композициясы деген не?

  11. Тьюринг теоремасының мазмұны неден тұрады?

  12. Дедекциялық шынжырға мысал келтір.

  13. Марковтың қалыпты алгоритмдері қалай анықталады?

  14. Әмбебап алгоритмнің есебі неден тұрады?

 

Зертханалық жұмыс №5 (3 сағат)

Тақырып: Алгоритмдерді көрсетуді формальдандыру.



  1. Формальді тілдер

  2. Алгоритмдерді көрсету тәсілдері

  3. Құрылымдық теорема

Формальды тілдер грамматикасын қарастыруды алгоритмнің қатаң сипаттамасын құру қажеттілігінен келетін болсақ, шын мәнісінде олардың қолданылу облысы әлдеқайда кеңірек. Формальды грамматика негізінде программалау тілдері және оларға трансляторлар құрылады. Жасанды интеллект есептерін шығару кезінде олар машиналық аударуға, сол сияқты эксперттік жүйелердегі өолданушылардың жауаптарына синтаксикалық дұрыс сөйлемдерді генерациялау үшін қолданылады. Формальды грамматикалар оқу және басқа да программаларда қолданылады.

Формалды тілдерді сипаттау тәсілдері

Объект-тілді сипаттау үшін метатіл қолданылуы қажет. Бірақ метатіл оъект-тілдің құрылымын бірмәнді анықтау үшін формальді тілдің бірқатар қасиеттеріне ие болуы керек, Бұдан, метатіл алдымен өзі сипатталуы қажет, бұл үшін ден сол сияқты тіл қажет -* әрине, мұндай процесстің ешқашан бітпейтіндігі туралы ой қалыптасуы мүмкін. Бірақ кез-келген метатілді сипаттау үшін табиғи тілді қолдануға болатыны дәлелденген. Осылайша формальді тілді құру үшін табиғи тілдің құралдарымен метатілді сипаттау қажет, содан кейін метатіл арқылы формальді тілді сипаттау қажет. Метатілдерді сипаттаудың екі нұсқасын қарастырайық.

Ең кең тараған метатілдердің бірі - Бекус-Наур нотациялары. Бекуса-Наура формасында сөйлем құру үшін әмбебап метасимволар қолданылады: { <, >, ::=, | }. Алғашқы екі метасимволды «бұрыштық жақшалар» деп атайды – олар терминді емес сөздерді қоршауға қажет. «::=» символы «анықтама бойынша бар» деп оқылады; «»"символы – «немесе». Бекус-Наура формасында жазылған сөйлемдерде бұрыштық жақшаларда тұрған терминалды емес символ объект-тілдің құрылымы анықтайтын роль атқарады. Бекус-Наур формулаларында әмбебап метасимволдардан айрықша объект-тілдің алфавитінен терминалды символдар қолданыла алады. Формальді тілдің терминалды символдары ешнәрсемен шектелмейді.

Формальді тілдердің сипатталуы формулалар тізбегінен тұрады, олардың әрқайсысының сол жағында объект-тілдің қандай-да бір құрылымын бейнелейтін бір метасимвол болады. Мұндай формуланың оң жағы немесе орбъект-тілдің метасимволдар және терминалды символдар тізімінен (бұл жерде ешқандай бөлгіштер қойылмайды), немесе «|» символымен бөлінген тізімдер жинағынан тұрады. Оң және сол бөліктері «::=» таңбасымен бір формулаға бірігеді.

Егер кез-келген теминальді емес символды теминалды символдар тізбегі ретінде көрсетуге болатын болса, онда объект-тілді толығымен Бекус-Наур формасында анықталған деп есептеуге болады.

Мысал ретінде көптеген программалау тілдерінде қолданылатын «идентификатор» ұғымын анықтауды қарастыруға болады.табиғи тілде анықтама төмендегідей айтылады: «Идентификатор – бұл әріптен басталатын әріптер мен цифрларлың кез-келген тізбегі». Бекус-Наур формасында оло төмендегідей көрінетін болады:



<идентифтор>::=<әріп>|<идентификатор><әріп>|<идентификатор>
<цифр>

<әріп>::= a|b|c|d|e…

<цифр>::= 0|1|2|3|…|9

Осы ұғымның анықтамасында рекурсивтілік бар екені көрінеді, себебі «идентификатор» ұғымы өзі арқылы анықталып тұр. Бір әріптен тұратын идентификатор қарапайым болып табылады. Бекус-Наур нотацияларының жетістігі олардың әріптік түрде көрсетілуі;
Келесі формальді тілді сипаттау тәсілі бдан да көрнекті деп есептеуге болады: оны PASCAL программалау тілін құрастырушы Никлаус Вирт ұсынған – және «синтаксикалық диаграммалар» деген атауға ие болған. Синтаксикалық диаграмма – бұл объект-тілдің қандай-да бір терминалды емес символын сипаттау схемасы (графикалық көрсетілуі). Схема үнемі бір кіріс және бір шығысқа ие. Схема элементтері ретінде объект-тілдің дөңгелекке алынған теминалды символдары немесе тіктөртбұрышқа алынған объект-тілдің теминалды емес символдары қызмет атқара алады. Элементтер анықталатын терминалды емес символдағы объектілердің ілесу ретін көрсететін бағытталған сызықтармен өзара біріктіріледі. Келесі бейнелеулер қабылданған:


Синтаксикалық диаграммалардың құрылымы программалау тілдерінің құрылымдарына ұқсас, бұл диаграммаларды әртүрлі тілдердің трансляторларын жазуға кең қолданылуына мүмкіндік берді. Синтаксикалық диаграммалардың көмегімен сипатталған тіл – PASCAL тілі болған.

Диаграмманы оқу стрелка бағытына сәйкес; тармақталу нүктесінде кез-келген маршрут таңдалоынуы мүмкін. Метатіл ретінде табиғи орыс тілі қолданылуы мүмкін; программалау тілдері ағылшын тілі негізінде құрылады. Терминальды символдар формальды тілдердің құрылымына сөзбе-сөз жазылады.

Синтаксикалық диаграммаларды құрудың бірнеше мысалын қарастырайық:

Қажетті жетілдіретін диаграммалар:



Ағылшын тілінде осы диаграммаға сәйкес идентификаторлар құру мысалдары: q, a123, identificator, e2e4.



PASCAL тілінің жалпы түрін көрсететін диаграмма:

Шартты және циклды жазбалар мысалы:



Осындай және ұқсас диаграммаларға сәйкес тілдің мүмкін синтаксикалық құрылымдары құрылады.

Сонымен, Бекус-Наур нотациялары және синтаксикалық диаграммалар – бұл формальді тілдер құрылатын метатілдер құрылымын сипаттаудың ұқсас екі тәсілі. Формальды грамматика құрылып болғаннан, және бұдан тіл туындаса, ол қолданбалы есептерді шешуге қолданыла алады – коммуникация, ақпаратты сақтау және өңдеу. Соңғы есептер класы тілдер көмегімен ақпаратты өңдеу тізбегін сипаттауды жасаудың қажеттігіне әкеледі, яғни алгоритмдерге және оларды өңдеуді жүргізетін адам немесе техникалық құрылғы түсініп, орындауға мүмкін формада көрсету.

Алгоритмдерді көрсету тәсілдері

Алгоритм жазылу тәсіліне қарай 3 түрге бөлінеді;



  1. Сөздік алгоритм немесе жаратылыс тілінде жазылған алгоритм;

  2. Графиктік алгоритм немесе блок-схема;

  3. Программалау тілінде жазылған программа;

Алгоритмнің құрылымдық түрлері:

  1. Сызықтық алгоритм – қарапайым амалдардың жазылу реті мен орындалу реті тізбектелген алгоритм.

  2. Тармақталған алгоритм – есептеу барысында қай амалдар тізбегінің орындалатыны шартқа байланысты алгоритм.

  3. Циклдық алгоритм – берілгендердің әртүрлі мәндері үшін белгілі амалдары қайталанып орындалатын алгоритм.

  4. Көмекші алгоритм – алгоритм орындалу барысында алгоритм ішінде пайдаланылатын алдын-ала құрылған дайын алгоритм.

Сөздік алгоритм:

Еклид алгоритмі



  1. n және m сандары берілген;

  2. k =mod m;

  3. k≠0? Онда

  4. n:= m және m:= k 1-ге көшеміз;

  5. k=0, тоқтаймыз.

Графиктік алгоритмнің шартты белгілері:







Циклдық құрылымның 3 түрін қарастыруға болады:


Шарт алдынан берілген цикл.



Шарт соңынан берілген цикл



Қайталау саны белгілі цикл (параметрлі цикл):

Тапсырма 1



Блок-схему схемасын құрып, программа жаз.

Тармақталған құрылымды программалау.

1. а, в, с нақты сандар берілген. Осы сандардың арасында тым болмаса бір қарама-қарсы сандар бар-жоғын анықта.


  1. n бүтін саны a,b,c сандарының ортақ бөлгіші болатынын анықта.

  2. Определить, имеется ли среди чисел А,В,С хотя бы одно делящееся на 7.

  3. Үш нақты сандар берілген. Теріс еместерінің квадратын тап.

  4. Үш нақты сандар берілген. Осы сандардың арасынан (1,3) кесіндісіне тиістілерін таңдап ал.

  5. x, y, z нақты сандары берілген. max. (x, y, z)-ті тап.

  6. x, y, z нақты сандары берілген. min(x, y, z)-ті тап.

  7. x,y,r,x1,y1 нақты сандары берілген. М(х,у) нүктесі центрі О(х1,у1), радиусы r болатын шеңберге жататынын анықта.

  8. х нақты саны берілген. Осы санның екіорынды екенін анықта.

  9. Екіорынды сан берілген. Осы сан өзінің цифрларының қосындысынан асып кететінін анықта.


Тапсырма 2.

x, k R берілген. Y-ті есепте.



  1. х,у екі бүтін сан берілген. Егер олардың екеуі де тақ болса, онда қосындысын тап, кері жағдайда тиісті хабарлама бер.

  2. жүктеу/скачать 0,6 Mb.

    Достарыңызбен бөлісу:
1   ...   63   64   65   66   67   68   69   70   ...   80



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