#1. Розбиття виконання алгорітма на послідовність закінчених дій називається властивістю ... + дискретності - детермінованості - визначеності - результативності
#2. Яку дію виконую команда НАМ - видаляє всі * зі слова - видаляє перше входження * у слові - дописує * в кінець слова + дописує * на початку слова
#3. Властивість алгоритму бути придатним для вирішення будь-якої задачі з деякого класу властивістю називається ... - Визначеності + Масовості - Результативності - детермінованості
#4. Виберіть істинне висловлювання: - клас примітивно-рекурсивних функцій ширше класу частиково-рекурсивних функцій + клас частково-рекурсивних функцій включає клас примітивно-рекурсивних функцій - клас частково-рекурсивних функцій співпадає з класом примітивно-рекурсивних функцій - перетин класу частково-рекурсивних функцій і клас примітивно-рекурсивних функцій пусто
#5. Функція f називається частково-рекурсивною відносно множини найпростіших функцій з базового набору, якщо вона будується + з найпростіших обчислюваних функцій кінцевим числом застосування операторів суперпозиції, примітивної рекурсії і мінімізації - з найпростіших обчислюваних функцій кінцевим числом застосування оператора суперпозиції - з найпростіших обчислюваних функцій кінцевим числом застосування операторів суперпозиції і примітивної рекурсії - з нуль-функції і функції наступності кінцевим числом застосування операторів суперпозиції і примітивної рекурсії і мінімізації
#6. Функція є примітивно рекурсивної, якщо вона виходить з набору вихідних функцій за допомогою оператора: 1) рекурсії; 2) обмеженою мінімізації; 3) підстановки - з перерахованого - 1 і 3 + 1 - 1, 2 і 3 - Не має вірної відповіді
#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
#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. Якщо кодування розв’язує тільки задачу «стиснення» інформації (зменшення або повне усунення надлишковості, що містить повідомлення), то код називається - Примітивним + Економним (статистичним) - Корегуючим - Не має вірної відповіді
