Екілік арифметика ережелері

Позициялық санау жүйесі — (4.2) теңдігін қанағаттандыратын жүйе.

Егер q — бүтін оң сан болса, позициялық санау жүйесі орын алады.

Позициялық санау жүйесінде цифрдың мәні оның сандағы орнымен анықталады: бірдей таңба әр түрлі мән қабылдайды. Мысалы, 222 ондық санында оң жақтағы бірінші цифр екі бірлікті, оған көрші — екі ондықты, ал сол жақтағысы — екі жүздікті білдіреді.

Кез келген позициялық санау жүйесі негізімен сипатталады. Позициялы санау жүйесінің q негізі (базисі)— берілген жүйеде санды бейнелеуде қолданылатын таңбалар немесе символдардың саны.

Позициялық санау жүйесі үшін келесі теңдікті жазуға болады

(4.3)

немесе , мұндағыА_q— негізіqболатын санау жүйесінде жазылған кез-келген сан; п + 1, т — бүтін және бөлшек разрядтардың саны.

Практикадасанның қысқартылған жазылуын қолданады:A_q =а_n а_n-1 ...а₁а₀а_-1 ...а_m.

Кесте4.1-де ондық цифрлардың әр түрлі санау жүйесіндегі эквиваленті келтірілген.

                                                                                               Кесте4.1

Кез келген позициялық санау жүйесінде кез келген санды мына түрде жазуға болады

.

(4.4)

ЭЕМ-де негізінен позициялық санау жүйелерін қолданады. Санның позициялық санау жүйесінде р_i разрядының салмағы төмендегі қатынаспен өрнектеледі

,

(4.5)

мұндағыi — оңнан солға есептегендегі разряд номері.

Егер разрядтың салмағыр_i = 10^kболса, онда келесі жоғарғы разрядтың салмағы p_i+1 = 10^k+1көрші кіші разряд салмағы — p_i-1 = 10^k-1. Разрядтардың арасындағы мұндай өзара байланыс олардың арасындағы ақпараттарды беру мүмкіндігіне алып келеді.

Дәріс6.

Тақырыбы: Ақпараттық үрдістерді автоматтандыру.Екілік қосындылауыштарда арифметикалық амалдардың орындалуы

( 6 апта 1 сағат)

Дәріс жоспары:

6.1. Екілік арифметика ережелері

6.2. Екілік қосындылауышта нүктесі бекітілген түрде көрсетілетін сандарды қосу.

Екілік арифметика ережелері

ЭЕМ-ге түсетін ондық жүйедегі сандарды процессор олардың екілік эквивалентіне түрлендіреді. ЭЕМ бағдарламаға байланысты ақпараттарды өңдегеннен кейін процессор екілік түрде алынған нәтижелерді ондық санау жүйесіне қайта түрлендіреді. Ондық сандардың екілік эквивалентіне амалдар қолданғанда процессор екілік арифметика ережелерін басшылыққа алады.

Кез келген ЭЕМ-нің арифметикалық – логикалық құрылғысының негізі ретінде қосындылауыш немесе азайтатын құрылғы алынады. Қосындылауыш – екілік екі цифрларды қосу амалын орындайтын цифрлық электронды құрылғы. Бұл құрылғыны екілік қосындылауыш деп атайды.

Арифметикалық амал нәтижесінде жаңа сан пайда болады: 

С=АÑ В (5.1)

мұндағы Ñ- арифметикалық амал таңбасы (қосу, азайту, көбейту,бөлу ).

Операнд - цифрлы автоматта орындалғанда арифметикалық амалдарға қатысатын сан. Цифрлы автомат сандардың автоматтық бейнелеріне ғана амал орындағандықтан санның автоматтық бейнесі операнд болып табылады. Яғни, машиналық амалдар үшін (5.1) өрнекті төмендегіндей жазған дұрыс:   

