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



бет8/8
Дата05.06.2017
өлшемі1,51 Mb.
#18191
1   2   3   4   5   6   7   8

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

Тақырыбы:Іздеу есептерінде ағаштарды қолдану: бинарлық, кездейсоқ бинарлық, оптималды және балансталған іздеу ағаштары.


Жалпы мәлімет

Іздеу (поиск) екіге бөлінеді:

  1. Тізбектеліп іздеу.

  2. Бинарлық іздеу.




  1. Тізбектеліп іздеу. Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады.

Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады.




  1. Бинарлық іздеу.

Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады. Бинарлық іздеудің алгоритмі:

  1. Массивтің ортаңғы элементінің индексін табу: mid=(low+high)/2.

  2. Орталық элементтің мәнін кілтпен салыстыру «Key». Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз.

  3. Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз.


Мысалға: Бүтін сандар тұратын А массиві берілсін. 33 кілті берілген элементі бар табу керек.

Мысал элементтері: А




0

1

2

3

4

5

6

7

8

-7

3

5

8

12

16

23

33

55

Low=0


High=8

mid=4


33>A(mid) 0 1 2 3 4 5 6 7 8

-7

3

5

8

12

16

23

33

55

mid
Low=5

High=8


mid=6

33>A(mid)


0 1 2 3 4 5 6 7 8

-7

3

5

8

12

16

23

33

55

mid

Low=7


High=8

mid=7


33=A(mid)

Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі.



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

Тақырыбы:Сұрыптау есебін шешу. Ішкі және сыртқы сұрыптаулар.



Жалпы мәлімет

Қарапайым таңдау әдісімен сұрыптау келесі қадамдарға келтіріледі:



  1. Массивтың ең үлкен элементінің номерін орнату.

  2. Массивтың ең үлкен және соңғы элементтерінің орындарын ауыстыру.

  3. Соңғы элементті жайына қалдырып, 1 мен 2 пунктты массивтың қалғандарына (соңғы элементсіз) қайта орындау.

  4. 3 пунктты массивтың қалдығы бір элементке дейін қысқарғанша қайталау.


Мысалы: сұрыптау процедурасын программаларды жобалаудың тілінде (псевдокодта) сипаттаймыз.
For i := n downto 2 do

Begin


Максимальды элементті табу а[1], ..., a[i];

Оның индексын k айнымалысында сақтау;

егер i<>k болса, a[i] мен a[k] орындарын ауыстыру;

End;
Бес элементтен тұратын массивтың мәндері былайша өзгереді: (30,20,10,50,40)


30 20 10 50 40

30 20 10 40 50

30 20 10 40 50

10 20 30 40 50

10 20 30 40 50


Ең үлкен элементті іздеу аймағының асты сызылған.
Бақылау сұрақтары:
1. Массивты сұрыптау деген не?

2. Кему реті бойынша сұрыптаудың өспелі рет бойынша сұрыптаудан айырмашылығы неде?

3. Қарапайым таңдау әдісімен сұрыптау арқылы массив элементтерін сұрыптау идеясын сипатта.

4. Бір қадамды орындау уақыты массивтың реттелмеген бөлігінің өлшеміне неліктен тура пропорционал?


Тапсырмалар варианттары:
Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.


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

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

  3. Массивты сұрыпта, массивтегі қайталанбайтын сандардың санын есепте.

  4. Сұрыптау процедурасын I параметры мәні әрбір қадамда өсетіндей етіп өзгерт.

  5. Қарапайым таңдау әдісі көмегімен массивтың жұп элементтерін сұрыпта.

  6. Қарапайым таңдау әдісі көмегімен массивтың тақ орындарда тұрған элементтерін сұрыпта.

  7. Қарапайым таңдау әдісі көмегімен массивтың оң элементтерін сұрыпта.

  8. Қарапайым таңдау әдісі көмегімен массивтың теріс элементтерін сұрыпта.

  9. n*m матрицасында бағандарды өсу реті бойынша сұрыпта.

  10. Футбол командаларының тізімі және чемпионатта әрбір команда алған ұпайлар саны берілген. Ұпайлар саны бірдей командалар жоқ екендігі белгілі. Жүлдегерлерді басып шығар.

  11. Реттелмеген массивте қайталанатын элементтер болуы мүмкін. Бірдей элементтер тобының ішінен біреуін ғана қалдыру керек.

  12. Жарсытың турнирлік кестесі А квадрат матрицасы арқылы берілген. Aij әрбір элементі i командасының j командасының қақпасына соққан голдар саны. Диагональ бойымен әрбір команданың орынын орналастыру керек (жеңілістерінің санын алып тастағандағы жеңістер саны бойынша, тең түскен жағдайда соғылған гол мен жіберілген голдардың айырмасы бойынша).


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

