Табиғи бірігу арқылы сұрыптау туралы

Жоспар
I. . Ақпараттық іздеудің қарапайым есебі
II. AVL.ағаштар және толыққа жуық бинарлы ағаштар.
III. Толықтау бинарлы ағаш.

1. Ақпараттық іздеудің қарапайым есебі
Іздеу әдістеріжәнеіздеумен байланысты есептерді зерттеу мәселесі, зерттеулердің жеке және қызықты бағыттарының бірі. Қарапайым ақпаратты іздеу есебін қарастырайық. Мысалы, университеттің мех-мат факультетінің барлық 1-ші курс студенттерінің ішінен берілген РНН1 арқылы немесе сынақ кітапшасының нөмері арқылы осы нөмірге немесе РНН-ге сәйкес студентті табу қажет болсын. Осы қойылған есеп қарпайым шешімге ие бола алады. Мысалы,қарапайым тізбектеп қарастыру әдісін қолданып,студенттер тіркелген кестеден тізбектеп барлық студенттердің РНН-нің ішінен берілген РНН-ді салыстыра тексере отырып табуға болады. Ал егер осындай іздеуге үлкен мегеполистің деректер қорынан берілген РНН-ді іздеп табу қажет болса, жәнеіздеуді осындай қарапайым жолмен ұйымдастырсақ, онда өте көп уақыт алатыны айқын. Мұндай әдіспен шешу жолы қабылданбайды.
Сөйтіп, А массиві берілсін. Берілген А массивінің элементтерінің табиғаты кез-келген болсын. Және Р массиві берілсін, массивтің элементтерінің табиғаты сан болсын. А массивінің кез-келген элементіне Р массивінің элементері бір мәнді сәйкестікпен тағайындалсын. Оған қоса P массивтің элементтерін А массивтің элементтерінің белгісі немесе кілттері деп атайды. Формальді түрде қойылған қарапайым ақпаратты іздеу есебінің қойылымын келесідегідей тұжарымдауға болады: р* кздейсоқ кілт берілсін. А массиві элементтерінің ішінен кілті р*-ға тең элементті табу қажет немесе А массивінің элементтері ішінен р* сәйкескілтті элемент жоқ екені анықталу қажет. Қойылған есепті математикалық тұрғыдан теориялық жолмен шешсек, онда Р кілттер жиынында анықталған қандайда бір функция түзуді қажет етеді. Түзілген функция кілті р* сәйкес А массивінің элементінің нөмерін бір қадам ішінде қайтаруы мүмкін, егер де ондай бар болса. Қойылған есепті шешудің тағы бір жолы бұл комбинаторикалық жол. Бұл жолдағы айғақты процедура ретінде іздеуді тізбектеп немесе басқаша айтқанда сызықтыіздеунегізіндеұйымдастырады. Тізбектеп іздеуде орташалап алғанда саны салыстыруларды қажет етеді. Бүтін мәнді оң анықталған аргументтері натурал сан болып келетін функциялар болсын. Егер барлық үшін шарты орындалатындай оң анықталған с константасы n0 нөмірі табылатын болса,онда функциясы О-үлкен –нен деп аталады және түрінде жазылады. Егер барлық үшін шартты орындалатындай оң анықталған с константасы n0 нөмірі табылатын болса, онда функциясы -үлкен –нен деп аталады және түрінде жазылады. Н Н -бүтін мәнді оң анықталған аргументтері натурал сан болып келетін функциялар болсын. Егер барлық үшін шартын қанағаттандыратындай оң анықталған константалары және нөмері табылатын болса,онда – Н – нен дейді және = () түрінде болады. Иии–

Қолданылған әдебиеттер:
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Балапанов Е.К., Бөрібаев Б. Информатикадан 30 сабақ, Алматы, 1999 ж.

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 7 бет
Таңдаулыға:

Семей қаласының Шәкәрім атындағы мемлекеттік университеті
Информатика және ақпараттық технология кафедрасы

СӨЖ
Тақырыбы: Табиғи бірігу арқылы сұрыптау

Орындаған: Даурембекова А.Е.
Топ: Т-341
Тексерген: Болсынбекова Ш.Ж.

Семей 2015

Жоспар
I. . Ақпараттық іздеудің қарапайым есебі
II. AVL-ағаштар және толыққа жуық бинарлы ағаштар.
III. Толықтау бинарлы ағаш.

1. Ақпараттық іздеудің қарапайым есебі
Іздеу әдістеріжәнеіздеумен байланысты есептерді зерттеу мәселесі, зерттеулердің жеке және қызықты бағыттарының бірі. Қарапайым ақпаратты іздеу есебін қарастырайық. Мысалы, университеттің мех-мат факультетінің барлық 1-ші курс студенттерінің ішінен берілген РНН1 арқылы немесе сынақ кітапшасының нөмері арқылы осы нөмірге немесе РНН-ге сәйкес студентті табу қажет болсын. Осы қойылған есеп қарпайым шешімге ие бола алады. Мысалы,қарапайым тізбектеп қарастыру әдісін қолданып,студенттер тіркелген кестеден тізбектеп барлық студенттердің РНН-нің ішінен берілген РНН-ді салыстыра тексере отырып табуға болады. Ал егер осындай іздеуге үлкен мегеполистің деректер қорынан берілген РНН-ді іздеп табу қажет болса, жәнеіздеуді осындай қарапайым жолмен ұйымдастырсақ, онда өте көп уақыт алатыны айқын. Мұндай әдіспен шешу жолы қабылданбайды.
Сөйтіп, А массиві берілсін. Берілген А массивінің элементтерінің табиғаты кез-келген болсын. Және Р массиві берілсін, массивтің элементтерінің табиғаты сан болсын. А массивінің кез-келген элементіне Р массивінің элементері бір мәнді сәйкестікпен тағайындалсын. Оған қоса P массивтің элементтерін А массивтің элементтерінің белгісі немесе кілттері деп атайды. Формальді түрде қойылған қарапайым ақпаратты іздеу есебінің қойылымын келесідегідей тұжарымдауға болады: р* кздейсоқ кілт берілсін. А массиві элементтерінің ішінен кілті р*-ға тең элементті табу қажет немесе А массивінің элементтері ішінен р* сәйкескілтті элемент жоқ екені анықталу қажет. Қойылған есепті математикалық тұрғыдан теориялық жолмен шешсек, онда Р кілттер жиынында анықталған қандайда бір функция түзуді қажет етеді. Түзілген функция кілті р* сәйкес А массивінің элементінің нөмерін бір қадам ішінде қайтаруы мүмкін, егер де ондай бар болса. Қойылған есепті шешудің тағы бір жолы бұл комбинаторикалық жол. Бұл жолдағы айғақты процедура ретінде іздеуді тізбектеп немесе басқаша айтқанда сызықтыіздеунегізіндеұйымдастырады. Тізбектеп іздеуде орташалап алғанда саны салыстыруларды қажет етеді. Бүтін мәнді оң анықталған аргументтері натурал сан болып келетін функциялар болсын. Егер барлық үшін шарты орындалатындай оң анықталған с константасы n0 нөмірі табылатын болса,онда функциясы О-үлкен - нен деп аталады және түрінде жазылады. Егер барлық үшін шартты орындалатындай оң анықталған с константасы n0 нөмірі табылатын болса, онда функциясы -үлкен - нен деп аталады және түрінде жазылады. Н Н -бүтін мәнді оң анықталған аргументтері натурал сан болып келетін функциялар болсын. Егер барлық үшін шартын қанағаттандыратындай оң анықталған константалары және нөмері табылатын болса,онда - Н - нен дейді және = () түрінде болады. Иии - нотациясында 1 ғана функция, бұл жағдайда функциясы, қандай да бір n0 нөмірден бастап функциясы үшін жоғары және төменгі шегі болып табылатынын айта кету маңызды. Компьютерлік жүйелерде көп тараған екілік іздеу алгоритмінің салыстыру санының күрделілігінің жоғарыдан бағасы жуық.Екілік іздеу алгоритмді қолдануда берілген бастапқы массив х1 ,х2 , ... ,х п реттелген бөлу қажет.Массивтің реті мысалға, өспелі х1 х2х п немесе кемімелі х1 х2 ... х п болу мүмкін.Бастапқы массивтің элементтер саны немесе элементтерінің мәндері уақыт айналымынан өзгеріп отыруы мүмкін,осыған орай реттеу алгоритмдерінің тиімділігі мәселесінің ролі арта түседі. Екілік іздеуді ұйымдастыратын алгоритмнің стандарты нұсқасы төменде көрсетілген.
functionBinSearch(b,p* ,n);
...
begin l:=0;
h:=n;
while l=h do
begin
m:=(l+h)div2;
if b[m]p* then h:=m-1
else
begin
binsearch:=m;
exit;
end;
end;
binsearch:= -1;
end; -1 мәнінің қайтарылуы р* -ның массивте табылмағанын көрсетеді.

2.AVL-ағаштар және толыққа жуық бинарлы ағаштар.

AVL ағаштары. Бинарлы ағаштардың бұл класы алдыңғы жағдайдағы мен салыстырғандағы тұрғызу алгоритмі күрделі болғанымен маңызды позитивті қасиеттерге ие болады.Бұл типті ағаштар көзге бейсимметриялы көрінуі мүмкін, бірақ оларда ұзын бұтақтар жоқ. Мұндай ағаштың түбірінен шыққан бұтақтың максималды ұзындығы ,мұнда c аспауы тиіс. AVL ағаштарды көбіне баланстандырылған ағаштар деп атайды.Бұтақ ұзындығы деп осы бұтаққа тиісті ең ұзын жолдың ұзындығы алынады.Ағаш төбесі балансы деп берілген төбеден шығатын оң же сол бұтақ ұзындықтарының айырмасын айтады. Егер ағаштың әрбір төбесіүшін баланстың абсолют мәні 1-ден артық болмаса, онда ағашты баланстандырылған (AVL) ағашд.а. n элементтен тұратын массив бойынша тұрғызылған AVL ағаштағы ең ұзын бұтақтың ұзындығын бағалайық. Бұл үшін санын белгілейміз, алдымен максималь ұзындығы l-ға тең бұтақтары бар AVL ағаштар жиынын қарастырамыз. Осы ағаштардың ішінде төбелер саны минимум болатындары да бар.Ары қарай бұл AVL ағаштарынминималдыдепатаймыз.Ендімы нафункциянықарастырайық.n(l)-AVL ағашындағы төбелердің минималь саны, бұтақтарының максималь ұзындығы тең. l=0,1,2,3,4 және 6 үшін минималь AV ағаштарының мысалын келтірейік.

2.5.сурет: a) n(0)=1, l=0 б) n(1)=2, l=1 в) n(2)=4,l=2 г) n(3)=7,l=3
... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.