Базалық құрлымдардан олардың суперпозицияларын нақты бір есептің шарттарына сәйкес құру мүмкіндігі,модулділік,декомпозиция мүмкіндігі
Рекурсия – бұл өзіне сілтеме бере отырып объектіні анықтау Рекурсия базасы
жүктеу/скачать 81,93 Kb.
|
| Рекурсия – бұл өзіне сілтеме бере отырып объектіні анықтау
Рекурсия базасы – бұл тривиальды жағдай, бұл кезде есептің шешімі сірә бар болады, яғни фугкцияның өзіне қатынауын талап етпейді Рекурсивті алгоритм –тікелей немесе жанама шақырудан тұратын алгоритм анықтамасы Рекурсия түрі, бұл процедурада тікелей деп аталатын өзіне өзі айқын қатынау Рекурсия түрі, бұл кезде А процедурасы В процедурасына қатынаудан тұрады, ал В А –ға жанама қатынай алатындығын көрсетеді Тікелей біріктіріп сұрыптаудың үш этапы: Сұрыпталатын массив мейлінше өлшемдері бірдей екі жартыға бөлінеді , Әрбір алынған жартылар жеке сұрыпталады (қандай-да бір алгоримтнің көмегімен соның ішінде біріктіру алгоритмі) , Жарты өлшемге ие реттелген массивтер бір массивке біріктіріледі Рекурсивті объектілерге жататындар: натурал сандар бинарлы ағаштар факториал функциясы Рекурсия базасы – Рекурсия базасы – бұл тривиальды жағдай, бұл кезде есептің шешімі сірә бар болады, яғни фугкцияның өзіне қатынауын талап етпейді Рекурсивті алгоритм – бұл алгоритм, тікелей немесе жанама осы алгоритмді шақырудан тұратын анықтама Келесі сұрыптау алгоритмдері үшін максимальды және орташа уақыттық күрделілік O(n2) сәйкес: қарапайым енгізу сұрыптауы,көпіршік әдісімен сұрыптау,таңдау сұрыптау Келесі сұрыптау түрлері болмайды: таратып сұрыптау,қосып , көпбөліктік сұрыптау Массивтерді сұрыптау әдістерінің кластары: кірістіріп таңдап алмастырып сұрыптау Келесі іздеу алгоритмдері болмайды: биіктікте, кірістіріп , Шелл іздеуі n элементтен тұратын массивтегі сызықты іздеу кезіндегі ең жақсы, ең жаман және орташа жағдайлардағы салыстырулар саны: 1 , n/2 , n Екілік іздеу ағашы — бұл келесі қосымша шарттар орындалатын екілік ағаш: екі ішкі ағаш та — сол және оң, іздеудің екілік ағашы болып табылады, таңдап алынған х түйіннің барлық сол ішкі ағаш түйіндеріндегі деректер кілтінің мәні негізгі х түйінінің деректер кілтінің мәнінен кем, таңдап алынған х түйіннің барлық сол ішкі ағаш түйіндеріндегі деректер кілтінің мәні негізгі Х түйінінің деректер кілтінің мәнінен кем емес Екілік ағаштағы іздеудің негізгі операциялары: find insert remove Екілік ағаштағы іздеу қызылды-қаралы ағаш деп аталады, егер оның келесі қасиеттері болса: әрбір төбе қызыл немесе қара болса, бірақ барлық жапырақтар – қара, егер төбе қызыл, онда оның екі мұрагері де қара, тамырдан жапырақтарға апаратын жолдағы қара төбелердің сандары бірдей болса Ішкі жолдарды іздеу алгоритмдері: Рабин - Карп алгоритмі, Кнут – Моррис - Пратт алгоритмі, Бойер - Мура алгоритмі Сыртқы жадыда ақпараттарды тиімді сақтауды қамтамасыз ететін Б-ағаштардың қасиеті: Әрбір беттің көп дегенде 2n кілттері, және аз дегенде n кілті болады (түбірліден басқа), Әрбір бет өзімен жапырақты көрсетеді, әйтпесе m+1 мұрагері болады, мұндағы m – беттегі кілттер саны, барлық беттер – жапырақтар бір деңгейде болады Хештеу кезіндегі коллизияларды рұқсат ету әдістері: ашық адресациялау әдісі, шынжырлар әдісі, сызықты мақұлдау В[4,5] жазуы қандай массивті анықтайды? 4 жол 5 бағаннан тұратын екі өлшемді массив ... a[i,j]:=a[j,i] ... амалы нені орындайды? матрицаны транспонирлейді Егер жол саны мен баған саны тең болса массив қалай аталады? текше немесе квадрат массив . .. s:=s*a[i,j]... алгоритмдік жазуы нені есептейді? а матрицасы элементтерінің көбейтіндісін y:=a[0] жазуы нені білдіреді? а массивінің нөлінші элементі у-ке меншіктелсін s:=s+a[i,i] формуласымен не есептеледі? массив элементтерінің ізі Қосалқы алгоритмнің кәдімгі алгоритмнен ерекшелігі ол басқа алгоритмнің ішінде бірнеше рет қолданылады i:=1 ден N-ға дейін S:=0 j:=1 ден М-ға дейін ц.б. S:=S+a [i,j] + b[j] ц.с. C[i]:=S ц.с. алгоритмі нені енсептейді? Екі өлшемді массив пен бір өлшемді массивтің элементтерінің қосындысын Реттеудің қандай түрлері бар? Өсу, кему, алфавит бойынша реттеу Сұрыптау дегеніміз не? Массив элементтерін белгілі бір ережені сақтайтындай етіп, реттеп орналастыру Ішкі сұрыптау деген не? Ішкі жадыға деректерді реттеп орналастыру Деректердің стандартты типтеріне жатпайтын тип қайсысы? Жазу Деректер структурасының жалпы классификациясы Физикалық, логикалық структурасы Ауқымды типтерге жататын типтер Композитті, күрделі құрылымды Деректердің статикалық структурасы деген не? Базалық, примитивті структуралардың құрылымды жиыны Жазулар (структуралар) деген не? Әртүрлі типті деректерді анықтайтын әрістердің ақырлы реттелген жиыны Стектер деген не? Өзгермелі ұзындықты, енгізу, шығару тек бір жақтан ғана жүргізілетін тізбектелген тізім "Бірінші келіп, бірінші кету" принципіне кезектің қай түрі негізделген? FIFO For … to … do … операторының қызметі Қайталауды орындау Procedure қызметші сәзімен сипатталатын алгоритм қосалқы алг Жай шартқа жатпайтын шартты анықта . a<=x<=b Екі өлшемді массивтерді бірбіріне көбейтіп, қосқанда қандай массив алады? екі өлшемді массив Кітапханаға бару алгоритмі қандай алгоритмге жатады? Тұрмыстық Қабырғалары тең болып берілген алтыбұрыштың ауданын табу қандай алгоритмге жатады? Қосалқы Қосалқы алгоритмді шақыру командасы:алгоритм атауы (іс жүзіндегі параметрлер тізбегі) Қосалқы алгоритмнің айнымалыларын басқаша қалай атауға болады? Параметрлер Локальды параметр деп неге айтады? қосалқы алгоритм ішінде ғана жұмыс істейтін айнымалыны Реттеудің қандай түрлері бар? өсу, кему, алфавит бойынша реттеу Көпіршіту жєне сызықты сұрыптау әдістерінің қадамы – Кемімелі қадам «Деректер реттелмеген болса, элементтің кілті анықталып, кілттің мӘнімен жазулар салыстырылады, сәйкестік болса жазудың табылғаны туралы ақпарат шығады, Әйтпесе іздеу сӘтсіз аяқталады» - бұл алгоритм іздеудің қай түрін анықтайды? Сызықты немесе біртіндеп іздеу Деректердің структурасын алгоритм көмегімен өңдейтін объект; Компьютер Деректер структурасына қолданылмайтын амалдар: Енгізу Құрылымдық программалаудың негізгі принциптеры: Кез-келген программа үш негізгі базалық конструкция типтерінен құрылған құрылымды көрсетеді, Қайталанатын немесе логикалық толық блокты көрсететін программа фрагменттері подпрограмма түрінде безендірілуі мүмкін, Программаны өңдеу қадамдық түрде, «жоғарыдан төмен» әдісі бойынша орындалады Ішкі программаға параметрлерді беру әдістері: мәні бойынша, сілтеме бойынша,аталуы б for циклын ұйымдастыру үшін керекті үш әрекет: цикл санағышының бастапқы мәнін қою, ағымдағы санағыш мәнін соңғы мәнмен салыстыру, цикл санағышының мәнін әрбір қадам сайын өзгертіп отыру Алгоритмдік тілдердегі программалаумен байланысты емес программалау: сызықты программалау , сызықты емес программалау, динамикалық Құрылымдық түрдегі деректер компонентіне дұрыс қатынау: массив компоненттеріне – есептелетін і индексі бар селектордың көмегімен, жазба компоненттеріне – жолдар компонентінің атауы бар селектордың көмегімен, көпмүше компоненттеріне – in арақатынас операциясының керектігін тексерудің көмегімен Программалау методологиялары: операциальды- бағытталған, процедуралы – бағытталған, объектіге – бағытталған Процедураға - бағытталған тілдерде ішкі программаларды қолдану кеңінен тәжірибеленуде, олар үшін келесілер шынайы: ішкі программа тақырыбында оны сипаттау үшін көрсетілетін параметрлер формалді деп аталады, ішкі программаны шақыру кезінде көрсетілетін параметрлер фактілі параметрлер деп аталады, шақырылған программада сипатталған объектілер, глобалді деп аталады және осы программамен шақырылатын процедуралар ішінде қолжетімді болады Программалардағы қателер түрі: семантикалық,логикалық синтаксистік Алгоритм құрудың алғашқы екі кезеңі. мақсаттың қойылымы , моделін әзірлеу Алгоритмдердің түрлері: сызықтық; тармақталған; циклдік Алгоритмнің айқындалушылық қасиетінің мағынасы: алгоритмді бірдей бастапқы мәндерге қолдану арқылы бірдей нәтижеге қол жеткізуіміз керек, алгоритмнің орындалуы әрбір қадамда нақты белгілі болуы, алгоритмнің орындалуы әрбір қадамда нақты белгілі, әр әрекет орындаушыға түсінікті және белгісіз анықталуы мүмкін емес Алгоритмнің көпшіліктік қасиетінің мағынасы : алгоритм нақты бір есептің ғана емес, соған ұқсас есептердің шығарылуын қамтамасыз етуі керек, әртүрлі бастапқы мәндер енгізген жағдайда да бір шешім алуды қамтамасыз етеді Алгоритмнің мардымдылық қасиетінің мағынасы : әртүрлі бастапқы мәндер енгізген жағдайда да бір шешім алуды қамтамасыз етеді, алгоритмдік үдеріс шешім бермей жатып үзілмеуі керек, берілген бастапқы мәндер үшін есепті шешу мүмкін еместігі Алгоритмнің аяқталымдылық қасиетінің мағынасы. алгоритмнің қарапайым әрекеттерінің тізбегі шексіз бола алмайды, алгоритмнің әрекеттері шектелмеген бола алмайды Евклид алгоритімінің нәтижесі: ең үлкен ортақ бөлгішті табу, екі бүтін санның ең үлкен ортақ бөлгішті табу Функцияны немесе процессті бейнелейтін тіктөртбұрыш қалай аталады: функционалдық түйіншек TRUE мағынасын қайтаратын логикалық тұжырымдама: 2<>8, (2<5) or (3>6), (2<5) and (6>3) Қарапайым стандартты мәліметтер типіне келесілер жатады: Double int char FALSE мағынасын қайтаратын логикалық тұжырымдама: (2<5) and (3>6),not (3<7), 2=8 Сілтемелерге арналған негізгі операциялар: Меншіктеу таңдау адресін алу Алгоритмнің шығу тарихы қай ғалыммен байланысты? Әл – Хорезми Алгоритм ұғымы - Алгоритмдеу моделдеумен бірге информатиканың жалпы әдісі , жеке қадамдардан тұратын, формальды түрде жазылған реттелген нұсқаулар тізбегі Алгоритмнің анықтамасы - Белгілі бір мәселені шешу үшін қойылатын мақсатқа бағытталған іс-әрекеттердің тізбегі, жеке қадамдардан тұратын, формальды түрде жазылған реттелген нұсқаулар тізбегі Алгоритмнің негізгі қасиеттері - Дискреттілік, түсініктілік, детерминделген, ортақтық, Нәтижелілік Алгоритмнің жалпы түрлері - Тұрмыстық, есептеу, қосалқы Алгоритмнің негізгі қызметі – Берілген ақпаратты өңдеу арқылы басқа, жаңа ақпарат құру. Алгоритмді жазу әдістері Блок-схема құру немесе бұйрықтар тізбегін құру Алгоритм модельдері Теориялық, практикалық Тьюринг машинасы Бірнеше бірдей секцияларға бөлінген, оқу-жазу инесі бар шекті дискіден тұратын абстрактылы машина Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші Бірнеше бірдей секцияларға бөлінген, оқу-жазу инесі бар шексіз лентадан тұратын абстрактылы машина Черч тезисі Алгоритмдік – есептелетін бөлшекті сандық функциялар класы барлық бөлшекті рекурсивті функциялар класымен беттеседі Есептелетін функциялар Әлдебір алгоритм көмегімен есептелетін функция Алгоритм деген не? Белгілі бір мәслені шешуге қажетті әрекеттердің шектеулі жиынтығы мен орындаушыға берілетін нұсқаулар жүйесі Рекурсивті функция Аргументі басқа функциядан тәуелді есептелетін функциялар Есептеу алгоритміне қайсысы жатады? фигура ауданын табу Есептеу алгоритміндегі негізгі объект – формула Орындаушы үшін реттеліп жазылған әрекеттер тізбегі қалай аталады? нұсқау немесе команда Алгоритм белгілі бір класқа жататын есептерді шығаратындай құрылса, алгоритмнің қай қасиетін анықтайды? Ортақтық Алгоритмнің барлық нұсқауларын дәл орындаған жағдайда шектеулі қадамнан соң белгілі бір жауап алынса, қай қасиетті қанағаттандырады? Нәтижелілік Алгоритмде мағынасын єрқалай түсінетін нұсқаулар болмаса, қай қасиетті қанағаттандырады Анықтылық Алгоритмде орындалатын әрекеттердің бірнеше жеке жеке қадамдар тізбегіне бөлінуі қай қасиетін анықтайды? Дискреттілік Алгоритм адамның бір тілді білетін, оқи алатын қасиеттеріне сүйеніп құрылса, алгоритмнің қай қасиетін анықтайды? Түсініктілік Команда немесе нұсқау деген не? Орындаушыдан біртұтас әрекет жасауды талап ететін жекенұсқау Математикалық формула көмегімен шығарылатын есептерге құрылған алгоритм қалай аталады? Есептеу алгоритмі есебіне құрылатын алгоритм түрі тармақталған есебіне құрылатын алгоритм түрі циклдік формуласының алгоритмі қай түрге жатады? Сызықты Екі санның үлкенін табу алгоритмі қандай алгоритмге жатады? Тармақталған a=3; b=4; c:= a>b өрнегі қандай мән қабылдайды жалған Ақиқат жєне жалған мәндерді қабылдайтын айнымалыларды қалай атайды? Логикалық Әріптер мен сандардың бірігуінен құралған мән қандай айнымалыға жатады? Литерлік 3.14 саны қандай шамаға жатады? Тұрақты формулаларындағы х-айнымалыларының типі қандай болады?Нақты Құрылған әрекеттер жиыны бірінен кейін бірі тізбектеліп орындалатын болса, қай алгоритмге жатады? Сызықты Айнымалының мәніне байланысты 1 немесе бірнеше әрекеттерді таңдап орындау керек болса, қай алгоритмге жатады? Тармақтаған Айнымалының мәніне байланысты бір немесе бірнеше әрекеттерді қайталап орындау керек болса, қай алгоритмге жатады? Цикл Бірнеше әрекеттердің тобын бір алгоритмде бірнеше рет қолдану керек болса, қай алгоритмге жатады? Қосалқы Алгоритм геометриялық фигуралармен құрылса қалай аталады? Блок схема Алгоритмнің анықтық қасиетін қанағаттандыратын нұсқау: Бір өлшемді массивтің екі элементінің қосындысы Алгоритмдер жазбасының негізгі әдістері: сөздік-формулалы алгоритмдік графикалық Базалық алгоритмдік құрылымдардың түрлері: циклдық сызықты тармақталған Алгоритмдердің міндетті қасиеттері:дискреттілік анықталғандық аяқталғандық жүктеу/скачать 81,93 Kb. Достарыңызбен бөлісу:
|