Алгоритмдеу және программалау 9 сынып

1 слайд
1

1 слайд

2 слайд
2 1-тарау. Кіріспе 2-тарау. Даму тарихы 3- тарау. Алгоритмдер негідері4-тарау. Қолданылатын әдебиеттер тізімі

2 слайд

3 слайд
3 Программалау тілі- бұл компьютермен қарым- қатынаста қолданылатын дұрыс құрылған сөздер, әріптер, сандар мен мнемоникалық қысқартулардан тұрады. ЭЕМ-ге арналған алғашқы программалар кезеңі (лампалық машина 40-50 х гг.) машиналық команда тілінде ( машинный код ). құрылды. Ассемблер тілі - адамға бағытталған машиналық команданың формасы. Пргораммалау тілдерін, табиғи имитациялық тілдерді және де компьютердің бірнеше командаларын құруға араналған бір нұсқада негізделген тәсілдерді жоғарғы сатыдағы тілдер деп атауға болады. Алғашқы жоғарғы дәрежедегі кең таралған тіл - FORTRAN (FORmula TRANslator) тілі болып табылады, сонымен қатар 1957 ж Джона Бекуса ( John Backus) көмегімен IBM фирмасының инженерлер топтарымен компьютерді программалауға арналған IBM 704 нұсқасы өңделді. FORTRAN компилярлық тіл болып табылады және де формуламен жұмыс үшін қолданылады, яғни бұл программа математикалық ғылым мен ғылыми- техникалық пәндерді қолданылады. Даму тарихы

3 слайд

