ПТАА
Нормальный алгоритм визначений схемою:
b->b
α!-> λ
Яким буде результат застосування цього алгритму до слова abbbb
За схемою примітивної рекурсії вирахувати значення функції для таких значень її аргументів х=2, у=3.
Ф(x0) = 1, Ж(x,y,z) = y+z
Виберіть визначення дескриптивної ТА
Властивість, яка визначає, що кожен крок алгоритму повинен бути точно і однозначно визначений на формальній мові виконавця та забезпечує однаковість результату, одержуваного при багаторазовому виконанні алгоритму, на одному і тому ж наборі вхідних даних
Що означає, що машина Поста працюс за дискретним принципом?
Виберіть коректний запис команди машини Поста?
Виберіть коректне продовження речення «Машина Тьюрінга НЕ має
Виберть властивсть НЕ характерну універсальніймашині Тьюрінга
Область застосовності НАМ це
Формальна модель алгоритма, яка базується на перетворенні слів у довільному алфавіті шляхом заміни однієї частини слова на іншу
Спосіб композиції нормальних алгоритмів А і В буде суперпозицією, якщо
Множину 1 називають алгоритмічно розв'язною відносно множини U, якщо
Яка з названих формальних моделей алгоритму НЕ базується на математичній моделі детермінованого автомату?
Вкажіть функції, що НЕ с базовими в формальній моделі алгоритму як частково- рекурсивної функції
Виберіть правильне визначення загально-рекурсивної функції
Який з виразів визначає симетричність асимптотичних оцінок
Оцінку алгоритму з точки зору енергоспоживання дас
До задач вичерпного перебору відносяться
Алгоритм пошуку пари найближчих точок, що базується на принципі поділу множини точок на підмножини, пошуку в них найближчих пар точок з послідуючим опрацюванням та аналізом отриманих часткових рішень, відноситься до стратегії
Для жадібного алгоритму істинно
До якої стратегії/ методу відноситься мурашиний алгоритм
Прийом, який визначає особин для подальшого розвитку популяції
Який із виразів відображає вірно співвідношення множин примітивно- рекурсивних, загально-рекурсивних та частково-рекурсивних функцій. Знак ( означає "входить до
Якщо мураха знаходиться перед розгалудженням маршруту в «мурашиному» алгоритмі, запропонованому Марко Дориго, він вибирає шлях
Вкажіть що з названого є конструктивним об'єктомВкажіть що з названого є конструктивним об'єктом
Який базовий оператор полягає у підстановці одних арифметичних функцій замість аргументів інших функцій
До якої із стратегій можна віднести задачу прокладання маршруту робота?
Прийом оцінювання "успішності" даної особини (хромосоми-рішення), тобто, близькість її до шуканого рішення
Задана оцінка 0 (f 1)= O(n log n). Чому дорівнює 0(0(f1 )) = ?
Принцип нормалізації - це
Стратегія, в рамках якої розв'язання задачі передбачає виконання повної або часткової обробки вхідних даних зі збереженням додаткової інформації для прискорення подальшого розв'язку поставленої задачі
Вкажіть правильне визначення властивості детермінованості алгоритму:
Виберіть твердження істинні для Універсальної машини Тьюрінга
Яка з підстановок стовідсовково гарантує закінчення виконання алгоритму
Властивість, яка визначає, що об'єкти, над якими працює алгоритм, повинні бути такими, що кожен такий об'єкт може бути набраний весь цілком і представлений для розгляду
Які твердження є істиними для алгоритму машини Поста?
Процес роботи нормального алгоритму завершується, якщо
Яка з названих формальних моделей алгоритму базується на уявленні про алгоритм як деякий детермінований пристрій, що здатний виконувати в кожний окремий момент лише чітко фіксовані елементарні операції.
Вкажіть визначення метричної теорії алгоритмів
Основна задача ТА
Машина Тьюринга є
До якої з формальних моделей алгоритму стосується теза Черча?
Яка з названих причин НЕ є причиною, що сприяла виникненню ТА
Загально-рекурсивна функція це функція, яка утворена з базових функцій за допомогою скінченного числа застосувань
Властивість у відповідності з якою алгоритм представляється як скінченна послідовність інструкцій виконавцю (кроків). Кожна інструкцій виконується тільки після того, як закінчилося виконання попередньої
Скінченна множина внутрішніх станів машини Тьюринга - це
Алгоритм машини Поста вважається НЕзастосовним за умови виникнення ситуації:
Область застосовності нормального алгоритму Маркова щодо деякого алфавіту це
Машина Тьюрінга має
Машина Тьюрінга має
Чому функції створені з використанням оператора мінімізації називаюит частково-рекурсивними
Властивість, яка визначає, що алгоритм вирішення задачі повинен бути застосовний для деякого класу задач, що розрізняються лише значеннями вхідних даних
Властивість алгоритму, що при точному виконанні всіх розпоряджень процес повинен припинитися за скінченну кроків з певною відповіддю на поставлене завдання
Зовнішнім алфавітом машини Тьюринга називається:
Зупинка виконання програми в машині Поста відбувається за командою:
Властивість що визначає, що кожен крок алгоритму повинен бути точно і однозначно визначений на формальній мові виконавця та забезпечує однаковість результату, одержуваного при багаторазовому виконанні алгоритму, на одному і тому ж наборі вхідних даних
Вважають, що якщо зафіксовано набір вхідних елементів та правил побудови об’єктів з них, то визначено:
Яка з дій НЕ входить до переліку неприпустимих команд машини Поста:
Прийом, який визначає особин для подальшого розвитку популяції:
Для того, щоб ствержувати що нормальні алгоритми Н1 і Н2 еквівалентні щодо алфавіту А, достатньо щоб:
Яка з базових функцій забезпечує знаходження наступного натуральнозначного значення:
Коли говоримо, що функція F – кількість операцій виконуваних алгоритмом, обмежена зверху функцією c1*g а знизу функцією c2*g (c1, c2 і n0 – позитивні константи такі, що c2*g <= f <= c1g то мова йде про оцінку:
Як працює НАМ? На 1му кроці знаходиться перше входження лівої частини 1шої підставновки до слова Р, відбувається заміна, а далі:
Функція, яка може бути отримана з найпростіших базових функцій за допомогою скінченного числа застосувань операторів суперпозиції, примітивної рекурсії та мінімізації, називається:
Ефективність алгоритму в ТА. Якою вона не буває?
Область застосовності НАМ
Створюйте онлайн-тести
для контролю знань і залучення учнів
до активної роботи у класі та вдома
