«Алгоритм жЩне оныЈ кЇрделілігі» пшнін ољыту-шдістемелік кешен

СЕМЕЙ љАЛАСЫНЫў ШШКШРІМ АТЫНДА’Ы МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ

3 деЈгейдегі СМК ›±жаты

ПОШК

042-39.1.11/03-2013

«Алгоритм жЩне оныЈ кЇрделілігі» пЩні бойынша о›у-Щдістемелік материалдар02.09.2013ж

№1 басылым

МАЗМ°НЫ

1. 
   ГлоссарийДЩрістерМашы›тану саба›тарыСтуденттердіЈ йздік ж±мыстарыныЈ жоспары
   

1. 
   АлгоритмніЈ шы“у тегі. АлгоритмніЈ тарихы. АлгоритмніЈ т±рмыста ›олданылуы. АлгоритмніЈ ›ажеттілігі. АлгоритмніЈ ›ызметі мен ма›саты.
   
2. 
   АлгоритмніЈ ЭЕМ-дегі рйлі. Информатика “ылымында“ы алгоритм. ОныЈ ма›саты мен міндеті.
   
3. 
   Алгоритмдік конструкциялар.
   

1. 
   тізбектелген конструкция
   
2. 
   тарма›тал“ан конструкция
   
3. 
   циклдік конструкция
   
4. 
   рекурсивті конструкция
   

Сонымен алгоритм дегеніміз белгілі бір мЩселені шешу Їшін ›ойылатын ма›сат›а ба“ыттал“ан іс-ЩрекеттердіЈ тізбегі. Олар т±рмысты›, есептеу, рекурсивті, ›осал›ы деп бйлінеді.

Сйз тЇріндегі Щрекеттер тізбегін кЇнделікті ймірде ешбір роботтыЈ, техниканыЈ кймегінсіз адам йздігінен орындаса ондай алгоритмдерді т±рмысты› алгоритм дейді. Мысалы: дЇкенге барып азы›-тЇлік Щкелу, саба››а дайындалу, т.б.

Формула кймегімен шы“арылатын, есептеуді ›ажет ететін, кЇрделілігіне байланысты белгілі бір техниканыЈ араласуын талап ететін алгоритмдерді есептеу алгоритмдері дейді.

Рекурсивті алгоритм деп есептеу алгоритмініЈ бір тЇрін айтады. ОныЈ нЩтижесі формуланыЈ ішіндегі бір параметрініЈ мЩні бас›а бір йзгеріп отыратын параметрден тЩуелді болудан шы“ады.

љосал›ы алгоритм дегеніміз кЇрделі алгоритмдердіЈ бірнеше жай алгоритмге бйлінуі ар›ылы негізгі алгоритмге ›ажетті уа›ытында “ана ша›ырылатын, жалпылама жа“дай“а негізделіп дербес ›±рылатын алгоритмдер.

љай алгоритм болса да негізгі ›асиеттерді ›ана“аттандыруы шарт:

1. 
   Дискреттілік ›асиет – орындалатын Щрекеттер тізбегі бірнеше ›адамдар“а бйлініп Їздікті ›±рылымды болуы керек. ЖЩне ›адамдардыЈ орындарын ауыстыру“а болмайды.
   
2. 
   ТЇсініктілік ›асиеті – орындаушы“а тЇсінікті жЩне орындай алатын н±с›аулар жиынынан командалардан т±руы ›ажет. Орындаушыдан бірт±тас Щрекет жасауды талап ету керек. Алгоритм орындаушы“а ба“ытталуы керек.
   
3. 
   Аны›тылы› ›асиеті – детерминделген деп те аталады, бір алгоритмді кез келген орындаушы орындай алатын болуы керек. љай орындаушы орындаса да алынатын нЩтиже біреу болуы керек. Орындаушы дербес шешім ›абылдамайтындай болып ›±рылуы керек, я“ни аны›, егжей-тегжейлі ойластырыл“ан, толы›, жал“ыз нЩтижелі болуы керек. Бір - екі минуттай деген сия›ты н±с›аулар болмау керек.
   
4. 
   Орта›ты› ›асиеті – бір алгоритм барынша Їлкен клас›а жататын есепті шешетіндей болуы керек, тек бастап›ы берілгендерді йзгерту ар›ылы “ана шешімді табу“а болатындай. Мысалы квадрат теЈдеуді шешу алгоритмін ах²+bx+c=0 жа“дайына ›±р“ан д±рыс болады, ал 4x²+5x-1=0 тЇріне ›±рса онда алгоритм дербес болады, не“±рлым жалпы болуы керек.
   
5. 
   НЩтижелілік ›асиеті – алгоритмніЈ пункттері немесе н±с›аулары шектелген, оныЈ шегі есептіЈ нЩтижесін беретіндей болуы керек. Алын“ан нЩтиженіЈ д±рысты“ын анализдеу керек.
   