4 слайд
4 Даму тарихы BASIC (Beginner's All-purpose Symbolic Instruction Code) тілі 1964 ж. Дармутский колледжінің Т. Курцом (Thomas Kurtz) және Д. Кемени ( John Kemeny) қызметкерлері арқылы өңделді. Олар ең алғашында бұл тілді, гуманитарлық ғылымды оқитын студенттер үшін арналған тіл ретінде құрды. Компьютер мен терминал арқылы интерекативті байланысуда қарапайымдылығымен, бағытылығы арқылы ерекшеленді. 70-80 жылдарда микрокомпьютерлерде орнатылған тіл ретінде кең таралды. ALGOL (ALGOrithmic Language ) 1958 жылы мамырда Цюрихе жиналысында АҚШ және Европа елінің бірлік ғылыми прграммалау тілі ретінде құрылған. ALGOL FORTRAN тілінен дамыған, бірақ оның негізгі түсініктері логикалық құрылымнан жинақталған. ALGOL 60 сипаттау үшін ең бірінші Бекуса-Наура (BNF – Backus-Naur form) форма программлау тілінің әмбебеап синтаксистік формасы қолданылды. Императивті программалау тілінің көбі ALGOL 60 тілінің тура және жанама ұрпағы болып табылады. Ол 20 жыл бұрын алгоритмдер мен ғылыми әдебиетті көрсету үшін арнайы бірлік құрал ретінде қолданылды.

4 слайд

5 слайд
5 Pascal тілінің авторы Никлаус Вирт (Niklaus Wirth) болып табылады, ол бұл тілді ХҮІІ ғасыр француз философы және математигінің атымен атаған. 1971 жылы Pascal тілінің алғашқы жазбасы шығарылды. Pascal тілі пайда болғаннан кейін программалауды оқыту сферасында кең тарала бастады. Pascal тілінің күшті құрлымдығы үлкен және жоғарғы типтегі программаларды құруға ыңғайлы болып табылады. Алғашқы нұсқаларында арнайы практикалық мүмкіндіктер болмады. Pascal құрлымдық программалау принципін нақтылау үшін арнайы к лассикалық тіл болып табылады. «Құрлымдық программалаудағы ескертулер» (1968 г.) жұмысында Э. Дийкстр (E. Dijkstra) “программалық қамсыздандырудың кризисін”, программаларда бір нүктеден екінші нүктеге басқаруды беретін көшу операторы GOTO ды көп қолданудан деп дәледеді. Дийкстр құрлымдық басқарудың үш типін қолдануды ұсынды: қарапайым бірізділік, альтернативті және қайталау. Даму тарихы

5 слайд

6 слайд
6 Bell Laboratories фирмасының жүйелік программалауының маманы Деннис Ричи ( Dennis Ritchie) 1972 жылы С тілін өңдеді. Бұл тіл төменгі сатыдағы тілдерге жақын, яғни аппаратқа тікелей енуді қамтамасыз етеді (С тілінде UNIX операциялық жүйесінің 90% жоғары программасының орталық коды (ядра) жазылған). С жетістігі-бұл бір орында және де сол уақытта үш түрлі жағдайда жұмыс істей алуы:С программалау тілі, UNIX операциялық жүйесі және PDP-11 кіші компьютер (в СССР аналог СМ-4 и СМ-1420). «С – бұл құрлығы, оның көмегімен әр түрлі программаларды құруға және өңдеуге» (Брайан Керниган – Kernighan B.W., Ritchie D.M. “The C Programming Language ” 1978 кітабының авторы). Даму тарихы

6 слайд

7 слайд
7 Тurbo Pascal компиляторы Borland International (Philippe Kahn, 1983 г.) фирмасында құрылған болатын. Turbo Pascal тілін өңдеуші А. Хейльсберг (Anders Hejlsberg) болатын, кейіннен Delphi жобасының авторы болды, сонымен қатар, Microsoft корпорациясына ауысқаннан кейін NET тілінің алдыңғы қатрлы архитекторы, ал одан кейін C# тілінің авторы болды. 80 жылдардың басында Bell Laboratories қызметкерлерімен бірге Б. Страуструп (Bjarne Stroustrup) С++ тілінің жаңа версиясын ұсынды. Онда қосымшалар қатары енгізілді, олардың бастапқы құралы объектілі- бағытталған программалау, яғни оны жүйелік программалар бағытытында сақтауға болады. Бұл тіл С тіліне ұқсас болып келеді, сондықтан қазіргі кезде программалау тілінің аймағында бұл тіл лидер ретінде қабылданған. С++ тілімен салыстырғанда Java объектілі бағдарлы тілі өте қарапайым болып келеді. Бұл тіл 90 жылдардың басында өңделген, бұл тілді Sun Microsystems компаниясының маманы Д. Гослинг (James Gosling) ұсынған. Java тілі World Wide Web үшін программалау формасын анықтайтын алғашқы тіл болып табылады. Даму тарихы

7 слайд

8 слайд
8 Программалаудағы прогреес көбіне жоғарғы дәрежедегі тілдердің қарама- қайшылығымен байланысты: • FORTRAN және АLGOL 60 (70-жылдар); • Pascal және С (80-жылдар); • С++ және Java (90-жылдар). Даму тарихы

8 слайд

9 слайд
9 АЛГОРИТМДЕР Ж ӘНЕ ҚҰРЫЛЫМДЫ ПРОГРАММАЛАУ Алгоритм түсінігі және қасиеттері Блок-схема тілі Қарапайым программа , алгоритмді өндеудің құрылымдық бағыты Алгоритмдердің негізгі құрылымы Программаларды жобалау тілі (псевдокод) Рекурсивті алгоритмдер Іздеу алгоритмдері Сұрыптау алгоритмдері Обьектілі – бағдарлы программалаудың принципі

9 слайд

10 слайд
10 Алгоритм – тапсырманы орындауға арналған әрекеттің тәртіппен жүруін жазу. 1.Дискреттілігі. Алгоритм есепті шешу процесін қадам -этап бойынша орындайды. Әр этапты орындау үшін белгілі бір уақыт қажет, яғни алғашқы мәндерді нәтижеге түрлендіру уақытқа дискретті жүреді . 2.Анықтылығы (детерминир ленген). Алгоритмнің әр ережесі нақты және біреу ғана болуы керек . 3.Нәтижелігі(финиттіліг, шегі). Алгоритм шекті қадам ішінде тапсырманы орындау керек . 4.Көпшілікке бірдейлігі . Есепті шешу алгоритмі жалпы түрде алынады, яғни ол алғашқы мәндері ғана өзгеше, кейбір тапсырма кластарына да қолданылады. (алгоритмді қолдану аясы ). Алгоритм қасиеттері

10 слайд

11 слайд
11 Блок-схем тілі–алгоритмдерді формальді жазу әдісі Z = X + Y Мәліметтерді өндеу(есептеу, жөнелту және т.б.) I >10 Иә Жоқ Шартты тексеру шығару Z Мәліметтерді еңгізу-шығару Басы Программаның басы, соңы немесе программа ішіндегі программа Атауы процедураны шақыру Байланыс сызықтары және оларды біріктіру A Байланыс нүктелері немесе дәнекерлер Түсініктеме

11 слайд

12 слайд
12 Алгоритмдердің негізгі (базалық) құрылымы – бұл жеке блоктарды стандартты біріктірудің шектеулі тәсілі немесе әрекеттің типті орындалуынын құрылымдық блоктары. Программаны кез- келген қарапайым логикалық есеп үшін нұсқау, тармақтау және қайталау (цикл) құрылымына бөлуге болатыны дәлелденген. Құрылымдық программалау технологиясы–программалауда басқарудың үш құрылымдық базасы қолданылатын (конструкциясы), программалау бағыты:нұсқау, тармақталу, цикл. Бұл программалардың өзін жеке есептеулерді шешу үшін, программаларға бөлуді ұсынатын (процедуралар) күрделі технология, яғни декомпозицияға негізделеді. Қарапайым программа – алгоритмі, ол үшін: •Жалғыз еңгізу мен жалғыз шығару бар. •Алгоритмнің әр элементі үшін сол элементі арқылы еңгізу мен шығару жолы бар (яғни алгоритм шексіз циклдерден және қажетсіз фрагменттерден тұрмайды).

12 слайд

13 слайд
13 Қарапайым программа Шексіз цикл Жете алмайтын үзінді Қарапайым және қарапайым емес программалар мысалдары

13 слайд

14 слайд
14 Алгоритмдер құрылымының негізгілері(базасы) мен олардың туындылары Із басу - әрекеттің (блоктар) кезекпен орындалуы. 1 2 3 1 2 3 Иә Жо қ 1 2 3 Иә Жо қ «Әзір» циклі (шарты соңынан берілген) - цикл денесі (блок2) шарт ақиқат болғанша орындалады (блок3). «Дейін» циклі (шарты алдын- ала берілген) - шарт орындалғанға дейін (блок 3), цикл денесі қайталана береді (блок 2).

14 слайд

15 слайд
15 Алгоритмдер құрылымының негізгілері(базасы) мен олардың туындылары Тармақталу - шартқа байланысты не бірінші, не екінші әрекетті орындау керек, соған байланысты қолданылады. 1 Иә Жо қ3 2 Иә Жо қ3 1 Айналып өту – бір тармақ ешқандай әрекеттерден тұрмаған кездегі, жеке жағдайы. I 1 I 1 2 i n I 2 I i I n Көптік таңдау - айнымалы I мәніне байланысты бірнеше әрекеттің ішінен береуінің орындалуын жалпылау тармағы .

15 слайд

16 слайд
16 Жобалау кезеңінде программаны альтернативті жазу тәсілі – псевдокодты қолдану (немесе программаны жобалау тілі PDL – Process Design Language). Ол ішікі жіне сыртқы синтаксистерден тұрады. Сыртқы синтаксис – программалау тілі үлгісінде құрылған және программа логикасын сипаттайтын, берілген операторлар жиыны. Сыртқы синтаксис алгоритмдердің негізгі құрылғысына сәйкес келеді. Және де сыртқы синтаксиске процедуралар мен модульдер де кіреді. Процедура – бұл машина жадысына сақталған программа, негізгі программаның түрлі орнынан шақырылады, әйтпесе басқа процедураларда шақырылады. Ол ішкі мәліметтерді сақтамай ақ шақырылады және орындалады. Модуль – бұл жүйеге қолданушыға ыңғайлы ұйымдастырылған бірнеше процедуралар. Модуль кезекті модульді шақыру арасында сақталған жалпы мәліметтерге рұқсаты бар. Ішкі синтаксис – жалпыланған, негізінен арнайы анықталмаған синтаксис, тапсырманы берілген облыста жазуға қолданылады. Кәдімгі қарапайым тілде жазылған, не қызметші тілде жазылған сөйлем қолданылуы мүмкін (мысалы, математикалық формулалар).

16 слайд

17 слайд
17 Сыртқы синтаксис операторлары псевдокода Із басу. Операциялар кезекпен бірінің астына бірі жазылады . Кезекпен орындалуды бөлу үшін – do …end-do операторлары қолданылады. бірінші операция екініші операция do үшінші операция end-do Индексті із басу (есеп бойынша цикл). Алдын-ала қадам саны анықталған цикл (қарапайым және классикалық цикл арасындағы орташа). for индексті тізім тізім do do-бөлігі end-do Әзір-циклі. until-мәтіні модификациясын қосқанда, құрылым операциясы, бір немесе бірнеше рет until-мәтіні ақиқат мәніне жеткенше орындалады. do do-бөлігі until until-мәтіні end-do

17 слайд

18 слайд
18 Сыртқы синтаксис операторы псевдокод Әзір-циклі. Do-бөлігі while-мәтіні ақиқат болғанша орындалады. Do-бөлігі while- мәтіні шартын есепті шешуді аяқтау үшін модификациялайды. while while-мәтіні do do-бөлігі end-do Тармақталу . Егер…онда… әйтпесе. if if-тест then then-бөлігі else else-бөлігі end-if case тізім 1 case-бөлім 1 тізім 2 case-бөлім 2 … тізім n case-бөлім n else else-бөлім end-case Көптік таңдау.

18 слайд

19 слайд
19 Алғашқы N бүтін санынын псевдокодты және блок- схеманы қолданып квадрат қосындысын есептеу алгоритмі Қосылғыштар санын еңгізу Сумма = 0 Номер = 1 do Сумма = Сумма + Номер 2 Номерді бірге арттыру until Номер > Қосылғыштар саны end-do Қосындыны шығару Иә Жоқ Басы Еңгізу N S = 0 i = 1 S = S + i 2 i = i + 1 i > N Шығару S Соңы    N i NiS 1 2222 ...21

19 слайд

20 слайд
20 Басқару құрылымдарынан басқа, құрылымдық програмалаудың маңызды аспектісі, мәселені шешуде қатысатын мәліметтерді ұйымдастыру болып табылады. Программа құрылымы мен мәліметтер құрылымы тығыз байланысқан. «Программа – бұл нақты, кейбір шын көрініске негізделген және мәліметтер құрылымынан тұратын, абстрактілі алгоритм бейнесі». (Н. Вирт). МӘЛІМЕТТЕР ТИПІ ҚҰРЫЛЫМДЫҚ (құрылымдар) ҚАРАПАЙЫМ (скалярлық) Статикалық құрылымдар (массивтер, жазбалар, жиындар) Динамикалық құрылымдар (тізімдер, кезектер, стектер, бұтақтар, графтар)

20 слайд

21 слайд
21 Рекурсия Есеп рекурсивті шешіледі,, есепті шешудің ең қарапайым тәсілі, егер оны басқа түрге түрлендіріп барып шешу мүмкін, бірақ шешімнің өзі белгісіз болуы мүмкін (қарапайы). Бұл түрлендіруді көп қайталау базистік бекітімге сәйкес келеді. Функция F рекурсвті болады, егер 1.     F(N) = G(N,F(N-1)), мұндағы G белгілі функция; 2.     F(1) – белгілі (базитік бекітім). N факториалды рекурсивті функцияны қолданып есептеу алгоритмі Fact(I) I > 1 Fact = I*Fact(I-1) Fact = 1 Қайтару Иә Жоқ Басы F = Fact(N) Еңгізу N Соңы Шығару F

21 слайд

22 слайд
22 Іздеу Іздеу – кейбір мәліметтер жиынынан (құрылымынан) қажетті элементті табу. Мәліметтер элементі- бұл кейбір ақпараттардан тұратын, кілттер (бүтін оң сан) мен денеден құрылытын жазба. Іздеудің қызметі қажетті кілті бар жазбаны табу. Сызықтық іздеу. Элементтер кезекпен бір-бірден қажеттісі табылғанша тексеріледі . N элементі бар массив үшін орташа шамамен салыстырғанда қажет ( N+1)/2 (есептеу күрделігі О ср (N)). Жеңіл программаланады, кысқа массивтерге қолданылады. Екілік (бинарлы) іздеу. Қолданылады, егер массив алдын -ала сұрпталған болса, (кілтерінің өсуі бойынша). Іздеу кілті массивтегі орта элементпен салыстырылады. Іздеу кезінде кілт мәні үлкен болса, онда осы операция массивтің екінші жартысына қайталанады, егер кіші болса –онда біріншісіне. Операция қажетті элементті тапқанша қайталана береді. Әр қадамда элемент диапозоны екі есе азаяды. Орта есеппен (log 2 N+1)/2 қажет, (есепт. күрделігі О ср (log 2 N)) салыстырғанда. Үлкен массивтерде (көп өлшемді) іздеу үшін қолданылады .

22 слайд

23 слайд
23 Сұрыптау Сұрыптау (реттеу) – мәліметтер элементін өсу немесе кему ретімен орналастыр. Сұрыптау тәсілін қолданбас бұрын сұрыпталатын элемент ( N) саны мен қанша элемент сұрыпталғанын ескеру қажет. Критерии сұрыптау тәсілін бағалау: - N элемент санына байланысты , аргументі N нен алынған басқа функция болатын, О-функциясы көмегімен есептеу алгоритм қиындығы сипатталатын, қажетті операциялар мөлшерін салыстыру; -жадыны қолдану сапасы ; мұнда...

23 слайд