«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері»
жүктеу/скачать 1,51 Mb.
|
«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері» пәнін оқыту-әдістемелік кешен 5В011100 - «Информатика» мамандығына арналған оқу - әдістемелік материалдар Семей 2013 МАЗМҰНЫ
1. Глоссарий Мәліметтер дегеніміз - дербес компьютерде өңдеуге болатын, кез келген ақпаратты сипаттайтын мәнді немесе мәндер жиыны. Мәліметтердің логикалық құрылымы дегеніміз - сәйес құрылымның моделі, берілу схемасы (екі өлшемді массив, тік бұрышты матрица). Мәліметтердің физикалық құрылымы дегеніміз - құрылымды компьютер жадысына орналастыру немесе сақтау схемасы (жады ұяшықтарының тізбегі). Динамикалық құрылым мәліметтері дегеніміз – ішкі жасалуы қандай да бір заң бойынша қалыптасқан, бірақ элементтер саны олардың өзара орналасуы, өзара байланысы программаның орындалу барысында динамикалық түрде өзгере алатын мәліметтер. Сызықтық құрылым мәліметтер типтері – орналасуы бойынша реттелген элементтер тізімін анықтайды. Сызықтық емес құрылым мәліметтер типтері – позициялық реттеусіз элементтерді анықтайды. Тікелей кіру дегеніміз – элементті тікелей таңдау және тізімдегі алдыңғы элементтерге байланыссыз таңдауды айтады. Массив дегеніміз – мәліметтердің бүтін санды индекс көмегімен кіруге болатын бір ғана типтен тұратын құрылымы. Реттелген сызықтық тізімде – мәліметтер бір-біріне қатысты реттеліп орналасады. Стек дегеніміз – элементтері тізімнің төбесі деп аталатын бір жағынан ғана қосылатын немесе өшірілетін сызықтық тізімді айтамыз (соңғысы келсе біріншісі кетеді). Шірет (очередь) дегеніміз – тізімнің басынан немесе аяғынан ғана кіруге болатын сызықтық тізім. Элементтер тізімнің соңына қойылады да басынан өшіріледі. Очередь приоритеті дегеніміз – очередь немесе шірет типті тізім, тізімдегі объектіні өшірген кезде ең жоғары приоритетке ие объект анықталады. Файл дегеніміз – байттар тізімі. Ол бір ағымға теңеледі, яғни, бір құрылғыдан екінші құрылғыға ауысып отыратын байттар тізбегі. Тек қана дисктік файлға тікелей кіруді жүзеге асыруға болады. Иррархиялық құрылым – бұл деңгейлері бойынша бөлінетін элементтер жиынындағы, яғни, бір деңгейдегі элемендеңгейде бірнеше ұрпағы болуы мүмкін. Тармақ (дерево) – бұл түпкі немесе тамыр деп аталатын бір ғана көзден тарайтын элементтері бар мәліметтер құрылымы. Пирамида дегеніміз – тармақтың ерекше түрі. Мұнда ең үлкен элемент үнемі түпкі деңгейде тұрады. Топ (группа) дегеніміз – элементтері ешқандай реттеусіз орналасқан сызықтық емес құрылым. Жиын дегеніміз – мәліметтер реттеусіз болғанда және мәліметтердің әрбір элементі өз алдына қайталанбайтын болғанда қолданылатын мәліметтер құрылымы. Граф дегеніміз – төбелер жиынынан және сол төбелерді қосатын байланыстар жиынынан тұратын мәліметтер құрылымы. Желі (сеть) дегеніміз – графтың ерекше формасы. Мұнда әрбір байланыстың өз салмағы болады. 2. Дәрістер Дәріс 1. Кіріспе, мәліметтер типтері Мақсаты: Мәліметтердің өңдеудің құрылымдары мен алгоритмдеріне кіріспе. Негізгі ұғымдары. Мәліметтер типтерімен танысу. Кіру әдістері. Соңғы 20-30 жылда құрылымдалған программалау идеялардың кең таралуы программалаудың теориясы мен практикасына үлкен әсер етіп, сәйкес алгоримдер мен программаларды жасаудағы мәліметтердің типі мен құрлымдарының ролі қайта қарауға алып келді. Осыған байланысты соңғы он жылдықта электронды есептеуіш машиналарды (ЭЕМ) программалық қамтамасыз ету саласында мамандар даярлайтын оқу орындарында мәліметтердің типтері мен құрылымдары пәні пайда болды. Бұл пән ақпараттық технологиялар саласында соған сәйкес программалық қамтамасыз етуге жоғары сапалы мамандар даярлауға мүмкіндік беретін компьютер ғылымы информатиканың фундаментальды (негізгі, түпкі) бөлімі болып саналады. Бұл курстың идеялық мазмұны программалық тілге тәуеді емес, бірақ мәліметтер құрылымын көрнекі түрде белгілеуге болатын Турбо Паскаль тілі қолданылады. Мәліметтер құрылымын кез келген программаның немесе программалық бөлімнің бөлінбес саласы болып саналады. Программаны жасауда нақтылы есепті сипаттайтын мәліметтер жиынын анықтап, есепті шешудің алгоритмін құру керек. Программаның мақсатына қарай мәліметтер әртүрлі күрделі деңгейде болуы мүмкін. Яғни жай типтерден бастап, жеткілікті типтегі күрделі құрылымдарға дейін. Мәліметтер дегеніміз - дербес компьютерде өңдеуге болатын, кез келген ақпаратты сипаттайтын мәнді немесе мәндер жиыны. Мәліметтердің маңызды мінездемесін беретін тип болып саналады. Ол мәліметтерді компьютер жадысына беруде қолданылады және осы мәндерге орындауға болатын амалдар жиыны мен мәліметтер мәндері жиынын анықтайды. Мәліметтерді ұйымдастырудың логикалық және математикалық моделі Мәліметтер құрылымы деп аталады. Мәліметтердің логикалық құрылымы және физикалық құрылымы ұғымы бар. Мәліметтердің логикалық құрылымы дегеніміз - сәйес құрылымның моделі, берілу схемасы (екі өлшемді массив, тік бұрышты матрица). Мұнда әрбір элементте индекс болады. Мәліметтердің физикалық құрылымы дегеніміз - құрылымды компьютер жадысына орналастыру немесе сақтау схемасы (жады ұяшықтарының тізбегі). Мәліметтердің барлық жиынын екіге бөлуге болады: Статикалық және динамикалық құрылым мәліметтері. Статикалық құрылым мәліметтері – жай және күрделі болуы мүмкін. Олар қандай да бір заңдылық бойынша жай құрылымдарда қалыптасады. Құрылым элементтерінің өзара орналасуы мен өзара байланысы әрқашан тұрақты болып қалады. Динамикалық құрылым мәліметтері дегеніміз – ішкі жасалуы қандай да бір заң бойынша қалыптасқан, бірақ элементтер саны олардың өзара орналасуы, өзара байланысы программаның орындалу барысында динамикалық түрде өзгере алатын мәліметтер. 
Мәліметтердің типтерін сызықтық құрылымды мәліметтер типтері және сызықтық емес мәліметтер типтері деп бөлуге болады. Сызықтық құрылым мәліметтер типтері – орналасуы бойынша реттелген элементтер тізімін анықтайды. Сызықтық емес құрылым мәліметтер типтері – позициялық реттеусіз элементтерді анықтайды. Тікелей кіру дегеніміз – элементті тікелей таңдау және тізімдегі алдыңғы элементтерге байланыссыз таңдауды айтады. 
Массив дегеніміз – мәліметтердің бүтін санды индекс көмегімен кіруге болатын бір ғана типтен тұратын құрылымы. А[0], А[1], А[2], …, А[n] Массивтермен жұмыс жасауда элементтерге кіруді ұйымдастыру маңызды әрекет болып саналады. Элементке логикалық деңгейде кіру үшін – массив аты мен элемент индексі керек. Ал физикалық деңгейде жұмыс жасауда элемент адресін массив атымен ізделіп отырған элемент индексі мен оның ұзындығына қарай есептеп шығару қажет болады. Индексті кіру мәліметтері типтері үшін – жазуға кіруге қолданылатын қандай да бір кілт байланыстырады. FLASH кесте – кілтпен байланысты мәліметтерді сақтайды. Кілт – мәліметтерді табу үшін қолданылатын бүтін санды индекске трансформацияланады. Кілт бүтін болуы мүмкін емес. Сөздік деп аталатын мәліметтер құрылымы ассоциация деп аталатын кілт және мән жұптарының жиынынан тұрады. Мысалға, кілт сөз болуы мүмкін, ал мән сөздің анықтамасын көрсететін сөйлем болуы мүмкін. Сызықтық құрылым мәліметтер типтері – мәліметтерге тізбектей кіруді пайдаланғанда мәліметтердің динамикалық құрылымы болып табылады да, келесі қасиеттерге ие болады: өлшемнің тұрақсыздығы ; жадыдағы элементтер құрылымдарының физикалық реттілігінің жоқтығы. Сызықтық тізім – элементтердің кез келген санына ие болады, тізімнің өлшемі тізімдегі элементтерді қосуға және алып тастауға байланысты өзгеріп отырады. Бірінші элементі басында орналасады, соңғы элементі аяғында орналасады және әрбір елемент (соңғысынан басқа) алдында бір элементке ие болады. Реттелген сызықтық тізімде – мәліметтер бір-біріне қатысты реттеліп орналасады. Стек дегеніміз – элементтері тізімнің төбесі деп аталатын бір жағынан ғана қосылатын немесе өшірілетін сызықтық тізімді айтамыз (соңғысы келсе біріншісі кетеді). Шірет (очередь) дегеніміз – тізімнің басынан немесе аяғынан ғана кіруге болатын сызықтық тізім. Элементтер тізімнің соңына қойылады да басынан өшіріледі. Очередь приоритеті дегеніміз – очередь немесе шірет типті тізім, тізімдегі объектіні өшірген кезде ең жоғары приоритетке ие объект анықталады. Файл дегеніміз – байттар тізімі. Ол бір ағымға теңеледі, яғни, бір құрылғыдан екінші құрылғыға ауысып отыратын байттар тізбегі. Тек қана дисктік файлға тікелей кіруді жүзеге асыруға болады. Иррархиялық құрылым – бұл деңгейлері бойынша бөлінетін элементтер жиынындағы, яғни, бір деңгейдегі элемендеңгейде бірнеше ұрпағы болуы мүмкін. Тармақ (дерево) – бұл түпкі немесе тамыр деп аталатын бір ғана көзден тарайтын элементтері бар мәліметтер құрылымы. Пирамида дегеніміз – тармақтың ерекше түрі. Мұнда ең үлкен элемент үнемі түпкі деңгейде тұрады. Топ (группа) дегеніміз – элементтері ешқандай реттеусіз орналасқан сызықтық емес құрылым. Жиын дегеніміз – мәліметтер реттеусіз болғанда және мәліметтердің әрбір элементі өз алдына қайталанбайтын болғанда қолданылатын мәліметтер құрылымы. Граф дегеніміз – төбелер жиынынан және сол төбелерді қосатын байланыстар жиынынан тұратын мәліметтер құрылымы. Желі (сеть) дегеніміз – графтың ерекше формасы. Мұнда әрбір байланыстың өз салмағы болады. Дәріс 2. Мәліметтер құрылымдарымен жасалатын әрекеттер Мақсаты: Мәліметтер құрылымдарымен жасалатын әрететтермен танысу. Алгоритмдер анализі және программаларды орындау уақыты ұғымдары. Құрылымдағы мәліметтер қандай да бір әрекеттер көмегімен өңделеді. Мәліметтер құрылымдарын таңдау осы әрекеттер орындайтын жиілікке тәуелді болады. Мәліметтерді өңдеуде келесі әрекеттер маңызды рольге ие болады: Құрылымды тексеру. Яғни құрылымның әрбір элементін оны кейін өңдеуге болатындай мақсатта кіру мүмкіндігі. Іздеу. Яғни берілген мәні бар элементтердің орнын табу. Қыстырып қою. Яғни құрылымға жаңа элементтер кіргізу. Өшіру . Құрылымдағы элементті алып тастау. Алгоритмдер анализі және программаларды орындау уақыты Бір есепті шешуге арналған әртүрлі алгоритмдерді салыстыру үшін программаның орындалу уақытын жуық мөлшерде анықтау үшін алгоритмдердің математикалық анализі қолданылады. Қолданбалы есептерді шешу процесінде есеп шығарудың неғұрлым жақын алгоритмін таңдау керек болады. Мұнда алгоритм келесі талаптарды қанағаттандыруы керек: Түсінуге жеңіл, программалық кодқа және орындауға, аударуға жеңіл болуға тиіс. Компьютер ресурстарын тиімді пайдалану және орындалу жылдамдығы неғұрлым тез болуы керек. Программаның орындалу уақытына келесі факторлар әсер етеді: Алғашқы ақпаратты программаға енгізу. Орындалып жатқан программаның компилияцияланған кодының сапасы. Программаның орындалуында пайдаланылып жатқан жатқан машиналық инструкциялар. Сәйкес программа алгоритмінің уақытша күрделілігі. Алгоритмнің Уақыт бойынша күрделілігі дегеніміз – жоспарланған нәтижеге жету үшін алгоритмге орындау қажет болатын қадамдармен өлшенетін алгоритмнің орындалу уақыты. Бұл терминнің синонимі ретінде, көбінесе алгоритмнің орындау уақыты сөзі пайдаланылады. Программаның орындалу уақыты алғашқы мәліметтердің мөлшеріне тәуелді. Мысалға, массивтегі ең кіші элементті табу бұл мәліметтер элементтерін салыстыруға негізгі операция немесе амал. N элементтерін массиві үшін алгоритмге N-1 салыстыру қажет болады және оның орындалу уақыты Т-ге пропорционал. Алгоритмдердің уақыт бойынша күрделілігін 0 символика деген қолданылады. Мысалы, егер қандай да бір программаның орындалу уақыты Т(n) О(n2) ретке ие болса, бұл дегеніміз қандай да бір С әлде n0 константалар болып, n0-дан үлкен немесе тең болатын n константалар үшін Т(n)<=cn теңсіздігі орындалады. Яғни, орындалу уақыты ең аз дәрежеде өсетін программаларды таңдап алуы керек. Бұл дегеніміз, неғұрлым өсу дәрежесі аз болса, компьютердің шығарып отырған есептің өлшемі соғұрлым көп болады деген сөз. Программаның орындалу уақытын теориялық түрде табу күрделі математикалық есеп, оның шешілу үшін бірнеше базалық принциптерді білу керек. Алдымен 3 маңызды ережелерді қарастырамыз:
Тұрақты көбейткіштер уақыт бойынша күрделі реттік анықтау үшін маңызды емес, яғни О(k*f)=0. Көбейткіштер ережесі: екі функцияның уақыт бойнша күрделі реттің көбейткіштері олардың күрделіліктің О(f*g)=O(f)*O(g). Қосындылар ережесі: функцияның уақыт бойынша күрдел реттің қосындылары қосылғыштардың ең үлкенінің ретіне тең болады. О(n+n+n)=O(n). Программалар анализінің ережелері: Меншіктеу, оқу және жазу операторларының орындалу уақыты О(1) ретке ие болады. Операторлар тізбегінің орындалу уақыты қосындылар ережесі бойынша анықталады. Шартты оператордың орындалу уақыты шартты түрде орындалып отырған оператордың орындалу уақытынан тұрады. Логикалық өрнекті есептеу уақыты – жалпы О(1) ретке ие болады. Барлық шарт конструкциясының уақыты логикалық өрнекті есептеу уақытынан және логикалық өрнек, ақиқаты және жалған мәндерді қабылдауда жүзеге асатын операторларды орындауға қажет ең көп уақыттан тұрады. Циклдарды орындау уақыты – цикл денесі оператордың орындалу уақытынан және циклды тоқтату шартын есептеудің уақытынан тұратын барлық цикл итерацияларының уақытын қосқанға тең болады. Сұрыптауға жататын элементтер саны кіретін мәліметтер көлемге өлшем бірлігі болып ткабылады. Мұндағы соңғы үш оператор О(1) орындалу ретіне ие болады. Қосындылар дәрежесіне сәйкес бұл операторлар топтары О(мах(1,1,1))=О(1). Егер операторы үшін логикалық өрнекті тексеру О(1) уақыт ретіне тең болады. Соңғы 5 оператор тобының, яғни ішкі циклдің орындалу ретін қарастырамыз, бұл операторлар үшін әрбір итеракциядағы орындалу уақыты О(1)-ге ие болады. Цикл n-1 рет орындалады. Сондықтан, көбейткіш ережесі бойынша циклдің барлық орындалу уақыты: О((n-1)*1)=O(n*1). Сыртқы циклді қарастырамыз: сыртқы цикл n-1 рет орындалады, сондықтан программаның жалпы қосынды орындалу уақыты Дәріс 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-тізбектің келесі элементіне көшу керек. Одан кейін шығатын тізбектің келесі элементіне көшу керек. Егер біреуі аяғына дейін өңделмесе, онда сол қалдықты шығатын тізбекке көшіру керек. Дәріс 5. Тізімдерде іздеу әректтерін жүргізу Мақсаты: Тізбектерде элементті іздеу ұғымын енгізу. Іздеу (поиск) екіге бөлінеді: Тізбектеліп іздеу. Бинарлық іздеу. Тізбектеліп іздеу. Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады. Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -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 салыстыру жүргізіледі. Дәріс 6. Файлдар және сыртқы тасымалдаушылардағы мәліметтер мен операциялар. Мақсаты: Файлдар және сыртқы тасымалдаушылардағы мәліметтер мен операциялар жүргізу ұғымын қалыптастыру. Балансталған көп жолдық бірігу, табиғи бірігу арқылы сұрыптау, сыртқы сұрыптау амалдарын түсіндіру. Көптеген қосымшаларда дисктердегі файлдарда орналасқан мәліметтерге кіру қажет болады. Мәліметтердің ұлкен жиындары жадыға бір уақытта сыйғызуға мүмкін емес миллиондаған жазулардан тұруы мүмкін. Оларды басқару үшін сыртқы сұрыптау мен іздеу алгоритмдері қажет. Аппаратты тұрғыдан алғанда файл жазулары дискте сақталатын, белгілі ұзындықтағы мәліметтер блоктарын құрайды. Логикалық тұрғыдан алғанда жазулар файлда тізбектеліп орналасады. Файлдық жүйе жекелеген жазуларға, сондай-ақ, барлық файлға толығымен кіруді жүзеге асыруға мүмкіндік береді. Сыртқы сұрыптау Файлдар түрінде ұйымдастырылған мәліметтерді сұрыптау сыртқы сұрыптау деп аталады. Егер файл оперативті жадыда сыймайтындай үлкен болса, онда сұрыптау - өте үлкен проблема. Барлық мәліметтерді бір массивте сақтауға болмайтындықтан, оларды сақтау үшін уақытша файлдарды қолдану керек. Тура біріктіру арқылы сұрыптау екі реттелген тізімді біріктіретін жай біріктіру әдісін қолданады. Басты идеясы біртіндеп үлкейетін элементтер түрінде файл ұйымдастырылатынында, яғни жазулар тізбегі r1<=r2<=…<=rn жазулар тізбегі. Мысалға, 3 деген ұзындықтағы сериялармен ұйымдастырылған бүтін сандар тізбегі:
Мұнда соңы 3 тен кем ұзындықта болуы мүмкін, бірақ оның жазулары да сұрыпталған. Сұрыптау алгоритмі FC 5,15,35,30,20,45,35,5,65,75,40,50,60,70,30,40,25,10,45,55 Файлды екіге бөлеміз. Оның элементтерін сәйкесінше екіге бөлеміз. Осылайша, әрбір жаңа файлда элементтер тізімі пайда болады. Ішкі тізімдерді салыстырамыз. Яғни, FA файлынан және FB файлынан бір-бір элементтен таңдап алып, жай біріктіру алгоритмін пайдалана отырып, қайтадан FC файлына жазамыз. Осылайша, барлық элементе қайтадан FC файлға ауысқанша жалғастырамыз. FА 5,35,20,35,65,40,60,30,25,45 FВ 15,30,45,5,75,50,70,40,10,55 FC 5,15,30,35,20,45,5,35,65,75,40,50,60,70,30,40,10,25,45,55 Бір қадамды қайталап, FА және FВ файлдарына екі элементті серияларды жазып шығарамыз. FА 5,15,20,45,65,75,60,70,10,25 FВ 30,35,5,35,40,50,30,40,45,55 FА және FВ файлдарындағы екі элементті серияларды FC файлына 4 элементті серияға біріктіреміз. Мұнда реттелген тізімдерді біріктіру алгоритмін пайдаланамыз. FC 5,15,30,35, 5,20,35,45 40 50 65 75 30 40 60 70 10 25 45 55
FС файлын екіге бөлетін қадамды FА және FВ файлында сәйкесінше 4 8 т.с.с элементтер серияларын құрай отырып және сериялардың әрбір жұптарын біріктіре отырып қайталаймыз. Процесс FА және FВ файлдары бір-бір реттелген тізімнен тұрғанда және олар FC сұрыпталған файлына соңғы рет бірікенде аяқталады. Түзу бірігу сұрыптау анализі. Сұрыптау бір элементі ішкі тізімдердің жүрістер сериясынан тұрады, әрбір жүрісте ішкі тізімнің ұзындығы екі еселенеді. Ол үшін log2n жүріс қажет болады. Түзу бірігу арқылы сұрыптау 2n log2n мәліметтерді қарауды талап етеді, сондықтан оның күрделілік реті O(n log 2n). Табиғи бірігу арқылы сұрыптау Түзу бірігу арқылы сұрыптауда алғашқы ұзындығы бірге тең болатын реттелген сериялар пайдаланылады да, олар әрбір жүріс сайын екі еселеніп отырады. Ең аяғында сериялар файлдардың барлығын қамтиды да сұрыпталу аяқталады. Мұның бір кемшілігі қысқа сериялар мен жұмыста көп уақыт кетеді. Мұндай сұрыптауды салыстырмалы түрде ұзын сериялардан бастасақ, алгоритмнің тиімділігі неғұрлым артады. Әрбір ретте неғұрлым екі серия бірігетін сұрыпталу әдісі Табиғи бірігу деп аталады. Сұрыптау алгоритмі Алғашқыда FC алғашқы файлды және алғашқы ұзындықтағы реттелген серияларды жасау үшін оперативті жадыдағы буфер керек: Алғашқы файлдың мәліметтері буферге блок бойынша оқылады. Әрбір блок сұрыпталудың кез келген алгоритмі арқылы сұрыпталады да (мысалы, тез сұрыпталу), кезек-кезек FB және FA файлдарына көшіріліп отырады. FC файлы біткен кезде қайтадан уақытша FА және FВ файлындағы мәліметтер блоктары қайтадан біріге бастайды. Осылайша, сұрыптау жай бірігуге ұқсас жалғаса береді. Алгоритм анализі: Мұнда әрбір жүрістен сериялардың саны екі есе қысқарады. Сондықтан жіберулердің жалпы саны ең жаман жағдайда n log2n тең болады. Ал жалпы жағдайда одан да аз болады. Балансталған көп жолдық бірігу Тізбектелген сұрыпталуға кететін шығын жүрістің санына прорпорционал болады. Шығынды азайтудың бір жолы екі уақытша немесе одан да көп файлдарды пайдалану R сериялы бірігу n уақытша файлдарға бөлінгенде Дәріс 7. Мәтіндерге тізбектеліп кіретін мәліметтердің сызықтық құрылымдық типтері. Мақсаты: Мәтіндерге тізбектеліп кіретін мәліметтердің сызықтық құрылымдық типтері ұғымы. Байланған сызықтық тізімдер түсініктерін енгізу. Байланған сызықтық тізімдер Тізім дегеніміз – сандары өзгеруі мүмкін элементтердің жиынтығы. Ол шынжырдағы шығыршық іспеттес. Тізімнің ұзындығы жаңа шығыршықтар қосу арқылы көбеюі мүмкін. Жаңа элементтер тізімге тізімнің бір жерін үзіп, соған жаңа элемент қосып, қайтандан жалғау арқылы кіргізуі мүмкін. Элементтер тізіміне сол сияқты тізімді үзіп, бір шығыршықты алып қайта жалғап қойған сияқты алынып тасталады. Тізімдер үш түрлі болады: 1. Бір байланысты. 2. Циклық 3. Екі байланысты Бір байланысты сызықтық тізім. Бір байланысты сызықтық тізім екі әдіспен жүзеге асуы мүмкін: 1-массивтер негізінде 2-көрсеткіштер көмегімен
Тізімді массив негізінде жүзеге асыру орындалмас бұрын тізімнің максималды өлшемін көрсетуді талап етеді. Массив негізіндегі тізімдерді жүзеге асыру компьютер жадысының үлкен көлемін қажет етеді. Тізімді жүзеге асыру үшін тізімнің ең үлкен мүмкін мөлшеріне жететіндей етіп жады көлемін бөлу қажет. Көрсеткіштер көмегімен жүзеге асыру. Тізімді сақтау үшін жадының үзіліссіз аймағын пайдаланудан босатады. Сондықтан бұл жағдайда элементтерді қосқанда немесе өшіргенде элементтер ары-бері жылжытуды қажет етпейді. Алайда, бұл жағдайда көрсеткіштерді сақтайтын қосымша жады керек болады. Тізімнің әрбір бөлігі – мәліметтер өрісінен және тізімдегі келесі элементтерді көрсететін көрсеткіштен тұрады. Байланған тізімнің құрылымы келесі түрде берілуі мүмкін: head ptr rear NULL
жүктеу/скачать 1,51 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
формуламен анықталады және О(n2) ретке ие болады. Жалпы О функциясының мәні берілгендер құрылымы алгоритмдер үшін полиномдық, логорифмдік және экспоненциалдық функциялар ішінен таңдап алынады. 
-ге тең. Ең жақсы жағдайда, яғни тізім реттелген жағдайда күрделілігі О(n)-ге , ал жаман жағдайда О(n2)-ге тең.
ішкі тізімдерден тұратын тізбек құрайды. Екінші жүріс бұл санды 
дейін қысқартады. Ал үшінші жүріс 
дейін қысқартады. Осылайша к жүрістен кейін 
бөлік қалады. n элементі N жүрісті бірігу мен сұрыптауда жүрістің жалпы саны k=logNn (N-жол, n-элементтер саны) тең болады. Әрбір жүрісте қайта жазудың n операциясы жүретін болғандықтан ең жаман жағдайда операцияның жалпы саны M=n logNn болады.