WorksheetsАлгоритм 3
Total questions: 30
Worksheet time: 15mins
Тікелей таңдау көмегімен сорттау:
Бастапқы кілттер (k=1):
a[1]=44; a[2]=55; a[3]=12; a[4]=42; a[5]=94; a[6]=18; a[7]=06; a[8] =67
Мұндағы a[1]-ді L қадамында табу керек:
L=2 a[1]=55.
L=2 a[2]=06.
L=3 a[1]=12.
L=4 a[1]=42.
L=2 a[1]=94.
A[1], a[2] элементтерін L қадамында тікелей таңдау сорттауымен табу керек:
Бастапқы кілттер (k=1):
a[1]=44; a[2]=55; a[3]=12; a[4]=42; a[5]=94; a[6]=18; a[7]=06; a[8] =67.
L=1 a[1]=44 a[2]=55.
L=1 a[1]=55 a[2]=44.
L=2 a[1]=44 a[2]=12.
L=3 a[1]=06 a[2]=44.
L=2 a[1]=06 a[2]=12.
Тікелей қосумен сорттау:
Бастапқы кілт (k=1): a[1]=44; a[2]=55; a[3]=12; a[4]=42; a[5]=94; a[6]=18; a[7]=06; a[8] =67
Мұндағы элементін a[1] L қадамнында табу керек:
L=2 a[1]=55.
L=2 a[1]=44.
L=3 a[1]=44.
L=4 a[1]=42.
L=2 a[1]=18.
Көпіршікті сорттау: (k=1) бастапқы кілттер:
a[1]=44; a[2]=55; a[3]=12; a[4]=42; a[5]=94; a[6]=18; a[7]=06; a[8] =67
a[1]-ді L қадамында табу керек:
L=3 a[1]=42.
L=2 a[1]=12.
L=1 a[1]=44.
L=2 a[1]=55.
L=3 a[1]=67.
Тікелей қосу көмегімен сорттау:
(k=1) бастапқы кілттер. a[1]=44; a[2]=55; a[3]=12; a[4]=42; a[5]=94; a[6]=18; a[7]=06; a[8] =67
a[2]-ді L қадамында табу керек
L=4 a[1]=42.
L=3 a[1]=12.
L=2 a[1]=12.
L=2 a[2]=55.
L=2 a[1]=18.
Сорттаудың сыртқы әдісін көрсетіңіз:
Тікелей бөлу, таңдаумен сорттау.
Бөлумен сорттау.
Ағаш көмегімен сорттау (Heapsort).
Таңдаумен сорттау.
Тікелей бөлу.
7 элементтен тұратын A массиві берілген: {10, 5, 13,10, 7,10, 9}.
k-ны табу керек:
k=0
for i in range(n):
if a[i]=x:
k=1
Мұндағы x= 0, k=-1.
Мұндағы x= 0, k=7.
Мұндағы x= 10, k=1.
Мұндағы x= 10, k=4.
Мұндағы x= 10, k=6.
i-ді табу керек. 7 элементтен тұратын массив берілген: {10, 5, 13,10, 7,10, 7}.
i=1;
while i<=n and a[i]<>x:
inc(i)
Мұндағы x= 7, i=7.
Мұндағы x= 10, i=4.
Мұндағы x= 10, i=6.
Мұндағы x= 10, i=1.
Мұндағы x= 7, i=0.
Негізгі алгоритмдік құрылымдар.
Программа денесіндегі шақыру.
Іздеу.
Тарату.
Функцияны шақыру.
Салыстыру нәтижесінен іздеу массивтің сол немес оң жақ жартысынан Х эталонымен салыстыру массивтің ортасында орналасқан және нәтижесінен салыстыруды іздеу:
L=0
R=N
while L<R:
m=(L+R)%2
if a[m]<X:
L=m+l
else R=m
Екілік сорттау.
Сызықтық іздеу.
Фиктивті элементпен іздеу.
Кедергі элементті іздеу.
Процедура қарапайым тізбектей барлық элементтерді көрсетумен аяқаталады және элементтерді салыстыру Х-пен орындалады:
for j in range(N):
if a[j]=X:
k=j
Сызықтық іздеу.
for j in range(N):
if a[j]=X:
j+=1
Кедергімен сызықтық іздеу.
i=0
while i<=N and a[i]<>X:
i+=1
Кедергімен іздеу:
i=0
while a[i]<>X:
inc(i)
for j in range(N):
if a[j]=X:
inc(j)
A[N+l]=X
i=0
while a[i]<>X:
i=i+l
for j in range(N):
if a[j]=X:
k=j
i=0
while i<=N and a[i]<>X:
inc(i)
Жолдағы іздеу алгоритмі:
Кою алгоритмі.
Кнут, Морис және Пратт алгоритмі.
Көпіршікті алгоритмі.
Шелл алгоритмі.
Евклид алгоритмі.
Модульді қолдану:
Кемшілігі: программаны орындаудың күрделілігі.
Кемшілігі: жобалау күрделілігі және әрі қарай программаның қызмет етуі.
Кемшілігі: жиі қолданылатын модульдерге дайын кітапханаларды қолдануға мүмкіндіктің болмауы.
Артықшылығы: өткізу операторы программаның кез келген жерінен басқарылады (goto).
Артықшылығы: дайын кітапханаларды жиі қолданылатын модульдерге қолдана алу мүмкіндігі.
Құрылымдық программалаудың артықшылығы:
Уақыт көбейеді, бірақ программалық өнімнің құны азаяды.
Программаның сенімділігі азаяды.
Уақыт азаяды, бірақ программалық өнімнің құны артады.
Программаның сенімділігін арттыру.
Өткізу операторы программаның кез келген жеріне қолданыла алады (goto).
Құрылымдық программалау технологиясының қағидалары:
Программа денесінде тек қана негізгі құрылым – қайталау (for, while, repeat) ғана қолданылады.
Программа денесінде тек қана негізгі құрылым – тармақталу (if, case) операторы қолданылады.
Программа денесінде тек негізгі құрылым – тізбектей орындалу ғана қолданылады.
Программалау төменнен жоғарыдан төмен қарай жүргізіледі.
Өткізу операторы программаның кез келген жерінде қолданыла алады (goto).
Жалпы ортақ әдістің жоқтығынан шешілмейтін есептер:
Пи санына жазудағы тоғызды тарату.
Соңғы белгіленген жәшіктегі Пост машинасы.
«Тоқтау» мәселесі.
Алгоритмнің эквиваленттілігі мәселесі.
Өзгерту мәселесі.
Жалпы әдістің жоқтығынан болатын тапсырмаларды логикалық соңнын болмағандығынан шеше алмау есептері:
«Тоқтау» мәселесі.
Пи санына жазудағы тоғызды тарату.
Санды есептеу.
Гильберттің оныншы мәселесі.
Соңғы белгіленген жәшіктегі Пост машинасы.
Жалпы әдістің жоқтығанан болатын тапрсырмаларды алгоритмдік шеше алмау:
«Тоқтау» мәселесі.
Пи санына жазудағы тоғызды тарату.
Соңғы белгіленген жәшіктегі Пост машинасы.
Өзгерту мәселесі.
Алгоритмнің эквиваленттілігі мәселесі.
Орындау көлеміне қарай алгоритмнің жіктелуі:
Тиімді алгоритмдер.
Алгоритмнің күрделілігіне қарай сандық-тәуелді емес.
Алгоритмнің күрделілігіне қарай сандық-тәуелдік.
Алгоритмнің күрделілігіне қарай параметрлік-тәуелді емес.
Күрделі алгоритмдер.
Қосу операциясы (бүтін сандық арифметика) …:
Char.
String.
Real и ShortInt.
Real.
Byte.
"Ақ жәшіктің " стратегиялық әдісі:
Алтын қиам әдісі.
Шарттың орындалу әдісі.
Қызмет етуші диаграмма әдісі.
Операторларды жабу әдісі.
Қателіктер және орындап көру әдісі.
"Қара жәшіктің" стратегиялық әдісі:
Оператор және шешімдердің жабылуы.
Шарттың жабылуы.
Шешімдердің жабылуы.
Операторлардың жабылуы.
Шарттың әдісі.
Шығу кезіндегі қателіктер:
Құрылымдық қателіктер.
Қателіктің түрлері.
Синтаксистік.
Семантикалық.
Прагматикалық.
Логикаға кері әсерте ететін программалық қателіктердің жіктелуі:
Орындалу кезіндегі қателік.
Компиляция қателігі.
Синтаксистік.
Құрылымдық қателіктер.
Семантикалық.
Синтаксистік қателік:
Жақшалардың келісілмегені.
Семантикалық.
Нөлге бөлу.
Аталған типтегі қателіккомпилятормен табылмайды.
Жады көлемінен шығып кету.
Мәліметке сілтеме жасау қателігі:
Арифметикалық операцияны орындау кезінде туатын қателік.
Әртүрлі типті мәлімет.
Нөлге бөлу.
Программа мәліметке үсыныс жасаған кезде туатын қателік.
Жады көлемінен шығып кету.
Есептеу қателігі –:
Массивтің шегінен индекс шығып кеткенде болатын қателік.
Арифметикалық операцияны орындау кезінде туатын қателік.
Программа мәліметке үсыныс жасаған кезде туатын қателік.
Айнымалының сипатталмаған мәні.
Жады көлемінен шығып кету.
Бем-Якопини теоремасы:
Программаның логикалық құрылымы төрт базалық комбинациядан тұруы мүмкін.
Программаныңлогикалық құрылымы шарт алдындағы және шарттан кейінгі қайталау операторынан тұрады.
Программаның логикалық құрылымы үш базалық құрылым комбинациясын тұрады.
Программаның логикалық құрылымы базалық іздеу, тармақталу, қайталау операторынан тұрмайды.
Программаның логикалық құрылымы шарттан тұрады.
Алгоритмдік аяқталмағандыққа алып келетін себептер:
Есепті шешудің жалпы әдісінің болмауы.
Артық ақпарат.
Компиляцияның қателігі.
Әдістің қателігі.
Әдістің дұрыс қолданылмағандығы.