Тақырыбы:Сұрыптау есебін шешу. Сұрыптау алгоритмдері.


Жалпы мәлімет

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


Мысалы: 5 1 8 4 9 элементтерінен тұратын массивты қарапайым ауыстыру әдісімен өспелі түрде реттейміз. Массивтың ағымдағы бөлігінің ұзындығы n-k+i, k – қарап шығу номері, i – ізделетін жұптың номері, п – k соңғы жұптың номері.

.

Бірінші қарауда барлық массив қарастырылады.


i = l5 4 8 2 9

> ауыстырамыз

i = 24 5 8 2 9

< ауыстырмаймыз

i = 34 5 8 2 9

> ауыстырамыз

i = 44 5 2 8 9



<
9 өзінің орнында тұр.
Екінші қарау: массивты бірінші элементтен төртінші элементке дейін қарастырамыз.
i = 14 5 2 8 9

< ауыстырмаймыз

i = 24 5 2 8 9

> ауыстырамыз

i = 34 2 5 8 9



< ауыстырмаймыз
8 өзінің орнында тұр.

Үшінші қарау: массивтың қарастырылып отырған бөлігі алғашқы үш элементті қамтиды.

i = 14 2 5 8 9

> ауыстырамыз

i = 22 4 5 8 9

< ауыстырмаймыз
5 өзінің орнында тұр.
Төртінші қарау: соңғы жұпты қарастырамыз.
i = 12 4 5 8 9

< ауыстырмаймыз

4 өзінің орнында тұр.

Ең кіші элемент (2) үшін тек бірінші орын ғана қалады.

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


Бақылау сұрақтары:
1. Массивтың екі элементінің орынын қалай ауыстырады?

2. Кірістірілген циклдар деген не?

3. Қарапайым таңдау әдісі мен қарапайым ауыстыру әдісінің айырмашылығы қандай?
Тапсырмалар варианттары:

Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.

Барлық варианттарға «көпіршік» сұрыптау процедурасын қолдану керек.

1. Ең жақсы және ең жаман жағдайлардағы орындалған ауыстырулар мен салыстырулар санын есепте.

2. Берілген қатардың n алғашқы элементтерін өсу реті бойынша орналастыр. Осы элементтерді кему реті бойынша басып шығар.

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

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

Тақырыбы:Сұрыптау есебін шешу. Сұрыптау алгоритмдері: таңдау арқылы сұрыптау, жылдам және таратпалы сұрыптау.


Жалпы мәлімет

Массивтерді сұрыптау алгоритмдері 4-ке бөлінеді:



  1. Таңдау арқылы сұрыптау.

  2. Ауыстыру арқылы сұрыптау (көпіршік әдіісі).

  3. Қою арқылы арқылы сұрыптау.

  4. Тез сұрыптау.


Сұрыптау немесе объектілер тізімін реттеу деп осы объектілердің қандай да бір сызықтық реттілікке қатысты өсуі мен кемуі бойынша орындауды айтамыз. Сұрыптаудың мәні сонда жазулар тізімінің реттілігін кілттік өріс мәндері кемімейтін тізбек құратындай етуіміз керек. Басқа сөзбен айтқанда R1, R2, .. , Rn жазулары кілттік мәндері K1, K2,…,Kn орналасуы керек. Ki12<….n.

Мұнда реттелген тізбектегі кілттердің бірдей мәндері бар жазулар бір-бірімен қатар орындалады. Сұрыптау әдістері 2 категорияға бөлінеді:

- массивтерді сұрыптау (ішкі сұрыптау)

- тізбектелген файлдарды сұрыптау (сыртқы сұрыптау).

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

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


Мысалға, 50,20,40,75,35 массив берілген.

0-жүріс. 20-ны таңдаймыз. Оны А0-мен ауыстырамыз (А0=50).

20,50,40,75,35.

1-жүріс. 35 таңдаймыз. Оны А1-мен орын ауыстырамыз.

20,35,40,75,50.

2-жүріс. 40 таңдаймыз. Оны А2-мен орын ауыстырамыз.

