Всеукраїнськ а студентськ а олімпіад а
| Вид материала | Документы |
- Навчально-методичний посібник містить методичні рекомендації щодо організації різних, 2939.08kb.
- Відділ освіти богуславської райдержадміністрації нака з 28. 09. 2011 р м. Богуслав, 68.26kb.
- 23. 11. 2011 р. №606 Про проведення ІІ міського туру ІІ етапу Всеукраїнських учнівських, 58.56kb.
- Інформація про переможців Всеукраїнських учнівських олімпіад 2011 року, 182.8kb.
- Міністерство освіти І науки україни головне управління освіти І науки, 54.67kb.
- Про методичні рекомендації щодо проведення ІІІ етапу Всеукраїнських учнівських олімпіад, 674.16kb.
- Автономної Республіки Крим, управліннями освіти обласних, Київської, Севастопольської, 431.33kb.
- Умови проведення І, II та III етапів учнівських олімпіад у місті Києві, 501.04kb.
- Україна новоодеська районна дердавна адміністрація відділ освіти наказ від 26. 10., 344.7kb.
- Шановні переможці ІІІ (міського) етапу Всеукраїнських учнівських олімпіад, 44.41kb.
В
сеукраїнська студентська олімпіада за напрямом «Комп’ютерна інженерія»
Максимальна кількість балів за кожну дисципліну 60.
Файли відповідей називати за номером завдання (наприклад: для завдання 1.1 файл розв’язку повинен називатися 1-1.cpp, для завдання 4.1 файл розв’язку повинен називатися 4-1.doc). Якщо розв’язок на завдання складається з декількох файлів, тоді їх потрібно додати до архіву (наприклад: для завдання 3.1 файл розв’язку повинен називатися 3-1.rar).
1 Програмування (мови C/С++)
Для перевірки своїх рішень на робочих місцях надані наступні компілятори:
– Borland C++ 3.1 (з пакетом TASM);
– Visual C++ 6.0;
– GNU C/C++.
Надсилаючи розв’язок необхідно зазначити компілятор (зі списку), який потрібно використовувати при перевірці. Компіляція буде виконуватись із використанням опцій компілятора по замовчуванню.
1.1 (Максимальна оцінка – 10 балів)
Задано функцію від значень вектора x з n елементів.
Для заданого вектора x обчислити f(x,1).
Кількість елементів вектора n (1≤n≤500000) задано у першому рядку файлу з ім’ям “1-1.in” (без лапок). Другий рядок файлу містить елементи вектору x, які є цілими числами, що не перевищують за абсолютним значенням 100000. Елементи вектора розділені між собою прогалиною. Значення f(x,1) треба вивести у файл з ім’ям “1-1.out” (без лапок).
Обмеження на час виконання програмою одного тесту – 2 сек.
Приклад:
| файл “1-1.in” | файл “1-1.out” |
| 1 101 | 101 |
1.2 (Максимальна оцінка – 15 балів)
Задано цілі числа a[1], b[1], a[2], b[2], …, a[n], b[n].
Розглядаючи пари (a[i], b[i]) при i=1..n як ліві та праві кінці відрізків на одній і тій же прямій, визначити, чи існує єдиний неперервний відрізок, що включає в себе всі задані, і кожна точка якого входить хоча б в один заданий відрізок, та визначити кінці такого відрізка, якщо він існує.
Кількість пар чисел n (1≤n≤100000) задано у першому рядку файлу з ім’ям “1-2.in” (без лапок). Кожний з наступних n рядків вхідного файлу містить пару цілих чисел a[i] та b[i] (a[i]<b[i]), кожне з яких не перевищує за абсолютним значенням 1000000. Числа розділені між собою прогалиною.
У файл з ім’ям “1-2.out” (без лапок) вивести два числа – координати лівого та правого кінців шуканого відрізку, якщо такий відрізок існує, або “No” (без лапок), якщо такого відрізку не існує.
Обмеження на час виконання програмою одного тесту – 2 сек.
Приклад:
| файл “1-2.in” | файл “1-2.out” |
| 2 -1 1 2 3 | No |
1.3 (Максимальна оцінка – 15 балів)
Задано непарне натуральне число N. Розташувати натуральні числа від 1 до N2 у матриці з розмірами NN так, щоб суми елементів у кожному рядку, кожному стовпці і кожній з двох діагоналей дорівнювали б одному і тому ж числу.
Непарне натуральне число N (1≤N≤499) задано у першому рядку файлу з ім’ям “1-3.in” (без лапок). Шукану матрицю треба вивести у файл з ім’ям
“1-3.out” (без лапок). Кожний рядок матриці виводити з нового рядка, в межах одного рядка числа розділяти між собою прогалиною. У разі існування декількох варіантів розв’язку вивести будь-який з них. Якщо для заданого N не існує жодного розв’язку, замість матриці вивести “No” (без лапок).
Обмеження на час виконання програмою одного тесту – 2 сек.
Приклад:
| файл “1-3.in” | файл “1-3.out” |
| 1 | 1 |
1.4 (Максимальна оцінка – 20 балів)
Прямокутний паралелепіпед розташовано у просторі таким чином, що його ребра паралельні осям прямокутної системи координат. Задано множину площин, кожна з яких є перпендикулярною до однієї з осей цієї ж системи координат. Знайти площу поверхонь усіх тривимірних об’єктів, що утворюються з паралелепіпеда при можливому перетині його об’єму площинами із заданої множини. Якщо жодна з площин не перетинає об’єм паралелепіпеда, то слід вважати, що такий об’єкт один – це сам паралелепіпед.
В перших 2 рядках вхідного файлу “1-4.in” містяться координати (x, y та z) двох найбільш віддалених одна від одної вершин прямокутного паралелепіпеда. Кожна з координат (x, y та z) задається цілим числом, що не перевищує за абсолютним значенням 10000000000.
Наступний рядок вхідного файлу містить ціле число N (1≤N≤300000), що дорівнює кількості площин у заданій множині.
Кожний з наступних N рядків вхідного файлу містить координати (x, y та z) точки перетину кожної з площин з віссю координат. Кожна з координат задається цілим числом, що не перевищує за абсолютним значенням 10000000000. Гарантується, що жодна з площин не містить в собі граней паралелепіпеда, також всі площини перетинають осі координат у точках з різними координатами, тобто всі N площин різні.
У файл з ім’ям “1-4.out” (без лапок) вивести з точністю до цілих загальну площу поверхонь усіх тривимірних об’єктів, що утворюються з паралелепіпеда при можливому перетині його об’єму площинами із заданої множини.
Обмеження на час виконання програмою одного тесту – 2 сек.
Приклад:
| файл “1-4.in” | файл “1-4.out” |
| 0 0 0 3 3 3 3 1 0 0 0 1 0 0 -1 0 | 90 |
2 Системне програмування
2.1 (Максимальна оцінка – 20 балів = 15 + 5 за оригінальність)
Реалізувати функцію, що виконує циклічне переміщення рядка на один символ з мінімальним використанням додаткової пам'яті при перезапису (наприклад, менше одного байта). Функція приймає параметри зі стека (довжина рядка, напрямок переміщення, покажчик на рядок) і повертає адресу зміненого рядка. Функцію виконати на асемблері в окремому модулі. Програму виклику функції й виводу результату написати мовою Сі. Переслати працюючий ехе-файл і тексти програм.
2.2 (Максимальна оцінка – 10 балів)
Скласти програму перевірки контрольної суми CMOS-RTC.
2.3 (Максимальна оцінка – 15 балів)
Напишіть на ANSI C програму виводу на екран при кожному натисканні на ліву клавішу мишки наступної інформації:
а) кількість функціональних клавіш (Fxx) у використовуваній клавіатурі; (7 балів)
б) число натискань кожної з Fxx. (8 балів)
2.4 (Максимальна оцінка – 15 балів)
У вікні додатку створити кнопку, на якій розташовано бітове зображення 16х16 пікселів, що обертається за годинниковою стрілкою. При натисканні на кнопку таке ж зображення починає обертатися в панелі задач (tray). При натисканні миші на зображенні в паналі задач, зображення починають обертатися протилежному напрямку.
3 Комп’ютерна графіка
Файли завдань знаходяться в електронній системі “Moodle”.
3.1 (Максимальна оцінка – 10 балів)
Тема. Тонова, кольорова корекція, ретуш та фотомонтаж графічних зображень.
Завдання. Необхідно з наданих фотографій отримати ті, що надані як зразки.
Вихідні дані.
- Вхідні файли зображень в форматі JPG.
- Вихідні файли зображень-зразків в форматі JPG.
Вимоги
- Робота виконується в растровому графічному редакторі Adobe Photoshop.
Результат
- Файли зображень в форматі JPG, архівовані в один файл формату RAR.
3.2 (Максимальна оцінка – 10 балів)
Тема. Створення ілюстрації в векторному графічному редакторі.
Завдання. Необхідно створити у векторному вигляді зображення логотипів у відповідності до виданого в растровому вигляді завдання.
Вихідні дані.
- Вхідний файл зображень в форматі GIF.
Вимоги
- Робота виконується у векторному графічному редакторі Adobe Illustrator.
- Об’єкти вихідного векторного зображення повинні мати оптимальну кількість вузлів.
Результат
- Файл зображень в форматі AI.
3.3 (Максимальна оцінка – 20 балів)
Тема. Створення анімації за допомогою Flash-технології.
Завдання. Необхідно створити файл анімації, відповідно до виданого завдання.
Вихідні дані.
- Файл анімації у форматі SWF.
Вимоги
- Робота виконується в графічному редакторі Macromedia Flash.
Результат
- Файл анімації в форматі FLA.
3.4 (Максимальна оцінка – 20 балів)
Тема. Створення інтерактивної анімації за допомогою Flash-технології.
Завдання. Необхідно створити файл анімації, відповідно до виданого завдання.
Вихідні дані.
- Файл анімації у форматі SWF.
Вимоги
- Робота виконується в графічному редакторі Macromedia Flash.
Результат
- Файл анімації в форматі FLA.
Завдання 3.1.
Вихідні зображення Результат
Завдання 3.2.
Вихідні зображення
Завдання 3.3.
Вихідний файл анімації
Завдання 3.4.
Вихідний файл анімації
4 Захист інформації
Файли результатів відправляти в форматі Microsoft Word.
4.1 Цифровий підпис (Максимальна оцінка – 18 балів)
Нехай цифровий підпис < r, s > під документом M з хеш-образом h = H(M) формується згідно правил
r = gk mod p
s = (k + x + h) mod p
де х – особистий ключ користувача А, g – первісний елемент, p – велике просте число, Н(·) – функція хешування, k – випадкове ціле число в інтервалі [ 2, p - 1].
Для повідомлення {M`,
Якщо
g (s`-H(M`))·y mod p = r` mod p,
повідомлення М є цілісним та справжнім.
Доведіть, що зловмисник може сформувати справжній підпис за цією схемою під будь-яким повідомленням від імені підписувача А, якщо він знає його відкритий ключ.
4.2 Схема Діффі-Хеллмана (Максимальна оцінка – 14 балів)
Зловмисник перехопив разові відкрити ключі двох абонентів мережі, які були сформовані по схемі Діффі-Хеллмана, – y1 = g mod N, y2 = g mod N. Знайдіть спільний секретний ключ y12 = y2 mod N цих абонентів, якщо N = 29, g = 14,
y1 = 19, y2 = 3.
4.3 Мережева безпека (Максимальна оцінка – 16 балів)
Адміністратор безпеки невеликої локальної мережі (побудована на базі комутатора, що не керується, і складається з робочих станцій Windows та декількох UNIX-серверів) звернув увагу на підвищення активності мережевого обміну.
Запуск мережевого аналізатору Wireshark (Ethereal) і перевірка мережевих параметрів дала наступні результати (надається нижче).
Завдання:
Виконайте аналіз наданої інформації. Визначте аномальний трафік (Ethernet-кадри та/або IP-пакети), якщо він присутній. Визначте мережевий трафік (Ethernet-кадри та/або IP-пакети), що не є аномальним, але є потенційно небезпечним, якщо такий присутній. Обґрунтуйте свої висновки щодо виявлених властивостей трафіку. Запропонуйте заходи щодо забезпечення безпеки локальної мережі.
Рисунок 4.1
Рисунок 4.2
Рисунок 4.3
4.4 Псевдовипадкові послідовності (Максимальна оцінка – 12 балів)
Дано зашифрований текст:
ССОЕЧЙЦКШПЬЛСЭБЪДМСФТМКААЯЧКВКЬЕФЯЗФЗСЖАЩЬМГЙЗЗШЪЗЕЬЭЫЕЩТВЛЧФТЖКШМЕЖВРРДЩЮИЮЪЖБЕУ
Для шифрування використовували наступну відповідність між російським алфавітом і множиною цілих
| А | 0 | И | 8 | Р | 16 | Ш | 24 |
| Б | 1 | Й | 9 | С | 17 | Щ | 25 |
| В | 2 | К | 10 | Т | 18 | Ь | 26 |
| Г | 3 | Л | 11 | У | 19 | Ы | 27 |
| Д | 4 | М | 12 | Ф | 20 | Ъ | 28 |
| Е | 5 | Н | 13 | Х | 21 | Э | 29 |
| Ж | 6 | О | 14 | Ц | 22 | Ю | 30 |
| З | 7 | П | 15 | Ч | 23 | Я | 31 |
Шифрування проводилося шляхом гамування, тобто відкритий текст підсумовувався з гамою-послідовністю за модулем 32.
В якості гами шифру використовувалася послідовність узагальнених чисел Фібоначчі.
Узагальнені числа Фібоначчі, звані p-числами - є числа, що породжуються лінійною рекурентною послідовністю порядку
з законом рекурсії:
, де
и 
,при наступних початкових умовах:
.Гамма починається зі значення
і обмежена лише довжиною повідомлення, яке шифрується.Ключем шифрування є
. Відомо, що значення ключа менше потужності використаного алфавіту.Завдання: знайти ключ і прочитати повідомлення.
5 Прикладна теорія цифрових автоматів
5.1 Надано пристрій для передавання даних в паралельному коді чотирьох керуючих сигналів, які закодовано.
Канал зв`язку має три лінії (активні дроти) і заземлення (пасивний дріт).
Вірогідність однократної помилки переданого коду порівняно дуже велика. Вірогідності двократної і трикратної помилок переданого коду порівняно дуже низькі.
Запропонуйте таблицю кодів (двійкових векторів), які забезпечать передачу означених чотирьох правильних сигналів (коли без помилок) і її відсутність (блокування і фіксація помилки) та обґрунтуйте свій вибір. Розробіть таблицю істинності (ТІ) для розпізнавання і фіксації помилок в цьому каналі зв`язку.
Отримайте аналітичний вираз функції по ТІ і проведіть її мінімізацію в базисі Буля. Наведіть її кінцевий аналітичний вираз.
(15 балів за повне і обґрунтоване рішення задачі).
5.2 Надано кілька схем: мультиплексори (типу 2 в 1) та будь які двоходові схеми (базис Буля).
Обґрунтуйте можливість (або неможливість) виконання на них комбінаційної схеми (КС) для повного однорозрядного суматора згідно
рис. 5.1а. Таблиця істинності (ТІ) та карти Карно (рис. 5.1.б) надано додатково для прискорення отримання аналітичних виразів для У1 і У2.
При побудові КС повного однорозрядного суматора використовуючи сучасні підходи створення логічних функцій (ЛФ) за допомогою універсальних логічних модулів (УЛМ) на мультиплексорах.
(15 балів за повне і обґрунтоване рішення задачі).
а) ПОС б) таблиця істинності, карти Карно
Рисунок 5.1 − Зображення ПОС, його ТІ і карти Карно функцій у1, у2
5.3 Надана схема цифрового автомату на J-K тригерах та дешифраторі, рисунок 5.2.
За наданою схемою визначити: до якого класу належить тип цифрового автомату (ЦА) та скласти: а) таблицю переходів станів і виходів; б) орієнтований граф.
Початковим станом вважати той, який ЦА прийме після сигналу ReSet, що надходить «0». Вхідний сигнал Х може приймати значення «0» або «1» в довільній послідовності відносно синхросигналу Clk.
(15 балів за повне і обґрунтоване рішення задачі)
5.4 Надано орієнтований граф переходів цифрового автомату «Продаж чаю і кави», рисунок 5.3.
Закодувати коди станів (Zi), умови виконання переходів між ними ЦА під дією вхідних керуючих сигналів (Xj) і вихідні сигнали Yк у вигляді ЦА (Мура або Мілі). Для кодування станів ЦА використати синхронні Т-тригери і при кодуванні звести до мінімуму кількість їх перемикань по виходах.
Надати таблицю переходів станів/виходів ЦА під дією вхідних керуючих сигналів.
(15 балів за повне і обґрунтоване рішення задачі).
Рисунок 5.2 – Схема ЦА на двох J-K тригерах та дешифраторі.
Рисунок 5.3 – Граф ЦА «Продаж чаю і кави».
Конкурсні завдання (перший тур) стор.