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

Алгоритмдер талдауында енгізілетін деректердің маңызы зор, өйткені алгоритмдердің орындалу тізбегі енгізілетін деректермен анықталады. Мысалы, N элементтен тұратын тізімдегі ең үлкен элементті табу алгоритімін қарастырайық:

L=a[1]

For i=2 to N do

If (a[i]>L) then

L=a[i]

Endif

Endfor

Егер тізім кему реті бойынша реттелген болса, онда цикл алдында бір меншіктеу болмайды. Егер тізім өсу реті бойынша реттелген болса, онда барлығы N меншіктеу жасалынады (біреуі цикл басында және N-1 циклда). Талдау кезінде біз енгізілетін мәндердің әр түрлі мүмкін жиындарын қарастыруымыз керек, өйткені егер біз бір жиынмен шектелсек, ол ең жылдам шешім беретін (немесе ең баяу) болуы мүмкін. Нәтижесінде алгоритм туралы жалған көрсетім аламыз. Оның орнына енгізілетін жиындардың барлық типтерін қарастырамыз.

Біз әр түрлі енгізілетін жиындарды әр бір жиындағы алгоритм жұмысына байланысты класстарға бөлеміз. Класстар саны және класстың әрбір жиынындағы жұмыс көлемін білу керек. Класстар бөлінгеннен кейін әрбір класстың бір жиынындағы алгоритмнің орындалуын көре аламыз. Егер класстар дұрыс таңдалса, онда бір класстағы барлық жиында алгоритмнің орындайтын амалдар саны бірдей болады, ал басқа класстағы жиындарда амалдар саны басқаша болады.

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

Нені есептеу керек деген сұрақ шешімі екі қадамнан тұрады. Бірінші қадамда мәнді амалдар немесе амалдар тобы таңдалады. Екінші қадамда осы амалдардың қайсысы алгоритм денесіне кіреді, ал қайсысына қосымша шығын кетеді немесе деректерді тіркеуге және есепке алуға кететінін таңдаймыз.

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

Біз арифметикалық амалдарды екі топқа бөлеміз: аддитивті және мультиаддетивті. Аддитивті операторларға (қысқаша қосу) қосу, азайту, санауышты өсіру, торларға (қысқаша көбейту) көбейту, бөлу және модуль бойынша қалдық табу жатады. Дұл екі топқа бөлу көбейту, қосуға қарағанда ұзағырақ істейтініне байланысты. Практикада көбейтулері аз алгоритмдер жиі қарастырылады.

Дәріс 10.

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

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

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

10.1. «Бөліп ал да, биле» түріндегі алгоритмдер

10.2. Турнирлер әдісі

10.1 «Бөліп ал да, биле» түріндегі алгоритмдер

«Бөліп ал да, биле» түріндегі алгоритм әр түрлі есептерді шешудің ыңғайлы да қуатты құралдарымен қамтамасыз етеді. Біз мұнда сондай алгоритмдерді таңдаймыз. Циклдағы салыстырулар санын есептегенде бізге тек бір циклдағы салыстырулар санын есептеп және оны итерациялар санына көбейтсе жеткілікті. Егер ішкі циклдың итерациялар саны сыртқы цикл параметрлеріне тәуелді болса, онда есептеулер күрделене түседі. 

«Бөліп ал да, биле» алгоритмдеріндегі итерацияларды есептеу оңай емес, ол ең алдымен рекурсивті шақыруларға, алғашқы және соңғы әрекеттерден тәуелді. Мысал ретінде «Бөліп ал да, биле» түріндегі келесі алгоритмді қарастырамыз.

Бұл алгоритм ең алдымен қарапайым рекурентті емес алгоритм (DirectSolutionатаулы) көмегімен табуға болатындай есептің өлшемі қаншалықты кіші екендігі тексеріледі. Егер ол кіші болса, онда ол шақырылады. Егер есептің өлшемі өте үлкен болса, онда алдымен DivideInput процедурасы шақырылады, ол кіріс деректерді кішірек бірнеше топқа бөледі (олардың саны numberSmaller). Бұл кішірек топтар бірдей өлшемді немесе өлшеидері бір-бірінен өзгешелеу болуы да мүмкін. Кіріс деректер тобының әрбір элементі ең болмағанда бір топқа кіреді, алайда сол бір элемент бірнеше топқа кіруі де мүмкін. Содан кейін әрбір кіші топта DivideAndConquer алгоритмін рекурсивті шақырады, ал CombineSolutions функциясы алынған нәтижені топтастырады.

Натурал сан факториалын циклда есептеу қиын емес, алайда төмендегі мысалда бұл есептеудің рекурсивті нұсқасы керек. N санының факториалы N-ді N-1 санының факториалына көбейткенге тең. Сондықтан мынадай алгоритмді келтіреміз:

10.2 Турнирлер әдісі

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

Сурет 9.1. Сегіз мәннен тұратын жиынтық үшін турнир ағашы

Турнирлер әдісі бойынша реті N болатын салыстырулар арқылы тізімнің екінші элементін іздестіру алгоритмін құрамыз. Қандай да бір салыстыру нәтижесінде біз «ұтушы» және «ұтылушыны» аламыз.

Дәріс 11.

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

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

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

11.1. Сызықтық іздестіру

11.2. Екілік іздестіру

11.3. Таңдау

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

Нақты мәнді іздестіру үшін таңдау есебін қарастыруға болады. Мұнда белгілі бір шартты қанағаттандыратын элементті табу керек. Мысалы, бізге бесінші орындағы элементті, соңынан санағанда жетінші элементті немесе орта мәні болатын элементті табу керек болатын кездерді қарастырамыз.

Бұдан былай біз берілген элементті ізделетін жиынды бекітілген деп есептейміз. Біз N элементтен тұратын жиын мынадай массив түрінде берілген деп есептейміз.

A: array [0..N-1] of item;

Әдетте item типі қандай да бір кілттік өрісі бар жазуды сипаттайды. Мақсат – кілттік өрісі берілген «іздестіру аргументіне» (x) тең элементті іздестіру болып табылады. Іздестіру нәтижесінде алынған I индексі мына шартты қанағаттандырады: A[i].key=x;

Ол табылған элементтің басқа өрістеріне қатынауды қамтамасыз етеді. Бізді іздестіру процессі қызықтыратын болғандықтан біз item типі тек кілттен тұрады деп есептейміз.

11.1 Сызықтық іздестіру

Ізделетін дерек туралы ешқандай қосымша ақпарат болмаса, онда массивті біртіндеп қарап шығу керек болады. Мұндай әдіс сызықтық іздестіру деп аталады. Іздестірудің аяқталу шарты мынадай:

1. элемент табылды, яғни a[i]=x.

2. барлық массив қарастырылды және ізделген элемент жоқ.

Бұл бізге мынадай алгоритм береді:

I:=0

While (i<N) and (a[i]=/ x) do i:=i+1 end;    (10.1)

Логикалық өрнектегі элементтердің реті маңызды болып табылады. Индексті өсірер алдындағы шарт мынадай түрде болады:

(0<=i<N) and (A[k]: 0<=k<i: a[k]=/x)(10.2)

Бұл шарт I ден кіші барлық к- лардың мәндері үшін ізделген элемент болған жоқ дегенді білдіреді. Осыдан және іздестіру шарт жалған болғанда ғана аяқталатындығынан соңғы шартты аламыз:

((i=N) or(a[i]=x)) and (A[k]: 0<= k<i: A[k]=/x)(10.3)

Әрбір қадам сайын индексті өсіріп және логикалық өрнекті есептеу керек. Бұл жұмысты қысқартып, іздестіруді тездету үшін – күрделі шартқа эквивалентті қарапайым шартты тұжырымдау керек. Ол үшін массив соңына х мәні бар қосымша элементті орналастыру керек. Мұндай элементті бөгет деп атайды. өйткені ол массив сыртына шығып кетпеуді қадағалайды.

Енді массив былай сипатталады:

A:array [0..N] of integer;

Және бөгеті бар сызықтық іздестіру былайша болады:

A[N]=x; i=0;

While a[i]=/x do i:=i+1 end; (10.4)

Қорытынды шарт:

(a[i]=x) and (a[k]: 0<=k<i: a[k]=/x)

I=N теңдігі ізделген элементтер болған жоқ екндігін көрсетеді.

11.2 Екілік іздестіру (қақ бөліп іздестіру)

Егер деректер реттелген болса, онда іздестіруді тиімдірек жасауға болады. Сондықтан біз а массиві реттелген деп санаймыз, яғни мына шартты қанағаттандырады:

A[k]: 1<=k<N : a[k-1]<=a[k]   (10.5)

Негізгі идея – кез- келген элементті кездейсоқ таңдау, мысалы a[m] элементін және оны х- іздестіру аргументімен салыстыру. Егер ол х- ке тең болса, онда іздестіру аяқталады. Егер ол х-тен кіші болса, онда индекстері m – нен кіші элементтердің барлығын іздестіруден алып тастаймыз, егер ол х-тен үлкен болса, онда m –ге тең немесе m – нен үлкен элементтердің барлығын іздестіруден алып тастаймыз. Бұл бізді мынадай алгоритмге алып келеді (оны қақ бөле отырып іздестіру деп атайды). Мұндағы l мен k индексті айнымалылары массивінің сәйкес сол және оң жақ бөлігінің шетін береді, сол аралықта ізделген элемент жатуы мүмкін:

L;=0; k;=N-1; found:=false;

While (l<=k) and found do

M:= l жәнеk аралығындағы кез келген мән.

if a[m]=x then found:=true else if a[m]<x then

l:=m+1 (6)

else k:=m-1

end;

end.

әрбір қадам алдында орындалатын шарт мынадай:

(l<=k) and (a[k]: 0<=k<l : a[k]<x) and (a[k]: K<k<N : a[k]>x)

бұдан мынадай нәтиже шығады:

found or ((l>k) and (a[k]:0<=k<l:a[k]<x) and (a[k]: K<k<N : a[k] > x))

Бұдан шығатыны:

(a[m]=x) or (a[k]: 0<=k<N : a[k]=/x

m – ді таңдау кездейсоқ, бірақ m алгоритм тиімділігіне әсер етеді. Біздің мақсатымыз - әрбір қадамда келесі іздестіруден көбірек элементті алып тастау; нәтижесінде максималды салыстырулар саны logN. Бұл алгоритмді тездетуге болады, егер:

(a[k]: 0<=k<l : a[k]<x) and (a[k] : K<=k<N : a[k]<=x) (10.7)

Іздестіру екі бөлікте массивті түгел қарап болғанша жүреді:

L : =0; k:=N;   (div-бүтін санды бүтін санға бөлген -

While l<k do   дегі бүтін бөлінді)

M:= (l+k) div2

If a[m]<x then l;=m+1 else k:=m end;

End;

11.3 Таңдау

Кей жағдайда бізге тізімдегі элемент ішінен арнайы қасиеттерді қанағаттандыратын элемент қажет болады, мысалы ең кіші, ең үлкен элемент. Жалпы жағдайда кіші орындағы элемент қызықтырады. Ол үшін мынадай әдісті қолдануға болады: біз тізімдегі ең үлкен элементті табамыз және оны тізім соңына орналастырамыз. Одан кейін біз табылған элементті шығарып тастап қалған тізімнен үлкен элементті табамыз. Нәтижесінде тізімдегі екінші элементті табамыз, оны соңынан санағанда екінші орынға орналастырамыз. Осы процедураның k – рет қайталап біз k –ші элементті табамыз. Нәтижесінде мынадай алгоритмге келеміз:

For I;=1 to k do

X:=a[1];L;=1;

For j:= 2 to n-(i-1) do

If a[j]>l thenX:=a[j];L:=j;End;

EndFor

Swap (a[n-(i-1)],a[l] );

EndFor

мұндағы A– берілген тізім; n –тізімдегі элемент саны; k – іздейтін элементтің реттік номері; swap- табылған элементті (қарастырмаймыз) алып тастау

Дәріс 12.

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

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

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

12.1. Массивтерді сұрыптау

12.2. Тура қосулар көмегімен сұрыптау

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

Сұрыптау алгоритмдерін таңдау өңделетін деректердің құрылымына байланысты, сұрыптауларға сәйкес әдістер екі класқа бөлінген: масивтерді сұрыптау және файлдарды сұрыптау. Кейде оларды ішкі және сыртқы сұрыптаулар деп атайды. Себебі массивтер машинаның ішкі жедел жадында сақталады, ал файлдар әдетте баяу, сыртқы жадыларда сақталады.

12.1 Масивтерді сұрыптау.Негізгі шарт: масивтерді сұрыптаудың таңдалған әдісі қатынау жадысын тиімді қолдану керек. Бұл элементтерді реттейтін ауыстырулар сол орында орындалу керек дегенді білдіреді.

Сол орында орындалатын сұрыптау әдістерін үш категорияға бөлуге болады:

1. Қосулар көмегімен сұрыптау (by insertion)

2. Ерекшелеу көмегімен сұрыптау (by selektion)

3. Алмастыру көмегімен сұрыптау (by exolange)

Барлық програмалар а айнымалысына амалдар қолданады, атап айтқанда орнында ауыстырылатын элементтер осында сақталады және төмендегідей түрде анықталған item және index типтеріне сілтейді:

Type item = RECORD key integer;

(* мұнда басқа компоненттер сипатталған*)

END(11.1)

Type index = integer;

Var a:array [1..n]of item

12.2 Тура қосулар көмегімен сұрыптау

Тура қосулар көмегімен сұрыптаудың негізгі идеясы - жаңа элементті реттелген тізімнің қажетті жеріне қосу болып табылады. Мұндай сұрыптауда кез келген тізімнің бірінші элементі сұрыпталған деп есептеледі. Екінші элементті бірінші элементтен тұратын тізімнің керек жеріне қосады. Енді берілген тізімнің үшінші элементін реттелген екі элементтен тұратын тізімнің қажет жеріне қосады. Бұл процесті берілген тізім элементінің барлығы тізімнің сұрыпталған бөлігіне қосылғанша жалғасады.

Келесі кестеде тура қосулар көмегімен сұрыптау мысалы келтірілген.

Қажетті орынды іздестіру процесін былай жүргізуге болады: х-ті кезектегі а_iэлементімен салыстырамыз. Одан кейін немесе х бос орынға қосылады немесе а_i оңға жылжиды және процесс солға кетеді. Бұл процесс келесі екі шарттың бірі орындалған кезде аяқталады: 1) кілті x-тің кілтінен кіші а_i элемент табылды; 2) дайын тізбектің сол жағына жетті;

Мұнда бөгет әдісін қолданған дұрыс, яғни х мәні бар а₀ бөгетін енгіземіз. Толық алгоритмді және программаны келтіреміз:

Procedure StraightInsertion;

Var i, j: index; x : item;

Begin

For i:=2 то n DO

x: = a[i]; a[0] : = x; j : = 1;

WHILE x < a[j – 1] DO a[j] : = a[j – 1]; j : = j – 1; END;

