Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні




Скачать 129.44 Kb.
НазваниеЛекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні
Дата конвертации16.11.2012
Размер129.44 Kb.
ТипЛекция
КІРІСПЕ. Алгоритмдер теориясы пәні. Әртүрлі алгоритмдердердің мысалдары. Алгоритмдерге қойылатын негізгі талаптар. Блок-сұлба және алгоритмның сипаттамасы.

Лекция мақсаты:

Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру.

Лекция мәтіні:

Алгоритм ұғымы – информатиканың ең іргелі ұғымдарының бірі. Алгоритмдеу модельдеумен қатар информатиканың жалпы әдісі санатында көрініп жұр. Әртүрлі жүйелердегі басқару үрдістері белгілі алгоритмдерді іске асыруға келіп тіреледі.

Алгоритм математика мен информатика арасындағы шекаралық, математикалық логикаға жанасатын пән- алгоритмдер теориясының жүйелі түрдегі зерттеу нысаны болып табылады.

“Алгоритм” атауы өзбек математигі Әл -Хорезми есімінен шыққан. Ол ІХ ғ. өзінде төрт арифметикалық амалдың орындалу ережелерін тұжырымдады. Кейінірек пайда болған “алгорифм” сөзі Евклидпен байланысты. Ол екі санның ең үлкен ортақ бөлгішін табу ережелерін тұжырымдаған көне грек математигі. Қазіргі математикада “алгоритм” атауы қолданылады.

“Алгоритм” атауының бірнеше анықтамасы бар. Мысалы академик А. Н. Колмогоров анықтамасы бойынша, алгоритм немесе алгорифм – бұл, қадамдардың бір шамасынан қойылған мәселенің шешіміне әкеліп тірейтін, қатаң анықталған ережелер бойынша орындалатын кез келген есептеу жүйесі.

Инженерлік практикада мына анықтама жиі қолданылады: алгоритм - қайсыбір есепті шешудің дәл тұжырымдалған ережелерінің ақырлы жиынтығы.

Алгоритмнің формальды анықтамасы іргелі теориялық ұғым болып табылады. Практика жүзінде, информатика әртүрлі есептерді шешудің алгоритмін жасап, және оларды қандай да бір орындаушы үшін жүзеге асырумен айналысады.

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

Алгоритмнің интуитивті ұғымы, әдетте, оның қасиеттерінің тізімімен және алгоритмді орындаушы ұғымын енгізумен анықталады. Алгоритм әр уақытта орындаушыны ескереді және сол үшін нұсқаулар жазылады. Орындаушы ретінде адам, компьютер және басқа да құрылғылар болуы мүмкін. Белгіленген әрекеттерді орындаушы түсінетіндей алгоритм сипаттамасы орындаушы тілінде жазылады.

Алгоритмнің қасиеттері


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

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

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

3. Алгоритмдерге қойылатын негізгі талап – нәтижелілік. Бұл талаптын мағынасы мынада: алгоритмнің барлық нұсқауларын дәл орындағанда үрдіс ақырлы қадамда аяқталуы және белгілі бір нәтиже алынуы қажет. Шешімі жоқ деген қорытынды – бұл да нәтиже.

4. Нақты бір есептің емес, берілген типтегі есептердің қандай да бір класының шешімін қамтамасыз ететін алгоритмдер кеңінен таралған. Алгоритмнің бұл қасиеті жалпылық қасиеті деп аталады. Қарапайым жағдайда жалпылық қасиеті әртүрлі бастапқы мәліметтерді пайдалануға мүмкіндік береді.

Блок-сұлба және алгоритмның сипаттамасы.

Кейбір орындаушыларға құрылған алгоритмді әртүрлі тәсілдермен: графикалық немесе сөздік сипаттаудың көмегімен, кесте түрінде, алгоритмдік тілде (программалау тілінде) жазылған формулалар тізбегімен беруге болады. Блок-схема деп аталатын алгоритмнің графикалық сипатталуына тоқталайық. Бұл тәсілдің көрнектілігінің негізінде, дербес жағдайда, алгоритмнің жоғары “оқылуын” және оны басқарудың анық бейнелеуін қамтамасыз ететін біраз артықшылығы бар.

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

