3 страница. Массивтерді реттеу есептерінде түйінді рольді үшін төменгі бағанның бірі атқарды

Массивтерді реттеу есептерінде түйінді рольді үшін төменгі бағанның бірі атқарды, дәлірек айтқанда . Ал салыстыру саны алмастыру санымен мынандай қарапайым теңсіздікпен байланысты 2^l , мұндағы l салыстыру саны. Мұнда біз массив элементерінің алғашқы орналасуының жаман варианттарына көңілімізді көбірек бөлеміз. Яғни алгоритмның жұмысының қортындысында алмастыру немесе салыстыру саны максимум болатын варианттарды қарастырамыз. Осыған қоса іздеу және сұрыптау алгоритмнің эффективтігінен бағалауда маңызды орын алатын эффективтіліктің «орташа» бағасы болады, яғни барлық алмастырулар бойынша алынған орташа бағасы.

Айтылған сұрыптау алгоритмін тиімділеу үшін бірнеше жол/ бар. Мысалы, алгоритм n элементі массивті реттеуде n-1 итерация қажет етеді. Бірақ массивтің элемент/іне байланысты, алгоритм оны n-1 итерациядан кем итерациядан реттеуі мүмкін. Осыны ескерсек, онда ондай жағдайларда тексеруді ұйымдастыруға болады. Әр итерацияда кем дегенде бір рет алмасу жүргізілсе, онда true (ақиқат) мәнін қабылдайтын қосымша логикалық айнымалы енгізуге болар еді. Сонымен қатар, әр жаңа итерацияның алдында бұл айнымалының мәнін қосымша тексеріп отыру қажет.

Көпіршіктеу сұрыптау алгоритмінің тиімділігін арттыру үшін процедураны келесі түрде ұйымдастыруды ұсынуға болады:әрбір келесі тізбектік айналу кезекпен және қарама-қарсы бағытта жүргізілсе.Сондай-ақ,егер аппараттық сүйемелдеу болса,онда бастапқы тізбектік есептеу процесін «конвейерлеп» отырып k көпіршіктерді бірінен кейін бірін жіберудің мәні бар.

22. Шелл сұрыптауы (Shell_sort) және оның ерекшеліктері

Айырбастаумен сұрыптайтын алгоритм/. Бұл сұрыптау алгоритм/ң классының өкілдері ретінде бұдан бұрын қарастырылған көпіршікпен сұрыптау, сонымен қатар Шеллдың сұрыптау алгоритмі, тез реттеу алгоритмі, т.б. алгоритм/ мыссал бола алады. Шеллдың реттеу алгоритмін қарастырсақ. Шеллдың реттеу алгоритмі көпіршіктік сұрыптау алгоритмін жалпылайды. Салыстырылатын бастапқы массивтің екі жақын орналасқан элементтерін ғана емес, бекітілген d қашақтықта орналасқан элементтерді де салыстырады. Бірінші қадамда массивтің жарты ұзындығына орналасқан элементтерді салыстырады, яғни тең. Келесі қадамда деп есептелінеді., ары қарай қашықтықтағы элементтер салыстырылып қажет жерде алмастырылып отырады. Осы процедураның соңғы кезеңдерінде элемент/ арасында қашақтық болған кезде алмастыру қажет етпеуі мүмкін, себебі алғашқы кезеңдерде салыстырылып ж/е алмастырылған элементтер өз орындарында орналасқанынан болады. Яғни кезеңдердің айналуына байланысты алмастыру саны төмендей береді екен. Шеллдың реттеу алгоритмінің жұмысын мысалмен көрсетсек:

Шеллдың реттеу алгоритмінің модификацияланған нұсқасы:

Procedure q.Shellsort (a,n);

……

Begin

k:=n div 2;

while k 1 do

begin for i:=k+1 to n do

if a[i-k]>a[i] then

Begin

r:=a[i]; j:=i-k;

L: a[j+k]:=a[j];

if a[j-k]>r then

Begin

j:=j-k; goto L;

End; end;

a[j]:=r;

End;

k:=k div 2;

End; end;

23. Quick_sort сұрыптауы оның ерекшеліктері

A. Hoar ұсынған шапшаң сұрыптау алгоритм. QuickSort алгоритмінің күрделілігі орташалап алғанда O(n*log₂ n) жақын болады. QuickSort алгоритмінің идеясына тоқталайық. Бастапқы берілген массивтің қандай да бір элементі таңдалып бекітіледі, әдетте массивтің ортаңғы немесе шеткі элементтерін осы тіректік элементпен кезекпен салыстырады. Салыстыру нәтижесінде кезекті элемент тіректік элементтен үлкен болса, онда оны тіректік элементтің оң жағына орналастырады. Кері жағдайда тіректік элементтің сол жағына алмасады. Осы тіректік элемент массивтің қалған барлық элементтерімен салыстырылғаннан кейін өзінің массивтегі түпкілікті орнын анықтайды. Сөйтіп, бұл элемент жаңа массивтегі орнына жайғасып массивті 2 бөлікке бөледі. Ол бөліктердің әрқайсысына да ұқсас процедура қолданылады, егер бөліктегі элемент саны бірден артық болса. Ал егер массивтің барлық элементтері осы процедурадан өтсе, соңында барлық элементтер өзінің орынын тауып реттелген массив түзіледі. Әрине әлі де массив элементтерін қандай тәртіппен таңдап салыстыру қажетті екенін анықтамадық. Салыстырудан кейін кезекті тексеруге келетін массив элементі осы массивтің қандай бөлігіне орналасатыны және оны қалай жүзеге асыратыны ашық сұрақ. QuickSort алгоритмінің жұмысын мысалмен көрсетейік.

25,31,7,4,10,18,13,5,21,11,9 массиві берілсін. Тіректік элемент ретінде ең шеткі сол элемент таңдалатын нұсқаны қарастырайық. Алгоритмнің жұмысына қажетті оң жақ (←) және сол жақ (→) сілтемелерді енгізейік. Сол жақ сілтеме сол жақтан массивтің шеткі элементінен бастап оңға қарай жылжиды. Бірінші қадамда бұл x₁ элементі. Оң жақ сілтеме сол жаққа қарай жылжиды, массивтің оң жақ шетіндегі элемент x_n –нен бастап жылжиды. Сол жақ сілтеме тіректік элемент x_i1 бастап, бірінші қадамда x_i1= x₁ болады, x_i элементін іздейді. Бұл элемент x_i1< x₁ қасиетке ие болу керек. Егер ондай элемент табылса, онда сілтеме осы элементке тоқталады. Ал егер ондай элемент табылмаса, онда бастапқы массив кемімелі болғаны болып шығады. Оң жақ сілтеме тіректік элемент x_k1 –дан бастап жылжиды. Бірінші қадамда x_k1= x_n тең. Сілтеме массивтен x_k < x_i1 қасиетке ие x_k элементін іздейді, Егер ондай элемент табылса, онда сілтеме сол элементке тоқталады. Егер табылмаса, онда сол жақ сілтемеге дейін массивтің бөлігі өспелі болғаны болады. Екі сілтеме екі әртүрлі массив элементтерде тоқталды. Яғни x_i , x_k элементтері i ≠ k. Осы элементтердің орынын ауыстырамыз.

Келтірген амалдарды қайталаймыз. Сітемелер массивтің 6ip элементінде кездессе, тіректік x_i1 элемент сілтемелер кездескен элементке «дейін» немесе «кейін» орнын ауыстырады. Жаңа этаптың басында бектілген элемент массивтегі екі бөлікке беліп, реттелінетін массивтің өзінің түпкілікті орынын табады. Жаңа этапта алгоритм массивтің кай бөлігінде сұрыптаманы жүргізуді шешеді. Процедураны жалғастыру ушін қай массив бөлігін таңдау қажетілігі маңызды кағидалық сұрақ. Теориялық негізделген кағида б/ша массивтің 2 бөлік/ң кішісі таңдалады деп жауап береді. Мысалымызға оралсақ, бұл жағдайдың шешімін анық байқауға болады. *-мен түпкілікті орны анықталатын элемент/ белгіленген, кейбip 6ip типті қадам/ көрсетілмеген:

25.31.7.4.10.18.13.5.21.11.9

25.31.7.4.10.18.13.5.21.11.9

25,9,7,4,10,18,13, 5,21,11,31

.....................................

