Національний університет "Львівська політехніка", IКТА, кафедра СКС
Напрям "Комп'ютерна інженерія" Семестр 4
Навчальний предмет "Алгоритми та методи обчислень"
ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 1








Питання
Варіант відповіді
Бали

1
Задачі, які дозволяє розв’язувати SH-модель алгоритму
Навести приклади
7

2
Дати тлумачення поняттю «абстрактний алгоритм»
Дати пояснення
7

3
Перетворення на машині Тюрінга U D Результат зліва
Рис. стрічки, сліду, програми
7

4
Теореми Гьоделя про неповноту, тлумачення
Навести розрахунок
7

5
Формальне визначення машини Тюрінга
Дати пояснення
6

6
Принципи Фон Неймана побудови комп’ютера
Дати пояснення
6

7
Теза Маркова, тлумачення
Дати пояснення
5

8
Визначити залишок без операції ділення:
Навести алгоритм
5

9
Евристичний алгоритм
Навести тлумачення
5

10
Обрати правильний вираз: 1. О(N+4); 2. О(сN+a); 3. О(N!); 4. О(3N3); O( )
Дати пояснення
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

9
Поняття система
Навести тлумачення
5

10
Обрати правильний вираз: 1. О(N+4); 2. О(сN+a); 3. О(N!); 4. О(3N3); O( )
Дати пояснення
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

9
Поняття "модель"
Навести тлумачення
5

10
Обрати правильний вираз: 1. О(с+4); 2. О(сN+a); 3. О(N); 4. О(кN); O( )
Дати пояснення
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

9
Модель інтеграла
Навести тлумачення
5

10
Обрати правильний вираз: 1.О(N+Ь); 2.О(сN+а); 3. О(Nc); 4. О(3N3).
; O( )
Дати пояснення
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

9
Модель похідної
Навести тлумачення
5

10
Обрати правильний вираз: 1. O( ); O(23+N); 3. О(Nc); 4. O(1010)
Дати пояснення
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

10
Обрати правильний вираз: 1. О(N+4); 2. О(сN+a); 3. О(N!); 4. О(3N3);
Дати пояснення
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

9
Структурний синтез алгоритму
Навести тлумачення
4

10
Обрати правильний вираз: 1. О(N+4); 2. О(сN+a); 3. O( ); 4. О(3N3);
Дати пояснення
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

9
Параметрична оптимізація алгоритму
Навести тлумачення
5

10
Обрати правильний вираз: 1. О(N+4); 2) O(aN); 3. О(сN+a; 4. О(3N3);
Дати пояснення
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

10
Обрати правильний вираз: 1. О(N2?); 2. О(сN+a); 3. О(0); 4. О(3N3);
Дати пояснення
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

10
Обрати правильний вираз: 1. О(N+4); 2. O( ); 3. О(N!); 4. О(3N3);
Дати пояснення
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

10
Обрати правильний вираз: 1. О(N/10); 2. О(сN+0); 3. O(33!); 4. О(3N3);
Дати пояснення
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

10
Обрати правильний вираз: 1. О(N+4); 2. О(сN+a); 3. О(N!); 4. О(3N3); O( )
Дати пояснення
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

9
Рекурсивна функція
Навести тлумачення
5

10
Обрати правильний вираз:1.O(33!) ; 2. О(1N+10); 3. О(N+4) ; 4. О(3N3);
Дати пояснення
5

Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.


Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.



Національний університет "Львівська політехніка", IКТА, кафедра СКС
Напрям "Комп'ютерна інженерія" Семестр 4
Навчальний предмет "Алгоритми та методи обчислень"
ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 13








Питання
Варіант відповіді
Бали

1
Алгоритми з експоненціальною складністю
Дати пояснення
7

2
Модулярна арифметика
Дати пояснення
7

3
Сумування на машині Тюрінга U a0+U Результат cправа
Рис. стрічки, сліду, програми
7

4
Використання поняття "чорна скринька"
Дати пояснення
7

5
Відмінність ФАС від моделі абстрактних алгоритмів
Навести приклади
6

6
Аксіоми комп’ютерного алгоритму
Навести формулювання аксіом
6

7
Алгоритм
Дати пояснення
5

8
Визначити залишок (10001110011010101011010101) mod7
Навести алгоритм
5

9
Часова складність SH-моделі алгоритму
Навести тлумачення
5

10
Обрати правильний вираз: 1.O(33!) ; 2. О(1N+10); 3. О(N+4) ; 4. О(3N3);
Дати пояснення
5

Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.


Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.


Національний університет "Львівська політехніка", IКТА, кафедра СКС
Напрям "Комп'ютерна інженерія" Семестр 4
Навчальний предмет "Алгоритми та методи обчислень"
ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 15












Питання
Варіант відповіді
Бали

1
Евристичні алгоритми, визначення, тлумачення
Дати пояснення
7

2
Визначення і призначення згортки двох сигналів
Дати пояснення
7

3
Сумування на машині Тюрінга U a0+U Результат зліва
Рис. стрічки, сліду, програми
7

4
Процес цифрової фільтрації
Навести розрахунок
7

5
Відмінність машини Тюрінга від SH-моделі
Навести приклади
6

6
Визначення властивості "елементарність" SH-моделі
Дати пояснення
6

7
Обрати правильний вираз: 1. О(N+4); 2. О(сN+a); 3. О(N4); 4. О(3N3)
Дати пояснення
5

8
Визначити залишок (1000111010101011010101) mod 111
Навести алгоритм
5

9
Числа Мерсена
Навести тлумачення
5

10
Обрати правильний вираз: 1. O(210); 2. О(сN+a); 3. O({A}); 4. О(3N3);
Дати пояснення
5

Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.


Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.


Національний університет "Львівська політехніка", IКТА, кафедра СКС
Напрям "Комп'ютерна інженерія" Семестр 4
Навчальний предмет "Алгоритми та методи обчислень"
ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 16








Питання
Варіант відповіді
Бали

1
Характеристики складності SH-моделі алгоритму
Дати пояснення
7

2
Властивість “ієрархічність” SH-моделі алгоритму
Дати пояснення
7

3
Сумування на машині Тюрінга U a0 a0 a0 U Результат cправа
Рис. стрічки, сліду, програми
7

4
Невизначеність часової складності нормальних алгоритмів Маркова
Навести розрахунок
7

5
Алгоритм роботи кодоімпульсного АЦП
Навести приклади
6

6
Уточнення поняття алгоритм
Дати пояснення
6

7
Визначити Lmin обчислення МСД чисел 49 й 23 за алгоритмом Евкліда
Навести розрахунок
5

8
Визначити залишок (1011001110011010101011010101) mod111
Навести алгоритм
5

9
Числа Ферма
Навести тлумачення
5

10
Обрати правильний вираз: 1. О(N+4); 2. О(nN+m); 3. O(10Log10N); 4.O()
; 4. О(3N3); O( )
Дати пояснення
5

Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.


Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.


Національний університет "Львівська політехніка", IКТА, кафедра СКС
Напрям "Комп'ютерна інженерія" Семестр 4
Навчальний предмет "Алгоритми та методи обчислень"
ЕКЗАМЕНАЦІЙНЕ КОНТРОЛЬНЕ ЗАВДАННЯ № 17








Питання
Варіант відповіді
Бали

1
Властивості абстрактного алгоритму
Дати пояснення
7

2
Визначення ДПФ
Дати пояснення
7

3
Сумування U a0 a0 a0 U Результат зліва
Рис. стрічки, сліду, програми
7

4
Алгоритм медіанної фільтрації
Навести розрахунок
7

5
Властивість “елементарність” абстрактних алгоритмів
Навести приклади
6

6
Задача квадратичного призначення
Дати пояснення
6

7
Значення робіт Тюрінга
Дати пояснення
5

8
Визначити залишок (10101110011010101011010101) mod111
Навести алгоритм
5

9
Абстрактний алгоритм
Навести тлумачення
5

10
Обрати правильний вираз: 1. О(N); 2. О(сN+a); 3. О(N!); 4. О(3N3); O( )
Дати пояснення
5

Затверджено на засіданні кафедри СКС протокол № 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

9
Комп’ютерний алгоритм
Навести тлумачення
5

10
Обрати правильний вираз: 1. О(N+4); 2. О(сN+a); 3. О(N!); 4. О(3N3); O( )
Дати пояснення
5

Затверджено на засіданні кафедри СКС протокол № 1 від 29.08.2012 р.


Зав. каф. СКС Дунець Р.Б. Викладач Черкаський М.В.