Әрбір блок-схеманың басының және соңының блоктары бар. Барлық блоктар ағын сызығымен байланысады. Әрбір блоктың “басы”, “соңы”, “тоқта” қызметші блоктарынан басқа бір кіріс және бір-екі шығыстық ағын сызығы болады. Блок-схемадағы ағын сызығының бағыты көлбеу және тігінен болады, және де оң бағыт болып блоктан оң және төменгі бағыттар, ал теріс – блоктан сол және жоғары бағыттар есептелінеді. Теріс бағыттардың бағыттауыштары болады.

Белгіленуі бойынша блоктар негізгі және көмекші болып бөлінеді. Негізгі блоктар ақпаратты енгізу/шығару және өңдеу бойынша әрекеттерді көрсетеді, ал көмекші блоктар бок-схеманы түсіндіру үшін және байланыстарды белгілеу үшін қолданылады.

Блоктармен анықталатын әрекеттер, немесе, түсініктер блокты білдіретін геометриялық фигуралардың ішінде жазылады.

Суретте блок-схемалардың негізгі элементтері келтірілген.

Блоктар және ағындар беттің үш: сол, орталық және оң жолағында орналасады. Сол жолақтағы солға-жоғары көшу үшін, ал оң жақтағы оңға-төмен көшу үшін қолданылады. Орталық - төмен көшу үшін.

Енгізу/шығару функциялары


Енгізу/шығару

құжат

Магниттік диск

Тура қатынайтын жад

Ақиқат

Жалған

Жоқ

Ия

Өңдеу функциясы

үрдіс

(мәліметтерді өңдеу)

Типтік үрдіс

(ішкі программа)

Шешім

(логикалық блок, тармақталу)

Блок-схема символдарын біріктіру


Ағын сызығы

Ағын сызығының бағытының өзгеруі

Байланыспаған екі ағын сызығының қиылысуы

Ағын сызығының тоғысуы

Алгоритмнің графикалық сипаттауына мысал қарастырайық.

БАСЫ

Енгізу n, X

R:=x1; m:=1

i:=2

xi>R

R:=xi; m:=i

i:=i+1

i n

Шығару R, m

Соңы

Сурет. N санның ішіндегі ең үлкен санды іздеу алгоритмінің блок-схемасы

1 Алгоритмдерді шығару жолдары берілген есептерімен бірге қатар орындалады. Ғылым саласында алгоритм түсінігі ол жаңа түсінік болып саналмайды, тек ХХ –шы ғасырда алгоритмге формалдау мүмкіндігі қарастырылды. Дәлірек айтқанда біз Тьюринг машинасының ұғымына тоқталамыз.

Есептеу теориясының негізінде қарастырсақ, онда көптеген ғалымдардың еңбектері келтіріліп көрсетілген. Есептерді шығара отырып бірнеше мамаңдар бір уақытта есептін шығару жолдарын әр түрлі тәсілде шешімдерін қызықтыра тауып отырады. Компьютердін дамуына қарай Тьюринг ұғымы қолайлы болып көрінді (себебі Тьюринг өзі есептерді практикада, есептеу машинасында қолданып жұмыс жасап есептеген, ал бұл уақытта басқа ғалымдар өз зерттеулерін математикада немесе логкада қарастырған). Осы жылдары Алонзо Черч , Эмиль Пост, Марков және тағы да басқа ғалымдар есептеу процедурасын формализациялануына әр түрлі модельдеу пікірлерін айтты. Айта кеткендей барлық модельдер бір-біріне байланысты болады.

Алгоритм ұғымын формальдаудың негізгі бағыттары.

Алгоритм математика мен информатиканың кең тараған негізгі ұғымдарының бірі. Көп жағдайда алгоритм ұғымы электронды есептеу машиналарына байланысты пайда болады деген пікір дұрыс емес. Алгоритм ұғымы электронды есептеу машиналарынан бірнеше ғасыр бұрын пайда болып өмірде қолданылып келеді.

Алгоритм деген сөздің өзі ІХ ғасырда өмір сүрген орта азиялық белгілі математик Мұхамедтің арабша атынан (альХорезм) латынша (algorіthmі) жазылуынан таралған.

Ол қазіргі уақытқа дейін өзіміз қолданып жүрген арифметикалық төрт амалдың орындалу ережелерін тұжырымдаған. Мұхамед Әл-Хорезми әдісін жақтаушылар алгоритмиктер деп, белгілі бір қасиеттері бар ережелер жүйесі алгоритм деп аталып кетті.

Қазіргі кездегі түсінігіміз бойынша алгоритм ұғымын кез келген процесті орындау үшін берілетін нұсқаулардың жиынымен байланыстыруға болады. “Мұнда есептің алгоритмі берілген” деген сөйлемді “Мұнда белгілі бір есепті шешуге қажетті амалдар беріліп, олардың орындалу реті көрсетілген” деп түсінуге болады. Күнделікті өмірде біз алгоритмнің көптеген түрлерімен кездесіп отырамыз. Мысалы, шай қайнату, торт пісіру, дәрі-дәрмек жасау, көше тәртібін сақтау, таныс кісімен сөйлесу, лифтпен көтерілу т.б.с.

Негізінде кез келген есептің шешімі белгілі бір берілген мәндер бойынша табылады. Сондықтан, алгоритмді берілген мәндерді нәтижеге түрлендіретін процесс деп қарастыруға да болады.

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

Алгоритмнің үздіктілігі деп алгоритмі сипатталып отырған процестің қадамдарға бөлінуін айтады. Қадамдарда нұсқау түрінде қарапайым іс-әрекеттің сипаттамасы беріледі. Алгоритм қадамдарды кез келген ретпен орындала бермейді. Әр адамның сипаттамасында келесі орындалатын қадам көрсетілуі мүмкін, егер ол ашық көрсетілмесе, нұсқаулар жазылу ретімен орындалады деп түсіну келісілген. Алгоритмде көрсетілген іс-әрекеттерді орындаушы адам немесе автоматты құрылғы (ЭЕМ) болуы мүмкін.

Алгоритм құрастыру және оны сипаттау әдістері. Алгоритм құру үшін, алдымен есептің шешу әдісін жақсы меңгеру керек. Алдымен берілген мәліметтермен есептелетін шамаларды анықтап, содан кейін ғана есепті шешу тәсілі бойынша алгоритм құрастырылады. Алгоритм құрастыру деп есепті шешуге қажетті амалдардың тізбегін анықтауды, ал сипаттау деп алгоритм қадамдарын мағынасы мен жазылу үлгісі тұрақты шартты белгілер жүйесі арқылы жазуды айтады. Алгоритм белгілі бір орындаушыға арналып жасалатындықтан, оны сипаттаған кезде атқарушының мүмкіншіліктері ескерілуі керек. Егер алгоритмді атқарушы адам болса, алгоритмнің көрнекі болуына аса көңіл аудару керек те, ал атқарушы ЭЕМ болса, электронды есептеуіш машиналардың ерекшеліктері ескерілуі керек, яғни онда енгізу, қорытындылау, меншіктеу қадамдары болуы тиіс.

Енгізу деп берілген мәліметтерді ЭЕМ есте сақтау құрылғысына жазуды, ал қорытындылау деп керісінше, ЭЕМ еске сақтау құрылғысынан пайдаланушыға жеткізуді айтады.

Енгізу, қорытындылау мен қатар меншіктеу операциясы есептец машиналарында қолданылатын маңызды операциялардың бірі. Меншіктеу деп белгілі бір шаманың мән қабылдауын айтады.

Алгоритмді сипаттаудың көптеген тәсілдері бар. Солардың ішіндегі ең қарапайымдары:

  1. Алгоритмді алгоритмдік тілде сипаттау.

  2. Алгоритмді схема арқылы сипаттау.

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

Алгоритмдерді базалық құрылымдардың композициясын пайдаланып сипаттау. Типтік алгоритмдер

Біз осы уақытқа дейін қарапайым алгоритмдерді сипаттауға қолданылатын алгоритмнің түрлі құрылымдарын қарастырдық. Бұл құрылымдар кез келген алгоритмді сипаттаудың негізі болып табылады. Осы құрылымдардың сан алуан комбинациялары (тармақталу құрылымыныңәр тармағының құрамына тізбектелу, тармақталу немесе цикл құрылымдары еніп тұруы мүмкін ) арқылы кез келген күрделі есептің алгоритмін сипаттауға болады. Жоғарыдағы мысалдарда тармақталу мен тізбектелудің немесе цикл мен тізбектелудің комбинацияларын қарастырдық. Енді цикл мен тармақталудың және циклдардың түрлі комбинацияларынан тұратын құрылымдарды қарастырамыз.

Тармақталған циклдар.Егер цикл денесінің құрамына тармақталу енсе, ондай құрылымды тармақталған цикл деп атайды. Ескерту: Мұндағы әр тармақ өз кезегінде күрделі құрылым (тізбектелу, тармақталу, цикл) болып келу мүмкін.Алгоритмі тармақталған цикл құрылымымен сипатталатын есепке мысал.

1-есеп. Есептеу формуласын таңдау арқылы функция мәндерінің таблицасын алу.

  1. Есептің математикалық қойылуы:

Берілген шартқа байланысты есептеу формуласын анықтап функция мәндерін есептеу керек.



Мұндағы х,а-дан b –ға дейін h қадаммен өзгереді.

a x b,h

5

  1. Енгізілетін және қорытындылатын шамаларды анықтау.

Енгізілетіндері: a,b,h

Қорытындылатыны: у-ң мәндері

  1. Алгоритм құрастыру және сипаттау

у-ң мәндері аргумент х-ң түрлі мәндері үшін берілген формулаларды бірнеше рет қайталап пайдалану арқылы есептеледі. У-тің әр мәнің есептеудің алдында берілген шартты тексеру арқылы ( х  с ) есептеу формулаларының не біріншісі, не екіншісі таңдалады. Бұл есептің алгоритмін сипаттауға тармақталған цикл құрылымы керектігін байқаймыз. Циклдың қайталау санын мына формула арқылы анықтап аламыз:

, ал аргумент

фомуласымен есептеледі.

Мұндағы i=1,2,…,n-1

Талдау: 4,5,6,7,8,9- блоктар цикл құрайды; 5,6,7,8.9- блоктар цикл денесі; 6,7,8 – тармақталу құрылымы.



1.2. ҚАБАТТАСҚАН ЦИКЛДАР

Цикл денесінің құрамына бір немесе бірнеше циклдар енуі мүмкін. Мұндай циклдарды қабаттасқан циклдар деп атайды. Циклдарды қоршап түрған циклды сыртқы деп, басқалары ішкі циклдар деп аталады. Қабаттасқан циклды ұйымдастыру әдісі де қарапайым циклды ұйымдастыру әдісіндей. Тек сыртқы, ішкі циклдардың параметрлері әртүрлі болуы керек және екеуі қатар өзгермеуге тиіс.

algor

Қабаттасқан цикл үлгісімен сипатталатын үлгі алгоритмдер.

1-алгоритм. Екі аргументті функцияның мәндерін есептеудің алгоритмі.

1) Есептің математикалық қойылуы: Төменде көрсетілген функцияның мәндерін есептеукерек:

Мұндағы, , hx- қадам, , hy- қадам

2) пайдаланылған айнымалылар: Берілгендері: a, b, c, d, hx, hy Нәтиже: z мәндерінің жиыны n1 – сыртқы циклдың қайталау саны, n2 – ішкі циклдың қайталау саны. 2) Алгоритм құрастыру және сипаттау

4-9 блоктар сыртқы циклды, ал 6-9 ішкі циклды құрайды. х-ң әр мәнінде у өзінің барлық мәндерін қабылдап шығады. Ішкі циклдың алдында х-ң мәні (5-6) есептеледі. Сөйтіп, х бойынша құрылған циклдың ішіне, у бойынша ұйымдастырылған цикл орналасады.

2-алгоритм. Қосынды түрінде берілген функцияның мәнін есептеудің алгоритмі.

1) Есептің математикалық қойылуы

функциясын есептеу керек. Мұндағы , h-аргументтің өзгеру қадамы

2) Қолданылатын айнымалылар: Берілгендері: a, b, h, n Нәтиже: у мәндерінің жиыны.

Бақылау сұрақтары:

  1. Алгоритм деген не? Алгоритмнің қандай қасиеттері бар, оларды қалай түсінесіз?

  2. Алгоритмді сипаттаудың қандай әдістерін білесіз?

  3. Алғашқы , қорытынды мәліметтер деп нені айтамыз?

4. Күрделі алгоритмдер қалай сипатталады?

5. Алгоритм құрылымдарының қандай комбинациялары болады?

6. Тармақталған цикл құрылымының схемалық үлгісі қандай?

Похожие:

Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні iconЕсенберлин шығармашылығы жөнінде мәлімет. «Көшпенділер» трилогиясы Сабақтың мақсаты
А/ Білімділік: І. Есенберлиннің өмірі мен шығармашылығы жөнінде мағлұмат беру, трилогияның мазмұны мен кейіпкерлерімен таныстыру....
Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні iconОқытушының жетекшілігімен студенттердің өз бетінше атқаратын жұмысына арналған әдістемелік нұсқау Тақырыбы: Тоталитаризм, оның негізгі типтері мен түрлері Пән: Саясаттану Мамандық: «5В110300 Фармация»
Сабақтың мақсаты: Студенттерге саяси режим туралы тұжырымдамалар мен ұғымдакрды, саяси режимнің туріне қарай жіктелуі, режимдердің...
Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні iconТабиғаттағы ақпарат ұғымы. Ақпарат түрлері. Ақпарат көзі, қабылдаушы мен жеткізу ортасы. Ақпарттық процестер. Адамның ақпаратты қабылдауы
Сабақ мақсаты: а Ақпарат ұғымымен, оның түрлерімен, үлгілерімен және өңдеу тәсілдерімен таныстыру
Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні iconЛекция 5 Лекция html тілінде тізімдерден пайдалану Тізім түрлері. Маркерленген тізімді құру тэгтері
Анықтамалар термин ( тэгі) және оның сипаттамасынан ( тэгі) тұрады. Тэгтің compact атрибуты тізімді ықшам түрде бейнелейді. Атрибуттың...
Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні iconАлгоритм және оның қасиеттері
...
Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні iconАлгоритм және оның қасиеттері
...
Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні iconЛекция курсы Шымкент-2010 ж. 1-лекция Мәдениет контекстіндегі философиялық шығармашылықтың тарихи типтері
Мәдениет дүниесіндегі философияның қатынасы мен тағайыны. Философия адам құштарлығының әр түрлі төрт саласының ғылым, поэзия, дін,...
Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні icon«Алгоритм» ұғымының даму тарихы. Алгоритм ұғымы Алгоритмдерді сипаттау тілдері мен құралдары

Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні iconСабақтың тақырыбы: Мотоатқыш взводы мен ротасын ұйымдастыру және ұрыс қимылдарының негіздері. Сабақтың мақсаты
Сабақтың мақсаты: Оқушыларға тактика ілімі туралы түсінік беру,Ұрыс және оның түрлері туралы түсіндіру
Лекция мақсаты: Алгоритм ұғымы, оның берілу түрлері мен типтері жөнінде мәлімет беру. Лекция мәтіні icon6D080600 – аграрлық техника және технология мамандығы бойынша PhD докторантураға түсу емтиханының бағдарламасы
Тәжірибелік зерттеулер. Тәжірибелік жіктелуі, мақсаты және түрлері. Есептеу тәжірибесі. Тәжірибені жоспарлаудың түрлері. Статисти-калық...
Разместите кнопку на своём сайте:
kk.convdocs.org



База данных защищена авторским правом ©kk.convdocs.org 2012-2019
обратиться к администрации
kk.convdocs.org
Главная страница