«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері»

1. 
   Массивті пирамидаға түрлендіру.
   
2. 
   А(0)-ді тізбетеп жоққа шығару және оны А(n-1), А(n-2) т.с.с А(1)-ге дейін қосу. Пирамидалық сұрыптау процесінде кезекті ең кіші элементтер өшіріліп отырады да, тізбекті түрде массивтің соңғы жағына орналасады. Осылайша, кему реті бойынша сұрыпта жүргізіледі. Мысал: А(5)=(50,20,75,35,25).
   

Мысалға А(5)=(50,20,75,35,25)

1. 20-ны өшіріп, А(4)-ке сақтаймыз:

2. 25-ті өшіріп, А(3)-ке қоямыз:

3. 35-ті өшіріп, А(2)-ге қоямыз:

4. 50-ді өшіріп, А(1)-ге қоямыз:

Сонымен, түбірі ғана қалғандықтан, массив сұрыпталды.

n элементтен тұратын массив тереңдігі k=log₂n болатын аяқталған бинарлық тармаққа сәйкес келеді. Массивті пирамидаға түрлендіру n/2 операциядан тұрады. Олардың әрқйсысы k салыстырудан артық салыстыруды қажет етпейді. Сұрыптаудың екінші фазасы n-1 операциясын қажет етеді. Олардың әрқайсысы k салыстырудан тұрады. Пирамидалық сұрыптаудың ең жаман жағдайдағы күрделілігі k*n/2+k*(n-1)=((3n/2)-1) log₂n тең болады. Алгоритмнің күрделілігі мынадай ретке тең: O(n log₂n).

Пирамидалық сұрыптау қосымша жадыны қажет етпейді. Ал мысалға турнирлық сұрыптауға қосымша жаңа массив жасалу қажет.
Дәріс 15.

Балансталған тармақтар. Графтар.

Мақсаты: Балансталған тармақтар ұғымын енгізу. AVL тармақтары, балансталған тармақтарға қосу, алып тастау әрекеттерін түсіндіру. Графтар. Негізгі ұғымдары мен анықтамаларын беру. Көршілестік матрицасы, инцидиенттік матрицасы түсініктері.
Негізгі ұғымдар. Бинарлық тармақтар алпы мәліметтерге қол жеткізуге арналған. Идеалды яғни ең жақсы жағдайда тармақ балансталған болады және реттілік биіктігі O(nlog₂n)-ға тең болады. Алайда, кейбір мәліметтер үшін тармақ туындаған болуы мүмкін. Онда оның биіктігі O(n)-ға тең болады және мәліметтерге кіру әжептәуір ақырындайды.

Тармақ балансталған болады сонда тек сонда ғана егер әрбір түйін үшін оның екі бұтағының биіктігі бір-бірінен бірге ғана айырмашылығы болса. Балансталған тармақтарды AVL тармақтар деп атайды (Ойлап тапқандардың фамилиялары бойынша – Адельсон-Венский-Ландис).

AVL тармақтар берілуі іздеудің бинарлық тармағына ұқсас болады. Барлық операциялар ұқсас тек қана тармаққа қою және тармақтан алып тастау операциялары өзгеше. Сол жақ және оң жақ бұтақтың арақатынасы туралы ақпаратты сақтау үшін түйіннің типі анықтамасына ө р і с қосылады. Ол өріс сол жақ және оң жақ бұтақтың айырмасын көрсететін баланстық көрсеткіш. Егер баланс –1-ге тең болса, онда түйіннің сол жағы басады. Себебі, сол жақ бұтақтың биіктігі көп. Ал, баланс оң болса, онда түйін оңға қарай тартады. Жалпы биіктігі бойынша балансталған тармақ баланс -1-ге тең болады. Ал AVL тармақтары [-1;1] араларында тербеледі.

1. 
   Тармақта кілт жоқ болғанша іздеу жолымен жүре беру.
   
2. 
   Жаңа түйін қосу және баланыстылықтың жаңа көрсеткішін анықтау.
   
3. 
   Іздеу жолымен қайтадан жүру және әрбір түйін үшін баланстылық көрсеткішін тексеру.
   

1-жағдай. Іздеу бағытындағы түйін басынан бастап балансталған деп есептейміз. Яғни балнс 0-ге тең. Бұтаққа жаңа элементті қосқаннан кейі, түйін қосу қай жақ бұтаққа жүргізілгеніне байланысты солға немесе оңға тарта бастайды. Егер элемент сол жақ бұтаққа қосылған болса, онда баланстық көрсеткіш -1-ге тең, ал оң жақ бұтаққа қосылған болса, баланстық көрсеткіші +1-ге тең болады.

Осы балансталған тармаққа 55 деген түйінді қосамыз:

2-жағдай. Түйіннің бұтағының біреуінің бір жағы басым және жаңа элемент жеңіл бұтаққа қосылады да, түйін балансталған болып өзгереді.

55 түйінін қосқаннан кейін:

3-жағдай. Түйіннің бұтақтарының бір жағы басым, жаңа элемент неғұрлым ауыр жағына қосылады. Ал олай болса, баланстылық шарты бұзылады. Себебі, баланс [1;1] шегінен аспуы тиіс. Ал тепе-теңдікті сақтау үшін бұрылыс жасау қажет.

жұбы. Мұндағы V-төбелердің құр емес жиыны. E - қабырғалар жиыны. Яғни, төбелер жұбы немесе қабырғалары жиыны деп аталатын мәліметтер элементтері жиынынан тұрады. Төбелер қалаларды көрсететін болса, қабырғалар арасындағы жолдарды көрсетеді.

1250 900

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

V_1, V_{2, ...,} V_n төбелерінің тізімі жол деп аталады. Мұндағы барлық i үшін 1<=i<=n, V_i,V_i+1 қабырғалары болады.

Бағдарланған графта V_1, V_{2, ...,} V_n төбелердің тізімі.

V₁V₂, V₂ V₃,...,V_n-1 V_n бағытталған доға түрінде болады. Графтардағы жол қарапайым деп аталады, егер графтардың төбелері әртүрлі болса. Жолдың ұзындығы осы жолды құрайтын қабырғалардың санына тең болса.

V_i және V_j төбелері байланған деп аталады егер, осы төбелер үшін V_i+1,V_i+2,.., V_j жолы бар болса. Граф байланысшы граф деп аталады егер, оның кез келген төбелер жұптары үшін оларды қосатын қарапайым жол болса.

Цикл дегеніміз - ұзындығы бірден кем болмайтын бір төбеден басталып сол төбеден аяқталатын қарапайым жол.

Графтардағы тармақ дегеніміз – бұл циклсыз графтар. Графтар өлшенген деп аталады егер, графтың әрбір қабырғасына мәні немесе салмағы жазылса.

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

Графтарды берудің келесідей әдістері бар:

1. 
   Инцидиенттік матрицасы.
   
2. 
   Көршілестік матрицасы.
   
3. 
   Салмақтық матрицасы.
   
4. 
   Қабырғалар тізімі.
   
5. 
   Көршілестік тізімі.
   

Қандай да бір нақтылы есепті шығару үшін қолдану қолайлылығына қарай осы әдістердің кез келгенін пайдалануға болады.

Инцидиенттік матрицасы дегеніміз – размері nm болатын матрица. Мұндағы n-төбелер саны, m-қабырғалар саны. Бағытталған граф үшін х,у қабырғаларына сәйкес келетін баған, у төбесіне сәйкес келетін жолда 1 болады. Ал х төбесіне сәйкес келетін жолда -1 болады, қалған жолдарда 0 болады. Тұзақ жағдайында басқа сан берілуі мүмкін. Яғни, хх болғанда 2 деген сан беріледі. Мысалы,
1 2 4 5

3 6

граф берілген, оның инцидиентті матрицасын жазамыз:
(1,2) (1,3) (3,2) (3,4) (5,4) (5,6) (6,5)

Бағытталған граф үшін х,у қабырғасына сәйкес келетін баған х,у төбесіне сәйкес келетін жолда 1 болады да, қалған жолдарда 0 болады.

2 4

1 6

3. 
   5
   

(1,2)(1,3)(1,5)(2,3)(2,5)(3,4)(4,5)(4,6)(5,6)

Графты инцидиентті матрица арқылы беру үшін nМ элемент қажет болады және олардың көбі 0 болады. Инцидиентті матрица ЭЕМ-ға енгізу мен өңдеуге қиын. Сондай-ақ ол қабырғалар туралы тура ақпарат бермейді. Х,у қабырғасы бар ма деген сұраққа жауап беру үшін барлық бағандарды қарап шығу қажет.

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

Достарыңызбен бөлісу: