#1. Блочний символ використовується в блок-схемі для позначення перевірки умов. - 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
#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
#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. Якщо кодування розв’язує тільки задачу узгодження алфавіту джерела повідомлення з алфавітом каналу, то код називається + Примітивним - Економним (статистичним) - Не має вірної відповіді - Корегуючим
