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

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

Семей қаласының Шәкәрім атындағы мемлекеттік университеті

Физика - математика факультеті, математика мамандығы

Орындаған: Абдулина П. Т-311

Тексерген:Рысжанова А. С.

Семей 2015ж

Жоспар

I. Кіріспе бөлім

А) Алгортим деген не және оның қасиеттері

II. Негізгі бөлім

А) алгоритм теориясы

Б) Алгоритмдік тіл, оның ережесі жіне оны орындаушыларының сипаттамалары

В) Алгоритмнің күрделілігі

С) Алгоритм түсінігі функция түсінігімен байланысы

Д) III. Қорытынды

IV. Әдебиеттер тізімі

Алгоритм - бастапқы берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалық объектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т. б. ) тәсілдерінің дәл сипаттамасы. Дербес программаны құру үшін программалау тілін білу ғана жеткіліксіз. Программаның түпкі негізі алгоритм ұғымынан құралады. Себебі алгоритм көмегімен программист өзі құрмақшы болып отырған программаға сәйкес мақсатқа жетуі үшін орындауы қажет әрекеттердің тізбегін құрастыруы керек. Алгоритмнің негізгі қызметі - берілген ақпаратты өңдеу арқылы басқа, жаңа ақпарат құру.

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

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

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

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

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

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

Қай алгоритм болса да негізгі қасиеттерді қанағаттандыруы шарт:

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

Түсініктілік қасиеті - орындаушыға түсінікті және орындай алатын нұсқаулар жиынынан командалардан тұруы қажет. Орындаушыдан біртұтас әрекет жасауды талап ету керек. Алгоритм орындаушыға бағытталуы керек.

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

Ортақтық қасиеті - бір алгоритм барынша үлкен класқа жататын есепті шешетіндей болуы керек, тек бастапқы берілгендерді өзгерту арқылы ғана шешімді табуға болатындай. Мысалы квадрат теңдеуді шешу алгоритмін ах2+bx+c=0 жағдайына құрған дұрыс болады, ал 4x2+5x-1=0 түріне құрса онда алгоритм дербес болады, неғұрлым жалпы болуы керек.

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

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

1. Алгоритм ақыpлы өлшемді нұсқаулар жиыны ретінде беріледі.

2. Нұсқауларды түсініп, есептеулерді жүргізетін есептегіш (көбінесе адам) болады.

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

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

Бұл қасиеттер электронды есептеу машиналарға ұқсастықты көрсетеді. Шынында да

1) машинаның программасы,

2) есептеу құрылысы,

3) жаттау қабілеті,

4) табиғи құрлысы.

Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық аспектілерде қолданылады. Теориялық аспект: Есептің алгоритмдік шешімі болатындығын немесе оны шешудің нақты алгоритмі болмайтындығына есепті зерттеу нәтижесінде алгоритмдер теориясының жауап беру мүмкіндігі теориялық аспектіге жатады. Алгоритмдік шешімі болмайтын есептер Тьюринг машинасын тоқтату есебіне келтіріледі. Ал алгоритмдік шешімі болатын есептер үшін олардың NP-толық есептер класына тиесілі ме екендігі анықталады. Егер тиесілі болса, онда бастапқы деректері үлкен болатын есептердің нақты шешімін алу үшін қанша уақыт кететінін анықтауға немесе оны шешудің жылдам нақты алгоритмі болмайтындығын айтуға мүмкіндік береді. Практикалық аспект: алгоритмдер теориясының, әсіресе асимптотикалық және практикалық талдаудың әдістері мен әдістемелері келесі мүмкіндіктерді береді: Берілген есепті шешуге арналған алгоритмдер жиынынан жасалатын программалық жүйедегі олардың ерекшелігін ескеретін тиімді алгоритмді таңдауға мүмкіндік береді. Күрделілік функциясы арқылы күрделі есептерді шешудің уақыттық бағалауларын алады. Белгілі уақыт ішінде қандай да бір есептің шешуі болмайтындығына шынайы баға беріледі.

Ақпаратты өңдеу саласындаың маңызды деген есептерін шешудің тиімді алгоримтмдерін құру мен жетілдіру.

Алгоритмдік тіл (ағылш. algorіtmіc - алгоритмдік және language - тіл) - ЭЕМ-мен шығарылатын есептердің алгоритмін бірмәнді түрде жазуға арналған жасанды тіл. Ол белгілер (символдар) жиынтығынан (Алгоритмдік тіл алфавитінен), синтаксистік ережелер мен семантикалық анықтамалардан құралған. Алгоритмдік тілдің негізгі белгілері латын не орыс алфавиттері әріптері, қандай да бір таңбалар мен шартты белгілер болуы мүмкін. Сөздер, сөз тіркестері (фразалар, сөйлемдер) , кестелер мен кестелер жүйесі Алгоритмдік тілдің құрылымы болып табылады. Түсіндіру ережелері ЭЕМ-де аппараттармен жүзеге асырылатын Алгоритмдік тіл машиналық тіл деп аталады. Алгоритмдік тіл табиғи тілден бірмәнділігі мен айқындылығы жағынан ерекшеленеді. Есептеу машинасына Алгоритмдік тілін пайдаланғанда бағдарламалау мен машина жұмысын үйлестіретін арнайы бағдарламалаушы - процессор қолданылады. Ол бағдарламаны енгізу, машиналық, синтаксистік, семантикалық талдаулар, формальды қателерді анықтау, бағдарламаны орындау т. б. жұмыстарды атқарады. Алгоритмдік тілдің бірнеше түрі бар. Олардың кейбіреулері ғана (мыс., алгол, кобол, лисп, Пл/1, Фортран, Паскаль т. б. ) кең тараған.

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

Интерпретатор - берілген прогамманың әрбір жолын (командасын) жеке - жеке аударып отырып орындайтын транслятор түрі.

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

Алгоритмдік тіл

Алгоритмдік тілдің жалпы ережесі

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

алг алгоритмнің атауы

арг A, B, C, D, X

нәт Y, R1, R2

басы

алгоритм командалары (серия)

. . .

соңы

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

Айнымалы: = өрнек немесе y: = ax - b

Мұндағы айнымалы шамаға өрнек мәні меншіктеледі немесе у айнымаласына ax - b өрнегінің мәні беріледі, «: =» - меншіктелу таңбасы, оның сол жақ бөлігіне кез келген айнымалы шама, оө жақ бөлігіне кез клген өрнек орналасады.

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

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

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

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

- шарты алдынан берілген - «әзірше» циклі,

- шарты соңынан берілген цикл - «дейін» циклі,

параметрлі цикл.

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

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

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

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

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

- Тілдің деңгейі тілдің формальдандырылу дәрежесіне де байланысты. Ол орындаушының кім болуынан тәуелді. Егер орындаушы адам болса, оған белгілі бір алгоритмдерді түсінікті сөз, сөз тіркестері арқылы түсіндіруге болады, ал рындаушы автомат болса, онда бірқатар міндетті талаптар қойылады.

- командаларды тұжырымдау барысында машинадан осы машина үшін қатаң анықталған операцияларды орындауды ғана талап ету.

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

Алгоритмдік тіл - ұғымдары:

алфавитті - тілде қолдануға болатын символдардың, белгілердің жиынтығы.

2) Тіл конструкциясы - айнымалы, өрнек, командалардың жазылу және алгоритмдік жазудың жалпы құрылымының ережелері. Оны синтаксис деп атайды.

3) Семантикасы - әр түрлі командалардың қызметі мен орындалу жолы.

Алгоритмнің тағы бір негізгі мінездемелерінің бірі - оның күрделілігі.

Әдетте алгоритмдер күрделілігінің дәрежесі оперативті жады және процессорлық уақыт сияқты қолданылатын компьютер ресурстарының көлемімен бағаланады. Осыған байланысты алгоритмнің уақыт бойынша күрделілігі және көлем бойынша күрделілігі анықталады. Көп жағдайда уақыт бойынша шектеулер басым рөл атқаратындықтан уақыт бойынша күрделілік маңызды болып есептеледі. Уақыт бойынша күрделілік орындалатын операциялар санымен анықталады, алғашқы мәліметтерге тәуелді (олардың көлеміне және шамасына)

Алгоритмнің уақыт бойынша күрделілігі - алгоритмнің есепті шешуіне жұмсаған уақыты, ол есептің өлшемі n-ге тәуелді функция. Бұл күрделіліктің есептің өлшемі өсудегі шектік мінездемесі асимптотикалық уақыт бойынша күрделілік деп аталады. Көлем бойынша күрделілік және асимптотикалық көлем бойынша күрделіліктер де осыған сәйкес анықталады Мысалы, егер алгоритм n өлшемді енгізулерді cn2 уақытында, мұнда c - қандай да бір тұрақты, өңдесе, онда уақыт бойынша күрделілік (n2) деп айтады. Алгоритмдерді талдауда ең жақсы, ең жаман және орта жағдайлар қарастырылады, сәйкес бағалаулар беріледі. Алгоритмдерді құру мен талдауда олардың тиімділігін салыстыру үшін теоретиктермен қарапайым жол ұсынылған: полиномиалдық және экспоненциалдық алгоритмдер арасындағы айырмашылық.

Егер алгоритмнің уақыт бойынша күрделілігі есеп өлшемі n-нің полиномиалдық функциясы түрінде өрнектелсе, онда алгоритм полномиалдық деп аталады. Алгоритмнің уақыт бойынша күрделілігі мұндай бағалуға бағынбаса, онда ол экспоненциалдық деп аталады. Есепті шешудің қарапайым алгоритмінің күрделілігі осы есептің күрделілігі деп аталады.

Егер есепті шешудің уақыт бойынша күрделілігі (f(n) ) -ге тең алгоритмі бар болса, онда есептің күрделілігі (f(n) ) -ға тең, мұнда f(n) - қандай да бір n-ге тәулді функция, . Сондай-ақ бұл есепті O(f(n) ) класының есебі деп атайды. Егер есеп O(f(n) ) класында жататын болса, мұнда f(n) -полином, немесе бұл өрнек полиноммен шектелген, онда ол полиномиалдық деп аталады.

Ұқсас жұмыстар

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

Алгоритм күрделілігі

Шешілмейтін алгоритмдер туралы түсінік

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

Алгоритм туралы мәлімет

Шешілмейтін алгоритмдер туралы түсінік. Алгоритм күрделілігі

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

ТЬЮРИНГ МАШИНАСЫ жә не Марковтың нормальді алгоритмы

Алгоритом туралы түсінік. Қасиеттері. Есептеу процесі ұғымы. Алгоритм күрделілігі. Алгоритмнің уақытша күрделілігі. Алгоритмнің теориялық күрделілігі

Пәндер