Қазақстан республикасының бiлiм және ғылым министрлiгi



бет1/5
Дата31.07.2017
өлшемі1,23 Mb.
  1   2   3   4   5

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БIЛIМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛIГI


СЕМЕЙ қаласының ШӘКӘРIМ атындағы МЕМЛЕКЕТТIК УНИВЕРСИТЕТI

«Іріктеу және іздеу әдістері» пәнінің


5В070400-

«Есептеу техникасы және бағдарламалық қамсыздандыру» мамандығына арналған

ОҚУ-ӘДІСТЕМЕЛІК КЕШЕН

Семей


2014
МАЗМҰНЫ

1 ГЛОССАРИЙ

2 ДӘРІСТЕР

3 ПРАКТИКАЛЫҚ САБАҚТАР

4 СӨЖ ЖӘНЕ СОӨЖ

ГЛОССАРИЙ
1.1 Іріктеу – «анықталған реті» бойынша элементтерді орналастыру процессі.
1.2 Басқалардан ертерек адамдармен танылатын әдіс, оның қарапайымдылығының арқасында, көпіршік сұрыптауы деп аталады (bubble sort), бұл әдісте келесі амалдар жүргізіледі: берілген ретті бұзатын көрші элементтерді орындармен ауыстыру. Бұл процесс толық файл сұрыпталған жағдайда ғана аяқталады.
1.3 Гномдардың сұрыптауы (ағылш. Gnome sort) — қосулары бар сұрыптауға ұқсаған алгоритм, бірақ керекті орынға элемент көпіршік әдісі бойынша орналастырылады.
1.4 Табиғи іріктеу (ағылш. Natural sort) — қосуы бар сұрыптаудың қарапайым және тиімді модификациясы, мұнда элементтер сұрыпталып қойған болуы мүмкін.

1.5 Жазба – кейбір құрылым немесе амал жайлы ақпараттар элементтерінң сәйкестігі. Жазбадағы әр элемент, мысалы, жұмысшының номері, тауардың бағасы, жазбаның өрісі болып аталады.


1.6 Кілт - файлды іріктеу ережелерінде қолданылатын шаманы сақтайтын өріс.
1.7 Жұптасқан алмастыру әдісі жұп және тақ қарастырулардың әртүрлі сандардан тұрады.
1.8 Тез сұрыптау – әдістің тиімділігіне әсер ететін критикалық мәнді алуға арналған әртүрлі тәсілдердің алгоритмдерінің жалпы аталуы.
1.9 Кірістік рекурсия- егер процедурада рекурсивті шақыру соңғы болмаса, онда мұндай рекурсия кірістік деп аталады.
1.10 Рекурсияның тереңдігі – бағдарламаның жұмыс барысында компьютердің жадысында сақталатын бастапқы процедураның аяқталмаған копияларының саны.
1.11 Массив – бір типті деректердің жиыны, әр элементтің өз индексі болады.
1.12 Массивтерді қосу – А массивті В массивына қосқанда С массиві пайда болады, яғни C[i]=A[i]+B[i]. Алу аналогтық түрде ұйымдастырылады.
1.13 Сыртқы сұрыптау – сыртқы сақтау құралдарында орналасқан деректерді сұрыптау.
1.14 Ішкі сұрыптау – компьютердің оперативті жадында орналасқан деректерді сұрыптау.

2 ДӘРІСТЕР
Дәріс № 1. Кіріспе. Іріктеу әдістері.
Дәрістің мақсаты – іріктеу және іздеу әдістерінің негізгі ұғымдарымен таныстыру, пәннің негізгі терминдерімен таныстыру.

Ағаштармен байланысты ұғымдар кең таралған және интуитивті түсінікті. Ағаштың бірнеше мүмкін анықтамалары бар.



Мысалы, графтар көзқарасы жағынан, ағаш деп жиі жағдайда бағытталмаған ұшы белгіленген, циклдары болмайтын, графты атайды. Бізді тек бағытталған ағаштар қызықтыратын болады, бағдарламаушылар көзқарастары жағынан. Сондықтан біз келесі рекурсивті анықтамамен қолданамыз: Т базалық типті R ағашы – бұл немесе (a) бос ағаш (бір де бір ұшы жоқ ), немесе (b) T типті кейбір ұш (ағаштың түбі) соңғы (мүмкін,нөльдік) Т базалық ағаштармен байланысқан санмен (Бұл ағаштар R ағашының ішіндегі ағаштар деп аталады). Бұл анықтамадан келесіні түсінуге болады, біржақты бағытталған тізім ағаш болып аталады. Сур. 1.


Рис. 1

Ағаштарды әртүрлі бейнеде көрсетуге болады ( бұл тек бірқалыпты иерархиялық құрылым). мысалы, 1 және 2 суреттерінде бір ағаштың екі бейнеленуі көрсетілген, бұл ағаштың базалық типінде латын алфавитінің әріптерінің көпшілігі бар. 2 суреттегі графтық бейнелеу бағдарламалау спецификасына жақынырақ.




сур. 2

Ағаштардың ішіндегі ағаштардың байланыстарын бұтаұтар деп атаймыз, ал әр ағаштың түбін ұшы деп атаймыз. Реттелген деп бұтақтары реттелген ағаштарды атаймыз. Мысалыр, 3 суретте екі реттелген ағаштар айырылады.




Рис.3

Ұштар саны немесе бұтақтар саны x ұшына жолы деп аталады. Биіетігі немесе тереңдігі деп ұштың максималды ұзындығын атаймыз.





№1 дәрісіне бақылау сұрақтары


  1. «Іріктеу және іздеу әдістері» пәнінің мақсаттары.

  2. Ағаштардың мүмкін болатын анықтамаларын атаңыз.

  3. Граф деген не?

  4. Ұшқа апаратын жолдың ұзындығы деген не?


Дәріс № 2. «Көпіршік» әдісі.

Дәрістің мақсаты- студенттерді сұрыптаудың ең қарапайым түрімен таныстыру, сұрыптау алгоритмінің спецификасымен таныстыру.

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

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

Қадам 1. аn –ді аn-1 – мен салыстырамыз, және егер аn < аn-1 онда оларды орындарымен ауыстырамыз, содан кейін аn-1 және аn-2 салыстырамыз, мүмкін, олардың да орындарын ауыстырамыз, аn-2 және аn-3 және ары қарай жалғастыра береміз, а2 және а1 элементтеріне келгенше. Нәтижесінде бірінші орында ең минималды элемент тұрады , ол содан кейін сұрыптау процессіне қактыспайды

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

Қадам 3.Ұқсас салыстырулар мен орын ауыстырулармен а3, а4, … , аn элементтерінің арасында а3 эелементінің орнына ең кіші элемент

. . . . .

Қадам n-1. Бұл сәтке дейін бірінші n-2 элементтер массивте реттелген болып тұрады, содан кейін тек екі аn-1 және аn арасында рет қою керек болады. Осы кезеңде сұрыптау процессі аяқталады.



Мысалы. 6 элемент берілген болсын –15, 33, 42, 07, 12, 19 бүтін сандар.

 

а1

а2

а3

а4

а5

а6

Орындалатын операциялар

қадам1

15

33

42

07

12

19

салыстыру 19 және 12, ауыстыру жоқ

15

33

42

07

12

19

салыстыру 12 және 07, ауыстыру жоқ

15

33

07

42

12

19

салыстыру 07 және 42, орындарын ауыстырамыз

15

07

33

42

12

19

салыстыру 07 және 33, орындарын ауыстырамыз

07

15

33

42

12

19

салыстыру 07 және 15, орындарын ауыстырамыз; 07 – минималды

қадам 2

07

15

33

42

12

19

салыстыру 19 және 12, ауыстыру жоқ

07

15

33

12

42

19

салыстыру 12 және 42, орындарын ауыстырамыз

07

15

12

33

42

19

салыстыру 12 және 33, орындарын ауыстырамыз

07

12

15

33

42

19

салыстыру 12 және 15, орындарын ауыстырамыз, 12 –екінші минималды.

қадам3

07

12

15

33

19

42

салыстыру 19 және 42, орындарын ауыстырамыз

07

12

15

19

33

42

салыстыру 19 және 33, орындарын ауыстырамыз

07

12

15

19

33

42

салыстыру 19 және 15, ауыстыру жоқ, 15 – үшінші минималды.

қадам4

07

12

15

19

33

42

салыстыру 42 және 33, ауыстыру жоқ

07

12

15

19

33

42

салыстыру 33 және 19, ауыстыру жоқ, 19 – төртінші элемент.

қадам 5

07

12

15

19

33

42

салыстыру 42 және 33, ауыстыру жоқ, сұрыптау аяқталды

 

07

12

15

19

33

42

 

Каталог: ebook -> umkd
umkd -> Мамандығына арналған Сұлтанмахмұттану ПӘнінің ОҚУ-Әдістемелік кешені
umkd -> Қазақстан Республикасының
umkd -> Қазақстан Республикасының
umkd -> Студенттерге арналған оқу әдістемелік кешені
umkd -> ПӘннің ОҚУ Әдістемелік кешені 5В011700 «Қазақ тілі мен әдебиеті» мамандығына арналған «Ұлы отан соғысы және соғыстан кейінгі жылдардағы қазақ әдебиетінің тарихы (1941-1960)» пәнінен ОҚытушыға арналған пән бағдарламасы
umkd -> «Балалар әдебиеті» пәніне арналған оқу-әдістемелік материалдар 2013 жылғы №3 басылым 5 в 050117 «Қазақ тілі мен әдебиеті»
umkd -> ПӘннің ОҚУ-Әдістемелік кешенінің
umkd -> 5 в 011700- Қазақ тілі мен әдебиеті
umkd -> 5 в 011700- Қазақ тілі мен әдебиеті
umkd -> «Филология: қазақ тілі» мамандығына арналған


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




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

    Басты бет