a[j] : = x END

END STRAIGHT INSERTION

Программа 11.1. Тура қосулар көмегімен сұрыптау мысалы

i n

Дәріс 13.

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

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

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

13.1. Шейкерлік сұрыптау

13.2. Шелл сұрыптауы

13.1 Шейкелік сұрыптау

Сұрыптау алгоритмін жақсартудың жолы – қандай да бір жүріс кезінде алмасулар болған, болмағандығын сақтау. Егер соңғы жүрісте алмасулар болмаса, алгоритмді аяқтауға болады. Бұл жақсарту, бірақ оны тағы да жақсартуға болады, егер алмасуды сақтап қана қоймай, сонымен қатар соңғы алмасудың орнын (индексін) сақтау. Осы к индексінен жоғары көршілес элементтердің жұптары реттеліп тұр. Сондықтан қарастыруларды осы индексте аяқтау керек. Үшінші жақсарту: тізбектің бағытын кезекпен қарау керек. Бұндай алгоритмді «Шейкерлік» алгоритм деп атайды.

«Шейкерлік» сұрыптау мысалы

L = 2     3     3     4     4

R = 8     8     7     7     4

Dir =            

___________________________

      44   06   06   06   06

      55   44   44   12   12

      12   55   12   44   18

      94   12   42   18   42

      18   94   18   55   55

      06   18   67   67   67

      67   67   94   94   94

Төменде Шейкерлік сұрыптаудың программасы келтірілген

PROCEDURE ShakerSort;

VAR j, k, L, R: index; x: item;

BEGINL: = 2; R: = n; k: = n;

REPEAT

FOR j: = R TOLBY – 1 DO

IFa[j-1]>a[j]THEN

x: = a[j-1]; a[j-1]:=a[j]; a[j]: = x; k: = j

END

END

L: = k+1;

FOR j:=L to R BY+1 do

IF a[j-1]>a[j] THEN

x:=a[j-1];a[j-1]:=a[j];a[j]:=x;k:=j

END

END

R:=k-1

UNTIL L>R

END ShakerSort

Программа 12.1. Шейкерлік сұрыптау

13.2 Шелл сұрыптауы

1959 жылы Д.Шелл өзінің жақсартылған сұрыптауын ұсынды. Осы әдісті мысалмен түсіндіреміз. Ең алдымен бір бірінен 4 позиция ара қашықтықта орналасқан элементтерді жеке топтастырамыз және сұрыптаймыз (кесте 12.1). Мұндай процесс төрттік сұрыптау деп аталады. Мысалда сегіз элемент және әрбір топ тура екі элементтен тұрады. Бірінші жүрістен кейін элементтер қайта топтастырылады – енді топтың әрбір элементі бір бірінен екі позицияда орналасады – және қайта сұрыпталады. Бұл екілік сұрыптау деп аталады. Соңғы үшінші жүрісте әдеттегі немесе бірлік сұрыптау жүргізіледі.

Барлық tара қашықтықтарды сәйкесінше h₁, h₂, …, h_tарқылы белгілейміз, олар үшін төмендегі шарт отындалады

Төменде Шелл сұрыптауы алгоритмінің программасы келтірілген.

Дәріс 14.

Тақырыбы: Ақпараттық модельдеу

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

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

14.1. Ақпараттық модельдеу туралы ұғым.

14.2. Модельдерді құрудың негізгі кезеңдері. Формальдау.

14.3. Математикалық модельдеу және есептеу эксперименті.

Модель— 1) қасиеттері белгілі бір мағынадағы жүйенің немесе процестің қасиеттеріне ұқсас объектілер немесе процестер жүйесі; 2) сериялы бұйымдарды жаппай өндіруге арналған үлгі, эталон; кез-келген бір объект жұмысы мен процессордың жұмыс істеуін модельдейтін программа немесе құрылғы. Модельге қойылатын негізгі талап – оның қасиеттерінің негізгі объектіге сәйкес келуі, яғни барабарлығы. Модельдеу – кез-келген құбылыстардың, процестердің немесе объект жүйелерінің қасиеттері мен сипаттамаларын зерттеу үшін олардың үлгісін құру және талдау; бір немесе жаңадан құрастырылған объектілердің сипатын анықтау немесе айқындау үшін олардың аналогтарында (моделінде) объектілердің әр түрлі табиғатын зерттеу әдісі. Модельдеу жүйесі – зерттелетін жүйенің немесе оның элементтерінің математикалық және физикалық аналогтарын құру және талдау.

Модель – модельдеу мақсаты тұрғысынан оқып үйренетін объектің/құбылыстың кейбір жақтарын ұқсастырып бейнелейтін жаңа объект.

Ақпараттықмодель:

1) басқару жүйесінде ақпарат айналымының процесін параметрлік ұсыну;

2) мәліметтер базасында – тұтастық шектеулер жиынтығы;

3) мәліметтер мен олардың арасындағы қатынастарды математикалық және программалық тәсілдермен ұсыну;

4) ақпараттық құралымдар мен олармен жүргізілетін операцияларды формальдық басндау.