[C]=[А ] Ñ [В] (5.2)

 мұндағы квадрат жақшада операндтардың автаматтық бейнесі белгіленген.

 Операндтар разрядтарының деңгейіне қосу және азайту арифметикалық амалдарының орындалуының ережелерін қарастырайық. Мұндағы а_i, в_i - А және В операндтарының разрядтары; с_i - қосынды разряды; п_i– берілген разрядтан көрші үлкен разрядқа тасымалдау.                        

Екілік жартылай қосындылауыш – арифметикалық әрекеттерді кесте 5.1-де көрсетілген ереже бойынша дайындайтын құрылым.

Екі разрядты қосқанда 1-ді тасымалдау екілік цифрларды қосу ережелерін бірқатар өзгертеді (кесте 5.2);

 Кесте 5.1                                 Кесте 5.2

жоғарыда айтылғандарды жалпылай айтқанда, А және В операндтарын қосқанда разрядтық әрекеттер ережесін былайша тұжырымдауға болады: 

а_i+в_i+п_i-1 =с_i+п_i;    (5.3)

 мұндағы п_i-1- (i-1)-ші разрядтан тасымалдау п_i - (i+1)-ші разрядқа тасымалдау (тасымалдар 0 немесе 1 мәндерін қабылдайды.)                                      

Екілік қосындылауыш - арифметикалық әрекеттерді кесте 5.2-де көрсетілген ереже бойынша орындайтын құрылғы.

Екілік арифметиканың ережесі негізінде екілік цифрларды азайту ережелерін  кесте 5.3-те көрсетілгендей етіп жазуға болады, мұндағы z_i+1, z_i - үлкен разрядтардан бірді қарызға алу. Қарызға алу – үлкен разрядтан бірді aзайтқанға тең. Көрші үлкен разрядтан бірді қарызға алғанды ескере отырып екілік цифрларды азайтуды кесте 5.4-те көрсетілгендей етіп жазуға болады (қарызға алуды тасымалдаудан айыру үшін бірдің алдына минус таңбасын қоямыз).

Кесте 5.3                               Кесте 5.4

Егер А азайғыш (1-ші операнд), В азайтқыш (2- ші операнд) болса, онда разрядты әрекет үшін былай жазуға болады:

a_i+b_i+z_i=с_i+z_i+1 (5.4)

Екілік азайтатын құрылғы деп арифметикалық әрекеттерді кесте 5.4-те көрсетілген ереже бойынша орындайтын құрылғыны айтамыз.

6.2 Екілік қосындылауышта нүктесі бекітілген түрде көрсетілетін сандарды қосу

Екілік қосындылауыштың бірнеше түрін қарастырамыз.

Тура кодтың екілік қосындылауышы - үлкен цифрлық таңбалық разрядтардың арасында разрядтық тасымалдау тізбегі болмайтын қосындылауыш. Тура кодтың екілік қосындылауышы таңбалары бірдей сандарды қосады. Яғни мұндай қосындылауыш алгебралық қосу амалын орындай алады.

[A]_т=Sg_A a₁,a₂,…a_n, [B]_т=Sg_B b₁,b₂,…b_nоперандтары берілсін. Мұндағы Sg_A, Sg_B - А және В үшін разрядтық таңбалар; а_i, в_i – кескіндердің цифрлық разрядтары.

Егер Sg_A=Sg_B болса, онда сандардың қосындысының таңбасы қосылғыштың таңбасына ие болады, ал нәтиженің цифрлық бөлігі операндтардың цифрлық бөліктерін қосқанға тең.

Мысал 1. A=0,1011; B=0,0100 сандарын тура кодтың қосындылауышында қосу керек.

[A]_т= 0,1011               Sg_A=0

⁺[B]_т= 0,0100 Sg_B=0

[C]_т= 0,1111                Sg_C=0                                  Жауабы: [C]_т=0,1111

Мысал 2. A=-0,0101, B=-0,1001 сандарын тура кодтық қосындылауышында қосу керек.

[A]_т=-0,0101  Sg_A=0,0101

⁺ [B]т=-0,1001 Sg_B=0,1001

                                 Sg_C=0,1110                                  Жауабы: [C]_т=0,1110

Тура кодтың екілік қосындылауышында сандарды қосқанда, операндтардың қосындысының абсолют мәні бірден асып кететін жағдай болуы мүмкін. Онда автоматтың разрядтық торының толып кетуі мүмкін. Толып кету белгісі- қосындылауыштың цифрлық бөлігінің үлкен разрядынан тасымалдау бірлігінің бар болуы. Бұл жағдайда j=1 толып кету сигналы пайда болуы керек. Бұл сигнал бойынша машина автоматты түрде тоқтайды және толып кетуді болдырмайтындай масштабтық коэффициентті түзетеді.

Қосымша кодтың қосындылауышы – қосымша кодтағы сандардың кескіндеріне амалдар қолданатын қосындылауыш. Қосымша кодтың екілік қосындылауышының ерекшелігі цифрлық бөліктің үлкен разрядынан таңбалық разрядқа разрядтық тасымалдау тізбегінің бар болуы.

Мысал 3.Қосымша код қосындылауышын қолданып A=0,1010, B=0,0100 сандарының қосындысын табу керек.

Бұл сандардың машиналық кескіндері қосылады:

[A]_қ=0,1010

⁺[B]_қ=0,0100

[C]_қ=0,1110                                                    Жауабы : [C]_қ =0,1110

Мысал 4.Қосымша код қосындылауышында A=-0,1011;B=0,0100 сандарының қосындысын табыңдар.

[A]_қ=1,0101

⁺ [B]_қ=0,0100

[C]_қ=1,1001                                                  Жауабы : [C]_қ =-0,0111      

Мысал 5.Қосымша код қосындылауышында A=0,1011;B=-0,0100 сандарының қосындысын табыңдар.

[A]_қ=0,1011

+ [B]_қ=1, 1100

[C]_қ=-(1)0,0111                                             Жауабы : [C]_қ =-0,1001

Кері кодтың екілік қосындылауышы – кері кодтағы сандардың кескіндеріне амалдар қолданатын қосындылауыш.

Мысал 6. Кері кодтың қосындылауышында сандардың A=0,0101, B=0,0111 қосындысын табыңдар.

   [A]_к=0,0101

⁺ [B]_к=0, 0111

   [C]_к=0,0111                                                               Жауабы : [C]_к =0,0111

Мысал 7. Кері кодтың қосындылауышында сандардың A=-0,0101, B=0,0111 қосындысын табыңдар.

    [A]к=1,1010

 + [B]к=0, 0111

       +(1)0,001

                             1

    [C]_к= 0,0010                                                   Жауабы : [C]_к = 0,0010

Дәріс 7.

Тақырыбы: Ақпараттық үрдістерді автоматтандыру.Логикалар алгебрасының негізгі ұғымдары

( 7 апта 1 сағат)

Дәріс жоспары:

7.1. Тұжырым. Логикалық (бульдік) айнымалы. Логикалық функция.

7.1 Тұжырым. Логикалық (бульдік) айнымалы. Логикалық функция

Логикалар алгебрасының негізгі ұғымы – тұжырым. Тұжырым қандайда бір сөйлемнің ақиқат немесе жалған екендігін бекітетін сөйлем. Кез – келген тұжырымды х символымен белгілеуге болады және егер тұжырым ақиқат болса x=1, ал жалған болса x=0 деп есептеуге болады.

Логикалық (бульдік ) айнымалы деп тек екі ғана мән x={0,1} қабылдайтын шаманы айтамыз. Егер тұжырымға сәйкес логикалық айнымалы кез-келген жағдайда x=1 мәнін қабылдайтын болса, онда тұжырым абсолютті ақиқат. Егер тұжырымға сәйкес логикалық айнымалы кез-келген жағдайда x=0 мәнін қабылдайтын болса, онда тұжырым абсолютті жалған.

Дәріс 8.

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

( 8 апта 1 сағат)

Дәріс жоспары:

