Тести --ТА

Варіант № 4

# Блочний символ використовується в блок-схемі для позначення перевірки умов.

- 1

- 2

- 3

- 4

#2. Як зміниться слово ваваа, якщо до нього застосувати наступний НАМ

- вава

- вваа

- вв

- ававаа

#3. Властивість алгоритму, що забезпечує при точному виконаннійого команд припинення процесу за кінцеве число кроків з видачею результатів називається властивістю ...

- Дискретності

- Детермінованості

- Зрозумілості

- Результативності

#4. Позначте всі елементарні (базові) функції для побудові класу частково-рекурсивних функцій:

- нуль-функція: O(x)=0;

- функція наступності: S(x)=x+1;

- функція проекції: (x1,x2,...,xn)=xm, 1?m?n.

- функція – константа Cqn(x1,x2,...,xn)=q, nIN, qI N

#5. Виберіть істинне висловлювання:

- клас примітивно-рекурсивних функцій ширше класу частиково-рекурсивних функцій

- клас частково-рекурсивних функцій включає клас примітивно-рекурсивних функцій

- клас частково-рекурсивних функцій співпадає з класом примітивно-рекурсивних функцій

- перетин класу частково-рекурсивних функцій і клас примітивно-рекурсивних функцій пусто

#6. Суперпозиція S2(0,S2(S,0)) дорівнює …

- 0

- 1

- x+1

- x

#7. Функція задана співвідношеннями

f(x,0)=0;

f(x,y+1)=f(x,y)+x.

Обчисліть f(5,2).

- 5

- 7

- 25

- 10

#8. Оператор примітивної рекурсії позначається як …

- 1

- 2

- S(x)

- M(z)

#9. Внутрішнім для машини Тьюринга є алфавіт

- A={a0,a1,...,an}

- Q={q0,q1,...,qn}

- {>, !, <}

- {?, ?, …}

#10. За початковий стан машини Тьюринга відповідає символ внутрішнього алфавіту ...

- qn

- R

- q0

- q1

#11. Зовнішним алфавітом машини Тьюринга є …

- A={ a0,a1,...,an}

- Q={q0,q1,...,qn}

- {R,L,S}

- {?, ?, …}

#12. Стрічка машини Тьюринга ...

- Обмежена зліва

- Обмежена справа

- Обмежена з обох сторін

- Не обмежена ні з одного боку

#13. Дана функціональна схема. На стрічці машини Тьюринга спочатку записано слово 10100. Каретка машини знаходиться в конфігурації стандартного початку (перший символ слова). Вкажіть, що буде записано на стрічці після виконання даної функціональної схеми.

q0 q1 q2

0 0 > q0 1< q1 0 < q2

1 1 > q0 0 < q2 1 < q2

< q1 _ ! q0

- 10101

- 10110

- 10011

- 11001

#14. Скільки елементарних дій може виконувати машина Тьюринга

- 1

- 2

- 3

- 4

#15. Дано масив чисел А= . Виконується сортування масиву методом вставки. Стан масиву після першого проходження …

- 5, 10, 18, 12, 4, 25

- 4, 5, 10, 18, 12, 25

- 4, 10, 5, 18, 12, 25

- 4, 5, 10, 12, 18, 25

#16. Часова ефективність алгоритму сортування вставкою …

- О(n log n)

- О(n)

- О(n2)

- О(log n)

#17. Часова ефективність алгоритму послідовний пошук …

- О(n log n)

- О(n)

- О(n2)

- О(log n)

#18. Кількісна характеристика, яка визначає об’єм пам’яті, необхідний для розміщення алгоритму

- часова складність

- ємкісна складність

#19. Множина всіх функцій, порядок росту яких при достатньо великих п дорівнює деякій константі, помноженій на значення функції g(n) позначається через

- ? (g(n))

- О(g(n))

- (g(n))

- (g(n))

#20. Функція t(n) має менший порядок росту ніж функція g(n), якщо дорівнює

- 0

- С

- 3

- Не має вірної відповіді

#21. Наступною перестановкою в лексикографічному порядку за 362541 буде…

- 364125

- 363541

- 362542

- 364521

#22. Наступним сполученням у лексикографічному порядку за 1256 буде…

- 1257

- 1345

- 1354

- 1265

#23. Скільки трьохзначних чисел можна скласти з цифр 1, 2, 3, якщо кожна входить тільки один раз?

- 6

- 3

- 5

- 10

#24. Складність алгоритму побудови лексикографічно наступного сполучення становить

- O(log n)

- O(n)

- О(n!)

- O(n log n)

#25. При знаходженні найкоротшого шляху у графі за алгоритмом Дейкстри.

На наступному кроці мітка вершини b дорівнює …

- 2

- 3

- 4

- 6

#26. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#27. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#28. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#29. Код має властивість префіксу чи ні?

- так

- ні

#30. Якщо кодування розв’язує тільки задачу узгодження алфавіту джерела повідомлення з алфавітом каналу, то код називається

- Примітивним

- Економним (статистичним)

- Не має вірної відповіді

- Корегуючим

Вариант 3

#1. Блочний символ використовується в блок-схемі для позначення початку або кінця алгоритму.

- 1

- 2

- 3

- 4

#2. Термін «алгоритм» походить від ...

- імені середньовічного узбецького математика Мухаммад ібн Муса аль-Хорезмі +

- описаної Евклідом послідовності дій для знаходження найбільшого загального дільника двох чисел

- понятті «нормальний алгорифм», введеного А.А. Марковим

- першої мови програмування

#3. Задан НАМ з алфавітом .

Результатом застосування даного НАМ до слова abbcb буде слово …

- bbcb

- aa

- a

- cb

#4. Функція f називається частково-рекурсивною відносно множини найпростіших функцій з базового набору, якщо вона будується

- з найпростіших обчислюваних функцій кінцевим числом застосування операторів суперпозиції, примітивної рекурсії і мінімізації

- з найпростіших обчислюваних функцій кінцевим числом застосування оператора суперпозиції

- з найпростіших обчислюваних функцій кінцевим числом застосування операторів суперпозиції і примітивної рекурсії

- з нуль-функції і функції наступності кінцевим числом застосування операторів суперпозиції і примітивної рекурсії і мінімізації

#5. Функція f називається примітивно-рекурсивною відносно множини найпростіших функцій з базового набору, якщо вона будується

- з найпростіших обчислюваних функцій кінцевим числом застосування операторів суперпозиції, примітивної рекурсії і мінімізації

- з найпростіших обчислюваних функцій кінцевим числом застосування операторів примітивної рекурсії

- з найпростіших обчислюваних функцій кінцевим числом застосування операторів суперпозиції и примітивної рекурсії

- з нуль-функції і функції наступності кінцевим числом застосування операторів суперпозиції и примітивної рекурсії і мінімізації

#6. Оператор наступності позначається як …

- 1

- 2

- S(x)

- 4

#7. Функція є примітивно рекурсивної, якщо вона виходить з набору вихідних функцій за допомогою оператора: 1) рекурсії; 2) обмеженою мінімізації; 3) підстановки - з перерахованого

- 1 і 3

- 1

- 1, 2 і 3

- 3

#8. Функція задана співвідношеннями

f(x,0)=0;

f(x,y+1)=f(x,y)+x.

Обчисліть f(5,2).

- 5

- 7

- 25

- 10

#9. Алфавітом переміщення керуючого пристрою для машини Тьюринга є алфавіт

- A={ a0,a1,...,an}

- Q={q0,q1,...,qn}

- {>, !, <}

- {?, ?, …}

#10. Сукупність команд машини Тьюринга

q01 > q01R

q10 > qz1E

q00 > q11R

q11 > q11L

и початкова конфігурація К = 1101q001, чому дорівнює заключна конфігурація

- 110111

- 111011

- 101111

- 111111

#11. Внутрішній стан машини Тьюрінга позначається

- 1

- 2

- 3

- П, Л, H

#12. Формальне визначення алгоритму необхідно при ...

- Обчисленні числових функцій і обчисленні предикатів

- Доказі можливості його побудови

- Доказі нерозв'язності задач

- Визначенні ефективності конкретного алгоритму

#13. Дана функціональна схема. На стрічці машини Тьюринга спочатку записано слово 1011. Каретка машини знаходиться в конфігурації стандартного початку (перший символ слова). Вкажіть першу дію, що виконає каретка машину Тьюринга.

q0 q1 q2

0 > q0 1< q2 0 < q2

1 > q0 0 < q1 1 < q2

< q1 1 ! q0 _ > q0

- Каретка переміщується вправо на нуль, залишається в стані q0, замінив 1 на 0

- Каретка переміщується вліво, змінить стан на q1 і замінить 1 на 0