Ақпараттық модель – модельденуші объектінің ақпаратты кодтау тілдерінің бірінде сипатталуы.

Модель құруды неден бастау қажет?

Біріншіден модельдеу мақсаты тұрғысынан объектіні талдау қажет. Бұл сатыда объектінің модельдеу субъектісіне таныс барлық қасиеттері қарастырылады.

Модельдеу мақсаты анықталған соң – модельдеу мақсаты тұрғысынан модельдеуші объектінің нақты белгілерін айқындау қажет.

Модельдеу объектісінің ерекшеленген белгілерін ұсыну формаларын таңдау – модельдеу практикасының келесі сатысы болып табылады.

Объектінің ерекшеленген қасиеттері мен белгілерінің бейнелеу формасы таңдалынған соң, таңдалған формадағы ерекшеленген қасиеттерге байланысты формальдау жұмысына кірісу қажет. Формальдау сатысының нәтижесі ақпараттық модель болады.

Модельдеу процесін аяқтау туралы айтпас бұрын құрылған модельдің модельдеу мақсатына және объектіге адекваттылығын тексеру қажет. Құрылған модельде мақсатқа сәйкес қайшылықтар кездессе нақтылау әрекеттерін орындап, моедльдің дәлдігін қайта тексеру қажет.

Ашылған модельдің модельдеу объектісінің бейнелену адекваттылығына талдау жасап, модельдеу мақсатына жету – модельдеудің соңғы сатысы.

Дәріс 15.

Тақырыбы: Ақпараттық жүйелер. «Жүйе» ұғымын анықтау. Жүйе элементтері, олардың өзара байланысы. 

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

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

14.1. «Жүйе» ұғымы ұғым.

14.2. Жүйе элементтері, олардың өзара байланысы

Жүйе (лат.systēma, гр.σύστημα– бөліктерден құралған тұтастық, қосылыс) – бір-бірімен қарым-қатынаста және байланыста болатын, сөйтіп белгілі бір тұтастық, бірлестік құратын көптеген құрамдас бөліктер жиынтығы; агрегаттар мен машиналардың территориялық принциппен емес, жұмыс істегенде атқаратын міндетіне негізделіп біріктірілген құрылымдар жиынтығы.

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

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

Жүйе деп кез елген объектінің, бір мезгілде біртұтас қарастырылатын, басты мақсатқа жету үшін әртекті элементтердің жиынтығының бірігуі деп түсінуге болады. Мақсаттары бойынша және құрамы бойынша жүйелер өзара айшықтанады. Информатика саласында «жүйе» түсінігі көп қолданылады және әр-түрлі мағыналы болып келеді. Бағдарламалық және техникалық құралдар жиынтығына сәйкестендіріліп жиірек қолданылады. Жүйе деп компьютердің аппаратық бөлігі де атала береді. Қолданбалы есептерді шешуге, көптеген құжаттарды енгізуге және есептерді басқаруға арналған, процедуралармен толықтырылған бағдарламаларды жүйе ретінде көрсетуге болады. «Жүйе» түсінігіне қосымша «Ақпараттық» сөзі оның құрылу және жұмыс жасау мақсатын білдіреді.

Ақпараттық жүйелер кез-келген аймақтағы есептерді шешу процесінде қажетті жинау, сақтау, өңдеу, іздеу, ақпаратты жіберумен қамсыздандырады. Олар жаңа өнімдер құруға және мәселелерді (маңызды проблемаларды) шешуге көмектеседі. Ақпараттық жүйелер – қойылған мақсатқа жету және ақпаратты тасымалдау, өңдеу үшін сақтауға арналғандарды қолданудың, әдістер мен қызметшілердің, құралдар жиынтығының өзара байланысы. Қазіргі уақытта ақпараттық жүйелер түсінігін дербес компьютерде ақпаратты өңдеудің негізгі техникалық құралдары ретінде есептейді. Үлкен ұйымдарда дербес компьютермен бірге ақпараттық жүйелер техникалық базасының құрамына мэйнфрейм немесе суперЭЕМ-ді кіргізуге болады. Егер шығарылған ақпаратты және оларды алу мүмкіндігіне арналған адам ролін есепке алмаса онда өздігінен ақпараттық жүйелерді техникалық іске асырудың мәні болмайды. Копьютер мен ақпараттық жүйелердің түсінік айырмашылығы әр түрлі.

Арнайы бағдарламалық құралдармен жабдықталған компьютерлер, ақпараттық жүйеге арналған құралдар және техникалық базасы бола алады. Ақпараттық жүйелердің даму сатысы. 60-жылдар. ақапараттық жүйелерге көзқарастың өзгерумен ерекшеленеді. Көптеген параметрлері бойынша периодтты есеп берулер одан алынған ақпарат қолданыла бастады. Ол үшін ұйымдарға көп функцияларды қамсыздандыру мүмкіндігі бар копьютерлік құралдар керек болды. 70 жылдар шешімдерді тез қабылдау процесстерін жылдамдату үшін ақпараттық жүйелер басқару құралдарында кеңінен қолданыла бастады. 80 жылдардың аяғында ақпараттық жүйелердің концепциялық қолданылуы тағы да өзгеріске ұшырайды. Олар ақпаоаттың стратегиялық қайнар көзі және барлық профилдағы ұйымдар үшін қолданыла бастады. Осы периодттағы ақпараттар жүйесі өз уақытында ақпаратты жеткізіп, ұйымдардың өз кәсібі бойынша алға жылжуына көмектесті. Ақпараттық жүйедегі процесстер

Ақпараттық жүйенің жұмысын қамсыздандыратын процесстерді блоктардан құралған схема түрінде көруге болады: Ақпаратты ішкі немесе сыртқы көздерден енгізу; Енгізілген ақпаратты қолайлы түрде көрсету және өңдеу; Басқа жүйеге тасымаладау немесе тұтынушыларға арналған ақпаратты шығару. Кері байланыс – ол кіру ақпараттарын сұрыптау үшін сол ұйымның қызметшілері өңдеген ақпарат Ақпараттық жүйелердің қасиеті. Кез келген ақпараттық жүйелер өзінің құрылымы, басқарылатын жүйенің жалпы принциптері негізі бойынша аналидеуге кезігуі мүмкін. Ақпараттық жүйелер динамикалық және дамушы бола алады. Ақпараттық жүйелерді құру барысында жүйелік ықпал жсау керек Ақпараттың жүйенің шығу өнімдері шешім қабылдау негізіндегі ақпараттар бола алады. Қазіргі уақытта ақпараттық жүйелерді компьютердің көмегімен таралған жүйелер деген көзқараста. Бірақ ақпараттық жүйені компьютерсіз вариантта алып қарауға болады. Бірнеше фирмалардан тауарды сатып алу кезінде ақпараттық жүйе сатып алушыны тіркеуге алады. Ол: сатып алушылар тобын анықтап, олардың құрамы және суранымдарын, содан кейін өзінің стратегиялық коптік топтарға бағытталуына. Потенциальды сатып алушыларға әр-түрлі ұсыныстар жіберуге Тұрақты сатып алушыларға тауарларға және қызметтерге рұқсат береді.

Ақпараттық жүйелер (ағылш.Information systems; қысқаша: IS) - деректерді тарату, құру, өңдеу, фильтрлеу, жинауға адамдар мен компанияларға қажетті техникалық құрал-жабдықтар мен бағдарламалық жасақтамаларды оқу.. Қойылған мақсатқа жету жолында ақпаратты сақтау, өңдеу және басқаларға беру үшін пайдаланылатын құралдардың, әдістердің және адамдардың өзара байланысты жиыны, пайдаланушылардың сұрауы бойынша ақпаратты сақтауға, іздестіруге және беруге арналған жүйе; мәліметтер базасы мәтінінің мағыналық бөлігіңде — мәліметтерді сақтау және олармен амал-әрекет жасауға арналған белгілі бір жүйенің формальды толықтығын құрайтын тұжырымды схема, ақпараттық база және ақпараттық процессор.

5. СЕМИНАР, ПРАКТИКА, ЗЕРТХАНАЛЫҚ ЖӘНЕ СТУДИЯЛЫҚ САБАҚТАРДЫҢ ЖОСПАРЛАРЫ

6. ЗЕРТХАНАЛЫҚ ЖӘНЕ СТУДИЯЛЫҚ

САБАҚТАРДЫ ОРЫНДАУДЫҢ НҰСҚАУЛЫҒЫ

Зертханалық жұмыс №1

Тақырыбы: Ақпаратты көрсету. Ақпаратты есептеу

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

1.1. Жұмыс мақсаты -кодтау принциптерін, ақпараттыөлшеудің негізгі бірліктерін оқып үйрену, ақпаратты көрсету дағдылардың қалыптастыру, ақпарат сандарын анықтауға есептер шығару.

1.2. Әдістемелік нұсқау

1.2.1. Ақпарат саны білім анықталмандығын азайтудың өлшемі ретінде

Мүмкін оқиғалардың саны К және ақпарат саны I өзара төмендегі формуламен байланысқан: K=2^I. Бұл формула: егер оқиғалардың саны белгілі болса, хабар санын; егер ақпарат саны белгілі болса, мүмкін оқиғалардың санын; анықтауға мүмкіндік береді

Мысал 1."Санды тап" ойын мысалында анықталмағандықты азайтуды қарастыруға болады. Ойынға қатысушылардың біреуі берілген аралықтан ( мысалы, 1-ден 32-ге дейінгі) бүтін санды ойлайды (мысалы, 30), екінші ойыншының мақсаты - бірінші ойынға қатысушының ойлаған санын "табу". Екінші ойыншы үшін білімнің бастапқы анықталмағандығы 32 мүмкін оқиғаны құрайды. Санды табу үшін, белгілі бір ақпарат саны қажет. Бірінші ойыншы тек қана "иә" және "жоқ" деп жауап бере алады. Екінші ойыншы келесі стратегияны таңдауы тиіс: жүйелі, әрбір қадамда білім анықталмағандығын екі есеге кеміту керек. Ол үшін, сұрақ қоя отырып берілген сан аралығын қақ ортасынан бөлу керек.

Ойын хаттамасы.

1-ден 32-ге дейінгі аралықтағы санды табу үшін 5 сұрақ керек болды. 32 санның біреуін анықтауға қажетті ақпарат саны 5 бит болды.

1928 ж. американдық инженер Р.Хартли ақпарат өлшемінің формуласын келесі түрде ұсынған болатын: I = log₂ K , мұндағыК - тең ықтималдық оқиғалардың саны; I - К оқиғалардың кез-келгені болатындай, хабарлаудағы бит саны. Кей жағдайда Хартли формуласын былай жазады: I = log₂ K = log₂ (1 / р) = - log₂ р, әрбір К оқиғалардың тең ықтималдық нәтижесі болатындықтан р= 1/К, сонда К=1/р.

Мысал 2.Кішкене шарА, В немесе Сүш сауыттың біреуінде.  Ол В сауытында екендiгi туралы хабар неше бит ақпараттан тұратындығын анықтау керек.

Шешуі.Мұндай хабар I=log₂3=1,585 бит ақпараттан тұрады.

1948 ж. американдық инженер және математик Шеннон әр түрлі ықтималдығы бар оқиғалар үшін ақпарат санын есептеу формуласын ұсынды.

Егер I – ақпарат саны, К - мүмкін оқиғалардың саны, р_i – жеке оқиғалардың ықтималдықтары, сонда әртүрлі ықтималдықтары бар оқиғалар үшін ақпарат санын төмендегі формуламен анықтауға болады: I = - Sum р_i log₂р_i , мұндағы i1-ден К-ға дейінгі мәндерді қабылдайды.

Енді Хартли формуласын Шеннон формуласының жеке жағдайы деп қарастыруға болады: I = -Sum1/К log₂(1/К) = I = log₂К.

Ықтималдықтары тең оқиғалар үшін алынатын ақпарат саны барынша көп.

Мысал 3.Егер а) симметриялы емес төртжақты кішкене пирамиданы; б) симметриялы және біркелкі төртжақты кішкене пирамиданы; лақтырса, оқиғалардың бірін орындау кезінде алынатын ақпарат санын анықтау керек.

Шешуі. а) төртжақты кішкене пирамиданы тастаймыз. Жеке оқиғалардың ықтималдығы мынадай болады: Р1=1/2, Р2=1/4, Р3=1/8, Р4=1/8, сонда осы оқиғалардың орындалуынан кейін алынған ақпарат саны төмендегі формуламен есептелінеді:

I =-(1/2 log₂1/2+1/4 log₂1/4+1/8 log₂1/8+1/8log₂1/8)=1/2+2/4+3/8+3/8=14/8=1,75(бит).

б) Енді симметриялыжәнебіркелкітөртжақтыкішкенепирамиданылақтырғанда алынған ақпаратсанынесептейміз:I = log₂4=2( бит ).

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

1. Ақпарат өлшемінің ең кіші бірлігі?

2. Хартли формуласын атаңыз.

3. Шеннон формуласын атаңыз.

Жеке тапсырмалар

1. Кәмпит 10 қораптың біреуінде. Ақпараттық анықталмағандықты анықтаңдар.
2. Дәптер екі сөренің біреуінде - жоғарғы немесе төменгі жатыр. Ол төменгі сөреде жатады деген хабар неше бит алып жүреді?
3. Шарик А, В немесе С сауытының бірінде орналасқан. Ақпараттық анықталмағандықты анықтаңдар.
4. Шарик 32 сауыттың бірінде орналасқан. Қайсысында орналасқандығы туралы хабар неше ақпараттық бірліктен тұрады?
5. Сіздің пойызыңыз 16 жолдың қайсысынан жүретінедігін анықтау үшін қанша сұрақ және қалай қою керек?
6. 4х4 "крестілер-нөлдер" ойынында екінші ойыншының бірінші жүруінен кейін бірінші ойыншы неше ақпарат санын алады.
7. Қандай да бір оқиғаны орындағаннан кейін 15 бит ақпарат алдық. Алғашқыда қанша мүмкін оқиғалар саны болды.
8. Бірінші оқиғаның ықтималдығы 0,5, ал екінші және үшінші оқиғалардың ықтималдығы 0,25. Осылардың біреуін орындағаннан кейін қанша ақпарат санын аламыз.
9. 32 секторлы рулетка ойынында қанша ақпарат саны алынады.

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

Тақырыбы: Мәтіндік, дыбыстық, графикалық ақпараттарды кодтау

(2 апта 2 сағ)

2.1. Жұмыс мақсаты -кодтау принциптерін, ақпараттыөлшеудің негізгі бірліктерін оқып үйрену, ақпаратты көрсету дағдылардың қалыптастыру, ақпарат сандарын анықтауға есептер шығару.

2.2. Әдістемелік нұсқау

2.2.1. Мәтіндік ақпаратты кодтау

Дәстүр бойынша, бір символды кодтау үшін саны 1 байт болатын ақпаратты қолданады, яғни I=1байт=8бит. К мүмкін оқиғалардың санын және I ақпарат санын байланыстыратын формула көмегімен неше әртүрлі символдарды кодтауға болатынын есептеуге болады (символдар - мүмкін оқиғалар есептей отырып):

К = 2^I = 2⁸ = 256,

яғни, мәтіндік ақпаратты өрнектеу үшін қуаттылығы 256 символ әліпби қолдануға болады. Кодтаудың мәні - әрбір символға 00000000-ден 11111111-ге дейінгі екілік кодты сәйкестікке қояды немесе 0-ден 255-ге дейінгі оған сәйкес ондық код.

Мысал 1.Екі мәтін символдардың бірдей санынан тұрады. Бірінші мәтін орыс тілінде жазылған, ал екіншісі нагури тайпасының тілінде, оның әліпбиі 16 символдан тұрады. Қай мәтінінде ақпарат саны көбірек?

Шешуі. I = К * а (мәтіннің ақпараттық көлемі символдар санының бір символдың ақпараттық салмағына көбейткенге тең). Екі мәтіннің де символдарының саны бірдей болғандықтан (К), онда айырма әліпбидің бір символының хабарлылығынан тәуелді болады (а).

2^а1=32, яғниа1=5 бит; 2^а2=16, яғниа2=4 бит; I1= К*5 бит, I2= К*4 бит.

Сонымен, орыс тілінде жазылған мәтін 5/4 рет көбірек ақпарат алып жүреді.

Мысал 2.2048 символдан тұратын хабар көлемі Мбайттың 1/512 бөлігін құрайды. Әліпбидің қуаттылығын анықтау керек.

Шешуі. I=1/512*1024*1024*8=16384 бит. Хабардың ақпараттық көлемін биттерге ауыстырдық. а = I/К =16384/1024=16 бит - әліпбидің 1 символына келеді.

2¹⁶=65536 символдар - қолданған әліпби қуаттылығы.

Нақ сондай әліпби Unicode кодтауында қолданылады, компьютерде символдық ақпаратты өрнектеуге арналған халықаралық стандарт болуы тиіс.

2.2.2. Графикалық хабарды кодтау

Егер қара - ақ суреттемелер туралы айтсақ, онда 0- қара, 1- ақ.

Егер де 256 сұр түстің дамуы түріндегі нүктелердің қиыстыруы түрінде қарастырса (атап айтқанда осындай қазіргі кезде жалпыға танымал), онда сегіз разрядты екілік сан кез келген нүктенің жарықтығын кодтау үшін жеткілікті.

Түрлі-түстің модельдері.

256 түстің дамуы үшін ( әрбір нүкте 3 байтпен кодталады) ең аз мәндер RGB(0,0,0) қара түске сай болады, ал аққа - барынша көптер үлкен координаталар (255,255,255) сәйкес. Түсті құраушының мәнінің байты неғұрлым көп болса, сол түс анағұрлым жарығырақ. Мысалы, қою көк (0,0,128) үш байтпен кодталады, ал ашық көк (0,0,255). Түрлі түсті графиканы өрнектеудің бірнеше режимі бар: А) толық түсті (TrueColor ); Б) High Color ; В) индекстік.

Толық түсті режимде әрбір құраушының жарықтығын кодтау үшін 256 мәннен қолданады (сегіз екілік разряд), яғни бір пиксель түсін кодтау үшін (RGB жүйесінде) 8*3=24 разряд жұмсау керек. Бұл 16,5 млн түсті бірмәнді анықтауға мүмкіндік береді. Бұл адам көзінің сезгіштігіне өте жақын.

CMYK жүйесінің көмегімен кодтағанда түрлі-түсті графиканы өрнектеу үшін 8*4=32 екілік разряд болуы керек.

High Color режимі - бұл 16- разрядты екілік сандардың көмегімен кодтау, яғни әрбір нүктені кодтау кезінде екілік разрядтар саны азаяды. Бірақ кодталған түстердің диапозоны өте көп азаяды.

Бейнеленетін түстердің саны (К) және оларды кодтауға қажетті бит (а) саны арасындағы байланыс төмендегі формуламен табылады: К = 2^а.

Экранға шығарылатын бейненің екілік коды бейне жадыда сақталады. Бейне жады - электрондық энергияға тәуелді есте сақтайтын құрылғы. Бейне жады мөлшері дисплейдің айыру қабілетіне және түстердің сандарына байланысты. Бірақ оның ең аз көлемі бейненің бір кадры (бір бет) сыятындай анықталады, яғни айыру қабілеттінің пиксель кодының мөлшеріне көбейту нәтижесі ретінде: V_min = M*N* a.

Сегіз түсті палитраның екілік коды.        

Он алты түсті палитра қолданылатын түстердің санын көбейтуге мүмкіндік береді. Мұнда пиксельдің 4 разрядты кодтауы қолданылады: негізгі түстердің 3 биті+ күшейте түскендіктің 1 биті. Соңғысы негізгі үш түстің үшеудің бір уақытта жарықтығын басқарады (үш электрондық шоқтардың күшейте түскендігін).

Он алты түстік палитраның екілік коды