8.1. Алгоритм ұғымы

8.2. Тьюринг және Пост машинасы көмегімен «алгоритм» ұғымын анықтау

8.3. Марковтың нормальды алгоритмдері

8.1 Алгоритм ұғымы

Алгоритм ұғымы – информатиканың фундаментальды ұғымдарының бірі. Алгоритмдеу модельдеумен қатар информатиканың жалпы әдісі ретінде қолданылады. Алгоритмдер алгоритмдер теориясы деп аталатын ғылыми пәннің жүйелі зерттеулерінің объектісі болып табылады. «Алгоритм» терминінің бірнеше анықтамасы бар. Мысалы, акдемик А.Н. Колмогоровтың анықтамасы бойынша алгоритм немесе алгорифм дегеніміз қойылған есепті қандай да бір қадамнан кейін шешімге әкелетін нақты қатаң ережелер бойынша орындалатын есептеу жүйесі.

Алгоритмнің математикалық анықтамасы ХХ ғасырдың 30 жылдарында үш типтегі модельдер түрінде алынды: Есептелетін (рекурсивті) функциялар; Шектелген немесе шектелмеген автоматтар теориясы; Марковтың нормальды алгоритмдері.

8.2 Тьюринг және Пост машинасы көмегімен «алгоритм» ұғымын анықтау

Жоғарыда Тьюринг және Пост машиналары цифрлы автоматтар мысалы ретінде қарастырылған. Бұл машиналар толығымен детерминделген универсалды орындаушылар болып табылады. Олардың көмегімен алғашқы деректер енгізілгеннен кейін нәтижені «оқуға» болады. Тьюринг және Пост машиналарында орындалатын есептеулерге шектеулер бар ма деген сұраққа Пост былайша жауап берген: «егер кез – келген және бір ғана деректер бойынша нәтижеге әкелетін жалпы әдіс болса ғана программа құруға берілген есептердің шешімі болады».

8.3 Марковтың нормальды алгоритмдері

Алгоритм ұғымын формальдау үшін 50 жылдары орыс математигі А.А. Марков ассоциативтік есептеулерді қолдануды ұсынды, ол нормальды алгоритм ұғымын енгізді. Мұнда алгоритм ауыстырымдар жүйесі түрінде беріледі, олар қандай символдарды ауыстыру керек екендігін және бұл ауыстырулар қандай ретпен жүретіндігін көрсетеді.

Ассоциативті есептеудің кейбір ұғымдарын келтіреміз. А алфавиті (әр түрлі символдардың шектелген тобы) берілсін. Оны құрайтын символдарды әріптер деп атаймыз. Алфавиттің кез – келген шектелген тізбегін осы алфавиттегі сөзі деп атаймыз. Сөздегі символдар саны оның ұзындығы деп аталады. Ұзындығы нолге тең сөз бос деп аталады. Егер q сөзін q=rst түрінде көрсетуге болса, онда S сөзі q сөзінің ішкі сөзі деп аталады. Мұндағы r және t - сол алфавиттегі кез – келген сөз.

А алфавитінде N және M екі сөзін қарастырамыз. Егер NM-нің бөлігі болса, онда NM-ге кіреді деп аталады. Қандай да бір алфавитте N-M, S-T, ... ауыстыруларының шектелген жүйесі берілсін. Мұндағы N,M,S,T ... осы алфавиттегі сөздер. N-M кез – келген ауыстыруын k сөзіне былайша қолдануға болады. Егер K-ге N сөзі бір немесе бірнеше рет кіретін болса, онда оның кез – келгені M сөзімен ауыстырыла алады және керісінше.

А алфавитіндегі алгоритм деп тиімді есептелетін функцияны айтамыз. Оның анықталу облысы ретінде А алфавитіндегі барлық сөздер жиынтығындағы қандай да бір ішкі жиынды айтамыз және мәні ретінде А алфавитіндегі сөздер болып табылады.

Дәріс 9.

Тақырыбы: Алгоритмдер теориясының негізгі ұғымдары. Алгоритм тиімділігі мен күрделілігіне талдау жасау

(9 апта 1 сағат)

Дәріс жоспары:

9.1. Алгоритм күрделілігі. Алгоритмнің асимптотикалық күрделілігі

9.2. Енгізілетін деректер классы

9.3. Нені есептеу керек және нені ескеру керек

9.1 Алгоритмнің күрделігі. Алгоритмнің асимтотикалық күрделілігі

Алгоритмге талдау жасай отырып, қойылған есепті берілген алгоритммен шешу қанша уақыт алатынын есептеуге болады. Әрбір қарастырылатын алгоритм үшін ұзындығы N болатын кіріс деректері массивінде берілген есеп қаншалықты жылдам шешілетінін бағалай аламыз. Алгоритмдердің тиімділігіне талдау жасағанда бізді алдымен уақыт қызықтырады, ал жады маңызды болған жағдайларды да қажет кезінде қарастырамыз.

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

Күрделі емес немесе қарапайым программалардағы орындалатын амалдар санын N – ге тәуелді функция ретінде дәл есептеуге болады. Біз алгоритмдер талдауын амалдардың дәл санын есептеуден бастаймыз.

Мысалы файлға кіретін әр түрлі символдар санын есептеу алгоритмін қарастырамыз

For all 256 символ do

санауышты нольге айналдыр

endfor

whileфайлда тағы да символдар бар ма do

кезекті символды енгіз

end while

Бұл инициализациялау циклында 256 жүріс орындалады. Егер кіріс файлында N символ болса, онда екінші циклда N жүріс болады. «Нені есептеу керек?» деген сұрақ туады. For циклында алдымен айнымалы циклы инициализацияланады, одан кейін әр бір айнымалы цикл шекарасынан шығып кетпеді ме деп тексеріледі және айнымалы өсіріледі. Бұл инициализация циклы 257 меншіктеу жасайды дегенді білдіреді (біреуі цикл айнымалысы үшін және 257 санауыш үшін), айнымалы цикл 256 рет өсіріледі, және айнымалы цикл шекарасында жататындығын 257 рет тексереді (бір қосымша циклды тоқтату үшін). Екінші циклда N+1 рет шартын тексереді (+1 файл бос болғандағы соңғы тексеру үшін) және санауышты N рет өсіреді. Барлық амалдар:

Өсірулер N+256

Меншіктер 257

Шарттарды тексеру N+258

Сонымен кіріс файлының өлшемі 500 символ болғанда алгоритмде 1771 амал амал орындалады, оның 770 – і инициализациялауға кетеді (43%). Енді N – ді өсірсе не болатынын көрейік. Егер файл 50 000 символдан тұрса онда алгоритм 100 771 амал орындайды, оның 770 – і инициализациялаумен байланысты (бұл барлық амалдың 1%). Инициализациялау амалының саны өскен жоқ, бірақ проценттік қатынаста N – ді өсіргенде ол өте аз болады.         

Енді басқа жағынан қарайық. Компьютердегі деректер былайша ұйымдастырылған – деректердің үлкен блогтарын көшірудің жылдамдығы меншіктеумен бірдей жүреді. Біз алдымен 16 санауышқа 0-ге тең мәндерді меншіктеп, одан кейін бұл блогты басқа санауыштарды толтыру үшін 15 рет көшірейік. Мұның нәтижесінде инициализациялау циклындағы тексерулер саны 33–ке дейін, меншіктеулер саны 33 және өсірулер саны 31 – ге дейін кемиді. Инициализациялау амалдарының саны 770-тен 97-ге, яғни 87% - ке кемиді. Егер біз алынған пайданы 50000 символдан тұратын файлды өңдеу амалдарының санымен салыстырсақ пайда 0,7% - тен кем (100 771 амалдың орнына 100 098 жұмсадық).

Бұдан біз инициализациялау салмағы алгоритмнің орындалу уақытына қатысты аса маңызды емес екндігін көреміз.