25,9,7,4,10,18,13, 5,21,11,31

9, 7, 4, 10,18, 13, 5, 21, Ц, 25*, 3i*

9, 7,4,10,18,13, 5,21,11,...

9, 7,4,10,18,13, 5,21,11,...

9, 7,4,5,18,13, 10,21,11,...

....................................

9, 7,4,5,18,13, 10,21,11,...

7, 4,5,9*,18,13, 10,21,11,...

7,4,5,...

7,4,5,...

4*, 5*, 7*, 9*, 18, 13,10,21,11,...

...18,13,10, 21,11,...

...18,13,10,11,21,...

...18,13,10,11,21,...

...13,10, 11, 18*,21*,.:.

...13,10,11,...

...13,10,11,...

...10*, 11*, 13*,...

4*, 5*, 7*, 9*, 10*, 11*, 13*, 18*, 21* 25*, 31*

24. Пирамидалы сұрыптау алгоритмі (Heap_sort) және оның ерекшеліктері

Қарастырылатын алгоритм таңдаумен (элементті) сұрыптау алгоритм/і классына жатады. Бірақ бұл алгоритмнің өзінің ерекше қасиет/і бар. Біріншіден, бастапқы массив бинарлы ағашпен беріледі. Бұл бинарлы ағаш құрылысы жағынан ерекшеленіп келеді, ондай ағаштарды толықтау ағаштар деп атайды.

3.1. а) сурет 3.1. б) сурет

Реттеу процессі екі этаптан тұрады. Бірінші этапта пирпмида тәріздес ағаш түзіледі. Бұл этаптың кез-келген қадамында ағаш 3.1 а және 3.2 б сурет/інде көрсетілгендей. 1-этаптың нәтижесі келесі қасиет/ге ие пирамида болады: ағаш түбірінен қорытынды төбеге шығатын кез-келген жолында түйіндер кемімелі, дәлелдеп айтқанда өспелі емес ретпен орналасады; пирамида ағаштың жоғарыдан төменге, сол жақтан оңға қарай түзіледі. 2-этапта құрылған ағаш-пирамидасында түйінд/іне бекітілген.

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

25. Newman_sort және оның ерекшеліктері

Тоғыстырып сұрыптау. Шапшаң сұрыптау алгоритмдердің тағы бір өкілі – тоғыстырып сұрыптайтын алгоритмді атауға болады. Ондай алгоритмдер жеткілікті дәрежеде жоғары шапшаңдықты, алайда бір ерекшелігі қосымша О (n) –ға жуық жад ұяшықтарын талап етеді. Тоғыстырып сұрыптайтын алгоритмдер екі реттелген массивті тоғыстыру алгоритмдерінен туындаған, сондықтан алдымен осы алгоритмнің идеясын қарастырған жөн болады. Екі реттелген массив берілсін. А массивінің өлшемі n болсын, B массивінің өлшемі m-ге тең болсын.Осы екі массивті тоғыстырайық. Тоғысқанда сұрыпталған массивті түзуіміз қажет. Тоғысқан массивті С деп белгілейік, өлшемі n+m тең. С массивінің элементтерін с= min (a,b), мұнда а А, b B ережесімен тағайындайық. Егер А мен B массивінің өлшемі екіншісінен көп болса, онда калдық элементтер С массивінің бос ұяшықтарына жазылуы тиіс. Бұл алгоритмнің орташа салыстыру саны min (n,m)+1 мәніне жақын болады.Алгоритмнің программалық нұсқасын көрсетейік.

Procedure merge (a,m,b,n,c);

…

Begin i:=1; j:=1;

For k:=1 to n+m do

Begin if i>n then goto N;

If j>m then goto M;

If a[i]<b[j] then

M: begin c[k]:=a[i]; i:=i+1; end

Else

N: begin c[k]:=b[j]; j:=j+1; end

End

End

Итерациялы тоғыстырып сұрыптау. N өлшемді массивті өлшемі 1-ге тең n ішкі массивке бөледі, бөлінген массивтер бірінші этапта өлшемі 2-ге тең реттелген массив құрып тоғысады. Қалған этаптарды осылайша жалғастырып, нәтижесінде тоғыстырылып сұрыпталған n өлшемді массив құрады. Массивті сұрыптауға кеткен этаптар саны [ log,n]+1 тең. Егер әр этапта n-нен артық емес салыстыру қажет болса, онда массивті сұрыптауға қажет салыстыру мен алмастыру саны nxlog₂n тең болады. Бұл баға элементтерді жұптап салыстыруға негізделген процедуралар үшін теориялық күрделіліктің төменгі шегі болып табылады.

Итерациялық тоғыстырып сұрыптау алгоритмдерін алмастыру санын кеміту арқылы шапшаңдатуға болады,яғни берілген массивте алгоритмнің жұмысы басталмай тұрып сұрыпталған ішкі массивтер болуы және тіпті оларың кейбіреулері бір элементтен ғана тұруы мүмкін. Мұндай жағдайда сұрыпталған бөліктердің өлшемдері үлкендерін тоғыстыра отырып процедураны шапшаңдатуға болады. Newmansort алгоритмінің программалық нұсқасы:

Procedure Neumannsort (a,b,n,z);

begin…

Procedure P (a,b,n,k);

Begin …

I:=1; k:=1; d:=1; j:=n; s:=n;

K:

L: if then go to if then Q else N;

If then go to M;

If a[i]<a[j] then

M: begin b[k]:=a[i]; i:=i+1;

If a[i]<a[i-1 ] then := true and else

N: begin b[k]:=a[j]; j:=j-1;

If a[j]<a[j+1] then := true; end else

K:=k+d; go to if i≤j then L else R;

Q: r:=k; k:=s; s:=r; d:=-d; go to K;

R: end P;

A: P (a,b,n,k);

If k>n then z:= false

Else begin P (b,a,n,k);

If k>n then z:=true

Else go to A; end;

End Newman sort

4,9,16,15,19,6,14,20,8,1 массивінің негізінде Newmansort процедурасын бейнелейтін мысал қосымша түсініктеме беруді қажет етпейді:

Мысал:

1-ші қадам 1,4,8,9,16,20,6,19,15,14

2-ші қадам 1,4,8,9,14,15,16,19,20,6

3-ші қадам 1,4,6,8,9,14,15,16,19,20

26. Экстремальды қасиеттері бар бинарлы ағаштың арнайы ішкі класс/ы

Ағашты ұсынудың ең қарапайым түрі әдеттегі құрылымды массив.

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Х10

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

Х1

Х2

-

Х3

-

-

-

Х4

-

-

-

-

-

-

-

Х5

Мұнда жады қажеттісінен көп артық талап етіледі.

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

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

· Бинарлы ағаш тұрғызуалгоритмі және олардың арнайы ерекшеліктері

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

· Экстремалды қасиеттері бар бинарлы ағаштың ішкі класстары

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

· Бинарлы ағаштармен жасалатын стандартты операциялар.

27. Бинарлы ағаштар қолданыстары және жалпылаулары

Бинарлы ағаш тәрізді құрылыс/конструкция/ практикалық жүйелерде қолданылғанымен, бинарлы ағаштардың Computer science аймағының өзінің ішінде қолданылуының көбірек маңызы бар. Бинарлы ағаштың қолданылуының бір түрімен оның айналымдарын анықтау кезінде таныстық, онда бинарлы ағаш арифметикалық өрнектерді көрсету үшін қолданылады.

Бинарлы ағаштың қолданылуының классикалық және анағұрлым көбірек айтылатын түріне минималды артықшылықтың Хаффман-код аталатын кодын құру үшін қолданылатын бинарлы ағаш жатады. Бинарлы ағаштардың шектелген – детерминдалған функцияларды беруде қолданылу мысалдары белгілі, мұндай функция/ туралы ғылымда бұл ағаштар арнайы атөа ие болады – нөмірленген ағаш/.

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

Бинарлы ағаш/ң машиналық графикада. М/ы, жазықтықта іздеу есебін шешу үшін ж/е бақылау нүктесінің орнын ауыстыру кезінде статикалық сахнаның үшбұрыш/ң көрінісінің реттілігін анықтау есебін шешу үшін қолданылады.

Жалпылау/. Жалпы құрылым болып табылатын әдеттегі ағаш ж/е граф түсінік/і программа сияқты динамикалық объектінің қасиет/ін сипаттауда ж/е зерттеуде ыңғайлы ж/е жеткілікті емес. Осы мақсат/ға анықтау/ жасау қажет болады. Осыған байланысты XX ғ. 50 – жыл/ң соңында, 60 – жыл/ң басында Ляпунова А.А., Янова Ю.И., Калужина Л.А., Лаврова С.С., Ершова А.П., Мартынюка В. жұмыс/ң арқасында теоретикалық программалауың негізін қалаған фундаменталды түсінік – операторлық схема түсінігі пайда болды. Осы теория негізінде программа/ды тиімділеу, жадыны экономдау, программаны параллель орындау мүмкіндігі ж/е т.б. есеп/дің тізбегін зерттеуге болады. Марынюк схемасы деп аталатын програманың басқарушы графымен берілетін операторлық схемаға мысал келтірейік.

1.1 сурет

28. AVL ағаштары және оның қолданылуы

Бинарлы ағаштардың бұл класы алдыңғы жағдайдағымен салыстырғандағы тұрғызу алгоритмі күрделі болғанымен маңызды позитивті қасиеттерге ие болады. Бұл тип ағаштар көзге бейсимметриялы көрінуі мүмкін, бірақ оларда ұзын бұтақтар жоқ, оны төменде келтірілген анықтаманы мұқият оқып шыққанда түсінуге болады. Мұндай ағаштың түбірінен шыққан бұтақтың максималды ұзындығы с*log2n, мұнда c=1.44 аспауы тиіс.

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

AVL ағаштарды көбіне баланстандырылған ағаштар деп атайды.

V төбесінен басталатын ағаш бұтағының ұзындығы депосы бұтаққа тиісті төбе/ деңгейінің максималь деңгейі мен V төбесі деңгейі арасындағы айырма аталады. Сонымен, бұтақ ұзындығы деп осы бұтаққа тиісті ең ұзын жолдың ұзындығы алынады. Көбіне ұзындық атауының орнына қосымша ат биіктік қолданылады.

Ағаш төбесі балансы деп берілген төбелерден шығатын оң және сол бұтақтар ұзындықтарының айырмасын айтады.

Егер ағаштың әрбір төбесі үшін баланстың абсолют мәні 1-ден артық болмаса, онда ағашты баланстандырылған (AVL) ағаш деп атайды.

N элементтен тұратын массив бойынша тұрғызылған AVL ағаштағы ең ұзын бұтақтың ұзындығын бағалайық. Бұл үшін L≥1 санын белгілейміз, алдымен максималь ұзындығы L- ға тең бұтақтары бар AVL ағаштар жиынын қарастырамыз. Осы ағаштардың ішінде төбелер саны минимум болатындары да бар. Ары қарай бұл AVL ағаштарын минимальды деп атаймыз.

Енді біз мына функцияны қарастырайық.

n(l)-AVL ағашындағы төбелердің минималь саны, бұтақтарының максималь ұзындығы L≥1 тең. Бұл жерде Шеннон функциясын еске түсіруге болады, бірақ аналогиясы тура болмайды, себебі Шеннон функциясы maxmin функциясы, ал біздің жағдайда maxmin.

AVL ағашқа жаңа төбе қосу кезінде бинарлы ағашты тұрғызудың қарапайым алгоритмі қолданылады. Осылайша, бар болған AVL ағашқа қайта қосылған төбе, оны N арқылы белгілейік, ағаш түбірі мен жаңа төбені қосатын ерекшеленген деп аталатын жол үшін ақырғы төбе болып табылады. Жаңа төбелерді қосу ағаш балансын бұзатын жағдайда ағаштан N төбесі алған позиция ақырғы болмауы мүмкін. Жаңа төбе қосу кезінде тек ерекшеленген жол бойындағы төбелер балансы өзгеретінін ескерсек, онда қосқаннан кейін осы жол бойындағы төбелер балансын ғана қайта есептеу керек. Сонда егер олардың ең болмағанда біреуіндегі баланс мәні ± 2 тең болса, онда жартылай және онша қиын емес ағашты қайта тұрғызу жүргізу керек.

AVL ағашқа жаңа төбелер қосу есебі шешімін корректі түрде жүргізетін жалпы талаптарға тоқталып кетейік: