Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 1
№ Питання Варіант відповіді Бали
1 Задачі, які дозволяє розв’язувати SH-модель алгоритму Навести приклади 7
2 Дати тлумачення поняттю «абстрактний алгоритм» Дати пояснення 7
3 Перетворення на машині Тюрінга U D Результат зліва Рис. стрічки, сліду, програми 7
4 Теореми Гьоделя про неповноту, тлумачення Навести розрахунок 7
5 Формальне визначення машини Тюрінга Дати пояснення 6
6 Принципи Фон Неймана побудови комп’ютера Дати пояснення 6
7 Теза Маркова, тлумачення Дати пояснення 5
8 Визначити залишок без операції ділення: Навести алгоритм 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. Каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет «Львівська політехніка», IКТА, кафедра СКС Напрям «Комп’ютерна інженерія» Семестр 4 Навчальний предмет «Алгоритми та методи обчислень» ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 2
№ Питання Варіант відповіді Бали
1 Дати тлумачення поняттю «задача» Дати пояснення, навести приклади 7
2 Необхідність уточнення поняття “алгоритм” Дати пояснення 7
3 Перетворення на машині Тюрінга UD. Результат справа Рис. cтрічки, сліду, програми 7
4 Визначення L прямого ДПФ Навести розрахунок 7
5 Простіші функції Гьоделя Дати пояснення 6
6 10-та проблема Гілберта, приклад діафантового рівняння Дати пояснення 6
7 Теза Тюрінга, тлумачення Дати пояснення 5
8 Визначити залишок без операції ділення: (1110+1011)mod 7 Навести алгоритм 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р. Зав. Каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет «Львівська політехніка», IКТА, кафедра СКС Напрям «Комп’ютерна інженерія» Семестр 4 Навчальний предмет «Алгоритми та методи обчислень» ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 3
№ Питання Варіант відповіді Бали
1 Структура пари задача-алгоритм Навести схему 7
2 Основна гіпотеза теорії алгоритмів Дати пояснення 7
3 Перетворення на машині Тюрінга U B Результат зліва Рис. стрічки, сліду, програми 7
4 Визначення L зворотного ДПФ Навести розрахунок 7
5 Система кодування Гьоделя Навести приклади 6
6 Визначення властивості дискретність SH-моделі Дати пояснення 6
7 Теза Чьорча, тлумачення Дати пояснення 5
8 Визначити залишок без операції ділення: Навести алгоритм 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 4
№ Питання Варіант відповіді Бали
1 Алгоритм як об’єкт розроблення Показати та пояснити схему 7
2 Система рекурсивних функцій Гьоделя - Чьорча Призначення, особливості 7
3 Перетворення на машині Тюрінга U B Результат cправа Рис. стрічки, сліду, програми 7
4 Визначення L прямого ШПФ Навести розрахунок 7
5 Система команд нормальних алгоритмів Маркова Навести приклади 6
6 Визначення властивості "ієрархічність" SH-моделі Дати пояснення 6
7 Дуалізм поняття "крок алгоритму" Дати пояснення 5
8 Визначити залишок без операції ділення: (110110+1011)mod 7 Навести алгоритм 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 5
№ Питання Варіант відповіді Бали
1 Принцип “Розділяй та пануй” Дати пояснення 7
2 Призначення модулярної арифметики Дати пояснення 7
3 Перетворення на машині Тюрінга D U Результат зліва Рис. стрічки, сліду, програми 7
4 Задача квадратичного призначення Навести розрахунок 7
5 Способи зменшення L абстрактних алгоритмів Навести приклади 6
6 Визначення властивості "детермінованість" SH-моделі та машини Тюрінга Дати пояснення 6
7 Поняття крок в системі Колмогорова Дати пояснення 5
8 Визначити залишок без операції ділення: (110110 –1011)mod 7 Навести алгоритм 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 6
№ Питання Варіант відповіді Бали
1 Розділення задачі на підзадачі в проектуванні комп’ютера Дати пояснення 7
2 Визначення машини Тюрінга Дати пояснення 7
3 Перетворення на машині Тюрінга D U Результат cправа Рис. стрічки, сліду, програми 7
4 Визначення L згортки двох сигналів Навести розрахунок 7
5 Ефективні алгоритми – зміна правила початку Навести приклади 6
6 Визначення властивості "масовість" SH-моделі Дати пояснення 6
7 Поняття крок в машине Тюрінга Дати визначення 5
8 Визначити залишок без операції ділення: (10011+1101)mod 7 Навести алгоритм 5
9 Перелік операцій розроблення алгоритму Навести тлумачення 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 7
№ Питання Варіант відповіді Бали
1 Словесне визначення SH-моделі алгоритму Дати пояснення 6
2 Виникнення проблем розв’язності Дати пояснення 6
3 Перетворення на машині Тюрінга D B Результат зліва Рис. стрічки, сліду, програми 6
4 Дві форми метелика ШПФ, операції обчислення Навести операції обчислення 6
5 Ефективні алгоритми – зміна правила закінчення Навести приклади 5
6 Парадокс брехуна Дати пояснення 5
7 Декартове множення Дати пояснення 4
8 Визначити залишок без операції ділення: (11011+10010)mod17 Навести алгоритм 4
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 8
№ Питання Варіант відповіді Бали
1 Параметрична модель алгоритму Дати пояснення 7
2 Взаємозалежність зміни параметрів і характеристик алгоритму Дати пояснення 7
3 Перетворення на машині Тюрінга D U Результат cправа Рис. стрічки, сліду, програми 7
4 L метелика ШПФ Навести розрахунок 7
5 Ефективні алгоритми – використання попередніх обчислень Навести приклади 6
6 Параметри SH-моделі алгоритму Дати пояснення 6
7 Проблеми, які розв’язують за допомогою ФАС Дати пояснення 5
8 Визначити залишок без операції ділення: (11011 –10010)mod17 Навести алгоритм 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 9
№ Питання Варіант відповіді Бали
1 Параметрична модель пари задача-алгоритм Дати пояснення 7
2 Параметрична оптимізація Дати пояснення 7
3 Сумування на машині Тюрінга * Ua0U Результат cправа Рис. стрічки, сліду, програми 7
4 Визначення часової складності SH-моделі Навести список способів 7
5 Алгоритм роботи часоімпульсного АЦП Навести приклади 6
6 Ефективні алгоритми – еквівалентні перетворення Дати пояснення 6
7 Функції нормальних алгоритмів Маркова Дати пояснення 5
8 Визначити залишок без операції ділення: (11101+10010)mod17 Навести алгоритм 5
9 Список параметрів алгоритму Навести тлумачення 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 10
№ Питання Варіант відповіді Бали
1 Праці Аль-Хорезмі, їх історичне значення Дати пояснення 7
2 Порівняння машин Тюрінга з SH-моделлю Дати пояснення 7
3 Сумування на машині Тюрінга Ua0U* Результат зліва Рис. стрічки, сліду, програми 7
4 Перетворення порядку слідування чисел ШПФ Навести розрахунок 7
5 Способи зменшення часової складності виводу ШПФ Навести формули 6
6 Визначення апаратної складності SH-моделі Дати пояснення 6
7 Модель похідної в дискретній математиці Навести алгоритм 5
8 Визначити залишок без операції ділення: (10101+10010)mod17 Навести алгоритм 5
9 Часова складність неформального алгоритму Навести тлумачення 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 11
№ Питання Варіант відповіді Бали
1 Недоліки абстрактних формальних алгоритмічних систем Дати пояснення 7
2 Визначення SH-моделі Дати пояснення 7
3 Сумування на машині Тюрінга U+U Результат cправа Рис. стрічки, сліду, програми 7
4 Ваговий метод зменшення часової складності обчислень Навести розрахунок 7
5 Способи побудови ефективних алгоритмів Навести приклади 6
6 Визначення ємнісної складності SH-моделі Дати пояснення 6
7 Модель інтеграла в дискретній математиці Дати пояснення 5
8 Визначити залишок без операції ділення: (10101+11110)mod17 Навести алгоритм 5
9 Часова складність машини Тюрінга Навести тлумачення 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 12
№ Питання Варіант відповіді Бали
1 Визначення програмної складності SH-моделі Дати пояснення 7
2 Призначення рекурсивних функцій Дати пояснення 7
3 Сумування на машині Тюрінга U+U Результат зліва Рис. стрічки, сліду, програми 7
4 Визначити часову складність схеми Горнера Навести розрахунок 7
5 Спосіб побудови ефективних алгоритмів – апроксимація Навести приклади 6
6 Визначення асимптотичної складності алгоритмів Дати пояснення 6
7 Відмінності тлумачення дискретності ФАС і SH-моделі Дати пояснення 5
8 Визначити залишок без ділення (100011100110101010000011010101) mod10001 Навести алгоритм 5
9 Часова складність одно стрічкової та багато стрічкової машини Тюрінга Навести тлумачення 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 14
№ Питання Варіант відповіді Бали
1 Алгоритми з поліноміальною складністю Дати пояснення 7
2 Напрямки уточнення поняття "алгоритм" Дати пояснення 7
3 Сумування на машині Тюрінга * U a0 a0U Результат cправа Рис. стрічки, сліду, програми 7
4 Визначення ШПФ Навести розрахунок 7
5 Тлумачення властивості “елементарність” ФАС Навести приклади 6
6 Визначення структурної складності SH-моделі Дати пояснення 6
7 Відмінності тлумачення кроку ФАС і SH-моделі Дати пояснення 5
8 Визначити залишок без ділення (100011100110101010000011010) mod10001 Навести алгоритм 5
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 13
№ Питання Варіант відповіді Бали
1 Алгоритми з експоненціальною складністю Дати пояснення 7
2 Модулярна арифметика Дати пояснення 7
3 Сумування на машині Тюрінга U a0+U Результат cправа Рис. стрічки, сліду, програми 7
4 Використання поняття "чорна скринька" Дати пояснення 7
5 Відмінність ФАС від моделі абстрактних алгоритмів Навести приклади 6
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 15
№ Питання Варіант відповіді Бали
1 Евристичні алгоритми, визначення, тлумачення Дати пояснення 7
2 Визначення і призначення згортки двох сигналів Дати пояснення 7
3 Сумування на машині Тюрінга U a0+U Результат зліва Рис. стрічки, сліду, програми 7
4 Процес цифрової фільтрації Навести розрахунок 7
5 Відмінність машини Тюрінга від SH-моделі Навести приклади 6
6 Визначення властивості "елементарність" SH-моделі Дати пояснення 6
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 16
№ Питання Варіант відповіді Бали
1 Характеристики складності SH-моделі алгоритму Дати пояснення 7
2 Властивість “ієрархічність” SH-моделі алгоритму Дати пояснення 7
3 Сумування на машині Тюрінга U a0 a0 a0 U Результат cправа Рис. стрічки, сліду, програми 7
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 17
№ Питання Варіант відповіді Бали
1 Властивості абстрактного алгоритму Дати пояснення 7
2 Визначення ДПФ Дати пояснення 7
3 Сумування U a0 a0 a0 U Результат зліва Рис. стрічки, сліду, програми 7
Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.
Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.
Національний університет "Львівська політехніка", IКТА, кафедра СКС Напрям "Комп'ютерна інженерія" Семестр 4 Навчальний предмет "Алгоритми та методи обчислень" ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 18
№ Питання Варіант відповіді Бали
1 Властивості SH-моделі алгоритму Дати пояснення 7
2 Визначення елементарного перетворювача Дати пояснення 7
3 Віднімання *U – U Результат cправа Рис. стрічки, сліду, програми 7
4 Еквівалентність згортки двох сигналівта добутку їх спектрів Дати пояснення 7
5 Асимптотична складність алгоритму Дати пояснення 6
6 Алгоритм знаходження нижньої границі методу гілок та границь Дати пояснення 6
7 Множення комплексних чисел Навести розрахунок 5
8 Визначити залишок (1011110011010101111010101) mod111 Навести алгоритм 5