ОперациялардыЈ реті алгоритмніЈ йз структурасымен аны›тал“ан жЩне енгізетін шамалардыЈ жеке мЩндеріне тЩуелсіз алгоритмдерді сызы›ты алгоритмдер дейді. ОлардыЈ н±с›аулары бірінен кейін бірі тізбектеліп орындалады.

Енгізетін шамалардыЈ жеке мЩндеріне тЩуелді, бірнеше ЩрекеттердіЈ біреуініЈ орындалуын та“айындауды тарма›ты алгоритм дейді.

Енгізетін шамалардыЈ жеке мЩндеріне тЩуелді бір немесе бірнеше ЩрекеттердіЈ ›айталануын та“айындауды циклдік алгоритм дейді. Циклдік алгоритмдер Їш тЇрге бйлінеді:

1. 
   шарты алдынан берілген – «Щзірше» циклі,
   
2. 
   шарты соЈынан берілген цикл – «дейін» циклі,
   
3. 
   параметрлі цикл.
   

Белгілі бір н±с›ау орындалып бол“ан соЈ логикалы› шарт тексеріліп, ол жал“ан мЩн ›абылдаса сол н±с›аудыЈ ›айталануы «дейін» циклі деп аталады.

Белгілі бір н±с›аудыЈ немесе н±с›аулар тобыныЈ неше рет ›айталануы керек екені алдын ала аны› болса, оны параметрлі цикл дейді.

АлгоритмніЈ берілу тЩсілдері:

1. 
   формула бойынша
   
2. 
   таблицалы› тЇрде
   
3. 
   блок-схема кймегімен
   

1. 
   ›атынас тілі
   
2. 
   математика тілі
   
3. 
   автоматтар тілі деп бйлінеді.
   

ОрындаушылардыЈ мЇмкіндігі тіл ›±ралдарыныЈ деЈгейін аны›тайды.

1. 
   ТілдіЈ деЈгейі алгоритмдік жазу командаларыныЈ тЩптіштеліп на›тылану дЩрЩжесіне тЩуелді. Я“ни орындаушы Їшін элементар деп есептелетін амалдыЈ шын мЩніндегі элементарлы› дЩрежесі ашып кйрсетілуі тиіс.
   
2. 
   ТілдіЈ деЈгейі тілдіЈ формальдандырылу дЩрежесіне де байланысты. Ол орындаушыныЈ кім болуынан тЩуелді. Егер орындаушы адам болса, о“ан белгілі бір алгоритмдерді тЇсінікті сйз , сйз тіркестері ар›ылы тЇсіндіруге болады, ал рындаушы автомат болса, онда бір›атар міндетті талаптар ›ойылады.
   
3. 
   командаларды т±жырымдау барысында машинадан осы машина Їшін ›атаЈ аны›тал“ан операцияларды орындауды “ана талап ету.
   
4. 
   Берілген машинаныЈ тілі Їшін ›абылдан“ан н±с›аулар ›±ру ережелерін “ана пайдалану“а болады.
   
5. 
   Ережелерде кйрсетілген нЩрселерді ешбір ›олдану“а болмайды, себебі машина ондай н±с›ауларды орындамайды.
   

1. 
   ТілдіЈ деЈгейі адам Їшін тЇсініктілік дЩрежесіне де тЩуелді. Ал“аш›ы ЭЕТ- мен ›атынас цифрлар тілі деЈгейінде болды. ЭЕТ жаппай тарал“анды›тан адам мен машинаныЈ ›атынасуын ›амсыздандыратын тілдіЈ жаЈа деЈгейлері пайда болды. љазір тілді «таби“иландыру» проблемасы ал“а ›ойылып отыр. Б±л проблема машинаныЈ йзін жетілдірумен ›атар жЇріп келеді. ’ылыми , инженерлік тілдер таби“и тіл мен математика тілін жымдастырады. Олар: Алгол, Фортран, Бейсик, паскаль, т.б.
   

Алгоритмдік тіл жай командалардыЈ жазылу ережесін, ›±рама команданыЈ, алгоритм ›±рамын, ма“ынасын дЩл жЩне бір мЩнді аны›тау керек.

Алгоритмтік тіл – алгоритмдерді біркелкі жЩне дЩл біркелкі жазудыЈ жЩне оларды орындаудыЈ ережелер мен белгілер жЇйесі.

КЩдімгі таби“и тілге жа›ын, екінші жа“ынан на“ыз алгоритмдік тілдердіЈ негізгі ›асиеттері бар тілдіЈ аны›тамасын берейік. Б±л тілді о›у алгоритмдік тілі деп аталады. Б±л тілде жазыл“ан алгоритмдер кЩдімгі текст сия›ты о›ылады жЩне Алгол, Фортран, Бейсик т.б. программалау тілдерін Їйренуге негіз болады.

Алгоритмдік тіл – ±“ымдары:

