ТАіСД
У РАМ-програмі операнд =i означає:
У рівнодоступній адресній машині (РАМ) всі обчислення відбуваються у регістрі, що називається:
Інформація, що зберігається на стрічці машини Тьюрінга, закодована знаками
Класична машина Тьюрінга має
Клас складності P-TIME це клас задач, що
Проблема „зупинки” є
Якщо задача L1 поліноміально зводиться до задачі L2, то
Класи складності P та NP
Задача називається NP-важкою, якщо
Конкатенацією двох слів abc та xyz є слово
Об’єднанням алгоритмів A(P)=xP та B(P)=Py є алгоритм
Обчислити суперпозицію s3(l13,l13,l23)
Функцію, яку можна отримати з найпростіших функцій із застосуванням скінченої кількості операторів суперпозиції, примітивної рекурсії та слабкої мінімізації називають
Функцію ф , що задається співвідношенням називають
Структура даних типу „черга” працює за принципом
Складність алгоритму сортування включенням становить
Будь-який алгоритм сортування, заснований на порівнянні елементів в найгіршому випадку виконується за час
Алгоритм сортування, при якому елементи з однаковим ключем зберігають свій початковий порядок, називається
Алгоритм сортування підрахунком реалізований псевдокодом
Знайти медіану множини {57, 52, 30, 44, 80, 11, 56, 40, 28, 45, 66}. Ввести число Відповідь
Яка з послідовностей є неспадною пірамідою (min-heap) Виберіть одну відповідь:
У РАМ-програмі операнд *i означає:
Виберіть одну відповідь:
Клас складності NP-TIME це клас задач, що
Проблема з'ясування виконувальності булевої формули
Конкатенацією двох слів ab та xyc є слово
Суперпозицією алгоритмів A(P)=xP та B(P) =Py є алгоритм
Обчислити функцію вибору аргументів I44(3, 6, 2, 1) . Ввести число
Обчислити суперпозицію S3(l22, l13, l33) , де Imn(x1,x2...xn) – функція вибору аргументів
Функцію, яку можна отримати з найпростіших функцій із застосуванням скінченої кількості операторів суперпозиції, примітивної рекурсії та мінімізації називають
Структура даних типу „стек” працює за принципом
Рівняння складності деякого алгоритму f(n) =3n2+nlog n+n . Складність цього алгоритму за порядком величини O(f(n)) дорівнює
Якщо 0≤c1g(n)≤f(n)≤c2g(n); c1, c2, n0 - const; n≥n0, то:
Якщо lim f(n)/g(n)=∞, то:
Складність алгоритму сортування злиттям становить
Алгоритм сортування підрахунком реалізований псевдокодом
Знайти медіану множини {63, 64, 17, 29, 61, 29, 63, 95, 10, 33, 98}. Ввести число
Яка з послідовностей є незростаючою пірамідою (max-heap)
Конкатенацією двох слів xyz та abc є слово
Обчислити функцію вибору аргументів I34 (3,6,2,1). Ввести число
Рівняння складності деякого алгоритму f(n)=2n+3logn . Складність цього алгоритму за порядком величини O(f(n) дорівнює
Якщо 0≤f(n)≤cg(n); c, n0 - const; n≥n0 то
Якщо lim f(n)/g(n)=const≠0 , то
Алгоритм сортування підрахунком реалізований псевдокодом
Яка з послідовностей є незростаючою пірамідою (max-heap)
Задача "комівояжера"
Задача називається NP-повною, якщо
Обчислити суперпозицію S3(l22, l13, l23) , де Im2(x1,x2...xn) – функція вибору аргументів
Функцію, яку можна отримати з найпростіших функцій із застосуванням скінченої кількості операторів суперпозиції і примітивної рекурсії називають
Складність алгоритму швидкого сортування в найгіршому випадку становить
Алгоритм сортування підрахунком реалізований псевдокодом
Знайти медіану множини {50, 83, 79, 66, 96, 18, 11, 36, 35, 55, 73}. Ввести число
Яка з послідовностей є неспадною пірамідою (min-heap)
Рівняння складності деякого алгоритму f(n)=3n+4n2-3n . Складність цього алгоритму за порядком величини O(f(n)) дорівнює
При побудові хеш-функції методом множення розмір хеш-таблиці
Проблема розпізнавання самозастосовності алгоритму є
Рівняння складності деякого алгоритму f(n)=2n2+3nlog n . Складність цього алгоритму за порядком величини O(f (n)) дорівнює
Рівняння складності деякого алгоритму f(N)=4N2+2N+N. Складність цього алгоритму за порядком величини O(f(N)) дорівнює
У якому зі списків функції оцінки складності алгоритмів розташовані в порядку зростання складності алгоритмів, які вони характеризують?
Вчений, що визначив клас NP і висловив гіпотезу P≠NP
Алфавіт А складається з 16-ти букв, алфавіт В – з 2-ох букв. Словами якої довжини можна закодувати всі букви алфавіту А в алфавіті В?
Розгалуження F(P) задане співвідношенням:
Знайти F ab ( )
Обчислити функцію вибору аргументів I24 (3,6,2,1)
Функції h (x)=0; f (x) = x+1 . Обчислити суперпозицію S2(f1,h1)
Функції f (x) = x+1 . Обчислити суперпозицію S2(f1,f1)
Складність алгоритму швидкого сортування в середньому випадку становить
Результат застосування машини Тьюрінга T1 :
q0a→⋀q0R
q0b→⋀q1R
q1c→cq2H
до слова P= abcc дорівнює (у початковий момент читаюча головка машини знаходиться на першій букві слова P )
Результат застосування машини Тьюрінга T1 :
q0a→⋀q0R
q0b→⋀q1R
q1c→cq2H
до слова P= abc дорівнює (у початковий момент читаюча головка машини знаходиться на першій букві слова P )
Яка з послідовностей є незростаючою пірамідою (max-heap)
Яка з послідовностей є незростаючою пірамідою (max-heap)
Проблема з'ясування виконувальності довільної формули А логіки висловлень (пропозиціональної форми), представленої в кон’юнктивній нормальній формі
Яка з послідовностей є неспадною пірамідою (min-heap)
Яка з послідовностей є неспадною пірамідою (min-heap)
Розгалуження F(P) задане співвідношенням:
Знайти F (ba)
Алгоритм називають „самозмінним”, якщо в процесі його виконання змінюється:
Задача, що полягає у побудові алгоритму, що дозволив би визначити, чи для довільного діофантового рівняння F(x1, x2...)= 0 існують цілочисельні розв’язки, називають:
При побудові хеш-функції методом ділення розмір хеш-таблиці
Якщо 0≤cg(n)≤f(n), c - const , то:
Якщо lim f(n)/g(n)=0, то:
Між класами примітивно-рекурсивних, частково-рекурсивних та загально-рекурсивних функцій можна записати такі
Дати визначення рекурсії:
Знайти медіану множин(69, 68, 69, 17, 75, 76, 53, 31, 37, 62, 59)
Створюйте онлайн-тести
для контролю знань і залучення учнів
до активної роботи у класі та вдома