- Каретка переміщується вправо на нуль, залишиться в стані q0, нічого не змінюючи

- Каретка переміщується вліво, змінить стан на q1 і зітре 1

#14. У моделі машини Тьюринга немає елементарної команди ...

- B (Назад)

- R (Вправо)

- L (Вліво)

- S (На місці)

#15. Дано масив чисел А= . Виконується сортування масиву методом бульбашки. Стан масиву після першого проходження …

- 5, 10, 18, 12, 4

- 4, 5, 10, 18, 12

- 4, 10, 5, 18, 12

- 5, 10, 12, 18, 4

#16. Часова ефективність алгоритму послідовний пошук …

- О(n log n)

- О(n)

- О(n2)

- О(log n)

#17. Часова ефективність алгоритму бінарний пошук…

- О(n log n)

- О(n)

- О(n2)

- О(log n)

#18. Кількісна характеристика, яка визначає час, що необхідний для виконання алгоритму

- часова складність

- ємкісна складність

#19. Множина всіх функцій, порядок росту яких при достатньо великих п не перевищує деяку константу, помножену на значення функції g(n) позначається через

- ? (g(n))

- О(g(n))

- (g(n))

- (g(n))

#20. Функція t(n) має більший порядок росту ніж функція g(n), якщо дорівнює

- 0

- С

- 3

- Не має вірної відповіді

#21. Наступною перестановкою в лексикографічному порядку за 362541 буде…

- 364125

- 363541

- 362542

- 364521

#22. Наступним сполученням у лексикографічному порядку за 1256 буде…

- 1257

- 1345

- 1354

- 1265

#23. Скільки парних сполучень можна скласти з цифр 1,3,5?

- 6

- 3

- 5

- 10

#24. Складність алгоритму побудови лексикографічно наступного сполучення становить

- O(log n)

- O(n)

- О(n!)

- O(n log n)

#25. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#26. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#27. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#28. Код має властивість префіксу чи ні?

- так

- ні

#29. Схему :

називають префіксною, якщо для будь-яких i та j (i, j=1,…,r, ) елементарний код

- є префіксом елементарного коду

- є постфіксом елементарного коду

- не є префіксом елементарного коду

- не є префіксом елементарного коду

#30. Якщо кодування розв’язує тільки задачу виявлення або виправлення помилок, що виникають в каналі зв’язку через перешкоди та спотворення сигналу, то код називається

- Примітивним

- Економним (статистичним)

- Корегуючим

- Не має вірної відповіді

Варіант 2

#1. Розбиття виконання алгорітма на послідовність закінчених дій називається властивістю ...

- дискретності

- детермінованості

- визначеності

- результативності

#2. Яку дію виконую команда НАМ

- видаляє всі * зі слова

- видаляє перше входження * у слові

- дописує * в кінець слова

- дописує * на початку слова

#3. Властивість алгоритму бути придатним для вирішення будь-якої задачі з деякого класу властивістю називається ...

- Визначеності

- Масовості

- Результативності

- детермінованості

#4. Виберіть істинне висловлювання:

- клас примітивно-рекурсивних функцій ширше класу частиково-рекурсивних функцій

- клас частково-рекурсивних функцій включає клас примітивно-рекурсивних функцій

- клас частково-рекурсивних функцій співпадає з класом примітивно-рекурсивних функцій

- перетин класу частково-рекурсивних функцій і клас примітивно-рекурсивних функцій пусто

#5. Функція f називається частково-рекурсивною відносно множини найпростіших функцій з базового набору, якщо вона будується

- з найпростіших обчислюваних функцій кінцевим числом застосування операторів суперпозиції, примітивної рекурсії і мінімізації

- з найпростіших обчислюваних функцій кінцевим числом застосування оператора суперпозиції

- з найпростіших обчислюваних функцій кінцевим числом застосування операторів суперпозиції і примітивної рекурсії

- з нуль-функції і функції наступності кінцевим числом застосування операторів суперпозиції і примітивної рекурсії і мінімізації

#6. Функція є примітивно рекурсивної, якщо вона виходить з набору вихідних функцій за допомогою оператора: 1) рекурсії; 2) обмеженою мінімізації; 3) підстановки - з перерахованого

- 1 і 3

- 1

- 1, 2 і 3

- Не має вірної відповіді

#7. Суперпозиція S2(S,S2(S,x)) дорівнює …

- x+1

- 2

- x+2

- 1

#8. Оператор суперпозиції позначається як …

- 1

- 2

- S(x)

- 3

#9. Внутрішнім для машини Тьюринга є алфавіт

- A={a0,a1,...,an}

- Q={q0,q1,...,qn}

- {>, !, <}

- {?, ?, …}

#10. В моделі машини Тьюринга немає елементарної команди …

- * (Назад)

- > (Праворуч)

- < (Ліворуч)

- ! (Зупинка)

#11. Символи, які машина Тьюринга читає і пише на стрічці, утворюють

- команди

- конфігурацію

- алфавіт

- вираження

#12. Внутрішнім алфавітом машини Тьюринга називається

- безліч конфігурацій машини

- безліччю станів машини

- безліч команд машини

- символи, записані на стрічці

#13. Керуюча головка Машини Тюрінга в кожен момент часу "вміє" ...

- Оглядати, зчитувати і записувати символ в одній клітинцістрічки

- Оглядати, зчитувати і записувати символи в кількох осередкахстрічки, що йдуть підряд

- Оглядати і записувати символ в одній клітинці стрічки

- Оглядати і зчитувати символ в одній клітинці стрічки

#14. Дана функціональна схема. На стрічці машини Тьюринга спочатку записано слово 10100. Каретка машини знаходиться в конфігурації стандартного початку (перший символ слова). Вкажіть, що буде записано на стрічці після виконання даної функціональної схеми.

q0 q1 q2

0 0 > q0 1< q1 0 < q2

1 1 > q0 0 < q2 1 < q2

< q1 _ ! q2

- 10101

- 10110

- 10011

- 11001

#15. Дано масив чисел А= . Виконується сортування масиву методом вставки. Стан масиву після першого проходження …

- 5, 10, 18, 12, 4, 25

- 4, 5, 10, 18, 12, 25

- 4, 10, 5, 18, 12, 25

- 4, 5, 10, 12, 18, 25

#16. Часова ефективність алгоритму швидке сортування …

- О(n log n)

- О(n)

- О(n2)

- О(log n)

#17. Часова ефективність алгоритму послідовний пошук …

- О(n log n)

- О(n)

- О(n2)

- О(log n)

#18. Кількісна характеристика, яка визначає об’єм пам’яті, необхідний для розміщення алгоритму

- часова складність

- ємкісна складність

#19. Множина всіх функцій, порядок росту яких при достатньо великих п не менше деякій константі, помноженій на значення функції g(n) позначається через

- ? (g(n))

- О(g(n))

- (g(n))

- (g(n))

#20. Функція t(n) має менший порядок росту ніж функція g(n), якщо дорівнює

- 0

- С

- 3

- Не має вірної відповіді

#21. Наступною перестановкою в лексикографічному порядку за 362541 буде…

- 364125

- 363541

- 362542

- 364521

#22. Наступним сполученням у лексикографічному порядку за 1256 буде…

- 1257

- 1345

- 1354

- 1265

#23. Скільки розміщень можна скласти з трьох елементів 1,3,5 по два ?

- 6

- 3

- 5

- 10

#24. Складність алгоритму побудови лексикографічно наступної перестановки за перестановкою a1a2…an становить

- O(log n)

- O(n)

- O(n log n)

- О(n!)

#25. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#26. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#27. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#28. Код має властивість префіксу чи ні?

- так

- ні

#29. Якщо слово має вигляд , то називають

- Постфіксом або закінченням

- Префіксом або початком

#30. Якщо кодування розв’язує тільки задачу «стиснення» інформації (зменшення або повне усунення надлишковості, що містить повідомлення), то код називається

- Примітивним

- Економним (статистичним)

- Корегуючим

- Не має вірної відповіді

Вариант 1

#1. Нехай дано слово P в алфавіті та задана нормальна схема

Результатом застосування даного нормального алгорифму до слову abаbcb є слово ...

- bbcb

- ссa

- a

- cb

#2. Марківський алгоритм - алгоритм

- стохастичний

- нормальний

- недетермінованих

- нелінійний

#3. Блочний символ використовується в блок-схемі для позначення введення і виведення даних.

- 1

- 2

- 3

- 4

#4. Формальне визначення алгоритму необхідно при …

- обчисленні числових функцій та обчисленні предикатів

- доказі можливості його побудові

- доказі нерозв’язуваності задач

- визначені ефективності конкретного алгоритму

#5. Позначте всі елементарні (базові) функції для побудові класу частково-рекурсивних функцій:

- нуль-функція: O(x)=0;

- функція наступності: S(x)=x+1;

- функція проекції: (x1,x2,...,xn)=xm, 1?m?n.

- функція – константа Cqn(x1,x2,...,xn)=q, nIN, qI N

#6. Функція є примітивно рекурсивної, якщо вона виходить з набору вихідних функцій за допомогою оператора: 1) рекурсії; 2) обмеженою мінімізації; 3) підстановки - з перерахованого

- 1 і 3

- 1

- 1, 2 і 3

- 3

#7. Суперпозиція S2(S,0) дорівнює …

- 1

- 0

- x

- x+1

#8. Оператор примітивної рекурсії позначається як …

- 1

- 2

- S(x)

- M(z)

#9. Зовнішнім алфавітом машини Тьюринга є…

- A={a0,a1,...,an}

- Q={q0,q1,...,qn}

- {>, !, <}

- {?, ?, …}

#10. Мінімальним елементом пам’яті машини Тьюринга є

- Каретка

- Ячейка

- внутрішній алфавіт

- Не має вірної відповіді

#11. В ячейці стрічки машини Тьюринга може зберігатися ...

- тільки одна буква зовнішнього алфавіту

- тільки одна буква внутріщнього алфавіту

- довільна кількість букв зовнішнього алфавіту

- довільна кількість букв внутрішнього алфавіту

#12. Керуючій пристрій машини Тьюринга в кожній момент часу "вміє" ...

- оглядати, считувати і записувати символ в одній ячейці стрічки

- оглядати, считувати і записувати символи в декількох ячейках стрічки, що йдуть поряд

- оглядати і записувати символ в одній ячейці стрічці

- оглядати і считувати символ в одній ячейці стрічці

#13. Внутрішнім для машини Тьюринга є алфавіт

- A={a0,a1,...,an}

- Q={q0,q1,...,qn}

- {R,L,S}

- {?, ?, …}

#14. Дано масив чисел А= . Виконується сортування масиву методом вибора. Стан масиву після першого проходження …

- 5, 10, 18, 12, 4, 25

- 4, 5, 10, 18, 12, 25

- 4, 5, 18, 12, 10, 25

- 4, 5, 10, 12, 18, 25

#15. Часова ефективність алгоритму сортування вибором …

- О(n log n)

- О(n)

- О(n2)

- О(log n)

#16. Часова ефективність алгоритму сортування вставкою …

- О(n log n)

- О(n)

- О(n2)

- О(log n)

#17. Кількісна характеристика, яка визначає час, що необхідний для виконання алгоритму

- часова складність

- ємкісна складність

#18. Множина всіх функцій, порядок росту яких при достатньо великих п не перевищує деяку константу, помножену на значення функції g(n) позначається через

- ? (g(n))

- О(g(n))

- (g(n))

- (g(n))

#19. Функція t(n) має той самий порядок росту, що і функція g(n), якщо дорівнює

- 0

- С

- 3

- Не має вірної відповіді

#20. Наступною перестановкою в лексикографічному порядку за 362541 буде…

- 364125

- 363541

- 362542

- 364521

#21. Наступним сполученням у лексикографічному порядку за 1256 буде…

- 1257

- 1345

- 1354

- 1265

#22. Скільки парних сполучень можна скласти з цифр 1,3,5?

- 6

- 3

- 5

- 10

#23. Перестановку b1b2…bn називають лексикографічно наступною за a1a2…an, якщо не існує такої перестановки с1с2…сn, що

- a1a2…an=с1с2…сn та с1с2…сn< b1b2…bn

- a1a2…an<с1с2…сn та с1с2…сn< b1b2…bn

- a1a2…an>с1с2…сn та с1с2…сn> b1b2…bn

- a1a2…an<с1с2…сn та с1с2…сn= b1b2…bn

#24. При знаходженні найкоротшого шляху у графі за алгоритмом Дейкстри.

На наступному кроці мітка вершини b дорівнює …

- 2

- 3

- 4

- 6

#25. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#26. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#27. Вказати вірне чи ні асимптотичне позначення

- так

- ні

#28. Код має властивість префіксу чи ні?

- так

- ні

#29. Якщо слово має вигляд , то називають

- Постфіксом або закінченням

- Префіксом або початком

#30. Алфавітне кодування, що задане таблицею

А1 А2

В1 В1В2

взаємно однозначне чи ні?

- так

- ні