«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері»
жүктеу/скачать 1,51 Mb.
|
Зертханалық жұмыс №7 Тақырыбы:Іздеу есептерінде ағаштарды қолдану: бинарлық, кездейсоқ бинарлық, оптималды және балансталған іздеу ағаштары. Жалпы мәлімет Іздеу (поиск) екіге бөлінеді: Тізбектеліп іздеу. Бинарлық іздеу. Тізбектеліп іздеу. Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады. Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады. Бинарлық іздеу. Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады. Бинарлық іздеудің алгоритмі: Массивтің ортаңғы элементінің индексін табу: mid=(low+high)/2. Орталық элементтің мәнін кілтпен салыстыру «Key». Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз. Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз. Мысалға: Бүтін сандар тұратын А массиві берілсін. 33 кілті берілген элементі бар табу керек. Мысал элементтері: А
Low=0
High=8 mid=4
33>A(mid) 0 1 2 3 4 5 6 7 8
mid Low=5 High=8
mid=6 33>A(mid) 0 1 2 3 4 5 6 7 8
mid Low=7
High=8 mid=7
33=A(mid) Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі. Зертханалық жұмыс №8 Тақырыбы:Сұрыптау есебін шешу. Ішкі және сыртқы сұрыптаулар. Жалпы мәлімет Қарапайым таңдау әдісімен сұрыптау келесі қадамдарға келтіріледі: Массивтың ең үлкен элементінің номерін орнату. Массивтың ең үлкен және соңғы элементтерінің орындарын ауыстыру. Соңғы элементті жайына қалдырып, 1 мен 2 пунктты массивтың қалғандарына (соңғы элементсіз) қайта орындау. 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 40 50 30 20 10 40 50 10 20 30 40 50 10 20 30 40 50 Ең үлкен элементті іздеу аймағының асты сызылған. Бақылау сұрақтары: 1. Массивты сұрыптау деген не? 2. Кему реті бойынша сұрыптаудың өспелі рет бойынша сұрыптаудан айырмашылығы неде? 3. Қарапайым таңдау әдісімен сұрыптау арқылы массив элементтерін сұрыптау идеясын сипатта. 4. Бір қадамды орындау уақыты массивтың реттелмеген бөлігінің өлшеміне неліктен тура пропорционал? Тапсырмалар варианттары: Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек. Сұрыптау процедурасын сұрыптау элементтердің кему реті бойынша жүргізілетіндей етіп өзгерт. Бүтін сандардың берілген тізбегі кему реті бойынша сұрыпталған ба, тексер. Егер жоқ болса, ретте. Массивты сұрыпта, массивтегі қайталанбайтын сандардың санын есепте. Сұрыптау процедурасын I параметры мәні әрбір қадамда өсетіндей етіп өзгерт. Қарапайым таңдау әдісі көмегімен массивтың жұп элементтерін сұрыпта. Қарапайым таңдау әдісі көмегімен массивтың тақ орындарда тұрған элементтерін сұрыпта. Қарапайым таңдау әдісі көмегімен массивтың оң элементтерін сұрыпта. Қарапайым таңдау әдісі көмегімен массивтың теріс элементтерін сұрыпта. n*m матрицасында бағандарды өсу реті бойынша сұрыпта. Футбол командаларының тізімі және чемпионатта әрбір команда алған ұпайлар саны берілген. Ұпайлар саны бірдей командалар жоқ екендігі белгілі. Жүлдегерлерді басып шығар. Реттелмеген массивте қайталанатын элементтер болуы мүмкін. Бірдей элементтер тобының ішінен біреуін ғана қалдыру керек. Жарсытың турнирлік кестесі А квадрат матрицасы арқылы берілген. 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
4 өзінің орнында тұр. Ең кіші элемент (2) үшін тек бірінші орын ғана қалады. Сөйтіп, массив қарапайым ауыстыру әдісімен өсу ретімен орналастырылды. Бұл әдіс сондай-ақ, «көпіршік әдісі» деп аталады. Бұл атау неғұрлым «жеңіл» элементтер аз-аздап бетіне, жоғары жүзіп шығатын процестің бейнелік интерпретациясынан келіп шығады. Бақылау сұрақтары: 1. Массивтың екі элементінің орынын қалай ауыстырады? 2. Кірістірілген циклдар деген не? 3. Қарапайым таңдау әдісі мен қарапайым ауыстыру әдісінің айырмашылығы қандай?
Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек. Барлық варианттарға «көпіршік» сұрыптау процедурасын қолдану керек.
Тақырыбы:Сұрыптау есебін шешу. Сұрыптау алгоритмдері: таңдау арқылы сұрыптау, жылдам және таратпалы сұрыптау. Жалпы мәлімет Массивтерді сұрыптау алгоритмдері 4-ке бөлінеді: Таңдау арқылы сұрыптау. Ауыстыру арқылы сұрыптау (көпіршік әдіісі). Қою арқылы арқылы сұрыптау. Тез сұрыптау. Сұрыптау немесе объектілер тізімін реттеу деп осы объектілердің қандай да бір сызықтық реттілікке қатысты өсуі мен кемуі бойынша орындауды айтамыз. Сұрыптаудың мәні сонда жазулар тізімінің реттілігін кілттік өріс мәндері кемімейтін тізбек құратындай етуіміз керек. Басқа сөзбен айтқанда R1, R2, .. , Rn жазулары кілттік мәндері K1, K2,…,Kn орналасуы керек. Ki1 Мұнда реттелген тізбектегі кілттердің бірдей мәндері бар жазулар бір-бірімен қатар орындалады. Сұрыптау әдістері 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.
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 болып реттеледі.
Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек. Өткен әдістерді есептерге қолданып көр:
Тақырыбы:Бинарлы ағаш негізінде сұрыптау. Топологиялық сұрыптау. Рекурсивті сұрыптау. Сұрыптау әдістерін салыстыру Жалпы мәлімет Қою арқылы сұрыптау Қою арқылы сұрыптау – келесі процеске ұқсас. Карточкаларға аттарды жазып, карточкаларды алфавит бойынша өзіне керекті орынға қыстырып қою арқылы реттеу. Мысалға: 50,20,40,75,35 массивін қыстыру арқылы сұрыптау керек. 50 элементінен бастаймыз. 20-ны 0 позициясына қыстыру, 50-ді 1 позициясына жылжыту. 40-ты 1 позициясына қыстыру, 50-ді 2 позицияға жылжыту. 75-ті 3 позициясына қыстыру. 35-ті 1 позициясына қыстыру, қалғандарын оңға қарай жылжыту.
Бұл жай енгізулермен сұрыптаудың жақсартылған варианты. Жаңа элементті қосуға қажетті дайын тізбек реттелген болып, енгізу орнын неғұрлым жылдам табуға негізделген. Ол үшін дайын тізбектің ортаңғы элементі ізделіп, ары қарай ортасынан бөлу қашан енгізу орыны анықталғанша жалғаса беретін бинарлық іздеу жүргізіледі. Есептеу күрделілігі: Енгізу орыны табылады егер, al<=item<=ar болса. Соңында іздеу интервалы 1 ге тең болуы керек; бұл дегеніміз I элементтерден тұратын интервал ортасынан (log2i) рет бөлінеді деген сөз. 
Салыстырулардың минимальды саны барлық элементтер кері ретпен орналасқанда, ал максимальды саны олардың осы кезде реттелген болғанында талап етіледі. Тез сұрыптау Тез сұрыптау әдісі – күнделікті тәжірибеден алынған. Мысалы: Аттары бойынша алфавиттік карточкалар жиынын қандай да бір әріпке қатысты, мысалы К, екі кіші жиынға бөлуге болады. Барлық К-дан кіші немесе тең тең болатын бір жиынға, К-дан үлкен болатын бір жиынға бөлеміз. Одан кейін әрбір жиын тағы да екіге бөлінеді т.с.с. Тез сұрыптау алгоритмінде орталық элементті анықтап, сол арқылы бөлу әдісі қолданылады. Яғни, алғашқы массив екіге бөлінеді. Орталық элементтен үлкен және орталық элементтен кіші. Тура осы әрекет алынған массивтің 2 бөлігіне де жүргізіледі. Осылайша бөліне береді. Әрбір бөлікте бір ғана қалғанша жалғастырамыз. Сұрыптау принципі: Массивтің орталық элементі таңдап алынады. Массивтің барлық элементтері солдан оңға және оңнан солға қарай қарап өтіледі. І. Солдан оңға қарай қозғалғанда A[scan up] деген элементті іздейміз және бұл элемент орталық элементтен үлкен болуы керек, оның позициясын есімізге сақтап аламыз. Оңнан солға қарай қозғалғанда A[scan down] деген элементті іздейміз. Ол элемент орталық элементтен кіші немесе тең болады. Позициясын есте сақтаймыз. Табылған элементтердің орындарын ауыстырамыз және scan up және scan down индекстері қиылысқанша іздеуді жалғастырамыз. 1-этапты орындап болғаннан кейін алғашқы масситің элементтері орталық элементке бөлінеді. 2-этапта 1-этаптың әрекеттері массивтің оң жақ және сол жақ бөліктері үшін жеке-жеке орындалады. 3-этапта осы әрекеттердің барлығы 4 бөлігі үшін жеке-жеке орындалады. 4-этапта 4 бөлігі жеке-жеке орындалады.
Тізімдер алғашында реттелген болғандықтан элементтер шығатын массивке сұрыпталған ретпен көшіріледі. Тізбектің біреуі аяқталғаннан кейін келесі тізбектің қалған бөліктері яғни элементтері шығтын массивке көшіріле салады. Сұрыпталған тізбектерді біріктіру алгоритмі Бір тізбек немесе тізбектің екеуі де біткенше келесі әрекеттерді орындау керек. Яғни, егер 1-тізбектің 1-элементі 2-тізбектің элементіне тең немесе кіші болса, онда оны шығатын тізбекке жазып қойып, 1-тізбектің келесі элементіне көшу керек. Әйтпесе, шығатын тізбекке 2-тізбектің элементін жазып, 2-тізбектің келесі элементіне көшу керек. Одан кейін шығатын тізбектің келесі элементіне көшу керек. Егер біреуі аяғына дейін өңделмесе, онда сол қалдықты шығатын тізбекке көшіру керек. Тапсырмалар варианттары: Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек. Өткен әдістерді есептерге қолданып көр:
іздеу: тармақтар және шекаралар әдісі, динамикалық программалау, тереңге іздеу Мақсаты: Программа құру және оны жүктеу Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру ОСӨЖ №6 Тақырыбы: Жылдам іздеу: массивтен бинарлық және кезекті іздеу, М-блоктық іздеу. Сызықты тізімнен таңдау. Мақсаты: Программа құру және оны жүктеу Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру СӨЖ №1 Тақырыбы: «Ассоциативті тізімдер»; Мақсаты: Тізімдер. Тізім түрлерін қарастыру. Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу СӨЖ №2 Тақырыбы: «Тізімдерді қайта ұйымдастыру»; Мақсаты: Тізімдерді ұйымдастыру Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу СӨЖ №3 Тақырыбы: «Пирамидалы сұрыптау»; Мақсаты: Сұрыптау есебін қарастыру Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу СӨЖ №4 Тақырыбы: «Мекен-жайды есептеу арқылы сұрыптау»; Мақсаты: Сұрыптау есебін қарастыру Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу БАҚЫЛАУШЫ - ӨЛШЕМДІК ҚҰРАЛДАР Мәліметтерді өңдеудің құрылымдары мен алгоритмдері түсінігі. Статикалық және динамикалық құрылым мәліметтері. Мәліметтер құрылымдарымен орындалатын амалдар. Мысал. Алгоритмдер анализы. Сұрыптау және іздеу. Массивтерді сұрыптау алгоритмдері. Таңдау арқылы сұрыптау. Ауыстыру арқылы сұрыптау. Қою арқылы сұрыптау. Жылдам сұрыптау. Іздеу есептері. Тізбектелген іздеу. Іздеу есептері. Бинарлық іздеу. Файлдар. Сыртқы тасымалдаушылардағы мәліметтермен амалдар орындау. Сыртқы сұрыптау. Файлдар. Сыртқы тасымалдаушылардағы мәліметтермен амалдар орындау. Табиғи бірігу арқылы сұрыптау. Байланған сызықтық тізімдер. Тізімдерде іздеу әректтерін жүргізу Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Бір байланысты сызықтық тізім. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Реттелген тізімді жасау. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Циклдық тізімдер. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Екі байланысты сызықтық тізім Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Стектер. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Кезектер ұғымы. Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Басымдықтар кезегі. Ағаштар. Негізгі ұғымдар. Ағаш тәрізді құрылымды беру әдістері. Екілік бинарлық ағаштар. Екілік ағаштардың құрылымы. Өрнектердің екілік ағаштары. Екілік іздеу ағаштары. Екілік ағаштармен жүргізілетін амалдар. Екілік іздеу тармағынан элементті алып тастау. Массивтермен берілген бинарлық ағаштар. Массивтермен берілген бинарлық ағаштар.Турнирлік сұрыптау. Массивтермен берілген бинарлық ағаштар. Пирамидалар түсінігі. Массивті пирамидаға түрлендіру. Пирамидаға элементтерді қосу және одан элементтерді алып тастау. Пирамидалық сұрыптау. Балансталған ағаштар. Графтар, олармен жүргізілетін амалдар Графтар. Көршілестік матрицасы. жүктеу/скачать 1,51 Mb. Достарыңызбен бөлісу:
|
-ге тең. Ең жақсы жағдайда, яғни тізім реттелген жағдайда күрделілігі О(n)-ге , ал жаман жағдайда О(n2)-ге тең.