Алгоритмдер және деректер структурасы
ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ
СЕМЕЙ ҚАЛАСЫНЫҢ ШӘКӘРІМ АТЫНДАҒЫ УНИВЕРСИТЕТІ
3 деңгейдегі СМК
құжаты ПОӘК
ПОӘК
042-14.2.07.1.20.0103-
2013
Алгоритмдер және 03.09.2013ж
деректер структурасы №1 басылым
пәні бойынша
оқу-әдістемелік
материалдар
АЛГОРИТМДЕР ЖӘНЕ ДЕРЕКТЕР ҚҰРЫЛЫМЫ
ПӘНІН ОҚЫТУ-ӘДІСТЕМЕЛІК КЕШЕН
5В060200 - Информатика мамандығына арналған
ОҚУ-ӘДІСТЕМЕЛІК МАТЕРИАЛДАР
Семей
2013.
МАЗМҰНЫ
Глоссарий
Дәрістер
Машықтану және зертханалық сабақтар
Студенттердің өздік жұмыстарының жоспары
1. Глоссарий
1.1 Алгоритм - белгілі бір мәселені шешу үшін қойылатын мақсатқа бағытталған
іс-әрекеттердің тізбегі.
1.2 Шама- есепті шығару барысында қолданылатын белгілеулер
1.3 Тұрмыстық алгоритм - cөз түріндегі әрекеттер тізбегін күнделікті өмірде
ешбір роботтың, техниканың көмегінсіз адам өздігінен орындаса ондай алгоритмдер
1.4 Есептеу алгоритмдері - формула көмегімен шығарылатын, есептеуді қажет
ететін, күрделілігіне байланысты белгілі бір техниканың араласуын талап ететін
алгоритмдер
1.5 Рекурсивті алгоритм - есептеу алгоритмінің бір түрі. Оның нәтижесі
формуланың ішіндегі бір параметрінің мәні басқа бір өзгеріп отыратын параметрден
тәуелді болудан шығады.
1.6 Қосалқы алгоритм - күрделі алгоритмдердің бірнеше жай алгоритмге бөлінуі
арқылы негізгі алгоритмге қажетті уақытында ғана шақырылатын, жалпылама жағдайға
негізделіп дербес құрылатын алгоритмдер.
1.7 Сызықты алгоритмдер - операциялардың реті алгоритмнің өз структурасымен
анықталған және енгізетін шамалардың жеке мәндеріне тәуелсіз алгоритмдер.
1.8 Тармақты алгоритм - енгізетін шамалардың жеке мәндеріне тәуелді, бірнеше
әрекеттердің біреуінің орындалуын тағайындау.
1.9 Циклдік алгоритм - енгізетін шамалардың жеке мәндеріне тәуелді бір немесе
бірнеше әрекеттердің қайталануын тағайындау.
1.10 Енетін шамалар немесе аргументтер - алгоритм үшін бастапқы берілгендер
немесе алғашқы информация болып табылатын шамалар.
1.11 Шығатын шамалар - алгоритмнің орындалу процесінде алынатын өңделген
информацияларды сақтауға арналған шамаларды
1.12 Аралық шамалар- енетін шамаларға да, шығатын шамаларға дажатпайтын
алгоритмді орындау процесінде аралық мәндерді сақтауға арналған шамаларда
2. Дәрістер
1-тақырып: Алгоритм ұғымы. Анықтамасы. Қасиеттері. Түрлері. Алгоритмді
жазу әдістері. Алгоритм модельдері
Дәріс жоспары:
1. Алгоритмнің шығу тегі. Алгоритмнің тарихы. Алгоритмнің тұрмыста
қолданылуы. Алгоритмнің қажеттілігі. Алгоритмнің қызметі мен мақсаты.
2. Алгоритмнің ЭЕМ-дегі рөлі. Информатика ғылымындағы алгоритм. Оның
мақсаты мен міндеті.
3. Алгоритмдік конструкциялар.
- тізбектелген конструкция
- тармақталған конструкция
- циклдік конструкция
- рекурсивті конструкция
Дербес программаны құру үшін программалау тілін білу ғана
жеткіліксіз. Программаның түпкі негізі алгоритм ұғымынан құралады. Себебі
алгоритм көмегімен программист өзі құрмақшы болып отырған программаға
сәйкес мақсатқа жетуі үшін орындауы қажет әрекеттердің тізбегін құрастыруы
керек. Алгоритмнің негізгі қызметі – берілген ақпаратты өңдеу арқылы басқа,
жаңа ақпарат құру.
Сонымен алгоритм дегеніміз белгілі бір мәселені шешу үшін қойылатын
мақсатқа бағытталған іс-әрекеттердің тізбегі. Олар тұрмыстық, есептеу,
рекурсивті, қосалқы деп бөлінеді.
Сөз түріндегі әрекеттер тізбегін күнделікті өмірде ешбір роботтың,
техниканың көмегінсіз адам өздігінен орындаса ондай алгоритмдерді тұрмыстық
алгоритм дейді. Мысалы: дүкенге барып азық-түлік әкелу, сабаққа дайындалу,
т.б.
Формула көмегімен шығарылатын, есептеуді қажет ететін, күрделілігіне
байланысты белгілі бір техниканың араласуын талап ететін алгоритмдерді
есептеу алгоритмдері дейді.
Рекурсивті алгоритм деп есептеу алгоритмінің бір түрін айтады. Оның
нәтижесі формуланың ішіндегі бір параметрінің мәні басқа бір өзгеріп
отыратын параметрден тәуелді болудан шығады.
Қосалқы алгоритм дегеніміз күрделі алгоритмдердің бірнеше жай
алгоритмге бөлінуі арқылы негізгі алгоритмге қажетті уақытында ғана
шақырылатын, жалпылама жағдайға негізделіп дербес құрылатын алгоритмдер.
Қай алгоритм болса да негізгі қасиеттерді қанағаттандыруы шарт:
1. Дискреттілік қасиет – орындалатын әрекеттер тізбегі бірнеше қадамдарға
бөлініп үздікті құрылымды болуы керек. Және қадамдардың орындарын
ауыстыруға болмайды.
2. Түсініктілік қасиеті – орындаушыға түсінікті және орындай алатын
нұсқаулар жиынынан командалардан тұруы қажет. Орындаушыдан біртұтас
әрекет жасауды талап ету керек. Алгоритм орындаушыға бағытталуы керек.
3. Анықтылық қасиеті – детерминделген деп те аталады, бір алгоритмді кез
келген орындаушы орындай алатын болуы керек. Қай орындаушы орындаса да
алынатын нәтиже біреу болуы керек. Орындаушы дербес шешім
қабылдамайтындай болып құрылуы керек, яғни анық, егжей-тегжейлі
ойластырылған, толық, жалғыз нәтижелі болуы керек. Бір - екі минуттай
деген сияқты нұсқаулар болмау керек.
4. Ортақтық қасиеті – бір алгоритм барынша үлкен класқа жататын есепті
шешетіндей болуы керек, тек бастапқы берілгендерді өзгерту арқылы ғана
шешімді табуға болатындай. Мысалы квадрат теңдеуді шешу алгоритмін
ах2+bx+c=0 жағдайына құрған дұрыс болады, ал 4x2+5x-1=0 түріне құрса
онда алгоритм дербес болады, неғұрлым жалпы болуы керек.
5. Нәтижелілік қасиеті – алгоритмнің пункттері немесе нұсқаулары
шектелген, оның шегі есептің нәтижесін беретіндей болуы керек. Алынған
нәтиженің дұрыстығын анализдеу керек.
Есептеулердің құрылымына қарай алгоритмдер сызықты, тармақталған,
циклдік деп үшке бөлінді.
Операциялардың реті алгоритмнің өз структурасымен анықталған және
енгізетін шамалардың жеке мәндеріне тәуелсіз алгоритмдерді сызықты
алгоритмдер дейді. Олардың нұсқаулары бірінен кейін бірі тізбектеліп
орындалады.
Енгізетін шамалардың жеке мәндеріне тәуелді, бірнеше әрекеттердің
біреуінің орындалуын тағайындауды тармақты алгоритм дейді.
Енгізетін шамалардың жеке мәндеріне тәуелді бір немесе бірнеше
әрекеттердің қайталануын тағайындауды циклдік алгоритм дейді. Циклдік
алгоритмдер үш түрге бөлінеді:
- шарты алдынан берілген – әзірше циклі,
- шарты соңынан берілген цикл – дейін циклі,
- параметрлі цикл.
Белгілі бір логикалық шарт тексеріліп, ол ақиқат мән қабылдаған
жағдайда бір немесе бірнеше нұсқаулар тобының қайталануы әзірше циклі деп
аталады.
Белгілі бір нұсқау орындалып болған соң логикалық шарт тексеріліп, ол
жалған мән қабылдаса сол нұсқаудың қайталануы дейін циклі деп аталады.
Белгілі бір нұсқаудың немесе нұсқаулар тобының неше рет қайталануы
керек екені алдын ала анық болса, оны параметрлі цикл дейді.
Алгоритмнің берілу тәсілдері:
- формула бойынша
- таблицалық түрде
- блок-схема көмегімен
Алгоритм құру мәселесі алгоритм жазуға қандай тілді пайдаланатынымызға
байланысты болады. Тіл – кейбір мағлұматтарды өрнектеу және жеткізу құралы.
Осы мағынасына қарай
1. қатынас тілі
2. математика тілі
3. автоматтар тілі деп бөлінеді.
Алгоритмді жазу үшін пайдаланылатын тілдің сипаты орындаушының
мүмкіндіктеріне байланысты.
Орындаушылардың мүмкіндігі тіл құралдарының деңгейін анықтайды.
1. Тілдің деңгейі алгоритмдік жазу командаларының тәптіштеліп нақтылану
дәрәжесіне тәуелді. Яғни орындаушы үшін элементар деп есептелетін
амалдың шын мәніндегі элементарлық дәрежесі ашып көрсетілуі тиіс.
2. Тілдің деңгейі тілдің формальдандырылу дәрежесіне де байланысты. Ол
орындаушының кім болуынан тәуелді. Егер орындаушы адам болса, оған
белгілі бір алгоритмдерді түсінікті сөз , сөз тіркестері арқылы
түсіндіруге болады, ал рындаушы автомат болса, онда бірқатар міндетті
талаптар қойылады.
1) командаларды тұжырымдау барысында машинадан осы машина үшін қатаң
анықталған операцияларды орындауды ғана талап ету.
2) Берілген машинаның тілі үшін қабылданған нұсқаулар құру ережелерін
ғана пайдалануға болады.
3) Ережелерде көрсетілген нәрселерді ешбір қолдануға болмайды, себебі
машина ондай нұсқауларды орындамайды.
Тілді формальдандыру адам тілінің көркемдік мүмкіндіктерін азайтады.
3. Тілдің деңгейі адам үшін түсініктілік дәрежесіне де тәуелді. Алғашқы
ЭЕТ- мен қатынас цифрлар тілі деңгейінде болды. ЭЕТ жаппай
таралғандықтан адам мен машинаның қатынасуын қамсыздандыратын тілдің
жаңа деңгейлері пайда болды. Қазір тілді табиғиландыру проблемасы
алға қойылып отыр. Бұл проблема машинаның өзін жетілдірумен қатар
жүріп келеді. Ғылыми , инженерлік тілдер табиғи тіл мен математика
тілін жымдастырады. Олар: Алгол, Фортран, Бейсик, паскаль, т.б.
Кәдімгі, табиғи тілге жақын, бірақ нағыз алгоритмдік тілдердің неізгі
қасиеттері бар тілді оқу алгоритмдік тілі деп атайды. Кейде жай алгоритмдік
тіл дейді. Олар кәдімгі текст түрінде жазылады, бірақ программалау
тілдерін үйретеді.
Алгоритмдік тіл жай командалардың жазылу ережесін, құрама команданың,
алгоритм құрамын, мағынасын дәл және бір мәнді анықтау керек.
Алгоритмтік тіл – алгоритмдерді біркелкі және дәл біркелкі жазудың
және оларды орындаудың ережелер мен белгілер жүйесі.
Кәдімгі табиғи тілге жақын, екінші жағынан нағыз алгоритмдік
тілдердің негізгі қасиеттері бар тілдің анықтамасын берейік. Бұл тілді оқу
алгоритмдік тілі деп аталады. Бұл тілде жазылған алгоритмдер кәдімгі текст
сияқты оқылады және Алгол, Фортран, Бейсик т.б. программалау тілдерін
үйренуге негіз болады.
Алгоритмдік тіл – ұғымдары:
1) алфавитті – тілде қолдануға болатын символдардың, белгілердің жиынтығы.
2) Тіл конструкциясы – айнымалы, өрнек, командалардың жазылу және
алгоритмдік жазудың жалпы құрылымының ережелері. Оны синтаксис деп
атайды.
3) Семантикасы - әр түрлі командалардың қызметі мен орындалу жолы.
Алфавитте символдар, тілдің көмекші сөздері (басы, егер, онда,
әйтпесе, соңы т.б.) бар. Олардың асты сызылуы керек.
Тілдің негізгі объектілері – командалар. Олар нұсқауларды жазу үшін
қолданылады. Олар екі түрлі:
1) Жай командалар
2) Құрама командалар
Жай командалар нақтылы орындалатын элементар әрекеттердің шектеулі
сипаттамасы. Оған меншіктеу, көшу, бос командалар жатады.
Құрама командаларға тарамқталу, қайталану командалары жатады.
Алгоритмдік тілде алгоритмнің сипатталауы
Басы
Жай команда 1;
Жай команда 2;
Егер шарт
Онда 1 – серия
Әйтпесе 2 – серия
Әзір шарт
Ц.б.
Құрама команда
Ц.с.
Бітті . соңы
Алгоритмнің түрлері. Алгоритмді жазу әдістері. Алгоритм модельдері
Алгоритмдік конструкциялар:
1. Сызықты
2. тармақты
3. қайталану
4. рекурсивті
1969 жылы В. Дейкстр өзінің деректер структурасы және
алгоритмдер статьясында кез келген алгоритмді жазу үшін негізгі 3
конструкцияның – сызықты, тармақты, қайталану - жеткілікті екенін
дәлелдеген. Сызықты алгоритмді тізбекті алгоритм деп те айтады.
Анықтама. Р алгоритмі тізбекті алгоритмдік конструкциямен
қарастырылады, егер Р алгоритмінің әрбір қадамы бір рет орындалса, және
әрбір i-ші қадамнан соң (i+1)-ші қадам орындалып, i-ші қадам соңғы қадам
болмаса.
Анықтама. Р алгоритмі тармақты алгоритмдік конструкциямен
қарастырылады, егер алгоритмнің қай қадамы орындалатыны енгізілген
деректерден тәуелді болса, және белгілі бір бастапқы деректер таңдалынып
алынған соң орындалатын тармақты конструкция тізбекті конструкцияға
келтіріледі.
Анықтама. Р алгоритмі қайталану алгоритмдік конструкциямен
қарастырылады, егер алгоритмнің қандай да бір қадамдар тобы бастапқы
берілгендерге байланысты бірнеше рет қайталануы керек болса.Кез келген
циклдік конструкцияның ішінде тармақты конструкция да, тізбекті конструкция
да болады.
Анықтама. R алгоритмі рекурсивті конструкциямен қарастырылады,
егер қандай да бір қадамда ол тура немесе жанама түрде қайтадан өзіне
қатысса, немесе белгілі бір қадамда оның алдыңғы қадамында орындалған
қадамдардың нәтижесі қайталанып қолданылса.
Кез келген алгоритмнің дәл немесе дұрыстығы алгоритм моделімен
негізделеді. Модель есепті шешуде қолданылатын құралдар жиыны, яғни келесі
қадамды анықтау әдісі, қарапайым әрекеттер, қадамдар.
Алгоритмнің моделі екіге бөлінеді:
1. теориялық
2. практикалық
Модель универсалды – жан–жақты, максимальды қарапайым, есепті шешуде
минимальды есептеу құралын қажет ететін болуы керек.
Практикалық, қолданбалы модельде есептеу тиімділігі, программалау
тиімділігі болу керек.
Теориялық модельдеу үш бағытта жүреді:
1. бүтін санды аргументтен тәуелді сандық функцияны есептеу алгоритмі,
олар есептелетін функция деп аталады. Есепті шешетін рекурсивті
функция құру мүмкіндігінің бар екенін Черч, Гегель, Клини ғалымдар
ашты.
2. машиналық математикамен байланысты. Пост, Тьюринг жұмыстарында
есепті шешетін алгоритмдік процесстер – қажетті немесе сәйкес түрде
құрастырылған машина орындайтын процесс деді.
3. А.А. Марков – математик, қалыпты алгоритм түсінігін енгізді.
Жалпы алгоритмдердің келесі түрлері болады:
1. Тұрмыстық
2. Есептеу
3. Рекурсивті
4. Қосалқы
Күнделікті өмірде белгілі бір мақсатқа жету үшін орындалатын, ешқандай
роботтың көмегін талап етпейтін, адамдардың сана – сезімінен тәуелді
әрекеттер жиынын тұрмыстық алгоритмдер дейді.
Формула көмегімен шығарылатын, есептеуді қажет ететін, күрделілігіне
байланысты белгілі бір техниканың араласуын талап ететін алгоритмдерді
есептеу алгоритмдері дейді.
Рекурсивті алгоритм деп есептеу алгоритмінің бір түрін айтады. Оның
нәтижесі формуланың ішіндегі бір параметрінің мәні басқа бір өзгеріп
отыратын параметрден тәуелді болудан шығады.
Қосалқы алгоритм дегеніміз күрделі алгоритмдердің бірнеше жай
алгоритмге бөлінуі арқылы негізгі алгоритмге қажетті уақытында ғана
шақырылатын, жалпылама жағдайға негізделіп дербес құрылатын алгоритмдер.
Алгоритмдер құрылымына қарай үшке бөлінеді:
1. Сызықты
2. Тармақталған
3. Қайталану немесе циклдік
Операциялардың реті алгоритмнің өз структурасымен анықталған және
енгізетін шамалардың жеке мәндеріне тәуелсіз, тізбектеліп орындалатын
алгоритмдерді сызықты алгоритмдер дейді.
Енгізетін шамалардың жеке мәндерінен тәуелді бірнеше әрекеттердің
біреуінің орындалуын тағайындайтын алгоритмдерді тармақталған алгоритмдер
дейді.
Циклдік алгоритмдер
2 түрлі:
1) дейін - шарты алдын – ала берілген
2) әзірше - шарты соңынан берілген
дейін циклында белгілі шарт тексеріліп, егер ол ақиқат болса ғана
цикл денесі қайталанып орындалады. Егер шарт бірден жалған болса, цикл
денесі бір де бір рет орындалмайды.
Цикл денесі дегеніміз – бірнеше рет қайталанып орындалатын әрекеттер
тобы.
Блок –схемасы
кейін циклында цикл денесі берілген шарт ақиқат болғанға дейін
қайталанады.Алдынғы алгоритмнен ерекшелігі – цикл денесі шартқа дейін ең
болмағанда 1 рет орындалады.
Блок – схемасы
Өзін тексеру сұрақтары
1. Алгоритмнің қасиеттері?
2. Алгоритм түрлері?
3. Алгоритм қолданыстары?
Ұсынылатын әдебиеттер
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары
(алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс,
1998г.
4. Острейковский В.А. Информатика, Москва, 2000 г.
5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А.,
Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
2-тақырып: “Алгоритм ұғымын тереңдету, анықтау. Тьюринг машинасын
программалау. Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші”
Дәріс жоспары:
1. Алгоритм – математиканың арнайы бөлімі.
2. Джордж Бульдің математикалық логикасы.
3. Логика мен алгоритмнің байланысы.
4. Әртүрлі оқиғаларға алгоритм құру әдістері.
5. Тьюринг машинасына мысалдар.
6. Тьюринг машинасының математикалық сипаттамасы.
7. Алгоритм анықтамасын дәлдеу.
8. Пост машинасы.
9. Пост машинасы мен Тьюринг машинасын салыстыру.
Алгоритмнің қатаң анықтамасы алгоритмдердің математикалық теориясында
тікелей қолданылады. Онда алгоритмнің жалпы қасиеттері, алгоритмдік
шешілудің дәлелдемесі қарастырылады. Ал практикада алгоритмді құру қатаң
анықталмаған.
Алгоритмді орындаушы – алгоритмнің сипаттамасын дұрыс түсініп, тарата
алатын субъект немесе әрекеттер тізбегін орындай алатын құрылғы.
Әрекеттерді орындауға арналған нұсқау әлдебір тілдің араласуымен
әрбір орындаушыға түсіндіріледі. Бұл тілдің қызметші сөздері , әрекетті
түсіндіретін немесе бейнелейтін командалары, оларды біріктірудің
синтаксистік ережесі болады. Командалар тізімі орындаушының командалар
жүйесі (СКИ) деп аталады. Дискретті ақпаратты өңдеуде қолданылатын
элементарлы әрекеттер бір таңбаны басқамен алмастыру болып табылады.
Кешенді әрекеттерді орындаушы абстрактілі және шын мәніндегі құрылғы болуы
мүмкін.
Процессордың әрекеттерін ақиқат элементарлы деп – машиналық команда
деп, ал олардың белгіленуін – машиналық код деп атайды. Алғашқы – төменгі
деңгейдегі код – ассемблер коды – құрылғыдан тәуелді ішкі тіл деп аталады.
Элементарлы әрекеттерді күрделі командаларға біріктіру бұл деңгейде
әлі жүрмейді. Ассемблердің жалпы командалар саны процессор командаларының
санымен тең, бірақ машиналық кодтардың символды қалпы қолданылады
–мнемоника – бұл қолданушыға екілік кодтан тиімді.
Мнемониканы машиналық кодқа ассемблер тілі орындайды.
Элементарлы әрекеттерді біріктіру командалары жоғары деңгейдегі
программаларда пайда болды. Тіл трансляторы берілген команданы элеменарлы
қадамдарға аударады.
Одан гөрі элементарлы командаларды интеграцилауды қолданьалы
программалар орындайды. ОКЖ – і мәзір, перне, терезе т.б. интерфейсті
басқару командаларынан тұрады.
Алгоритм абстрактілі машина іспеттес.
Тьюринг машинасы – белгілі бір есептерді шығаруға арналған қатаң
математикалық құрылым, математикалық аппарат. Бұл аппарат машина деп аталу
себебі оның құрамдас бөлігінің және функцияларының есептеу техникасына
ұқсауында. Тьюринг машинасының есептеу техникасынан ерекшелігі оның еске
сақтау құрылғысы шексіз лентадан тұруында, ал есептеу техникасының еске
сақтау құрылғысы қаншалықты үлкен көлемді болса да шектеулі. Сондықтан
Тьюринг машинасын лентасы шексіз болғандықтан есептеу техникасы түрінде
қолдануға болмайды.
Тьюринг машинасымен жұмыс істеу үшін объектілер туралы ұғымдарға
тоқталу қажет.
Анықтама. Әлдебір алфавиттен алынған әріптердің кез келген тізбегі осы
алфавитте сөз деп аталады.
Анықтама. Сөздегі әріптердің саны сөз ұзындығы деп аталады. Әріптері
жоқ сөзді бос сөз дейді. Олар немесе деп белгіленеді.
Әлемдегі барлық объектілерді әртүрлі алфавиттегі сөздер түрінде
қарастыруға болады. Сондықтан алгоритмнің жұмыс істеу объектілері сөздер
болып табылады.
Анықтама. Алгоритм қолданылатын сөзді енгізілетін сөз дейді.
Алгоритмнің нәтижесі шығарылатын сөз деп аталады. Алгоритм қолданылатын
сөздердің жиыны алгоритмнің қолданылу облысы деп аталады.
Әрбір Тьюринг машинасында 2 бөлік бар:
1. Ұяшықтарға бөлінген екі жағынан да шексіз лента
2. Автомат - жазуоқу инесі
Тьюринг тезисі: Кез келген алгоритм үшін сәйкес Тьюринг машинасын
құруға болады.
Анықтама. Тьюринг машинасы деп жүйесін айтады. Мұндағы: А –
шекті –жиын, Тьюринг машинасының алфавиті, - А алфавитінің бос сөзі, Q
–Тьюринг машинасының жағдайын білдіретін шекті жиынның элементі, q1- ТМ-ның
бастапқы жағдайы, q0- МТ-ның тоқтау жағдайы, пассивті жағдай, Т-МТ-ның
жылжу жиыны, - МТ-ның программасы.
Анықтама. Алгоритм (Тьюринг бойынша) – қойылған есепті шешуге
келтірілетін Тьюринг машинасына құрылған программа.
Тьюринг машинасы мен тезисі болашақта да қолданылады, себебі кез
келген проблема шешілмейді деп айтуға болмайды, шешілмейтін есеп болмауы
керек, оны қандай да бір шешілетін түрге келтіру керек, соған
орайластырылған алгоритм құрастыру керек.
Машинаның белгілі бір процесті орындауының өзі алгоритмдік процесс
болып табылады. Сондықтан алгоритмге қойылатын талаптар мен қасиеттер оны
орындайтын машинаға да қойылады:
1) Машинаның жұмысы дискретті, бірінен кейін бірі орындалатын жеке – жеке
командалармен орындалуы керек.
2) Әрекеттер детерминделген , яғни қадамдар қатаң реттелген , ал олардың
нәтижесі алдыңғы қадамда алынған нәтижелермен тікелей байланысты болуы
керек.
3) Жұмыс алдында алғашқы берілгендер алгоритмнің анықталу облысынан алынуы
керек.
4) Саны санаулы қадамдарды орындаудан соң нәтиже алынуы керек.
5) Машина универсалды , жан – жақты болуы керек, оның көмегімен кез –
келген алгоритмді орындайтын болуы керек.
Сипатталған машинаның құрылғылары немесе структурасы қарапайым болса және
орындалатын қадамдар элементарлы болса, алгоритмнің орындалуы машинаның
жұмыс істеуі деп есептеуге болады .
Машинаның орындайтын қадамдары элементарлы болуы үшін белгілі бір алфавит
арқылы ақпаратты алмастыру керек. Сондықтан алгоритм – кез– келген ақырлы
алфавиттен берілгендерді немесе ақпаратты алмастыру
Ережелерінің ақырлы кез келген жүйесі.
Алгоритмнің анықталу облысынан алынған бастапқы берілгендер А
аофавиті және ақырлы {}таңбалар тізбегін құрасын, мұндай тізбекті сөз
дейді. Алгоритмді орындау барысында жаңа сөз құрылады {}, олар В
алфавитін құрайды. Бұл алмастыруды жүргізу үшін келесі қадамдар орындалады:
1) Бастапқы сөзінің бір сөзін В алфавитінен таңбасымен
алмастыру.
2) Бастапқы сөздің таңбасын өшіру.
3) В алфавитінен бір таңбаны бастапқы сөзге қосу.
Егер алфавитке бос таңба деп аталатын таңба қосылса, оны сөзге оң
жағынан да сол жағынан да қоссақ та сөз өзгермейді, яғни 1) операция бос
таңбаны алмастыру болады. Сонда 2) – 3) – операцияларды орындасақ та,
бәрібір 1) – қадамда тағы сол алдыңғы қадам қалады. Сондықтан абстрактылы
машина әр символды зерттейді, сосын шексіз лентаға – жадыға сақтайды,
егер символ бос болмаса оны басқа таңбамен алмастырады да жаңа қалыпта
тұрады.
Бұл машина туралы теорияны Алан Тьюринг (1936-1937), Эмиль Пост сияқты
ғалымдар ұсынған. Осы принципке сәйкестелген есептеу машиналары 8-9
жылдан кейін пайда болған.
Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші
Бұл машинаның Тьюрингтен айырмашылығы – ол өзінің теориясында
машина емес алгоритмдік жүйе деген терминді қолданған.
Оның абстрактылы машинасы бірнеше бірдей секцияларға бөлінген, оқу-
жазу инесі бар шексіз лентадан тұрады. Әр секция бос немесе толтырылған
болуы мүмкін. Лентаға түк жазылмаса секция бос, лентаға жазылып белгі
түссе секция толық деп есептеледі.
Лента жағдайы процесс уақытында өзгермелі болды. Осы лента жағдайы
мен оқу-жазу инесінің орны туралы ақпарат Пост машинасының жағдайын
айқындайды.
Инені , метка-белгі М болсын. Секция бос болса, ешбір белгі
түспейді. Бір қадам жасағанда ине оңға немесе солға 1 қадам жылжып белгіні
салады немесе өшіреді. Программадағы командаларға сәйкес машина 1 жағдайдан
келесі жағдайға көшіп отырады.
Әрбір команданың структурасы ХКУ болсын,
Х – орындалатын команда нөмірі,
К – орындалатын әрекет туралы нұсқау,
У – келесі команда нөмірі.
№ команда Командалардың Машина әрекетінің сипаттамасы
жазылуы
1 Оңға қадам Х(У Инені оңға қарай 1 секцияға жылжыту
2 Солға қадам Х(У Инені солға қарай 1 секцияға
жылжыту
3 Белгі салу Х V У Секцияға белгі қойылады
4 Белгіні өшіру Х x У Секциядан белгі өшіріледі
5 Басқаруды Х У1 Секцияда белгі жоқ болса басқару у1
ауыстыру У2 командасына, әйтпесе у2 командасына
беріледі
6 тоқтату Х стоп ! Машина жұмысын тоқтатады
7 Тармақты ? a; b Ұяшықты қарау, егер ұяшықта 0
ұйымдастыру тұрса, онда а номерлі командаға
көші, әйтпесе b нөмірлі командаға
көшу.
Бұл әрекеттерге қойылатын қосымша шарттар:
- ХМУ командасы бос секцияда орындалмайды
- ХсУ командасы толық секцияда орындалады
- У командасының нөмірі программадағы бар команда нөмірімен сәйкес болуы
керек.
Егер келтірілген шарттар сақталмаса, онда машина нәтижесіз жұмысын
аяқтайды. Х стоп командасы нәтижелі орындалады. Себебі, ол өзінің
алдындағы әрекеттер орындалып барып солардың нәтижесінде орындалады.
Кейде машина тоқтамауы мүмкін, егер командалардың ешқайсысында тоқтау
командасына көшу нөмірі болмаса.
Пост машинасы оң бүтін сандарды жазуды қарастырады, себебі кез келген
сөз цифр түрінде кодталады.
Лентада К бүтін саны К+1 келесі белгіленген секцияларда, унарлы санау
жүйесі қолданылып жазылады.
0,2,3 сандарыныің жазылуы:
М М
1 кл 25 20 10
2 кл 10 10 0
3 кл 15 13 11
. . .. .. .. .
. . .
11 кл17 18 10
кл [i, j] =
алг қосу (бүт таб кл [1:11,1:3], бүт S)
арг кл
нәт S
басы бүт i,j
S:=0
i:=1
әзір i≤11
цикл басы
j:=1
әзір j≤3
цикл басы
S:=S+ кл [i, j]
j:=j+1
цикл соңы
i:=i+1
цикл соңы
Соңы
4. реттелмеген массивте біртіндеп іздеу алгоритмі
Деректерге көп қолданылатын операциялардың бірі – іздеу. Іздеу
мәселесі ЭЕМ-нің дамуының алғашқы жылдарынан бастап басты мәселелердің бірі
болды. Аз көлемді ішкі жады мен тізбекті – лента типті құрылғыларда
сақталған деректердің арасынан керекті ақпаратты іздеу ішкі жадының
кеңейтілуін талап етті.
Іздеу операциясы екі нәтиже береді:
1. сәтті іздеу
2. сәтсіз іздеу.
Іздеу сәтті болса, ізделінді элементтің орналасқан жері табылады,
яғни ол массивтің элементінің номерін береді.
Іздеудің бірнеше әдістері бар:
1. белгілі бір элементті іздеу
2. кез келген элементті іздеу т.б.
Мысалмен қарастырсақ:
Екі жиын берілсін: және . А жиыны В жиынының ішкі жиыны
болатын, болмайтынын анықтау керек болсын.
Бұл есепті шешу үшін екі әдісті қолдануға болады:
1. Элементтер беттескенге дейін әрбір аi элементтерін сәйкес bi
элементтерімен салыстыру
2. А және В жиындарын реттеп алып, екі жиынның элементтерін бір бірімен
беттескенше салыстыру
Іздеудің бірінші нұсқасында n, m-сандары аз болғанда тиімді, ал олар
өссе, онда ә-ші әдіс тиімді болады. Алгоритмнің негізгі мазмұны оның
күрделілігінде.
Алгоритмнің күрделілігі итерация ұғымымен байланысты.
Анықтама. Итерация дегеніміз алгоритмді енгізілетін деректерге қолдану
операциясы. Әрбір келесі итерацияның бастапқы берілгендері болып оның
алдындағы итерацияда анықталған мәндер алынады.
Егер массив реттелмеген болса, онда біртіндеп іздеу әдісін қолдануға
болады:
A[1..n] массиві берілсін. P-ға тең элементті іздеу керек болсын.
1. i=1; болғанда бастаймыз
2. егер ai=p шарты орындалса, онда іздеу сәтті аяқталады
3. әйтпесе I:=i+1 деп келесі элементке көшеміз
4. егер i=n болса, онда 2-ші пунктке көшеміз, әйтпесеәздеу сәтсіз
аяқталады.
Бұл алгоритмнің күрделілігі n-1-ге тең, себебі элементтерді р-мен
салыстыру саны сонша.
5. реттелмеген массивте бинарлы іздеу алгоритмі
Егер массив реттелген болса, онда бинарлы-екілік іздеуді
қолдануға болады. Оны логарифмдік іздеу немесе дихотомия әдісі дейді.
Мұнда екі көрсеткіш пайдаланады: l=1 массивтің алғашқы
элементін көрсетеді, u=n массивтің соңғы элементін көретеді:
1. l=1; u=n; болады
2. егер ul болса, онда алгоритм сәтсәз аяқталады, әйтпесе [l,u]
аралығының ортасын табамыз. Осы моментте ізделінді k элементі массивте бар
болса, al=k=au шартының орындалатынын білеміз. I=(l+u) div 2 деп аламыз
, сонда I массивтің ортасын көрсетеді.
3. Егер kai болса, онда 4-ші пунктке көшеді, егер kai болса, онда 5-ші
пунктке көшеді, егер k=ai болса, онда іздеу сәтті аяқталады.
4. u=i-1 деп орналастырамыз және 2-ші пунктке көшеміз
5. l=i+1 деп орналастырамыз және 2-ші пунктке көшеміз.
Бұл алгоритмде күрделілік дәрежесі -ге тең болады.
Реттеу, сұрыптау алгоритмі
Деректерге көп қолданылатын амалдардың бірі – сұрыптау.
Сұрыптау дегеніміз – массив элементтерін белгілі бір ережені
сақтайтындай етіп, реттеп орналастыру.
Сұрыптау ішкі және сыртқы деп бөлінеді. Сыртқы сұрыптауға сыртқы
жадыдағы деректерді сұрыптау жатады. Ал ішкі сұрыптауға ішкі жадыға
деректерді реттеп орналастыру жатады.
Ішкі сұрыптау бірнеше әдіспен орындалады:
1. Көпіршіту әдісі
Әдістің бұлай аталуы массивтің 1-ші және 2-ші элементтері
салыстырылып, егер 1-ші элемент үлкен болса, олар орындарын ауыстырады, ал
үлкен болмаса орнында қалады, сонда ауыр элемент астына түсіп жеңілі бетіне
шығатын болғандықтан көпіршу сияқты көрінеді.
Мысалы.
a1, a2, a3, ... , an тізбегі берілген. Элементтерін өсу реті бойынша
реттеу керек.
алг реттеу (бүт n, нақ таб a[1:n])
aрг n, a
нәт a
басы бүт i, нақ Б
әзір i≤n-1
ц. б.
егер a[i] ≤a[i+1]
онда i:=i+1
әйтпесе
Б:=a[i];
a[i]:=a[i+1];
a[i+1]:=Б
i:=1;
бітті
ц. с.
а – ны шығару.
Соңы.
Дәл осылай кемуі бойынша да реттеуге болады.
2. Сызықты сұрыптау
Массивтің ішінен ең үлкен элемент табылады. Ол элемент р-шы орында
тұрсын. Сол элементті n-ші орындағы элементпен салыстырады. Егер np
болса, онда n-ші орында орналасқан элементпен орындарын ауыстырады. Әрі
қарай қалған реттелмеген элементтердің ішінен тағы ең үлкен элемент
табылады да, ол (n-1)-ші элементпен салыстырылады, егер ең үлкен элемент (n-
1)-ші элементтен үлкен болса, орнында қалады да, болмаса орындарын
ауыстырады. Осы процесс барлық элементтерге қолданылып шығады.
Алгоритмі келесідей болады:
Белгілеулер: a[1..n] –берілген массив болсын, r – массивтің реттелмеген
элементтерінің саны.
1. R=n болсын.
2. Max=max{a[1..r]} табамыз.
3. Maxr және a[max]a[r] болса, онда a{max] элементі мен a[r]
элементі орындарын ауыстырады
4. әйтпесе R=r-1 деп реттелмеген келесі элементтерге көшеміз. Алғашқы r
элементтер – реттелмеген элементтерді құрайды, ал соңғы n-r элементтер
өсуі бойынша реттеледі.
5. Егер r=1 болса, онда реттеу аяқталады, әйтпесе 2-ші пунктке көшеді.
3. Кірістіру арқылы сұрыптау.
Алдында қарастырылған көпіршіту және сызықты сұрыптау әдістері
кемімелі қадаммен сұрыптауға жатады. Шынында да, әрбір сұрыптау итерациясын
орындаған сайын реттелмеген элементтер саны 1-ге кеміп отырады.
Ал кірістіру арқылы сұрыптау өзгеше принциппен орындалады:
Массивтің алғашқы 2 элементі реттеледі де реттелген s жиынын құрайды. Сосын
келесі екі элемент реттеледі де сол жағынан үлкен элемент, оң жағынан кіші
элемент орналаспайтындай етіп s –реттелген жиынға кірістіріліп отырады. S
жиынға кірістірілетін элементтің орны дихотомия әдісімен анықталады.
Кірістіру әдісінде келесі бағалаулар дұрыс:
Салыстыру саны=1+2+[log23]+1+[log24]+1+...+[log 2(n-1)]+1=(n-1)+log2(n-
1)!=nlog2n;
Меншіктеу саны: min=0; max=3+4+5+...+n+1=(n+4)(n-1)2
Күрделілігі: O(n2)-меншіктеу саны бойынша, O(nlog2n)-салыстыру саны
бойынша.
Өзін тексеру сұрақтары
1. Реттелмеген массивте біртіндеп іздеу алгоритмі қалай жүреді?
2. Реттелген массивте бинарлы іздеу алгоритмі қалай жүреді?
3. Сұрыптаудың қандай әдістері бар?
Ұсынылатын әдебиеттер
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары
(алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс,
1998г.
4. Острейковский В.А. Информатика, Москва, 2000 г.
5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А.,
Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
6-тақырып: Алгоритмдер және деректер структурасы
Дәріс жоспары:
- негізгі түсініктер
- ақпаратты сақтау
- деректер структурасының классификациясы
- деректер структурасына қолданылатын амалдар
- программалау технологиясы
Деректер структурасы мен алгоритмдер программаның негізгі
құраушысы болып табылады. Компьютердің өзі сол деректердің структурасы мен
алгоритмдерден тұрады. Орнатылған деректердің структурасы екілік шамалар
сақталған жады сөзі және регистрлер түрінде көрінеді. Аппаратураның
конструкциясына бекітілген алгоритмдер – орандауға жататын, жадыға
енгізілген деректерден команда – бұйрық түрінде ойластырылған электронды
логикалық тізбекке айналдырылған қатаң ережелер. Сондықтан кез келген
компьютердің жұмыс негізінде тек қана деректердің бір түрімен белгілі бір
биттермен немесе екілік цифрлармен операцияларды орындауды білу жатады. Осы
деректермен компьютер тек орталық процессордың бұйрықтар жүйесімен
анықталатын, сәйкес өзгермейтін алгоритмдердің жиынымен жұмыс істейді.
Программалау тілдерінде қабылданған деректердің типтері
натуралды, бүтін, нақты сандардан, литерлерден, жолдардан, т.б. тұрады.
Кейбір программалау тілдерінде деректердің типтері компиляторда
анықталса, кейбіреуінде типті анықтап көрсету керек болады. Программада
деректердің мәндері қанша қажет болса, сонша өзгеріп, ал типі өзгеріссіз
қалуы керек.
Деректер структурасының классификациясы.
Деректердің структурасы жалпы жағдайда деректер элементтерінің
жиыны және олардың арасындағы байланыс жиыны деп қарастырылады.
Деректер структурасының классификациясы бірнеше белгілеріне
қарай анықталады:
1. Деректердің физикалық структурасы
2. Деректердің логикалық структурасы
Деректердің машина жадысында қалай орналасатыны, физикалық
көрінісі физикалық структурасы деп аталады.
Ал машина жадысында орналастырылуын есепке алмаған жағдайда
деректердің қарастырылуы логикалық структурасы деп аталады.
Жалпы деректер структурасының типтері екіге бөлінеді:
1. Қарапайым немесе жай типтер
2. интегралданған- ауқымды типтер
Жай типтерге базалық, примитивті типтер жатады. Оларды биттен
үлкен құрмалас бөліктерге бөлуге болмайды.
Ауқымды типтерге композитті, күрделі құрылымды типтер жатады.
Олардың құрамдас бөлігі басқа бір структуралар болуы мүмкін.
Деректер элементтерінің арасында айқын берілген байланыстың бар
болу, болмауына қарай деректердің структурасы тағы 2-ге бөлінеді:
1. байланысты
2. байланыссыз
Деректер структурасының маңызды белгілерінің бірі -
өзгермелілігі- элементтердің саны және олардың арасындағы байланыс өзгеріп
отырады.
Структуралардың өзгеруі элементтердің мәнінің өзгеруіне
соқтырмайды. Сондықтан структуралардың өзгермелілігіне қарай үшке бөлінеді:
1. статикалық
2. жартылай статикалық
3. динамикалық
Деректердің тағы бір маңызды белгісі – реттелгендік. Бұл
белгісіне қарай:
1. сызықты
2. сызықты емес структуралар болып бөлінеді.
Программалау тілдерінде Деректер структурасы мен Деректер
типі ұғымдары тығыз байланысты. Кез келген деректер (тұрақты шама,
айнымалы, функция мәні, өрнек т.б.) өздерінің типімен мінезделеді.
Әр тип бойынша ақпарат мына ұғымдарды бірмәнді анықтайды:
- көрсетілген типтің деректерді сақтау структурасын, яғни дерекке
ұяшық бөліп, онда қалай жазылатыны, екілік түрін ойластыруды;
- сипатталған типті объектінің қабылдайтын мәндер жиынын;
- сипатталған типті объектіге қолданылатын амалдар жиынын;
Деректер структурасына қолданылатын амалдар:
1. Құру
2. Жою
3. Таңдау
4. Жаңарту
Құру операциясы деректер структурасына жадыдан ұяшықтар бөлу
болып табылады.
Жою операциясы құруға қарама қарсы, жадыдан деректерді өшіру
болып табылады.
Таңдау операциясын структуралардың өз ішінде деректерге рұқсат
алу үшін программист қолданады. Рұқсат алу операциясының түрі қажетті
деректер структурасының типінен тәуелді.
Жаңарту операциясы деректер структурасында деректер мәндерін
өзгертуге көмектеседі.
Бұл операциялар барлық деректер структурасына жалпы
қолданылатын операцияларға жатады, ал кейбір деректер структурасына
қолданылатын арнаулы операциялар бар.
Өзін тексеру сұрақтары
1. Деректер структурасы деген не?
2. Деректер структурасына қолданылатын амалдар
3. Программалау технологиясы деген не?
Ұсынылатын әдебиеттер
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары
(алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Симонович С., Евсеев Г.Практическая информатика: Инфорком-
Пресс, 1998г.
4. Острейковский В.А. Информатика, Москва, 2000 г.
5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов
М.А., Шкатов П.Н. Вычислительная техника и программирование,
Москва, 1990.
7-тақырып: Деректердің жай структурасы
Дәріс жоспары:
1. сандық типтер
• бүтін
• нақты
• ондық
• сандық типтерге қолданылатын операциялар
2. Биттік типтер
3. Логикалық типтер
4. Терілімді типтер
5. Шектелген типтер
6. Көрсеткіштер
Деректер структурасы қабылдайтын мәндерінің түрлеріне қарай келесі
типтерге бөлінеді:
1. Сандық типтер
2. Биттік типтер
3. Логикалық типтер
4. Символдық типтер
5. Терілімді типтер
6. Шектелген типтер
7. Көрсеткіштер
8. Тізімдер
9. Жазулар
10. Файлдар
11. Массивтер
12. Жиындар
13. Таблицалар
14. Стектер
15. Кезектер
16. Дектер
17. Жолдар
18. Динамикалық типтер
19. Графтар
20. Ағаштар (бұтақтар)
Жай типтерге жататындары:
1. Сандық
2. Биттік
3. Логикалық
4. Символдық
5. Терілімді
6. Шектелген
7. Көрсеткіштер
Сандық типтер нақты-ондық, бүтін типтер деп бөлінеді. Бүтін сандар
көмегімен табиғаты жағынан дискретті – объектілерінің саны санаулы болатын
объектілердің саны беріледі. Таңбалы сандарды ЭЕМ-ң жадысында орналастыруда
екілік кодпен немесе қосымша кодпен кодтау әдісі қолданылады. Олардың
ұзындығы 1,2,4 байт болуы мүмкін. Осыған байланысты бүтін типті деректердің
өзі ұзын бүтін, қысқа бүтін, бүтін болып бөлінеді, оларға сәйкес байттық
орындар бөлінеді.
Нақты типті деректердің өзі тұрақты нүктелі, айнымалы нүктелі болып
бөлінеді, олардың да жадыдағы байттары әртүрлі. Бүтін сандардың мәні жадыда
дәл анықталса, нақты сандардың мәні белгілі бір дәлдікпен анықталады.
Биттік типтер деректердің екілік разрядтарымен жұмыс жасауға
көмектееді. Биттік типтер бір бірімен байланысы жоқ байттардың жиыны.
Логикалық типтер логикалық ақиқат, жалған, иә, жоқ сияқты мәндерді
қабылдайтын, 1 байт орын алатын деректер.
Символдық типтер алдын ала анықталған символдар жиыныннан қабылданатын
мәндер. Дербес ЭЕМ-дерде көбіне стандартты ASCII –символдар коды таблицасы
орнатылған, одан басқа EBCDIC-кодтар таблицасы да бар. Символдық типті
деректерге салыстыру, жалғастыру операциясы қолданылады.
Терілімді типтерге қолданушы анықтайтын, өз бетімен құратын белгілі
бір шарттарға байланысты топтастырылған деректер жиынынан тұратын типтер
жатады. Мысалы: жылдың он екі айы, апта күндері, т.б.
Шектелген типтерге терілімді типтердің ішінен белгілі бір аралықты
қамтитын деректерден құралатын, кей жағдайда қолданушы өзі анықтайтын
деректер типтері жатады. Мысалы: жаз айлары, қыс айлары, демалыс күндері,
т.б.
Көрсеткіштер деректер орналасқан ұяшықтың адресін анықтайтын типтер.
Олар типтендірілген көрсеткіштер және типтендірілмеген көрсеткіштер деп
бөлінеді. Егер типтендірілген көрсеткіш деп жарияланса, онда олар бүтінге
көрсеткіш, символға көрсеткіш т.б. деп аталуы мүмкін. Ал типтендірілмеген
көрсеткіштер кез келген ұяшықтың адресін анықтайды, ол деректердің мәніне
көңіл аудармайды. Көрсеткіштер деректерді алмастыру уақытында жадыны
реттеуге тиімді.
Өзін тексеру сұрақтары
1. Деректердің қандай типтері бар?
2. Сандық типтер қалайша бқлінеді?
3. Күрделі типтер қалайша бөлінеді?
Ұсынылатын әдебиеттер
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары
(алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс,
1998г.
4. Острейковский В.А. Информатика, Москва, 2000 г.
5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А.,
Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
8-тақырып: Деректердің статикалық структурасы
Дәріс жоспары:
7. векторлар
8. массивтер
9. жиындар
10. жазулар
11. таблицалар
Деректердің статикалық структурасы базалық, примитивті структуралардың
құрылымды жиынынан тұрады. Оларға жады тұрақты-автоматты түрде бөлінеді,
себебі олардың мәндері өзгермейді.
Векторлар – бір өлшемді массивтер- бір типті саны санаулы элементтер
жиынынан тұратын деректер. Вектордың әр элементінің нөмірі оның тұрған
орнын анықтайды. Элементтері тізбектелген ұяшықтар жиынын құрайды.
Элементтің типіне қарай жадыдан байттар бөлінеді. Жады көлемі элементтер
санын элементтер ұзындығына көбейту арқылы анықталады.
Массивтер – екі өлшемді, көп өлшемді болады.
Біртипті саны санаулы элементтердің жиынтығынан тұратын, әрбір
элементі индекспен номерленген, индекстерінің саны массив өлшемін
білдіретін атаулы деректерді массив дейді.
Массивті қолдану үшін оның атауы және индексі анықталуы керек. Екі
индексті массив екі өлшемді, үш индексті массив үш өлшемді деп аталады.
Жазулар (структуралар).
Әртүрлі типті деректерді анықтайтын өрістердің ақырлы реттелген жиыны
жазулар деп аталады.
Жазуларды белгілі бір заттық облыстан алынған объектіні толық анықтап,
программалау үшін қолданған тиімді. Жазу өрістермен құралады. Өрістерді
компоненттер деп те атайды. Жазу деректер таблицасын еске түсіреді.
Таблицаның бағандарының атаулары өрістер, таблицаның әр жолы жазу немесе
жазба деп аталады Программада жазулар өздерінің атауымен және өріс атауымен
біріктіріліп қолданылады.
Жиындар - біртипті, мәндері қайталанбайтын деректердің жиынтығы.
Жиын базалық типке жататын деректердің бәрін қабылдайды. Базалық тип
256 мүмкін мәндерден аспауы керек, жадыда 32 байтқа дейін орын алады және
массивтер сияқты орналасады, элементтері индекстеледі.
Таблицалар - элементтері жазу болатын векторды айтуға болады. Вектор
сияқты әр элементі индекстелмейді. Әр өрісті толық анықтайтын кілттік өріс
тағайындалып, сол кілт бойынша деректер қолданылады. Кілт - біртипті көп
жазулардың жиынынан таңдалынатын мәндері қайталанбайтын белгілі бір өріс.
Бір таблицада бір немесе бірнеше кілт болуы мүмкін. Таблицаға логикалық
деңгейдегі операциялар қолданылады: іздеу, сұрыптау.
Іздеу операциясы екі әдіспен орындалады:
1. Біртіндеп іздеу немесе сызықты іздеу
Деректер реттелмеген болса, элементтің кілті анықталып, кілттің
мәнімен жазулар салыстырылады, сәйкестік болса жазудың табылғаны туралы
ақпарат шығады, әйтпесе іздеу сәтсіз аяқталады.
2. Бинарлы іздеу.
Жазулар таблицаға алфавит бойынша немесе өсу реті бойынша енгізіледі.
Белгілі бір жазуды іздеу таблицаның ортасындағы сол жазуға сәйкес кілттік
өрістің мәнін зерттеуден басталады. Егер кілттің мәні үлкен болса, онда
таблицаның үстіңгі жартысының ортасындағы жазуға сәйкес кілттің мәні
тексеріледі, осы процедура таблицаның үстіңгі жартысында сәйкес жазу
табылғанша жалғасады да, егер іздеу сәтті аяқталса іздеу тоқтатылады. Егер
кілттің мәні кішкентай болса, онда таблицаның төменгі жартысының ортаңғы
жазуына сәйкес кілт мәні тексеріледі,
Таблицаны сұрыптау белгілі бір ереже талабын қанағаттандыратындай
етіп жазуларды реттеуге жатады. Сұрыптау алгоритмдері көп, оны таңдауға
әсер ететін факторлар:
- Қол астында бар жады ресурсы: енгізілетін және шығарылатын жиындар
жадының әртүрлі облысында орналасуы керек пе, әлде шығарылатын жиындар
енгізілетін жиындардың орнына жазылуы керек пе - сол зерттеледі.
- Енгізілетін жиындар бастапқы кезден бастапреттелген болуы.
- Операцияның уақытша мінездемесі: алгоритмнің жылдам орындалуы үшін
кілттік өрістің мәндері сандық тип немесе символдық тип болуы ескеріледі.
- Алгоритмнің күрделілігі: алгоритм неғұрлым қарапайым болса, орындалуы
соғұрлым жеңіл болады.
Сұрыптау стратегиялары:
1. Таңдау стратегиясы. - енгізілетін жиыннан реттелу шартын
қанағаттандыратын элемент таңдалынып алынады да номеріне байланысты орны
анықталып, шығарылатын жиынға енгізіледі.
2. Енгізу стратегиясы - енгізілетін жиыннан номерлі элемент таңдалынып,
реттелу шартына сәйкес орнын анықтап шығарылатын жиынға енгізіледі.
3. Тарату, орналастыру стратегиясы - енгізілетін жиын бірнеше ішкі жиынға
бөлінеді де, сұрыптау әр ішкі жиында жүргізіледі.
4 Біріктіру, жымдастыру стратегиясы - Сұрыпталған әрбір ішкі жиынды
жымдастыру арқылы шығарылатын жиын құрастырылады.
Көпмүшелікті Горнер схемасымен есептеу алгоритмі
y= a0xn+a1 xn-1+...+an-1 x + an теңдеуімен берілген көрсеткіші n-ге
тең көпмүшеліктің мәнін есептеү керек.
Горнер схемасы бұл көпмүшеліктегі көбейту және қосу амалдарының санын
максималды ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
СЕМЕЙ ҚАЛАСЫНЫҢ ШӘКӘРІМ АТЫНДАҒЫ УНИВЕРСИТЕТІ
3 деңгейдегі СМК
құжаты ПОӘК
ПОӘК
042-14.2.07.1.20.0103-
2013
Алгоритмдер және 03.09.2013ж
деректер структурасы №1 басылым
пәні бойынша
оқу-әдістемелік
материалдар
АЛГОРИТМДЕР ЖӘНЕ ДЕРЕКТЕР ҚҰРЫЛЫМЫ
ПӘНІН ОҚЫТУ-ӘДІСТЕМЕЛІК КЕШЕН
5В060200 - Информатика мамандығына арналған
ОҚУ-ӘДІСТЕМЕЛІК МАТЕРИАЛДАР
Семей
2013.
МАЗМҰНЫ
Глоссарий
Дәрістер
Машықтану және зертханалық сабақтар
Студенттердің өздік жұмыстарының жоспары
1. Глоссарий
1.1 Алгоритм - белгілі бір мәселені шешу үшін қойылатын мақсатқа бағытталған
іс-әрекеттердің тізбегі.
1.2 Шама- есепті шығару барысында қолданылатын белгілеулер
1.3 Тұрмыстық алгоритм - cөз түріндегі әрекеттер тізбегін күнделікті өмірде
ешбір роботтың, техниканың көмегінсіз адам өздігінен орындаса ондай алгоритмдер
1.4 Есептеу алгоритмдері - формула көмегімен шығарылатын, есептеуді қажет
ететін, күрделілігіне байланысты белгілі бір техниканың араласуын талап ететін
алгоритмдер
1.5 Рекурсивті алгоритм - есептеу алгоритмінің бір түрі. Оның нәтижесі
формуланың ішіндегі бір параметрінің мәні басқа бір өзгеріп отыратын параметрден
тәуелді болудан шығады.
1.6 Қосалқы алгоритм - күрделі алгоритмдердің бірнеше жай алгоритмге бөлінуі
арқылы негізгі алгоритмге қажетті уақытында ғана шақырылатын, жалпылама жағдайға
негізделіп дербес құрылатын алгоритмдер.
1.7 Сызықты алгоритмдер - операциялардың реті алгоритмнің өз структурасымен
анықталған және енгізетін шамалардың жеке мәндеріне тәуелсіз алгоритмдер.
1.8 Тармақты алгоритм - енгізетін шамалардың жеке мәндеріне тәуелді, бірнеше
әрекеттердің біреуінің орындалуын тағайындау.
1.9 Циклдік алгоритм - енгізетін шамалардың жеке мәндеріне тәуелді бір немесе
бірнеше әрекеттердің қайталануын тағайындау.
1.10 Енетін шамалар немесе аргументтер - алгоритм үшін бастапқы берілгендер
немесе алғашқы информация болып табылатын шамалар.
1.11 Шығатын шамалар - алгоритмнің орындалу процесінде алынатын өңделген
информацияларды сақтауға арналған шамаларды
1.12 Аралық шамалар- енетін шамаларға да, шығатын шамаларға дажатпайтын
алгоритмді орындау процесінде аралық мәндерді сақтауға арналған шамаларда
2. Дәрістер
1-тақырып: Алгоритм ұғымы. Анықтамасы. Қасиеттері. Түрлері. Алгоритмді
жазу әдістері. Алгоритм модельдері
Дәріс жоспары:
1. Алгоритмнің шығу тегі. Алгоритмнің тарихы. Алгоритмнің тұрмыста
қолданылуы. Алгоритмнің қажеттілігі. Алгоритмнің қызметі мен мақсаты.
2. Алгоритмнің ЭЕМ-дегі рөлі. Информатика ғылымындағы алгоритм. Оның
мақсаты мен міндеті.
3. Алгоритмдік конструкциялар.
- тізбектелген конструкция
- тармақталған конструкция
- циклдік конструкция
- рекурсивті конструкция
Дербес программаны құру үшін программалау тілін білу ғана
жеткіліксіз. Программаның түпкі негізі алгоритм ұғымынан құралады. Себебі
алгоритм көмегімен программист өзі құрмақшы болып отырған программаға
сәйкес мақсатқа жетуі үшін орындауы қажет әрекеттердің тізбегін құрастыруы
керек. Алгоритмнің негізгі қызметі – берілген ақпаратты өңдеу арқылы басқа,
жаңа ақпарат құру.
Сонымен алгоритм дегеніміз белгілі бір мәселені шешу үшін қойылатын
мақсатқа бағытталған іс-әрекеттердің тізбегі. Олар тұрмыстық, есептеу,
рекурсивті, қосалқы деп бөлінеді.
Сөз түріндегі әрекеттер тізбегін күнделікті өмірде ешбір роботтың,
техниканың көмегінсіз адам өздігінен орындаса ондай алгоритмдерді тұрмыстық
алгоритм дейді. Мысалы: дүкенге барып азық-түлік әкелу, сабаққа дайындалу,
т.б.
Формула көмегімен шығарылатын, есептеуді қажет ететін, күрделілігіне
байланысты белгілі бір техниканың араласуын талап ететін алгоритмдерді
есептеу алгоритмдері дейді.
Рекурсивті алгоритм деп есептеу алгоритмінің бір түрін айтады. Оның
нәтижесі формуланың ішіндегі бір параметрінің мәні басқа бір өзгеріп
отыратын параметрден тәуелді болудан шығады.
Қосалқы алгоритм дегеніміз күрделі алгоритмдердің бірнеше жай
алгоритмге бөлінуі арқылы негізгі алгоритмге қажетті уақытында ғана
шақырылатын, жалпылама жағдайға негізделіп дербес құрылатын алгоритмдер.
Қай алгоритм болса да негізгі қасиеттерді қанағаттандыруы шарт:
1. Дискреттілік қасиет – орындалатын әрекеттер тізбегі бірнеше қадамдарға
бөлініп үздікті құрылымды болуы керек. Және қадамдардың орындарын
ауыстыруға болмайды.
2. Түсініктілік қасиеті – орындаушыға түсінікті және орындай алатын
нұсқаулар жиынынан командалардан тұруы қажет. Орындаушыдан біртұтас
әрекет жасауды талап ету керек. Алгоритм орындаушыға бағытталуы керек.
3. Анықтылық қасиеті – детерминделген деп те аталады, бір алгоритмді кез
келген орындаушы орындай алатын болуы керек. Қай орындаушы орындаса да
алынатын нәтиже біреу болуы керек. Орындаушы дербес шешім
қабылдамайтындай болып құрылуы керек, яғни анық, егжей-тегжейлі
ойластырылған, толық, жалғыз нәтижелі болуы керек. Бір - екі минуттай
деген сияқты нұсқаулар болмау керек.
4. Ортақтық қасиеті – бір алгоритм барынша үлкен класқа жататын есепті
шешетіндей болуы керек, тек бастапқы берілгендерді өзгерту арқылы ғана
шешімді табуға болатындай. Мысалы квадрат теңдеуді шешу алгоритмін
ах2+bx+c=0 жағдайына құрған дұрыс болады, ал 4x2+5x-1=0 түріне құрса
онда алгоритм дербес болады, неғұрлым жалпы болуы керек.
5. Нәтижелілік қасиеті – алгоритмнің пункттері немесе нұсқаулары
шектелген, оның шегі есептің нәтижесін беретіндей болуы керек. Алынған
нәтиженің дұрыстығын анализдеу керек.
Есептеулердің құрылымына қарай алгоритмдер сызықты, тармақталған,
циклдік деп үшке бөлінді.
Операциялардың реті алгоритмнің өз структурасымен анықталған және
енгізетін шамалардың жеке мәндеріне тәуелсіз алгоритмдерді сызықты
алгоритмдер дейді. Олардың нұсқаулары бірінен кейін бірі тізбектеліп
орындалады.
Енгізетін шамалардың жеке мәндеріне тәуелді, бірнеше әрекеттердің
біреуінің орындалуын тағайындауды тармақты алгоритм дейді.
Енгізетін шамалардың жеке мәндеріне тәуелді бір немесе бірнеше
әрекеттердің қайталануын тағайындауды циклдік алгоритм дейді. Циклдік
алгоритмдер үш түрге бөлінеді:
- шарты алдынан берілген – әзірше циклі,
- шарты соңынан берілген цикл – дейін циклі,
- параметрлі цикл.
Белгілі бір логикалық шарт тексеріліп, ол ақиқат мән қабылдаған
жағдайда бір немесе бірнеше нұсқаулар тобының қайталануы әзірше циклі деп
аталады.
Белгілі бір нұсқау орындалып болған соң логикалық шарт тексеріліп, ол
жалған мән қабылдаса сол нұсқаудың қайталануы дейін циклі деп аталады.
Белгілі бір нұсқаудың немесе нұсқаулар тобының неше рет қайталануы
керек екені алдын ала анық болса, оны параметрлі цикл дейді.
Алгоритмнің берілу тәсілдері:
- формула бойынша
- таблицалық түрде
- блок-схема көмегімен
Алгоритм құру мәселесі алгоритм жазуға қандай тілді пайдаланатынымызға
байланысты болады. Тіл – кейбір мағлұматтарды өрнектеу және жеткізу құралы.
Осы мағынасына қарай
1. қатынас тілі
2. математика тілі
3. автоматтар тілі деп бөлінеді.
Алгоритмді жазу үшін пайдаланылатын тілдің сипаты орындаушының
мүмкіндіктеріне байланысты.
Орындаушылардың мүмкіндігі тіл құралдарының деңгейін анықтайды.
1. Тілдің деңгейі алгоритмдік жазу командаларының тәптіштеліп нақтылану
дәрәжесіне тәуелді. Яғни орындаушы үшін элементар деп есептелетін
амалдың шын мәніндегі элементарлық дәрежесі ашып көрсетілуі тиіс.
2. Тілдің деңгейі тілдің формальдандырылу дәрежесіне де байланысты. Ол
орындаушының кім болуынан тәуелді. Егер орындаушы адам болса, оған
белгілі бір алгоритмдерді түсінікті сөз , сөз тіркестері арқылы
түсіндіруге болады, ал рындаушы автомат болса, онда бірқатар міндетті
талаптар қойылады.
1) командаларды тұжырымдау барысында машинадан осы машина үшін қатаң
анықталған операцияларды орындауды ғана талап ету.
2) Берілген машинаның тілі үшін қабылданған нұсқаулар құру ережелерін
ғана пайдалануға болады.
3) Ережелерде көрсетілген нәрселерді ешбір қолдануға болмайды, себебі
машина ондай нұсқауларды орындамайды.
Тілді формальдандыру адам тілінің көркемдік мүмкіндіктерін азайтады.
3. Тілдің деңгейі адам үшін түсініктілік дәрежесіне де тәуелді. Алғашқы
ЭЕТ- мен қатынас цифрлар тілі деңгейінде болды. ЭЕТ жаппай
таралғандықтан адам мен машинаның қатынасуын қамсыздандыратын тілдің
жаңа деңгейлері пайда болды. Қазір тілді табиғиландыру проблемасы
алға қойылып отыр. Бұл проблема машинаның өзін жетілдірумен қатар
жүріп келеді. Ғылыми , инженерлік тілдер табиғи тіл мен математика
тілін жымдастырады. Олар: Алгол, Фортран, Бейсик, паскаль, т.б.
Кәдімгі, табиғи тілге жақын, бірақ нағыз алгоритмдік тілдердің неізгі
қасиеттері бар тілді оқу алгоритмдік тілі деп атайды. Кейде жай алгоритмдік
тіл дейді. Олар кәдімгі текст түрінде жазылады, бірақ программалау
тілдерін үйретеді.
Алгоритмдік тіл жай командалардың жазылу ережесін, құрама команданың,
алгоритм құрамын, мағынасын дәл және бір мәнді анықтау керек.
Алгоритмтік тіл – алгоритмдерді біркелкі және дәл біркелкі жазудың
және оларды орындаудың ережелер мен белгілер жүйесі.
Кәдімгі табиғи тілге жақын, екінші жағынан нағыз алгоритмдік
тілдердің негізгі қасиеттері бар тілдің анықтамасын берейік. Бұл тілді оқу
алгоритмдік тілі деп аталады. Бұл тілде жазылған алгоритмдер кәдімгі текст
сияқты оқылады және Алгол, Фортран, Бейсик т.б. программалау тілдерін
үйренуге негіз болады.
Алгоритмдік тіл – ұғымдары:
1) алфавитті – тілде қолдануға болатын символдардың, белгілердің жиынтығы.
2) Тіл конструкциясы – айнымалы, өрнек, командалардың жазылу және
алгоритмдік жазудың жалпы құрылымының ережелері. Оны синтаксис деп
атайды.
3) Семантикасы - әр түрлі командалардың қызметі мен орындалу жолы.
Алфавитте символдар, тілдің көмекші сөздері (басы, егер, онда,
әйтпесе, соңы т.б.) бар. Олардың асты сызылуы керек.
Тілдің негізгі объектілері – командалар. Олар нұсқауларды жазу үшін
қолданылады. Олар екі түрлі:
1) Жай командалар
2) Құрама командалар
Жай командалар нақтылы орындалатын элементар әрекеттердің шектеулі
сипаттамасы. Оған меншіктеу, көшу, бос командалар жатады.
Құрама командаларға тарамқталу, қайталану командалары жатады.
Алгоритмдік тілде алгоритмнің сипатталауы
Басы
Жай команда 1;
Жай команда 2;
Егер шарт
Онда 1 – серия
Әйтпесе 2 – серия
Әзір шарт
Ц.б.
Құрама команда
Ц.с.
Бітті . соңы
Алгоритмнің түрлері. Алгоритмді жазу әдістері. Алгоритм модельдері
Алгоритмдік конструкциялар:
1. Сызықты
2. тармақты
3. қайталану
4. рекурсивті
1969 жылы В. Дейкстр өзінің деректер структурасы және
алгоритмдер статьясында кез келген алгоритмді жазу үшін негізгі 3
конструкцияның – сызықты, тармақты, қайталану - жеткілікті екенін
дәлелдеген. Сызықты алгоритмді тізбекті алгоритм деп те айтады.
Анықтама. Р алгоритмі тізбекті алгоритмдік конструкциямен
қарастырылады, егер Р алгоритмінің әрбір қадамы бір рет орындалса, және
әрбір i-ші қадамнан соң (i+1)-ші қадам орындалып, i-ші қадам соңғы қадам
болмаса.
Анықтама. Р алгоритмі тармақты алгоритмдік конструкциямен
қарастырылады, егер алгоритмнің қай қадамы орындалатыны енгізілген
деректерден тәуелді болса, және белгілі бір бастапқы деректер таңдалынып
алынған соң орындалатын тармақты конструкция тізбекті конструкцияға
келтіріледі.
Анықтама. Р алгоритмі қайталану алгоритмдік конструкциямен
қарастырылады, егер алгоритмнің қандай да бір қадамдар тобы бастапқы
берілгендерге байланысты бірнеше рет қайталануы керек болса.Кез келген
циклдік конструкцияның ішінде тармақты конструкция да, тізбекті конструкция
да болады.
Анықтама. R алгоритмі рекурсивті конструкциямен қарастырылады,
егер қандай да бір қадамда ол тура немесе жанама түрде қайтадан өзіне
қатысса, немесе белгілі бір қадамда оның алдыңғы қадамында орындалған
қадамдардың нәтижесі қайталанып қолданылса.
Кез келген алгоритмнің дәл немесе дұрыстығы алгоритм моделімен
негізделеді. Модель есепті шешуде қолданылатын құралдар жиыны, яғни келесі
қадамды анықтау әдісі, қарапайым әрекеттер, қадамдар.
Алгоритмнің моделі екіге бөлінеді:
1. теориялық
2. практикалық
Модель универсалды – жан–жақты, максимальды қарапайым, есепті шешуде
минимальды есептеу құралын қажет ететін болуы керек.
Практикалық, қолданбалы модельде есептеу тиімділігі, программалау
тиімділігі болу керек.
Теориялық модельдеу үш бағытта жүреді:
1. бүтін санды аргументтен тәуелді сандық функцияны есептеу алгоритмі,
олар есептелетін функция деп аталады. Есепті шешетін рекурсивті
функция құру мүмкіндігінің бар екенін Черч, Гегель, Клини ғалымдар
ашты.
2. машиналық математикамен байланысты. Пост, Тьюринг жұмыстарында
есепті шешетін алгоритмдік процесстер – қажетті немесе сәйкес түрде
құрастырылған машина орындайтын процесс деді.
3. А.А. Марков – математик, қалыпты алгоритм түсінігін енгізді.
Жалпы алгоритмдердің келесі түрлері болады:
1. Тұрмыстық
2. Есептеу
3. Рекурсивті
4. Қосалқы
Күнделікті өмірде белгілі бір мақсатқа жету үшін орындалатын, ешқандай
роботтың көмегін талап етпейтін, адамдардың сана – сезімінен тәуелді
әрекеттер жиынын тұрмыстық алгоритмдер дейді.
Формула көмегімен шығарылатын, есептеуді қажет ететін, күрделілігіне
байланысты белгілі бір техниканың араласуын талап ететін алгоритмдерді
есептеу алгоритмдері дейді.
Рекурсивті алгоритм деп есептеу алгоритмінің бір түрін айтады. Оның
нәтижесі формуланың ішіндегі бір параметрінің мәні басқа бір өзгеріп
отыратын параметрден тәуелді болудан шығады.
Қосалқы алгоритм дегеніміз күрделі алгоритмдердің бірнеше жай
алгоритмге бөлінуі арқылы негізгі алгоритмге қажетті уақытында ғана
шақырылатын, жалпылама жағдайға негізделіп дербес құрылатын алгоритмдер.
Алгоритмдер құрылымына қарай үшке бөлінеді:
1. Сызықты
2. Тармақталған
3. Қайталану немесе циклдік
Операциялардың реті алгоритмнің өз структурасымен анықталған және
енгізетін шамалардың жеке мәндеріне тәуелсіз, тізбектеліп орындалатын
алгоритмдерді сызықты алгоритмдер дейді.
Енгізетін шамалардың жеке мәндерінен тәуелді бірнеше әрекеттердің
біреуінің орындалуын тағайындайтын алгоритмдерді тармақталған алгоритмдер
дейді.
Циклдік алгоритмдер
2 түрлі:
1) дейін - шарты алдын – ала берілген
2) әзірше - шарты соңынан берілген
дейін циклында белгілі шарт тексеріліп, егер ол ақиқат болса ғана
цикл денесі қайталанып орындалады. Егер шарт бірден жалған болса, цикл
денесі бір де бір рет орындалмайды.
Цикл денесі дегеніміз – бірнеше рет қайталанып орындалатын әрекеттер
тобы.
Блок –схемасы
кейін циклында цикл денесі берілген шарт ақиқат болғанға дейін
қайталанады.Алдынғы алгоритмнен ерекшелігі – цикл денесі шартқа дейін ең
болмағанда 1 рет орындалады.
Блок – схемасы
Өзін тексеру сұрақтары
1. Алгоритмнің қасиеттері?
2. Алгоритм түрлері?
3. Алгоритм қолданыстары?
Ұсынылатын әдебиеттер
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары
(алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс,
1998г.
4. Острейковский В.А. Информатика, Москва, 2000 г.
5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А.,
Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
2-тақырып: “Алгоритм ұғымын тереңдету, анықтау. Тьюринг машинасын
программалау. Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші”
Дәріс жоспары:
1. Алгоритм – математиканың арнайы бөлімі.
2. Джордж Бульдің математикалық логикасы.
3. Логика мен алгоритмнің байланысы.
4. Әртүрлі оқиғаларға алгоритм құру әдістері.
5. Тьюринг машинасына мысалдар.
6. Тьюринг машинасының математикалық сипаттамасы.
7. Алгоритм анықтамасын дәлдеу.
8. Пост машинасы.
9. Пост машинасы мен Тьюринг машинасын салыстыру.
Алгоритмнің қатаң анықтамасы алгоритмдердің математикалық теориясында
тікелей қолданылады. Онда алгоритмнің жалпы қасиеттері, алгоритмдік
шешілудің дәлелдемесі қарастырылады. Ал практикада алгоритмді құру қатаң
анықталмаған.
Алгоритмді орындаушы – алгоритмнің сипаттамасын дұрыс түсініп, тарата
алатын субъект немесе әрекеттер тізбегін орындай алатын құрылғы.
Әрекеттерді орындауға арналған нұсқау әлдебір тілдің араласуымен
әрбір орындаушыға түсіндіріледі. Бұл тілдің қызметші сөздері , әрекетті
түсіндіретін немесе бейнелейтін командалары, оларды біріктірудің
синтаксистік ережесі болады. Командалар тізімі орындаушының командалар
жүйесі (СКИ) деп аталады. Дискретті ақпаратты өңдеуде қолданылатын
элементарлы әрекеттер бір таңбаны басқамен алмастыру болып табылады.
Кешенді әрекеттерді орындаушы абстрактілі және шын мәніндегі құрылғы болуы
мүмкін.
Процессордың әрекеттерін ақиқат элементарлы деп – машиналық команда
деп, ал олардың белгіленуін – машиналық код деп атайды. Алғашқы – төменгі
деңгейдегі код – ассемблер коды – құрылғыдан тәуелді ішкі тіл деп аталады.
Элементарлы әрекеттерді күрделі командаларға біріктіру бұл деңгейде
әлі жүрмейді. Ассемблердің жалпы командалар саны процессор командаларының
санымен тең, бірақ машиналық кодтардың символды қалпы қолданылады
–мнемоника – бұл қолданушыға екілік кодтан тиімді.
Мнемониканы машиналық кодқа ассемблер тілі орындайды.
Элементарлы әрекеттерді біріктіру командалары жоғары деңгейдегі
программаларда пайда болды. Тіл трансляторы берілген команданы элеменарлы
қадамдарға аударады.
Одан гөрі элементарлы командаларды интеграцилауды қолданьалы
программалар орындайды. ОКЖ – і мәзір, перне, терезе т.б. интерфейсті
басқару командаларынан тұрады.
Алгоритм абстрактілі машина іспеттес.
Тьюринг машинасы – белгілі бір есептерді шығаруға арналған қатаң
математикалық құрылым, математикалық аппарат. Бұл аппарат машина деп аталу
себебі оның құрамдас бөлігінің және функцияларының есептеу техникасына
ұқсауында. Тьюринг машинасының есептеу техникасынан ерекшелігі оның еске
сақтау құрылғысы шексіз лентадан тұруында, ал есептеу техникасының еске
сақтау құрылғысы қаншалықты үлкен көлемді болса да шектеулі. Сондықтан
Тьюринг машинасын лентасы шексіз болғандықтан есептеу техникасы түрінде
қолдануға болмайды.
Тьюринг машинасымен жұмыс істеу үшін объектілер туралы ұғымдарға
тоқталу қажет.
Анықтама. Әлдебір алфавиттен алынған әріптердің кез келген тізбегі осы
алфавитте сөз деп аталады.
Анықтама. Сөздегі әріптердің саны сөз ұзындығы деп аталады. Әріптері
жоқ сөзді бос сөз дейді. Олар немесе деп белгіленеді.
Әлемдегі барлық объектілерді әртүрлі алфавиттегі сөздер түрінде
қарастыруға болады. Сондықтан алгоритмнің жұмыс істеу объектілері сөздер
болып табылады.
Анықтама. Алгоритм қолданылатын сөзді енгізілетін сөз дейді.
Алгоритмнің нәтижесі шығарылатын сөз деп аталады. Алгоритм қолданылатын
сөздердің жиыны алгоритмнің қолданылу облысы деп аталады.
Әрбір Тьюринг машинасында 2 бөлік бар:
1. Ұяшықтарға бөлінген екі жағынан да шексіз лента
2. Автомат - жазуоқу инесі
Тьюринг тезисі: Кез келген алгоритм үшін сәйкес Тьюринг машинасын
құруға болады.
Анықтама. Тьюринг машинасы деп жүйесін айтады. Мұндағы: А –
шекті –жиын, Тьюринг машинасының алфавиті, - А алфавитінің бос сөзі, Q
–Тьюринг машинасының жағдайын білдіретін шекті жиынның элементі, q1- ТМ-ның
бастапқы жағдайы, q0- МТ-ның тоқтау жағдайы, пассивті жағдай, Т-МТ-ның
жылжу жиыны, - МТ-ның программасы.
Анықтама. Алгоритм (Тьюринг бойынша) – қойылған есепті шешуге
келтірілетін Тьюринг машинасына құрылған программа.
Тьюринг машинасы мен тезисі болашақта да қолданылады, себебі кез
келген проблема шешілмейді деп айтуға болмайды, шешілмейтін есеп болмауы
керек, оны қандай да бір шешілетін түрге келтіру керек, соған
орайластырылған алгоритм құрастыру керек.
Машинаның белгілі бір процесті орындауының өзі алгоритмдік процесс
болып табылады. Сондықтан алгоритмге қойылатын талаптар мен қасиеттер оны
орындайтын машинаға да қойылады:
1) Машинаның жұмысы дискретті, бірінен кейін бірі орындалатын жеке – жеке
командалармен орындалуы керек.
2) Әрекеттер детерминделген , яғни қадамдар қатаң реттелген , ал олардың
нәтижесі алдыңғы қадамда алынған нәтижелермен тікелей байланысты болуы
керек.
3) Жұмыс алдында алғашқы берілгендер алгоритмнің анықталу облысынан алынуы
керек.
4) Саны санаулы қадамдарды орындаудан соң нәтиже алынуы керек.
5) Машина универсалды , жан – жақты болуы керек, оның көмегімен кез –
келген алгоритмді орындайтын болуы керек.
Сипатталған машинаның құрылғылары немесе структурасы қарапайым болса және
орындалатын қадамдар элементарлы болса, алгоритмнің орындалуы машинаның
жұмыс істеуі деп есептеуге болады .
Машинаның орындайтын қадамдары элементарлы болуы үшін белгілі бір алфавит
арқылы ақпаратты алмастыру керек. Сондықтан алгоритм – кез– келген ақырлы
алфавиттен берілгендерді немесе ақпаратты алмастыру
Ережелерінің ақырлы кез келген жүйесі.
Алгоритмнің анықталу облысынан алынған бастапқы берілгендер А
аофавиті және ақырлы {}таңбалар тізбегін құрасын, мұндай тізбекті сөз
дейді. Алгоритмді орындау барысында жаңа сөз құрылады {}, олар В
алфавитін құрайды. Бұл алмастыруды жүргізу үшін келесі қадамдар орындалады:
1) Бастапқы сөзінің бір сөзін В алфавитінен таңбасымен
алмастыру.
2) Бастапқы сөздің таңбасын өшіру.
3) В алфавитінен бір таңбаны бастапқы сөзге қосу.
Егер алфавитке бос таңба деп аталатын таңба қосылса, оны сөзге оң
жағынан да сол жағынан да қоссақ та сөз өзгермейді, яғни 1) операция бос
таңбаны алмастыру болады. Сонда 2) – 3) – операцияларды орындасақ та,
бәрібір 1) – қадамда тағы сол алдыңғы қадам қалады. Сондықтан абстрактылы
машина әр символды зерттейді, сосын шексіз лентаға – жадыға сақтайды,
егер символ бос болмаса оны басқа таңбамен алмастырады да жаңа қалыпта
тұрады.
Бұл машина туралы теорияны Алан Тьюринг (1936-1937), Эмиль Пост сияқты
ғалымдар ұсынған. Осы принципке сәйкестелген есептеу машиналары 8-9
жылдан кейін пайда болған.
Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші
Бұл машинаның Тьюрингтен айырмашылығы – ол өзінің теориясында
машина емес алгоритмдік жүйе деген терминді қолданған.
Оның абстрактылы машинасы бірнеше бірдей секцияларға бөлінген, оқу-
жазу инесі бар шексіз лентадан тұрады. Әр секция бос немесе толтырылған
болуы мүмкін. Лентаға түк жазылмаса секция бос, лентаға жазылып белгі
түссе секция толық деп есептеледі.
Лента жағдайы процесс уақытында өзгермелі болды. Осы лента жағдайы
мен оқу-жазу инесінің орны туралы ақпарат Пост машинасының жағдайын
айқындайды.
Инені , метка-белгі М болсын. Секция бос болса, ешбір белгі
түспейді. Бір қадам жасағанда ине оңға немесе солға 1 қадам жылжып белгіні
салады немесе өшіреді. Программадағы командаларға сәйкес машина 1 жағдайдан
келесі жағдайға көшіп отырады.
Әрбір команданың структурасы ХКУ болсын,
Х – орындалатын команда нөмірі,
К – орындалатын әрекет туралы нұсқау,
У – келесі команда нөмірі.
№ команда Командалардың Машина әрекетінің сипаттамасы
жазылуы
1 Оңға қадам Х(У Инені оңға қарай 1 секцияға жылжыту
2 Солға қадам Х(У Инені солға қарай 1 секцияға
жылжыту
3 Белгі салу Х V У Секцияға белгі қойылады
4 Белгіні өшіру Х x У Секциядан белгі өшіріледі
5 Басқаруды Х У1 Секцияда белгі жоқ болса басқару у1
ауыстыру У2 командасына, әйтпесе у2 командасына
беріледі
6 тоқтату Х стоп ! Машина жұмысын тоқтатады
7 Тармақты ? a; b Ұяшықты қарау, егер ұяшықта 0
ұйымдастыру тұрса, онда а номерлі командаға
көші, әйтпесе b нөмірлі командаға
көшу.
Бұл әрекеттерге қойылатын қосымша шарттар:
- ХМУ командасы бос секцияда орындалмайды
- ХсУ командасы толық секцияда орындалады
- У командасының нөмірі программадағы бар команда нөмірімен сәйкес болуы
керек.
Егер келтірілген шарттар сақталмаса, онда машина нәтижесіз жұмысын
аяқтайды. Х стоп командасы нәтижелі орындалады. Себебі, ол өзінің
алдындағы әрекеттер орындалып барып солардың нәтижесінде орындалады.
Кейде машина тоқтамауы мүмкін, егер командалардың ешқайсысында тоқтау
командасына көшу нөмірі болмаса.
Пост машинасы оң бүтін сандарды жазуды қарастырады, себебі кез келген
сөз цифр түрінде кодталады.
Лентада К бүтін саны К+1 келесі белгіленген секцияларда, унарлы санау
жүйесі қолданылып жазылады.
0,2,3 сандарыныің жазылуы:
М М
1 кл 25 20 10
2 кл 10 10 0
3 кл 15 13 11
. . .. .. .. .
. . .
11 кл17 18 10
кл [i, j] =
алг қосу (бүт таб кл [1:11,1:3], бүт S)
арг кл
нәт S
басы бүт i,j
S:=0
i:=1
әзір i≤11
цикл басы
j:=1
әзір j≤3
цикл басы
S:=S+ кл [i, j]
j:=j+1
цикл соңы
i:=i+1
цикл соңы
Соңы
4. реттелмеген массивте біртіндеп іздеу алгоритмі
Деректерге көп қолданылатын операциялардың бірі – іздеу. Іздеу
мәселесі ЭЕМ-нің дамуының алғашқы жылдарынан бастап басты мәселелердің бірі
болды. Аз көлемді ішкі жады мен тізбекті – лента типті құрылғыларда
сақталған деректердің арасынан керекті ақпаратты іздеу ішкі жадының
кеңейтілуін талап етті.
Іздеу операциясы екі нәтиже береді:
1. сәтті іздеу
2. сәтсіз іздеу.
Іздеу сәтті болса, ізделінді элементтің орналасқан жері табылады,
яғни ол массивтің элементінің номерін береді.
Іздеудің бірнеше әдістері бар:
1. белгілі бір элементті іздеу
2. кез келген элементті іздеу т.б.
Мысалмен қарастырсақ:
Екі жиын берілсін: және . А жиыны В жиынының ішкі жиыны
болатын, болмайтынын анықтау керек болсын.
Бұл есепті шешу үшін екі әдісті қолдануға болады:
1. Элементтер беттескенге дейін әрбір аi элементтерін сәйкес bi
элементтерімен салыстыру
2. А және В жиындарын реттеп алып, екі жиынның элементтерін бір бірімен
беттескенше салыстыру
Іздеудің бірінші нұсқасында n, m-сандары аз болғанда тиімді, ал олар
өссе, онда ә-ші әдіс тиімді болады. Алгоритмнің негізгі мазмұны оның
күрделілігінде.
Алгоритмнің күрделілігі итерация ұғымымен байланысты.
Анықтама. Итерация дегеніміз алгоритмді енгізілетін деректерге қолдану
операциясы. Әрбір келесі итерацияның бастапқы берілгендері болып оның
алдындағы итерацияда анықталған мәндер алынады.
Егер массив реттелмеген болса, онда біртіндеп іздеу әдісін қолдануға
болады:
A[1..n] массиві берілсін. P-ға тең элементті іздеу керек болсын.
1. i=1; болғанда бастаймыз
2. егер ai=p шарты орындалса, онда іздеу сәтті аяқталады
3. әйтпесе I:=i+1 деп келесі элементке көшеміз
4. егер i=n болса, онда 2-ші пунктке көшеміз, әйтпесеәздеу сәтсіз
аяқталады.
Бұл алгоритмнің күрделілігі n-1-ге тең, себебі элементтерді р-мен
салыстыру саны сонша.
5. реттелмеген массивте бинарлы іздеу алгоритмі
Егер массив реттелген болса, онда бинарлы-екілік іздеуді
қолдануға болады. Оны логарифмдік іздеу немесе дихотомия әдісі дейді.
Мұнда екі көрсеткіш пайдаланады: l=1 массивтің алғашқы
элементін көрсетеді, u=n массивтің соңғы элементін көретеді:
1. l=1; u=n; болады
2. егер ul болса, онда алгоритм сәтсәз аяқталады, әйтпесе [l,u]
аралығының ортасын табамыз. Осы моментте ізделінді k элементі массивте бар
болса, al=k=au шартының орындалатынын білеміз. I=(l+u) div 2 деп аламыз
, сонда I массивтің ортасын көрсетеді.
3. Егер kai болса, онда 4-ші пунктке көшеді, егер kai болса, онда 5-ші
пунктке көшеді, егер k=ai болса, онда іздеу сәтті аяқталады.
4. u=i-1 деп орналастырамыз және 2-ші пунктке көшеміз
5. l=i+1 деп орналастырамыз және 2-ші пунктке көшеміз.
Бұл алгоритмде күрделілік дәрежесі -ге тең болады.
Реттеу, сұрыптау алгоритмі
Деректерге көп қолданылатын амалдардың бірі – сұрыптау.
Сұрыптау дегеніміз – массив элементтерін белгілі бір ережені
сақтайтындай етіп, реттеп орналастыру.
Сұрыптау ішкі және сыртқы деп бөлінеді. Сыртқы сұрыптауға сыртқы
жадыдағы деректерді сұрыптау жатады. Ал ішкі сұрыптауға ішкі жадыға
деректерді реттеп орналастыру жатады.
Ішкі сұрыптау бірнеше әдіспен орындалады:
1. Көпіршіту әдісі
Әдістің бұлай аталуы массивтің 1-ші және 2-ші элементтері
салыстырылып, егер 1-ші элемент үлкен болса, олар орындарын ауыстырады, ал
үлкен болмаса орнында қалады, сонда ауыр элемент астына түсіп жеңілі бетіне
шығатын болғандықтан көпіршу сияқты көрінеді.
Мысалы.
a1, a2, a3, ... , an тізбегі берілген. Элементтерін өсу реті бойынша
реттеу керек.
алг реттеу (бүт n, нақ таб a[1:n])
aрг n, a
нәт a
басы бүт i, нақ Б
әзір i≤n-1
ц. б.
егер a[i] ≤a[i+1]
онда i:=i+1
әйтпесе
Б:=a[i];
a[i]:=a[i+1];
a[i+1]:=Б
i:=1;
бітті
ц. с.
а – ны шығару.
Соңы.
Дәл осылай кемуі бойынша да реттеуге болады.
2. Сызықты сұрыптау
Массивтің ішінен ең үлкен элемент табылады. Ол элемент р-шы орында
тұрсын. Сол элементті n-ші орындағы элементпен салыстырады. Егер np
болса, онда n-ші орында орналасқан элементпен орындарын ауыстырады. Әрі
қарай қалған реттелмеген элементтердің ішінен тағы ең үлкен элемент
табылады да, ол (n-1)-ші элементпен салыстырылады, егер ең үлкен элемент (n-
1)-ші элементтен үлкен болса, орнында қалады да, болмаса орындарын
ауыстырады. Осы процесс барлық элементтерге қолданылып шығады.
Алгоритмі келесідей болады:
Белгілеулер: a[1..n] –берілген массив болсын, r – массивтің реттелмеген
элементтерінің саны.
1. R=n болсын.
2. Max=max{a[1..r]} табамыз.
3. Maxr және a[max]a[r] болса, онда a{max] элементі мен a[r]
элементі орындарын ауыстырады
4. әйтпесе R=r-1 деп реттелмеген келесі элементтерге көшеміз. Алғашқы r
элементтер – реттелмеген элементтерді құрайды, ал соңғы n-r элементтер
өсуі бойынша реттеледі.
5. Егер r=1 болса, онда реттеу аяқталады, әйтпесе 2-ші пунктке көшеді.
3. Кірістіру арқылы сұрыптау.
Алдында қарастырылған көпіршіту және сызықты сұрыптау әдістері
кемімелі қадаммен сұрыптауға жатады. Шынында да, әрбір сұрыптау итерациясын
орындаған сайын реттелмеген элементтер саны 1-ге кеміп отырады.
Ал кірістіру арқылы сұрыптау өзгеше принциппен орындалады:
Массивтің алғашқы 2 элементі реттеледі де реттелген s жиынын құрайды. Сосын
келесі екі элемент реттеледі де сол жағынан үлкен элемент, оң жағынан кіші
элемент орналаспайтындай етіп s –реттелген жиынға кірістіріліп отырады. S
жиынға кірістірілетін элементтің орны дихотомия әдісімен анықталады.
Кірістіру әдісінде келесі бағалаулар дұрыс:
Салыстыру саны=1+2+[log23]+1+[log24]+1+...+[log 2(n-1)]+1=(n-1)+log2(n-
1)!=nlog2n;
Меншіктеу саны: min=0; max=3+4+5+...+n+1=(n+4)(n-1)2
Күрделілігі: O(n2)-меншіктеу саны бойынша, O(nlog2n)-салыстыру саны
бойынша.
Өзін тексеру сұрақтары
1. Реттелмеген массивте біртіндеп іздеу алгоритмі қалай жүреді?
2. Реттелген массивте бинарлы іздеу алгоритмі қалай жүреді?
3. Сұрыптаудың қандай әдістері бар?
Ұсынылатын әдебиеттер
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары
(алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс,
1998г.
4. Острейковский В.А. Информатика, Москва, 2000 г.
5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А.,
Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
6-тақырып: Алгоритмдер және деректер структурасы
Дәріс жоспары:
- негізгі түсініктер
- ақпаратты сақтау
- деректер структурасының классификациясы
- деректер структурасына қолданылатын амалдар
- программалау технологиясы
Деректер структурасы мен алгоритмдер программаның негізгі
құраушысы болып табылады. Компьютердің өзі сол деректердің структурасы мен
алгоритмдерден тұрады. Орнатылған деректердің структурасы екілік шамалар
сақталған жады сөзі және регистрлер түрінде көрінеді. Аппаратураның
конструкциясына бекітілген алгоритмдер – орандауға жататын, жадыға
енгізілген деректерден команда – бұйрық түрінде ойластырылған электронды
логикалық тізбекке айналдырылған қатаң ережелер. Сондықтан кез келген
компьютердің жұмыс негізінде тек қана деректердің бір түрімен белгілі бір
биттермен немесе екілік цифрлармен операцияларды орындауды білу жатады. Осы
деректермен компьютер тек орталық процессордың бұйрықтар жүйесімен
анықталатын, сәйкес өзгермейтін алгоритмдердің жиынымен жұмыс істейді.
Программалау тілдерінде қабылданған деректердің типтері
натуралды, бүтін, нақты сандардан, литерлерден, жолдардан, т.б. тұрады.
Кейбір программалау тілдерінде деректердің типтері компиляторда
анықталса, кейбіреуінде типті анықтап көрсету керек болады. Программада
деректердің мәндері қанша қажет болса, сонша өзгеріп, ал типі өзгеріссіз
қалуы керек.
Деректер структурасының классификациясы.
Деректердің структурасы жалпы жағдайда деректер элементтерінің
жиыны және олардың арасындағы байланыс жиыны деп қарастырылады.
Деректер структурасының классификациясы бірнеше белгілеріне
қарай анықталады:
1. Деректердің физикалық структурасы
2. Деректердің логикалық структурасы
Деректердің машина жадысында қалай орналасатыны, физикалық
көрінісі физикалық структурасы деп аталады.
Ал машина жадысында орналастырылуын есепке алмаған жағдайда
деректердің қарастырылуы логикалық структурасы деп аталады.
Жалпы деректер структурасының типтері екіге бөлінеді:
1. Қарапайым немесе жай типтер
2. интегралданған- ауқымды типтер
Жай типтерге базалық, примитивті типтер жатады. Оларды биттен
үлкен құрмалас бөліктерге бөлуге болмайды.
Ауқымды типтерге композитті, күрделі құрылымды типтер жатады.
Олардың құрамдас бөлігі басқа бір структуралар болуы мүмкін.
Деректер элементтерінің арасында айқын берілген байланыстың бар
болу, болмауына қарай деректердің структурасы тағы 2-ге бөлінеді:
1. байланысты
2. байланыссыз
Деректер структурасының маңызды белгілерінің бірі -
өзгермелілігі- элементтердің саны және олардың арасындағы байланыс өзгеріп
отырады.
Структуралардың өзгеруі элементтердің мәнінің өзгеруіне
соқтырмайды. Сондықтан структуралардың өзгермелілігіне қарай үшке бөлінеді:
1. статикалық
2. жартылай статикалық
3. динамикалық
Деректердің тағы бір маңызды белгісі – реттелгендік. Бұл
белгісіне қарай:
1. сызықты
2. сызықты емес структуралар болып бөлінеді.
Программалау тілдерінде Деректер структурасы мен Деректер
типі ұғымдары тығыз байланысты. Кез келген деректер (тұрақты шама,
айнымалы, функция мәні, өрнек т.б.) өздерінің типімен мінезделеді.
Әр тип бойынша ақпарат мына ұғымдарды бірмәнді анықтайды:
- көрсетілген типтің деректерді сақтау структурасын, яғни дерекке
ұяшық бөліп, онда қалай жазылатыны, екілік түрін ойластыруды;
- сипатталған типті объектінің қабылдайтын мәндер жиынын;
- сипатталған типті объектіге қолданылатын амалдар жиынын;
Деректер структурасына қолданылатын амалдар:
1. Құру
2. Жою
3. Таңдау
4. Жаңарту
Құру операциясы деректер структурасына жадыдан ұяшықтар бөлу
болып табылады.
Жою операциясы құруға қарама қарсы, жадыдан деректерді өшіру
болып табылады.
Таңдау операциясын структуралардың өз ішінде деректерге рұқсат
алу үшін программист қолданады. Рұқсат алу операциясының түрі қажетті
деректер структурасының типінен тәуелді.
Жаңарту операциясы деректер структурасында деректер мәндерін
өзгертуге көмектеседі.
Бұл операциялар барлық деректер структурасына жалпы
қолданылатын операцияларға жатады, ал кейбір деректер структурасына
қолданылатын арнаулы операциялар бар.
Өзін тексеру сұрақтары
1. Деректер структурасы деген не?
2. Деректер структурасына қолданылатын амалдар
3. Программалау технологиясы деген не?
Ұсынылатын әдебиеттер
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары
(алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Симонович С., Евсеев Г.Практическая информатика: Инфорком-
Пресс, 1998г.
4. Острейковский В.А. Информатика, Москва, 2000 г.
5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов
М.А., Шкатов П.Н. Вычислительная техника и программирование,
Москва, 1990.
7-тақырып: Деректердің жай структурасы
Дәріс жоспары:
1. сандық типтер
• бүтін
• нақты
• ондық
• сандық типтерге қолданылатын операциялар
2. Биттік типтер
3. Логикалық типтер
4. Терілімді типтер
5. Шектелген типтер
6. Көрсеткіштер
Деректер структурасы қабылдайтын мәндерінің түрлеріне қарай келесі
типтерге бөлінеді:
1. Сандық типтер
2. Биттік типтер
3. Логикалық типтер
4. Символдық типтер
5. Терілімді типтер
6. Шектелген типтер
7. Көрсеткіштер
8. Тізімдер
9. Жазулар
10. Файлдар
11. Массивтер
12. Жиындар
13. Таблицалар
14. Стектер
15. Кезектер
16. Дектер
17. Жолдар
18. Динамикалық типтер
19. Графтар
20. Ағаштар (бұтақтар)
Жай типтерге жататындары:
1. Сандық
2. Биттік
3. Логикалық
4. Символдық
5. Терілімді
6. Шектелген
7. Көрсеткіштер
Сандық типтер нақты-ондық, бүтін типтер деп бөлінеді. Бүтін сандар
көмегімен табиғаты жағынан дискретті – объектілерінің саны санаулы болатын
объектілердің саны беріледі. Таңбалы сандарды ЭЕМ-ң жадысында орналастыруда
екілік кодпен немесе қосымша кодпен кодтау әдісі қолданылады. Олардың
ұзындығы 1,2,4 байт болуы мүмкін. Осыған байланысты бүтін типті деректердің
өзі ұзын бүтін, қысқа бүтін, бүтін болып бөлінеді, оларға сәйкес байттық
орындар бөлінеді.
Нақты типті деректердің өзі тұрақты нүктелі, айнымалы нүктелі болып
бөлінеді, олардың да жадыдағы байттары әртүрлі. Бүтін сандардың мәні жадыда
дәл анықталса, нақты сандардың мәні белгілі бір дәлдікпен анықталады.
Биттік типтер деректердің екілік разрядтарымен жұмыс жасауға
көмектееді. Биттік типтер бір бірімен байланысы жоқ байттардың жиыны.
Логикалық типтер логикалық ақиқат, жалған, иә, жоқ сияқты мәндерді
қабылдайтын, 1 байт орын алатын деректер.
Символдық типтер алдын ала анықталған символдар жиыныннан қабылданатын
мәндер. Дербес ЭЕМ-дерде көбіне стандартты ASCII –символдар коды таблицасы
орнатылған, одан басқа EBCDIC-кодтар таблицасы да бар. Символдық типті
деректерге салыстыру, жалғастыру операциясы қолданылады.
Терілімді типтерге қолданушы анықтайтын, өз бетімен құратын белгілі
бір шарттарға байланысты топтастырылған деректер жиынынан тұратын типтер
жатады. Мысалы: жылдың он екі айы, апта күндері, т.б.
Шектелген типтерге терілімді типтердің ішінен белгілі бір аралықты
қамтитын деректерден құралатын, кей жағдайда қолданушы өзі анықтайтын
деректер типтері жатады. Мысалы: жаз айлары, қыс айлары, демалыс күндері,
т.б.
Көрсеткіштер деректер орналасқан ұяшықтың адресін анықтайтын типтер.
Олар типтендірілген көрсеткіштер және типтендірілмеген көрсеткіштер деп
бөлінеді. Егер типтендірілген көрсеткіш деп жарияланса, онда олар бүтінге
көрсеткіш, символға көрсеткіш т.б. деп аталуы мүмкін. Ал типтендірілмеген
көрсеткіштер кез келген ұяшықтың адресін анықтайды, ол деректердің мәніне
көңіл аудармайды. Көрсеткіштер деректерді алмастыру уақытында жадыны
реттеуге тиімді.
Өзін тексеру сұрақтары
1. Деректердің қандай типтері бар?
2. Сандық типтер қалайша бқлінеді?
3. Күрделі типтер қалайша бөлінеді?
Ұсынылатын әдебиеттер
1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары
(алгоритмдеу). Алматы, 1990ж.
2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс,
1998г.
4. Острейковский В.А. Информатика, Москва, 2000 г.
5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А.,
Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
8-тақырып: Деректердің статикалық структурасы
Дәріс жоспары:
7. векторлар
8. массивтер
9. жиындар
10. жазулар
11. таблицалар
Деректердің статикалық структурасы базалық, примитивті структуралардың
құрылымды жиынынан тұрады. Оларға жады тұрақты-автоматты түрде бөлінеді,
себебі олардың мәндері өзгермейді.
Векторлар – бір өлшемді массивтер- бір типті саны санаулы элементтер
жиынынан тұратын деректер. Вектордың әр элементінің нөмірі оның тұрған
орнын анықтайды. Элементтері тізбектелген ұяшықтар жиынын құрайды.
Элементтің типіне қарай жадыдан байттар бөлінеді. Жады көлемі элементтер
санын элементтер ұзындығына көбейту арқылы анықталады.
Массивтер – екі өлшемді, көп өлшемді болады.
Біртипті саны санаулы элементтердің жиынтығынан тұратын, әрбір
элементі индекспен номерленген, индекстерінің саны массив өлшемін
білдіретін атаулы деректерді массив дейді.
Массивті қолдану үшін оның атауы және индексі анықталуы керек. Екі
индексті массив екі өлшемді, үш индексті массив үш өлшемді деп аталады.
Жазулар (структуралар).
Әртүрлі типті деректерді анықтайтын өрістердің ақырлы реттелген жиыны
жазулар деп аталады.
Жазуларды белгілі бір заттық облыстан алынған объектіні толық анықтап,
программалау үшін қолданған тиімді. Жазу өрістермен құралады. Өрістерді
компоненттер деп те атайды. Жазу деректер таблицасын еске түсіреді.
Таблицаның бағандарының атаулары өрістер, таблицаның әр жолы жазу немесе
жазба деп аталады Программада жазулар өздерінің атауымен және өріс атауымен
біріктіріліп қолданылады.
Жиындар - біртипті, мәндері қайталанбайтын деректердің жиынтығы.
Жиын базалық типке жататын деректердің бәрін қабылдайды. Базалық тип
256 мүмкін мәндерден аспауы керек, жадыда 32 байтқа дейін орын алады және
массивтер сияқты орналасады, элементтері индекстеледі.
Таблицалар - элементтері жазу болатын векторды айтуға болады. Вектор
сияқты әр элементі индекстелмейді. Әр өрісті толық анықтайтын кілттік өріс
тағайындалып, сол кілт бойынша деректер қолданылады. Кілт - біртипті көп
жазулардың жиынынан таңдалынатын мәндері қайталанбайтын белгілі бір өріс.
Бір таблицада бір немесе бірнеше кілт болуы мүмкін. Таблицаға логикалық
деңгейдегі операциялар қолданылады: іздеу, сұрыптау.
Іздеу операциясы екі әдіспен орындалады:
1. Біртіндеп іздеу немесе сызықты іздеу
Деректер реттелмеген болса, элементтің кілті анықталып, кілттің
мәнімен жазулар салыстырылады, сәйкестік болса жазудың табылғаны туралы
ақпарат шығады, әйтпесе іздеу сәтсіз аяқталады.
2. Бинарлы іздеу.
Жазулар таблицаға алфавит бойынша немесе өсу реті бойынша енгізіледі.
Белгілі бір жазуды іздеу таблицаның ортасындағы сол жазуға сәйкес кілттік
өрістің мәнін зерттеуден басталады. Егер кілттің мәні үлкен болса, онда
таблицаның үстіңгі жартысының ортасындағы жазуға сәйкес кілттің мәні
тексеріледі, осы процедура таблицаның үстіңгі жартысында сәйкес жазу
табылғанша жалғасады да, егер іздеу сәтті аяқталса іздеу тоқтатылады. Егер
кілттің мәні кішкентай болса, онда таблицаның төменгі жартысының ортаңғы
жазуына сәйкес кілт мәні тексеріледі,
Таблицаны сұрыптау белгілі бір ереже талабын қанағаттандыратындай
етіп жазуларды реттеуге жатады. Сұрыптау алгоритмдері көп, оны таңдауға
әсер ететін факторлар:
- Қол астында бар жады ресурсы: енгізілетін және шығарылатын жиындар
жадының әртүрлі облысында орналасуы керек пе, әлде шығарылатын жиындар
енгізілетін жиындардың орнына жазылуы керек пе - сол зерттеледі.
- Енгізілетін жиындар бастапқы кезден бастапреттелген болуы.
- Операцияның уақытша мінездемесі: алгоритмнің жылдам орындалуы үшін
кілттік өрістің мәндері сандық тип немесе символдық тип болуы ескеріледі.
- Алгоритмнің күрделілігі: алгоритм неғұрлым қарапайым болса, орындалуы
соғұрлым жеңіл болады.
Сұрыптау стратегиялары:
1. Таңдау стратегиясы. - енгізілетін жиыннан реттелу шартын
қанағаттандыратын элемент таңдалынып алынады да номеріне байланысты орны
анықталып, шығарылатын жиынға енгізіледі.
2. Енгізу стратегиясы - енгізілетін жиыннан номерлі элемент таңдалынып,
реттелу шартына сәйкес орнын анықтап шығарылатын жиынға енгізіледі.
3. Тарату, орналастыру стратегиясы - енгізілетін жиын бірнеше ішкі жиынға
бөлінеді де, сұрыптау әр ішкі жиында жүргізіледі.
4 Біріктіру, жымдастыру стратегиясы - Сұрыпталған әрбір ішкі жиынды
жымдастыру арқылы шығарылатын жиын құрастырылады.
Көпмүшелікті Горнер схемасымен есептеу алгоритмі
y= a0xn+a1 xn-1+...+an-1 x + an теңдеуімен берілген көрсеткіші n-ге
тең көпмүшеліктің мәнін есептеү керек.
Горнер схемасы бұл көпмүшеліктегі көбейту және қосу амалдарының санын
максималды ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz