#1. Нехай дано слово P в алфавіті та задана нормальна схема Результатом застосування даного нормального алгорифму до слову abаbcb є слово ... - bbcb + ссa - a - cb
#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)
#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
#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 взаємно однозначне чи ні? - так + ні
