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

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 13 бет
Таңдаулыға:

Кіріспе
Алгоритм-бұл орындалудың нақты сипаттамасы арқылы деректерді өңдеудің кейбір қадамдардың ақылға қонымды саны мәселені шешуге әкеледі кез келген қолайлы нұсқалар үшін осы типтегі деректер.
Деректер-бұл ақпарат (сандар, фактілер, құбылыстардың сипаттамасы және т. б.) формализацияланған (нақты) түрде.
Кез-келген мәселені шешу үшін сізге қажет:
1. Бастапқы деректерді енгізіңіз.
2. Бастапқы деректерді нәтижелерге түрлендіру (шығу деректер).
3. Нәтижелерді шығару.
Алгоритмдер теориясы-алгоритмдерді зерттейтін ғылым алгоритмдердің жалпы қасиеттері мен заңдылықтары және оларды ұсынудың әртүрлі ресми модельдері.
Алгоритмдер теориясының міндеттері :
* есептердің алгоритмдік шешілмейтіндігін дәлелдеу
* алгоритмдердің күрделілігін талдау
* алгоритмдердің жіктелуі
* алгоритмдердің сапасын бағалау критерийлерін әзірлеу және басқа да.
Алгоритмдердің қасиеттері:
1. Дискреттілік-алгоритм есепті шешу процесін қарапайым қадамдардың дәйекті орындалуы ретінде көрсетуі керек.
2. Сенімділік-алгоритмнің әр ережесі айқын, бір мәнді болуы керек және вариацияларға орын қалдырмауы керек.
3. Тиімділік-алгоритм есепті соңғы қадамдармен шешуге әкелуі керек.
4.(Детерминированность). Әр қадамнан кейін келесі қадамның орындалатынын көрсету керек немесе тоқтату пәрменін беру керек.
5. Массалық - мәселені шешу алгоритмі жалпы түрде жасалады және тек кірістермен ерекшеленетін кейбір тапсырмалар класына қолданылуы керек. Бұл ретте кіріс кейбір саладан таңдалуы мүмкін, алгоритмнің қолданылу саласы деп аталады.

1 бөлім
Алгоритмдерді ұсыну формалары:
1. Ауызша (табиғи тілдегі жазбалар);
2. Графикалық (графикалық символдардан алынған суреттер);
3. Псевдокодтар (шартты түрде алгоритмдерді сипаттау
алгоритмдік тілде, оның ішінде бағдарламалау тілінің элементтері, табиғи тіл тіркестері, жалпы қабылданған математикалық белгілер және т. б.);

1.1Алгоритмдерді ұсынудың ауызша формасы.
Алгоритмдерді жазудың ауызша әдісі-деректерді өңдеудің дәйекті кезеңдерінің сипаттамасы. Алгоритм табиғи тілде еркін презентацияда берілген. Оны ауызша, жазбаша түрде табиғи тілде, жазбаша түрде ресми тілде сипаттауға болады. Мысалы. Ең үлкен ортақ бөлгішті табу алгоритмін жазыңыз, екі натурал сан.
1. Екі санды орнатыңыз; 5 және 10
2. Егер сандар тең болса, онда олардың кез-келгенін жауап ретінде алыңыз және 5!=10 тоқтаңыз, немесе алгоритмді орындауды жалғастырыңыз;
3. Сандардың көпшілігін анықтаңыз; 10
4. Сандардың көбісін 10 - 5-тен үлкен және сандардың аз айырмашылығымен ауыстырыңыз;
5. Алгоритмді 2-қадамнан қайталаңыз.
Нәтижесі: 5
Ауызша әдіс бірқатар кемшіліктерге ие:
* мұндай сипаттамалар қатаң ресми емес;
* жеке тұлғалардың түсінігін екі ұштылыққа жол береді
* ұйғарымдар;
* жазбалардың нақтылығынан зардап шегеді.

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

1-сурет

1.3 Псевдокод
Псевдокод-алгоритмдерді біркелкі жазуға арналған белгілер мен ережелер жүйесі.
Ерекшеліктері:
* Командаларды жазу үшін қатаң синтаксистік ережелер қабылданбайды, бұл алгоритмді жобалау сатысында жазуды жеңілдетеді.
* Ресми тілдерге тән кейбір құрылымдар бар.
* Мағынасы бір рет анықталған қызметтік сөздер бар. Олар баспа мәтінінде қалың қаріппен ерекшеленеді, ал қолжазба мәтінінде асты сызылады.
* Псевдокодтың Бірыңғай немесе ресми анықтамасы жоқ, әртүрлі псевдокодтар мүмкін, олар қызметтік сөздер жиынтығымен және негізгі құрылымдармен ерекшеленеді. Мұндай құрылымдарға әдетте бұтақтар (егер ...болса ... басқаша ...) және циклдар (цикл ... дейін ..., цикл дейін, цикл дейін...).
2 бөлім
2 Алгоритмді таңдаудағы маңызды факторлар
Алгоритмді таңдаудағы маңызды факторлардың бірі-оның жұмыс жылдамдығы. Алгоритмді есептеудің күтілетін уақытының сипаттамасы математикалық процесс болып табылады. Бұл тарауда алгоритмнің жұмыс уақытын болжауға негізделген математикалық құралдар берілген. Осы тарауды оқығаннан кейін сіз осы кітапта да, алгоритмдерге арналған басқа кітаптарда да қолданылатын әртүрлі математикалық терминдерді түсінуіңіз керек.
Көптеген тапсырмаларда бағдарламаның орындалу уақыты осы мәліметтер жиынтығының өсуімен артады. Сонымен қатар, шамадан тыс ықшам көріністер (мүмкін қысу технологиясын қолдану арқылы) бағдарламаның орындалуын негізсіз баяулатуы мүмкін. Тапсырманың данасын кодтаудың оңтайлы әдісін анықтау таңқаларлық қиын, өйткені тапсырмалар бізге нақты әлемнен келеді және оны бағдарлама арқылы шешу үшін дұрыс идеяға аудару керек. Алгоритмді есептеу кезінде біз белгілі бір алгоритмнің қаншалықты тиімді жүзеге асырылуы мүмкін екендігі туралы мәселені анықтауда мәселенің данасын кодтау шешуші фактор емес деп санаймыз. Тапсырма данасын ұсыну тек орындалатын операциялардың түріне және жиынтығына байланысты болуы керек. Тиімді алгоритмдерді жасау көбінесе тапсырманы ұсыну үшін дұрыс деректер құрылымын таңдаудан басталады.
Алгоритмдерді ұсынудың бағдарламалық формасы. Компьютерде іске асыру үшін алгоритмді бағдарламалау тілдерінің бірінде сипаттау керек. Бағдарламалау тілінде жазылған Алгоритм бағдарлама деп аталады. Бағдарлама мәтіні листинг деп аталады. Компьютерге енгізу кезінде транслятор бағдарламасы алгоритмді машиналық алгоритмдік тілге "аударады", онда барлық мәліметтер мен барлық әрекеттер екілік сандар түрінде ұсынылады.
Алгоритмдердің күрделілігін талдау
Алгоритмдердің күрделілігін талдаудың мақсаты - осы мәселені шешудің оңтайлы алгоритмін табу.
Оңтайлы (Оптимальный) алгоритм - минимальды уақыт және минимальды жады
2.1 Күрделілік теориясы
Күрделілік теориясы есептеу теориясының бөлігі бола отырып, мәселені шешу үшін қажетті ресурстарды немесе есептеу құнын зерттейді. Алгоритмнің есептеу күрделілігі-бұл функция,белгілі бір алгоритммен орындалатын жұмыс көлемінің кіріс қасиеттеріне тәуелділігін анықтау. Жұмыс көлемі әдетте есептеу ресурстары деп аталатын уақыт пен кеңістіктің абстрактілі ұғымдарымен өлшенеді.
Уақыт мәселені шешу үшін қажетті қарапайым қадамдардың санымен анықталады, ал кеңістік жад көлемімен немесе деректер тасымалдаушысындағы орынмен анықталады.
2.2 Алгоритмдердің күрделілігі
Алгоритмдердің күрделілігі әдетте жұмыс уақыты немесе пайдаланылған жад бойынша бағаланады. Екі жағдайда да күрделілік кіріс көлеміне байланысты: 100 элементтен тұратын массив 1000-ға қарағанда тезірек өңделеді. Сонымен қатар, нақты уақытты аз адамдар қызықтырады: бұл процессорға, деректер түріне, бағдарламалау тіліне және басқа да көптеген параметрлерге байланысты. Тек асимптотикалық күрделілік маңызды, яғни. кіріс көлемін шексіздікке жеткізудегі қиындық.

N енгізу элементтерін өңдеу үшін кейбір алгоритмге 4n3 + 7n шартты операцияларды орындау керек делік. N көбейтілген кезде, жұмыстың соңғы уақытына N-нің текшеге салынуы оны 4-ке немесе 7n-ге көбейтуге қарағанда едәуір әсер етеді.содан кейін бұл алгоритмнің уақыт күрделілігі O(n3) - ге тең, яғни кіріс көлеміне байланысты болады. текше.

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

Мысалдар
O (n) -- сызықтық күрделілік
Мұндай күрделілік, мысалы, сұрыпталмаған массивтегі ең үлкен элементті іздеу алгоритміне ие. Олардың қайсысы максималды екенін түсіну үшін массивтің барлық N элементтерін аралап шығуымыз керек.

O (log n) -- логарифмдік күрделілік
Қарапайым мысал-екілік іздеу. Егер массив сұрыпталған болса, онда оның белгілі бір мәні бар-жоғын жартысына бөлу арқылы тексере аламыз. Біз орташа элементті тексереміз, егер ол ізделгеннен үлкен болса, массивтің екінші жартысын тастаймыз -- ол жерде ол жоқ. Егер аз болса, керісінше -- бастапқы жартысын тастаңыз. Сонымен, біз екіге бөлуді жалғастырамыз, соңында log N элементтерін тексереміз.
Бағдарламалауда алгоритмдердің есептеу күрделілігі әдетте алгоритм орындайтын әрекеттер саны мен Қолданылатын жад мөлшері бойынша ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.