1. 
   алфавитті – тілде ›олдану“а болатын символдардыЈ, белгілердіЈ жиынты“ы.
   
2. 
   Тіл конструкциясы – айнымалы, йрнек, командалардыЈ жазылу жЩне алгоритмдік жазудыЈ жалпы ›±рылымыныЈ ережелері. Оны синтаксис деп атайды.
   
3. 
   Семантикасы - Щр тЇрлі командалардыЈ ›ызметі мен орындалу жолы.
   

ТілдіЈ негізгі объектілері – командалар. Олар н±с›ауларды жазу Їшін ›олданылады. Олар екі тЇрлі:

1. 
   Жай командалар
   
2. 
   љ±рама командалар
   

љ±рама командалар“а тарам›талу, ›айталану командалары жатады.

Алгоритмдік тілде алгоритмніЈ сипатталауы

Басы

Жай команда 1;

Жай команда 2;

Егер шарт

Онда 1 – серия

Шйтпесе 2 – серия

Шзір шарт

Ц.б.

љ±рама команда

Бітті . соЈы

Алгоритмдік конструкциялар:

1. 
   Сызы›ты
   
2. 
   тарма›ты
   
3. 
   ›айталану
   
4. 
   рекурсивті
   

Кез келген алгоритмніЈ дЩл немесе д±рысты“ы алгоритм моделімен негізделеді. Модель есепті шешуде ›олданылатын ›±ралдар жиыны, я“ни келесі ›адамды аны›тау Щдісі, ›арапайым Щрекеттер, ›адамдар.

АлгоритмніЈ моделі екіге бйлінеді:

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.
   

1. 
   Алгоритм – математиканыЈ арнайы бйлімі.
   
2. 
   Джордж БульдіЈ математикалы› логикасы.
   
3. 
   Логика мен алгоритмніЈ байланысы.
   
4. 
   ШртЇрлі о›и“алар“а алгоритм ›±ру Щдістері.
   
5. 
   Тьюринг машинасына мысалдар.
   
6. 
   Тьюринг машинасыныЈ математикалы› сипаттамасы.
   
7. 
   Алгоритм аны›тамасын дЩлдеу.
   
8. 
   Пост машинасы.
   
9. 
   Пост машинасы мен Тьюринг машинасын салыстыру.
   

АлгоритмніЈ ›атаЈ аны›тамасы алгоритмдердіЈ математикалы› теориясында тікелей ›олданылады. Онда алгоритмніЈ жалпы ›асиеттері, алгоритмдік шешілудіЈ дЩлелдемесі ›арастырылады. Ал практикада алгоритмді ›±ру ›атаЈ аны›талма“ан.

Алгоритмді орындаушы – алгоритмніЈ сипаттамасын д±рыс тЇсініп, тарата алатын субъект немесе Щрекеттер тізбегін орындай алатын ›±рыл“ы.

Шрекеттерді орындау“а арнал“ан н±с›ау Щлдебір тілдіЈ араласуымен Щрбір орындаушы“а тЇсіндіріледі. Б±л тілдіЈ ›ызметші сйздері , Щрекетті тЇсіндіретін немесе бейнелейтін командалары, оларды біріктірудіЈ синтаксистік ережесі болады. Командалар тізімі орындаушыныЈ командалар жЇйесі (СКИ) деп аталады. Дискретті а›паратты йЈдеуде ›олданылатын элементарлы Щрекеттер бір таЈбаны бас›амен алмастыру болып табылады. Кешенді Щрекеттерді орындаушы абстрактілі жЩне шын мЩніндегі ›±рыл“ы болуы мЇмкін.

ПроцессордыЈ Щрекеттерін а›и›ат элементарлы деп – машиналы› команда деп, ал олардыЈ белгіленуін – машиналы› код деп атайды. Ал“аш›ы – тйменгі деЈгейдегі код – ассемблер коды – ›±рыл“ыдан тЩуелді ішкі тіл деп аталады.

Элементарлы Щрекеттерді кЇрделі командалар“а біріктіру б±л деЈгейде Щлі жЇрмейді. АссемблердіЈ жалпы командалар саны процессор командаларыныЈ санымен теЈ, біра› машиналы› кодтардыЈ символды ›алпы ›олданылады –мнемоника – б±л ›олданушы“а екілік кодтан тиімді.

Мнемониканы машиналы› код›а ассемблер тілі орындайды.

Элементарлы Щрекеттерді біріктіру командалары жо“ары деЈгейдегі программаларда пайда болды. Тіл трансляторы берілген команданы элеменарлы ›адамдар“а аударады.

Одан гйрі элементарлы командаларды интеграцилауды ›олданьалы программалар орындайды. ОКЖ – і мЩзір, перне, терезе т.б. интерфейсті бас›ару командаларынан т±рады.

1. 
   
   жүктеу/скачать 0.89 Mb.
   
   Достарыңызбен бөлісу: