1. Машина Тьюринга

Машина Тьюринга - это теоретическая модель компьютера. Машина состоит из ленты, на которой имеются символы, и головки записи-чтения. Во время работы машины головка может двигаться на один символ вправо или влево:

Во время работы машина всегда находится в каком-то состоянии и ее работой управляет программа, которую можно представить с помощью таблицы из пяти столбцов:

В начале работы машина всегда находится в состоянии 0, и дальнейшее поведение будет таким:

• находит в таблице строку, первый столбец которой содержит текущее состояние машины, а во втором столбце имеется символ, который находится над головкой записи-чтения;
• записывает на ленту вместо имеющегося символа тот символ, который имеется в третьем столбце;
• перемещает головку чтения на один символ в ту сторону, которая указана в четвертом столбце;
• переходит в состояние, которое указано в последнем столбце.

Знак "_" во втором и третьем столбцах таблицы обозначает пробел. Состояние "стоп" обозначает, что машина закончит работу. Имеющиеся в таблице пустые строчки используются только для лучшего отображения самой таблицы.

В вышеприведенном примере программа двигается по ленте слева направо, удаляя начальные нули в двоичных числах, и заканчивает работу после символа решетки.

Точнее, находясь в начальном состоянии 0, машина видит на ленте пробел и, согласно первой строке таблицы, перемещает головку записи-чтения вправо, при этом оставаясь в состоянии 0. Так повторяется до тех пор, пока машина не доберется до первого нуля. Согласно второй строке таблицы, вместо нуля она записывает пробел и перемещает головку дальше вправо, но по-прежнему оставаясь в состоянии 0. Теперь машина добралась до первой единицы. Согласно третьей строчке таблицы, машина перемещает головку опять направо, но при этом сама машина переходит в состояние 1. Далее машина читает с ленты пробел, который находится за единицей. Согласно четвертой с конца строке, пробел остается неизменным, а машина переходит в состояние 0. Действуя аналогично, машина закончит свою работу в состоянии, которое изображено на последнем рисунке.

Вопрос

Что делает следующая программа?

Во втором столбце имеющийся знак "*" означает "любой другой символ" и соответствующую ему строку используют, если никакая другая не подходит; в третьем столбце имеющийся знак "*" означает, что на ленту записывается тот же символ, что и прочитали с нее.

[Raadionupud]

A. Заменит имеющиеся на ленте единицы двойками

B. Заменит имеющиеся на ленте двойки единицами

C. Ищет на ленте группу единиц и записывает на ленту "T" (true, истина), если в группе имеется четное число единиц, или "F" (false, ложь) в противном случае

D. Ищет на ленте группу единиц и записывает на ленту "T" (true, истина), если в группе имеется нечетное число единиц, или "F" (false, ложь) в противном случае

2. Морковный робот

В поле морковка посажена в пять рядов и по семь морковок в каждом:

На поле работает робот, который можно запрограммировать с помощью следующих команд собирать морковку:

Если какую-то команду или группу команд необходимо повторить, то перед ней можно записать количество необходимых повтор. Например, 3F означает, что робот перемещается на три шага вперед, а 4(F R) означает, что робот перемещается по квадрату и возвращается в исходную точку.

Вопрос

Какая из приведенных команд подходит, чтобы робот собрал все морковки?

[Raadionupud]

A. 2(P 6(F P) R F R) (P 6(F P) L F L) 7P

B. R 3(P 4(F P) L F L) (P 4(F P) R F R)

C. 2(P 6(F P) R F R P 6(F P) L F L) P 6(F P)

D. 5(7P L F R) 7P

3. Новая больница

В одном государстве имеется шесть больших городов. На нижеприведенной карте показано, сколько времени занимает переезд из одного города в другой:

На данный момент больница имеется только в городе F, и это означает, что в худшем случае (если заболеет житель города A) потребуется 5 часов, чтобы добраться до больницы.

Вопрос

Где необходимо построить вторую больницу, чтобы в самом худшем случае время доставки больного было наименьшим возможным?

[Raadionupud]

A. В городе A

B. В городе B

C. В городе C

D. В городе D

E. В городе E

4. Мастер стульев

Альберт мастерит стулья. У каждого стула должно быть четыре ножки одинаковой длины. У разных клиентов разные пожелания, и поэтому Альберт мастерит стулья разной высоты:

Материал для изготовления ножек Альберт собирает в лесу. Часто найденный материал оказывается разной длины. При необходимости Альберт может длинные ножки укоротить (при укорачивании ножки может использоваться только одна часть):

Так как укорачивание ножек является трудоемким занятием, Альберт хочет этим заниматься как можно меньше.

Сейчас у Альберта на складе 32 ножки:

Вопрос

Какое наименьшее количество ножек ему надо укоротить, чтобы получить материал для изготовления восьми стульев?

[Täisarv]

5. Срочная встреча

Двум друзьям необходимо срочно встретиться. Перемещаясь пешком, им понадобится одна минута, чтобы добраться из своего местоположения до соседней клетки в той же строке или столбце. Добравшись до велосипеда или машины, они смогут перемещаться быстрее: на велосипеде - две клетки в минуту, а на машине - пять клеток в минуту. Через воду они не могут перебраться ни на одном средстве.

Вопрос

Какое наименьшее количество минут им понадобится, чтобы добраться до одной и той же клетки?

[Täisarv]

6. Описание ожерелья

Жан любит мастерить ожерелья. Он хочет передать описания своих ожерелий друзьям и использует для этого самостоятельно придуманный язык.

Каждую бусинку он обозначает соответствующей форме буквой: S (star, пятиугольник), T (triangle, треугольник), R (rectangle, четырехугольник), L (line, черта). Вместо того чтобы просто записать последовательность бусинок, Жан использует хитрую схему:

• если в ожерелье несколько одинаковых бусинок идут подряд, то сначала записывается количество бусинок, а затем обозначение бусинки;
• если в ожерелье есть повторяющийся участок, то сначала записывается количество повторов, а затем в скобках указывается описание участка.

Например, ожерелье

может быть описано с помощью S3(TR)3SL. Длина этого описания 9 знаков.

Вопрос

Сколько знаков будет в минимальном описании нижеприведенного ожерелья (учитываются как буквы, так и цифры и скобки)?

[Raadionupud]

A. 12 знаков

B. 13 знаков

C. 14 знаков

D. 15 знаков

7. Гномы

Белоснежка и семь гномов живут в одном доме. Для простоты обращения к гномам используем расположенные на их колпаках номера:

Между гномами произошло несколько ссор и теперь дела обстоят следующим образом: гном под номером 12 дружит с гномами под номерами 1 и 2, 13 дружит с 1 и 3, 23 дружит со 2 и 3, и только 123 по-прежнему дружит со всеми.

Чтобы примирить гномов, Белоснежка предложила игру - в зависимости от названного ею числа гномы будут заходить в дом или выходить из дома следующим образом:

• если Белоснежка называет число "2", то гном под номером 2 и его друзья (12, 23 и 123) заходят в дом;
• если Белоснежка называет число "3", то гном под номером 3 и его друзья (13, 23 и 123) заходят в дом;
• если Белоснежка называет число "4", то гном под номером 1 и его друзья меняют свои местонахождения (те, кто до этого были внутри дома, выходят; те, кто до этого были снаружи дома, заходят);
• если Белоснежка называет число "5", то гном под номером 2 и его друзья меняют свои местонахождения;
• если Белоснежка называет число "6", то гном под номером 3 и его друзья меняют свои местонахождения.

Представим, например, что гномы под номерами 1, 2 и 12 находятся внутри дома, а все остальные - снаружи. Если Белоснежка называет число "5", то гномы под номерами 2 и 12 выходят из дома, а гномы под номерами 23 и 123 заходят в дом; остальные остаются там, где они были.

На данный момент все семь гномов находятся в доме, но Белоснежке захотелось всех их выпроводить из дома, чтобы побыть наедине с принцем.

Вопрос

Какую самую короткую последовательность чисел должна назвать Белоснежка, чтобы выпроводить всех гномов из дома?

Впиши только числа без пробелов или других знаков!

[Tekst]

8. Угадайка

Юра играет в компьютерную игру Угадайка. Компьютер генерирует состоящий из четырех различных цифр пароль. Делая предположения, игрок старается угадать пароль. На каждое предположение компьютер отвечает, сколько цифр в предложенном варианте были такими же, как и в пароле, и находятся ли они в предложенном варианте на том же месте, что и в пароле.

Юра уже сделал пять предположений и получил на них следующие ответы:

Вопрос

Какой пароль сгенерировал компьютер?

Введи четыре цифры без пробелов!

[Tekstikast]

9. Групповая работа

Обычно для выполнения групповой работы восемь учеников делятся на три группы:

На нижеприведенном рисунке каждая точка обозначает одного ученика, а цвет точки обозначает группу, к которой он обычно принадлежит:

Каждая линия соединяет двух учеников, которые не хотят работать вместе и предпочитают быть в разных группах.

К сожалению, один из столов сегодня сломался, и теперь учеников надо разделить на две группы. Это можно сделать так, что только двое учеников, которые не хотят работать друг с другом, будут в одной и той же группе.

Вопрос

Линия под каким номером будет соответствовать паре, которая должна согласиться работать в этот раз вместе, чтобы учеников можно было бы разделить на две группы?

[Täisarv]

10. Узоры

Имеется три представленных на картинках узора. Каждый из них может быть получен за счет повторения какого-то одного квадратика. Для этого у квадратика должно быть одно важное свойство.

Вопрос

У какого из нижеприведенных квадратиков нет этого свойства?

[Raadionupud]

A. B. C. D.

11. Идеальная температура

Бобр Фемистокл постоянно следит за температурой воды и записывает ее значения. Как только бобр просыпается, он сразу же смотрит и записывает первое значение температуры. Перед тем как пойти спать, Фемистокл записывает последнее на сегодня значение температуры. Бобр знает, что температура постоянно немного меняется, но в течение дня он записывает только экстремальные значения - значения, где как предыдущее, так и следующее значения будут более низкими, или значения, где как предыдущее, так и следующее значения будут более высокими. Например, если бы температура менялась в течение дня так, как показано на нижеприведенном графике, то Фемистокл записал только значения, которые располагаются в точках A, B, C, D и E.

Вчера Фемистокл записал следующие значения температуры:
5,1; 5,8; 5,5; 5,9; 5,3; 5,7; 5,4; 5,8; 5,6.

У Фемистокла есть только одна любимая температура, при которой он чувствует себя лучше всего. Вчера такая температура наблюдалась ровно пять раз.

Вопрос

Исходя из приведенных данных, в каком промежутке находится идеальная для Фемистокла температура?

Запиши разделенными друг от друга минусом нижнюю и верхнюю границы промежутка, например 5,1-5,6!

[Tekstikast]

12. Преобразование Барроуза-Уилера

Рассмотрим следующий алгоритм для преобразования некоторого слова:

1. в конце слова поставить маркер *;
2. составить список из текстов, которые получились при каждом циклическом сдвиге слова с маркером;
3. отсортировать список по алфавиту (учитывая, что маркер * должен располагаться в конце алфавита);
4. результат сложить из последних знаков текстов из отсортированного списка.

Циклическим сдвигом текста называется текст, который получили следующим образом - берутся некоторые расположенные в начале текста знаки и перемещаются (не меняя порядок знаков) в его конец.

Например, при использовании этого алгоритма для преобразования слова BANANA мы в результате получим BNN*AAA:

Вопрос

Какой получится результат, если использовать этот алгоритм для преобразования слова BEBRAS?

Впиши нужные символы без пробелов!

[Tekstikast]

13. Таблица истинности

Таблица истинности описывает значение (○ или ●) какого-либо логического выражения в случае всех возможных значений ее переменных. Например, в следующей таблице представлены значения одного выражения со всеми возможными истинными значениями переменных x, y и z:

Описанное в таблице выражение можно представить и с помощью формулы, перечислив все входы, которые в результате дадут ●:

(x=○ and y=○ and z=●) or
(x=● and y=○ and z=○) or
(x=● and y=○ and z=●) or
(x=● and y=● and z=○) or
(x=● and y=● and z=●)

Если мы представим выражение таким образом, то для ее записи нам потребуется 15 раз ссылаться на переменные.

Если посмотреть на таблицу чуть внимательнее, то можно заметить, что при x=● результат будет всегда ●, и, исходя из этого, формулу можно сократить так, чтобы ссылаться на переменные только четыре раза:

(x=○ and y=○ and z=●) or 
(x=●)

Но это еще не предел. Достаточно будет сослаться на переменные трижды:

(y=○ and z=●) or 
(x=●)

Две строчки последней формулы можно представить графически следующим образом:

Вопрос

Теперь рассмотрим таблицу побольше

и соответствующее ей графическое представление (обратите внимание на порядок переменных c и d):

Какое минимальное количество ссылок на переменные потребуется, чтобы представить это выражение с помощью формулы?

[Täisarv]

14. Сжатие изображений

В растерной графике изображение представляет собой мозаику, состоящую из маленьких одноцветных квадратов (пикселей). В случае черно-белого изображения каждый пиксель может быть либо черным, либо белым - это обычно обозначается с помощью чисел 0 и 1.

Для того чтобы уменьшить объем данных, образующийся при сохранении изображения, используются различные методы сжатия. Нижеприведенный рисунок наглядно демонстрирует один простой метод для сжатия черно-белых изображений.

Первое число каждой строки показывает количество белых, расположенных друг за другом, пикселей (если первый пиксель черного цвета, то строка начинается с числа 0). Дальше попеременно указывается количество черных и белых пикселей.

Вопрос

Какое изображение спрятано за следующими данными?

15
5, 3, 7
4, 1, 3, 1, 6
3, 1, 5, 1, 5
2, 1, 7, 1, 4
1, 1, 4, 1, 4, 1, 3
1, 1, 3, 3, 3, 1, 3
1, 1, 4, 1, 4, 1, 3
2, 1, 7, 1, 4
3, 1, 5, 1, 5
4, 1, 3, 1, 1, 1, 4
5, 3, 3, 1, 3
12, 1, 2
13, 1, 1
15

[Raadionupud]

A. B.

C. D.

15. Сколько раз кивнули?

В научном музее установили новый автомат по продаже билетов, который для общения с посетителями использует электронную систему зрения. Для покупки N количества билетов посетитель должен встать перед автоматом, кивнуть N количество раз вниз и затем поднять голову вверх.

Электронная система зрения следит за длиной видимой части переносицы (на нижеприведенных картинках она отмечена красной линией), записывает это значение в переменную nose и далее делает выводы о положении головы:

Картинка	Объяснение
	Если значение nose равно 1, то голова расположена прямо
	Если значение nose больше 1 (на картинке nose = 1.3), то голова направлена вниз
	Если значение nose меньше 1 (на картинке nose = 0.7), то голова направлена вверх

Программа по продаже билетов запускается, как только следующий посетитель становится перед камерой и смотрит прямо в нее.

Вопрос

Какая из следующих программ продаст посетителю правильное количество билетов?

[Raadionupud]

A. B.

C. D.