20,35,40,75,50.

3-жүріс. 50 таңдаймыз. Оны А3-пен орын ауыстырамыз.

20,35,40,50,75.
Соңғы қалған 75 саны ең үлкен элемент сұрыпталып шыққанда:

20,35,40,50,75.


Сұрыптау – массив өлшеміне ғана тәуелді салыстырулардың белгіленген санына ие болуы керек. i-ші жүрісте (A… A)-ге дейінгі элементтердің салыстырулар саны (n-1-(i+1)+1)=n-i-1 тең болады.

Салыстырулардың жалпы саны мына формуламен анықталады:

Алгоритмнің күрделілігі – О(n) тең болады.


Ауыстыру арқылы сұрыптау.

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

Мысал. Массив:

50,20,40,75,35

0-жүріс. 50 мен 20салыстырылады.

20,50,40,75,35

1-жүріс. 50 мен 40 салыстырылады

20,40,50,75,35

2-жүріс. 50 мен 70 реттелген, сондықтан қалады.

20,40,50,70,35

3-жүріс.75 пен 35 салыстырылады.

20,40,50,35,75

4-жүріс. 50 мен 35 салыстырылады

20,40,35,50,75

5-жүріс. 40 пен 35 салыстырылады

20,35,40,50,75

20 мен 30 реттелген

20,35,40,50,75 болып реттеледі.
Массивтегі жүрістер саны минимальды немесе максимальды элемент қай жерде орналасқанына байланысты. Мұнда бірінен кейін бірі келетін жүрістердің бағытын ауыстыру арқылы жылдамдатуға болады. Мұндай алгоритм Шейкер сұрыптауы деп аталады.

Есептеу күрделілігі. Массив реттелген болған жағдайда бүкіл тізім бойынша 1 ғана жүріс өтеді. Мұнда тиімділігі О(n)-ға тең. Ал ең тиімсіз жағдайда i-1 жүріс орындалады және i-ші жүрісте n-i-1 салыстыру жүргізіледі. Ең тиімсіз жағдайда тиімділігі О(n2) тең. Жалпы жағдайда таңдау арқылы сұрыптау көбікше арқылы сұрыптауға қарағанда ауыстырылатын сан аздығымен тиімді болады. Шейкер сұрыптау алгоритмі элементтердің барлығы немесе көпшілігі сұрыпталған жағдайда пайдаланған тиімді.

Тапсырмалар варианттары:

Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.

Өткен әдістерді есептерге қолданып көр:

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

2. Кему реті бойынша «көпіршік» сұрыптау процедурасын жазу керек.

3. Берілген қатардағы ең кіші элементтен үлкен екінші элементті табу керек.

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

Тақырыбы:Бинарлы ағаш негізінде сұрыптау. Топологиялық сұрыптау. Рекурсивті сұрыптау. Сұрыптау әдістерін салыстыру


Жалпы мәлімет

Қою арқылы сұрыптау

Қою арқылы сұрыптау – келесі процеске ұқсас. Карточкаларға аттарды жазып, карточкаларды алфавит бойынша өзіне керекті орынға қыстырып қою арқылы реттеу. Мысалға:

50,20,40,75,35 массивін қыстыру арқылы сұрыптау керек.

50 элементінен бастаймыз. 20-ны 0 позициясына қыстыру, 50-ді 1 позициясына жылжыту.

40-ты 1 позициясына қыстыру, 50-ді 2 позицияға жылжыту.

75-ті 3 позициясына қыстыру.

35-ті 1 позициясына қыстыру, қалғандарын оңға қарай жылжыту.

Есептеу күрделілігі: жалпы салыстырулар саны -ге тең. Ең жақсы жағдайда, яғни тізім реттелген жағдайда күрделілігі О(n)-ге , ал жаман жағдайда О(n2)-ге тең.
Бинарлық қоюлар арқылы сұрыптау.

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



Есептеу күрделілігі: Енгізу орыны табылады егер, al<=item<=ar болса. Соңында іздеу интервалы 1 ге тең болуы керек; бұл дегеніміз I элементтерден тұратын интервал ортасынан (log2i) рет бөлінеді деген сөз.

Салыстырулардың минимальды саны барлық элементтер кері ретпен орналасқанда, ал максимальды саны олардың осы кезде реттелген болғанында талап етіледі.


Тез сұрыптау
Тез сұрыптау әдісі – күнделікті тәжірибеден алынған.

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

Сұрыптау принципі:

Массивтің орталық элементі таңдап алынады. Массивтің барлық элементтері солдан оңға және оңнан солға қарай қарап өтіледі.

І. Солдан оңға қарай қозғалғанда A[scan up] деген элементті іздейміз және бұл элемент орталық элементтен үлкен болуы керек, оның позициясын есімізге сақтап аламыз. Оңнан солға қарай қозғалғанда A[scan down] деген элементті іздейміз. Ол элемент орталық элементтен кіші немесе тең болады. Позициясын есте сақтаймыз. Табылған элементтердің орындарын ауыстырамыз және scan up және scan down индекстері қиылысқанша іздеуді жалғастырамыз.

1-этапты орындап болғаннан кейін алғашқы масситің элементтері орталық элементке бөлінеді.

2-этапта 1-этаптың әрекеттері массивтің оң жақ және сол жақ бөліктері үшін жеке-жеке орындалады.

3-этапта осы әрекеттердің барлығы 4 бөлігі үшін жеке-жеке орындалады.

4-этапта 4 бөлігі жеке-жеке орындалады.

Есептеу күрделілігі. Тиімділік анализі кей жағдайда ғана мүмкін болады. Айталық, массив элементтер саны n=2 (K=log2n) 1-сканерлеуде n-1 салыстыру жүргізіледі. Оның нәтижесінің өлшемі өлшемді ішкі тізім пайда болады. Өңдеудің келесі фазасында әрбір ішкі тізім үшін n/2 салыстыру қажет болады. Осылайша, бөлу процесі табылған ішкі тізімдер тек бір ғана элементтер тұрғанша К жүрістен кейін аяқталады. Мұндағы салыстырулардың жалпы саны мына формуламен анықталады: n*k=n*log2n. Жалпы түрдегі тізім үшін есептеу күрделілігі – О(n log2n) тең болады. Ал ең нашар жағдайда орталық элемент ең кіші элемент болғанда есептеу күрделігі O(n2) тең болады.
Сұрыпталған тізбектерді біріктіру
Екі А жіне В реттелген тізімдер берілген. Оның ұзындықтары сәйкесінше m және n. Біріктіру нәтижесінде ұзындығы m және n болатын С реттелген тізімін алу қажет. әрбір элемент бойынша біріктіру жүргізіледі. Ағымдағы өткізу нүктесі әрбір тізімнің басына орналасады. Ағымдағы нүктедегі мәндер салыстырылады. Нәтижесінде солардың кішісі массивке көшіріледі. Тізбектегі мән өңделіп болғаннан кейін келесі санға бір қадам жасалады да, салыстыру жалғастырылады.

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


Сұрыпталған тізбектерді біріктіру алгоритмі
Бір тізбек немесе тізбектің екеуі де біткенше келесі әрекеттерді орындау керек. Яғни, егер 1-тізбектің 1-элементі 2-тізбектің элементіне тең немесе кіші болса, онда оны шығатын тізбекке жазып қойып, 1-тізбектің келесі элементіне көшу керек. Әйтпесе, шығатын тізбекке 2-тізбектің элементін жазып, 2-тізбектің келесі элементіне көшу керек. Одан кейін шығатын тізбектің келесі элементіне көшу керек.

Егер біреуі аяғына дейін өңделмесе, онда сол қалдықты шығатын тізбекке көшіру керек.



Тапсырмалар варианттары:

Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.

Өткен әдістерді есептерге қолданып көр:

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

2. «Көпіршік» сұрыптау әдісінде, егер қандай да бір екі көршілес элемент реттелмеген болса (мысалы, a[4] пен a[5]), олар ауыстырылады, одан кейін алгоритм келесі жұпты a[5] пен a[6] салыстыруға көшеді. Оның орынына a[4] элементін ғана қарап, оның қатардың жоғарғы жағына жүіп шығуына мүмкіндік беруге болады. Ол үшін a[4] пен a[3] салыстырамыз. Егер a[3] үлкен болса, ауыстыру жүргіземіз де, a[3] пен a[2] салыстырамыз. Осы көрсетілген әдісті жүзеге асыр.

3. Бүтін санды массивте бірдей элементтердің ең үлкен санын тап.

4. N бүтін сан берілген, a мен b аралығында неше сан жатыр?

4.Студенттердің өздік жұмыстар жоспары

ОСӨЖ №1
Тақырыбы: Сұрыптау есептері. Сұрыптау алгоритмдері

Мақсаты: Программа құру және оны жүктеу

Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру

ОСӨЖ №2
Тақырыбы: Сұрыптау есептері. Қою арқылы сұраптау

Мақсаты: Программа құру және оны жүктеу

Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру
ОСӨЖ №3
Тақырыбы: Сұрыптау есептері. Таңдау арқылы сұрыптау

Мақсаты: Программа құру және оны жүктеу

Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру

ОСӨЖ №4
Тақырыбы: Іздеу есептерінің шешілімі. іздеу: қайтару арқылы теріп алу.

Мақсаты: Программа құру және оны жүктеу

Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру

ОСӨЖ №5
Тақырыбы: Іздеу есептерінің шешілімі.

іздеу: тармақтар және шекаралар әдісі, динамикалық программалау, тереңге іздеу



Мақсаты: Программа құру және оны жүктеу

Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру

ОСӨЖ №6
Тақырыбы: Жылдам іздеу: массивтен бинарлық және кезекті іздеу, М-блоктық іздеу. Сызықты тізімнен таңдау.

Мақсаты: Программа құру және оны жүктеу

Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру

СӨЖ №1
Тақырыбы: «Ассоциативті тізімдер»;
Мақсаты: Тізімдер. Тізім түрлерін қарастыру.

Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу
СӨЖ №2
Тақырыбы: «Тізімдерді қайта ұйымдастыру»;

Мақсаты: Тізімдерді ұйымдастыру

Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу
СӨЖ №3
Тақырыбы: «Пирамидалы сұрыптау»;

Мақсаты: Сұрыптау есебін қарастыру

Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу
СӨЖ №4
Тақырыбы: «Мекен-жайды есептеу арқылы сұрыптау»;

Мақсаты: Сұрыптау есебін қарастыру

Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу

БАҚЫЛАУШЫ - ӨЛШЕМДІК ҚҰРАЛДАР


  1. Мәліметтерді өңдеудің құрылымдары мен алгоритмдері түсінігі.

  2. Статикалық және динамикалық құрылым мәліметтері.

  3. Мәліметтер құрылымдарымен орындалатын амалдар. Мысал.

  4. Алгоритмдер анализы.

  5. Сұрыптау және іздеу.

  6. Массивтерді сұрыптау алгоритмдері.

  7. Таңдау арқылы сұрыптау.

  8. Ауыстыру арқылы сұрыптау.

  9. Қою арқылы сұрыптау.

  10. Жылдам сұрыптау.

  11. Іздеу есептері. Тізбектелген іздеу.

  12. Іздеу есептері. Бинарлық іздеу.

  13. Файлдар. Сыртқы тасымалдаушылардағы мәліметтермен амалдар орындау. Сыртқы сұрыптау.

  14. Файлдар. Сыртқы тасымалдаушылардағы мәліметтермен амалдар орындау. Табиғи бірігу арқылы сұрыптау.

  15. Байланған сызықтық тізімдер.

  16. Тізімдерде іздеу әректтерін жүргізу

  17. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Бір байланысты сызықтық тізім.

  18. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Реттелген тізімді жасау.

  19. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Циклдық тізімдер.

  20. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Екі байланысты сызықтық тізім

  21. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Стектер.

  22. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Кезектер ұғымы.

  23. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Басымдықтар кезегі.

  24. Ағаштар. Негізгі ұғымдар.

  25. Ағаш тәрізді құрылымды беру әдістері.

  26. Екілік бинарлық ағаштар.

  27. Екілік ағаштардың құрылымы.

  28. Өрнектердің екілік ағаштары.

  29. Екілік іздеу ағаштары.

  30. Екілік ағаштармен жүргізілетін амалдар.

  31. Екілік іздеу тармағынан элементті алып тастау.

  32. Массивтермен берілген бинарлық ағаштар.

  33. Массивтермен берілген бинарлық ағаштар.Турнирлік сұрыптау.

  34. Массивтермен берілген бинарлық ағаштар. Пирамидалар түсінігі.

  35. Массивті пирамидаға түрлендіру.

  36. Пирамидаға элементтерді қосу және одан элементтерді алып тастау.

  37. Пирамидалық сұрыптау.

  38. Балансталған ағаштар.

  39. Графтар, олармен жүргізілетін амалдар

  40. Графтар. Көршілестік матрицасы.


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет