1 (базовый уровень, время – 3 мин)

Тема:  Использование и анализ информационных моделей (таблицы, диаграммы, графики).

Типы заданий:

1.  На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе запишите целое число – так, как оно указано в таблице.

Решение:

1. определим для каждой вершины её степень, то есть, количество ребёр, в которыми она связана; в таблице степень вершины – это количество заполненных клеток в строке (или в столбце)

2. сопоставление степеней вершин в таблице и на рисунке позволяет сразу обнаружить в таблице вершины А (она имеет № 3), Ж (№ 4) и Б (№ 6)
3. нас интересуют вершины Г и Ж; вершину Ж мы нашли, вершина Г имеет степень 2 и связана, кроме вершины Ж, с вершиной Д степени 3;
4. степень 2 имеют вершины № 1 и 2, но только вершина № 1 связана, кроме Ж, с вершиной  степени 3 (№ 7), поэтому вершина № 1 – это Г
5. по таблице определяем протяжённость дороги из пункта Г в пункт Ж, она равна 9.

Ответ: 9.

2.  На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15. Определите, какова длина кратчайшего пути из пункта Д в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Решение:

1. сложность этой задачи в том, что схема симметрична; легко понять, что без дополнительных данных (используя только степени вершин – количество связанных с ними ребёр) мы не сможем различить вершины А и В, Г и Е, Д и Ж
2. определим степени вершин:

3. как и видно из рисунка, у нас две вершины степени 2 (А и В), две вершины степени 3 (Д и Ж) и три вершины степени 4 (Б, Г и Е), причем вершина Б однозначно определяется как вершина степени 4, которая связана с двумя вершинами степени 2
4. для того, чтобы различить оставшиеся вершины, определим длины путей ЖГА, ЖЕВ, ДГА и ДЕВ; мы не знаем, где какой маршрут, но точно знаем, что эти четыре маршрута

П3 → П1 → П7 = 7 + 12 = 19

П3 → П6 → П5 = 10 + 6 = 16

П4 → П1 → П7 = 5 + 12 = 17

П4 → П6 → П5 = 9 + 6 = 15

5. из дополнительного условия (Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15.) находим, что маршрут ЖГА – последний, так что П4 = Ж, П6 = Г и П5 = А; в итоге получается

6. кратчайший путь из Д в В можно найти с помощью дерева возможных маршрутов – это будет путь ДЕВ длиной 19

Ответ: 19.

3.  Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.

Решение:

1. поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:

2. Ответ: 17.

4.  Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.

Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.

Решение:

1. обратим внимание, что числа в таблице нас совсем не интересуют – достаточно знать, что между данными пунктами есть дорога
2. нам нужно найти все пути, которые проходят через 6 и более пунктов, считая начальный и конечный; то есть между A и Z должно быть не менее 4 промежуточных пункта
3. начнем с перечисления всех маршрутов из А, которые проходят через 2 пункта; по таблице видим, что из A можно ехать в B, C и Z; количество пунктов на маршруте будем записывать сверху:

4. маршрут AZ нас не интересует, хотя он и пришел в конечный пункт, он проходит меньше, чем через 6 пунктов (только через 2!); здесь и далее такие «неинтересные» маршруты из A в Z будем выделять серым фоном
5. теперь ищем все маршруты, проходящие через 3 пункта; из B можно ехать только в C, а из С – в D и Z:

6. далее из C едем в D и Z, а из D – в E, F и Z:

7. строим следующий уровень только для тех маршрутов, которые ещё не пришли в Z:

8. следующие два уровня дают «интересные» маршруты, проходящие через 6 или 7 пунктов:

9. на последней схеме зелёным фоном выделены «интересные» маршруты, их всего 6; красным фоном отмечены маршруты, в которых получился цикл – они дважды проходят через один и тот же пункт; такие маршруты запрещены и мы далее их не рассматриваем

Ответ: 6.

10. можно было нарисовать схему возможных маршрутов в виде дерева:

5. (А вдруг такая задача будет на экзамене)))) Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

         Аэропорт вылета          Аэропорт прилета         Время вылета         Время прилета

        СОСНОВО         КРАСНЫЙ         06:20         08:35

        КРАСНЫЙ         ОКТЯБРЬ         10:25         12:35

        ОКТЯБРЬ         КРАСНЫЙ         11:45         13:30

        БЕРЕГ         СОСНОВО         12:15         14:25

        СОСНОВО         ОКТЯБРЬ         12:45         16:35

        КРАСНЫЙ         СОСНОВО         13:15         15:40

        ОКТЯБРЬ         СОСНОВО         13:40         17:25

        ОКТЯБРЬ         БЕРЕГ         15:30         17:15

        СОСНОВО         БЕРЕГ         17:35         19:30

        БЕРЕГ         ОКТЯБРЬ         19:40         21:55

Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.

1) 15:40         2) 16:35         3)17:15         4) 17:25

Решение:

1. для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ
2. из аэропорта ОКТЯБРЬ есть три рейса:

        ОКТЯБРЬ         СОСНОВО         13:40         17:25

        ОКТЯБРЬ         КРАСНЫЙ         11:45         13:30

        ОКТЯБРЬ         БЕРЕГ         15:30         17:15

3. построим граф, около каждого пункта запишем время прибытия

4. проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс  «БЕРЕГ-СОСНОВО», вылетающий в 12:15
5. таким образом, правильный ответ – 4 (прямой рейс).

6. На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Решение.

Сопоставим населённые пункты графа и населённые пункты в таблице. Необходимо определить номера населенных пунктов A и G. Из F ведут шесть дорог. Таким образом F — 3. Заметим, что из пунктов A и G нет дороги в населённые пункты C и E, из которых идут 2 дороги. Следовательно, пункты 6 и 7 это либо A, либо G.

Ответ: 67.

Примеры разбора задач.

1. Кодирование растровых изображений.

Задача 1: Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 128 на 128 пикселей  при условии, что в изображении могут использоваться 32 различных цвета? В ответе запишите только целое число, единицу измерения писать не нужно.

Решение:

Для хранения растрового изображения нужно выделить в памяти I = Р · i  битов, где Р – количество пикселей и i – глубина цвета (разрядность кодирования).

Формула для нахождения количества цветов в используемой палитре:  N=2i, где N – количество цветов и i – глубина цвета (разрядность кодирования).

Найдем разрядность кодирования:

N=2i=32=25, отсюда i = 5 бит. 

Найдем объем памяти: I = Р * i = 128*128*5=5*27*27=5*214бит=(1Кбайт=213бит)=

5*214/213Кбайт=10 Кбайт

Ответ: 10

Задача 2: Рисунок размером 32 на 1024 пикселей занимает в памяти 28 Кбайт (без учёта сжатия). Найдите максимально возможное количество цветов в палитре изображения.

Решение:

Для хранения растрового изображения нужно выделить в памяти I = Р · i  битов, где Р – количество пикселей и i – глубина цвета (разрядность кодирования).

Значит, i=I/P=28 Кбайт/32*1024==(1Кбайт=213бит)= 28*213/25*210=28/4=7бит

Формула для нахождения количества цветов в используемой палитре:  N=2i, где N – количество цветов и i – глубина цвета (разрядность кодирования).

N=2i=27=128 цветов

Ответ: 128

Задача 3: Рисунок размером 512 на 128 пикселей занимает в памяти 32 Кбайт (без учёта сжатия). Найдите максимально возможное количество цветов в палитре изображения.

Решение:

Для хранения растрового изображения нужно выделить в памяти I = Р · i  битов, где Р – количество пикселей и i – глубина цвета (разрядность кодирования).

Значит, i=I/P=32 Кбайт/512*128=(1Кбайт=213бит)= 32*213/29*27=32/8=4бит

Формула для нахождения количества цветов в используемой палитре:  N=2i, где N – количество цветов и i – глубина цвета (разрядность кодирования).

N=2i=24=16 цветов

Ответ: 16

Задача 4: После преобразования растрового 256-цветного графического файла в 16-цветный формат его размер уменьшился на 15 Кбайт. Каков был размер исходного файла в Кбайтах?

Решение:

Формула для нахождения количества цветов в используемой палитре:  N=2i, где N – количество цветов и i – глубина цвета (разрядность кодирования).

Найдем разрядность кодирования256-цветного графического файла:

N=2i=256=28, отсюда i1 = 8 бит. 

Найдем разрядность кодирования16-цветного графического файла:

N=2i=16=24, отсюда i2 = 4 бит. 

По условию задачи, I2 = I1 – 15

I2 = I1 – 15

Р * i2= Р * i1-15

Р=15/( i1-i2)=15 Кбайт/4

Найдем объем памяти: I1 = Р * i1=15 Кбайт/4 * 8=30 Кбайт

Ответ: 30

Задача 5: После преобразования растрового графического файла его объем уменьшился в 2 раза. Сколько цветов было в палитре первоначально, если после преобразования было получено растровое изображение того же разрешения в 16-цветной палитре?

Решение:

Формула для нахождения количества цветов в используемой палитре:  N=2i, где N – количество цветов и i – глубина цвета (разрядность кодирования).

Найдем разрядность кодирования 16-цветного графического файла:

N=2i=16=24, отсюда i2 = 4 бит. 

Для хранения растрового изображения нужно выделить в памяти I = Р · i  битов, где Р – количество пикселей и i – глубина цвета (разрядность кодирования).

По условию задачи, I2 = I1/2 

Р * i2= Р * i1/2

i1=2* i2=4*2=8 бит

N=2i=28=256 цветов

Ответ: 10

2. Кодирование звука. Скорость передачи информации.

Задача 1: Производится двухканальная (стерео) звукозапись с частотой дискретизации 48 кГц и глубиной кодирования 24 бита. Запись длится 1 минуту, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?

1) 0,3         2) 4        3)  16        4)  132

Решение:

Для хранения информации о звуке длительностью  секунд, закодированном с частотой дискретизации Гц и глубиной кодирования бит требуется I=B*f*t бит памяти. При двухканальной записи (стерео)  объем памяти, необходимый для хранения данных одного канала, умножается на 2. Для упрощения ручных расчетов можно использовать приближённые равенства: 1 мин = 60 сек ≈ 64 сек = 26 сек, 1000 ≈ 1024 = 210, тогда         

F = 48 кГц = 48 * 210 Гц                            

I=2 * 24 * 48 * 210 * 26 = 18*223 бит =(1Мбайт=223бит)=18Мбайт   

Ответ: 3

Задача 2: Производится двухканальная (стерео) звукозапись с частотой дискретизации 22 кГц и глубиной кодирования 24 бита. Запись длится 2 минуты, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?

1) 11         2) 12        3)  13        4)  15

Решение:

Для хранения информации о звуке длительностью  секунд, закодированном с частотой дискретизации Гц и глубиной кодирования бит требуется I=B*f*t бит памяти. При двухканальной записи (стерео)  объем памяти, необходимый для хранения данных одного канала, умножается на 2. Для упрощения ручных расчетов можно использовать приближённые равенства: 1 мин = 60 сек ≈ 64 сек = 26 сек, 1000 ≈ 1024 = 210, тогда         

F = 22 кГц = 22 * 210 Гц,  2 мин = 2*26 сек                           

I=2 * 24 * 22 * 210 * 27 = 3*11*222 бит =(1Мбайт=223бит) ≈16Мбайт   

Ответ: 4

Задача 3: Производится одноканальная (моно) звукозапись с частотой дискретизации 128 Гц. При записи использовались 64 уровня дискретизации. Запись длится 6 минут 24 секунд, её результаты записываются в файл, причём каждый сигнал кодируется минимально возможным и одинаковым количеством битов. Какое из приведённых ниже чисел наиболее близко к размеру полученного файла, выраженному в килобайтах?

1) 24         2) 36         3) 128         4) 384

Решение:

Для хранения информации о звуке длительностью  секунд, закодированном с частотой дискретизации Гц и глубиной кодирования бит требуется I=B*f*t бит памяти.

t=6 мин 24 сек=384 

При записи использовались 64 уровня дискретизации, найдем глубину кодирования:

N=2В=64=26, тогда B=6 бит.

I=6 * 128 * 384=36*213 бит=(1Кбайт=213бит) = 36 Кбайт 

Ответ: 2

Задача 4: Производится одноканальная (моно) звукозапись с частотой дискретизации 64 Гц. При записи использовались 64 уровня дискретизации. Запись длится 5 минут 20 секунд, её результаты записываются в файл, причём каждый сигнал кодируется минимально возможным и одинаковым количеством битов. Какое из приведённых ниже чисел наиболее близко к размеру полученного файла, выраженному в килобайтах?

1) 10         2) 15         3) 32         4) 64

Решение:

Для хранения информации о звуке длительностью  секунд, закодированном с частотой дискретизации Гц и глубиной кодирования бит требуется I=B*f*t бит памяти.

t=5 мин 20 сек=320 сек 

При записи использовались 64 уровня дискретизации, найдем глубину кодирования:

N=2В=64=26, тогда B=6 бит.

I=6 * 64 * 320=15*213 бит =(1Кбайт=213бит) = 15 Кбайт 

Ответ: 2

Задача 5: Производилась двухканальная (стерео) звукозапись с частотой дискретизации 64 кГц и 24-битным разрешением. В результате был получен файл размером 48 Мбайт, сжатие данных не производилось. Определите приблизительно, сколько времени (в минутах) проводилась запись. В качестве ответа укажите ближайшее к времени записи целое число.

Решение:

Для хранения информации о звуке длительностью  секунд, закодированном с частотой дискретизации Гц и глубиной кодирования бит требуется I=B*f*t бит памяти. При двухканальной записи (стерео)  объем памяти, необходимый для хранения данных одного канала, умножается на 2. Для упрощения ручных расчетов можно использовать приближённые равенства: 1 мин = 60 сек ≈ 64 сек = 26 сек, 1000 ≈ 1024 = 210, тогда         

F = 64 кГц = 64 * 210 Гц,  

Определим приблизительно, сколько времени (в минутах) проводилась запись: t= I/2*B*f

I = 48 Мбайт / 2*24*64 *210 = 48*223/24*217= 128 сек ≈ 2 мин

Ответ: 2

Задача 6: Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 80 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 3 раза выше и частотой дискретизации в 4 раз меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б за 15 секунд. Во сколько раз скорость пропускная способность канала связи с городом Б выше, чем канала связи с городом А? В ответе запишите только целое число.

Решение:

Для хранения информации о звуке длительностью  секунд, закодированном с частотой дискретизации Гц и глубиной кодирования бит требуется I=B*f*t бит памяти. Объем переданной информации I вычисляется по формуле  I=q*t, где  – пропускная способность канала (в битах в секунду или подобных единицах), а  – время передачи.

Пусть в х раз пропускная способность канала связи с городом Б выше, чем канала связи с городом А, тогда q2 = x*q1 , с другой стороны q=I/t, т.е.

q1=I1/t1, q2=I2/t2 , а I2=I1*3/4      

х*I1/t1= I1*3/(4* t2 )  

x= 3*t1/(4* t2 ) =3*80/(4*15)=4

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

Ответ: 4

Задача 7: Музыкальный фрагмент был записан в формате моно, оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла – 24 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате стерео (двухканальная запись) и оцифрован с разрешением в 4 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Укажите размер файла в Мбайт, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно.

Решение:

Для хранения информации о звуке длительностью  секунд, закодированном с частотой дискретизации Гц и глубиной кодирования бит требуется I=B*f*t бит памяти. При двухканальной записи (стерео)  объем памяти, необходимый для хранения данных одного канала, умножается на 2.

I2=2*I1*4/1,5=48Мб*4/1,5=128 Мбайт

Ответ: 128

3. Определение скорости передачи информации при заданной пропускной способности канала.

Задача 1: Сколько секунд потребуется обычному модему, передающему сообщения со скоростью 28800 бит/с, чтобы передать цветное растровое изображение размером 640х480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами?

Решение:

Объем переданной информации I вычисляется по формуле  I=q*t, где  – пропускная способность канала (в битах в секунду или подобных единицах), а  – время передачи. Для хранения растрового изображения нужно выделить в памяти I = Р · i  битов, где Р – количество пикселей и i – глубина цвета (разрядность кодирования).

Найдем объем памяти: I=640 * 480 * 3 байт=(1байт=8бит)=10*26*3*24*3*23=900*213бит.

Найдем время передачи сообщения: t=900*213/225*27=4*26=256 сек

Задача 2: Скорость передачи данных через ADSL-соединение равна 128000 бит/с. Передача текстового файла через это соединение заняла 1 минуту. Определите, сколько символов содержал переданный текст, если известно, что он был представлен в 16-битной кодировке Unicode.

Решение:

Объем переданной информации I вычисляется по формуле  I=q*t, где  – пропускная способность канала (в битах в секунду или подобных единицах), а  – время передачи.

Найдем объем памяти: I=128000*60=1000*27*60бит.

С другой стороны объем текстового сообщения вычисляется по формуле: I=K*i, где К-количество символов в сообщении, i- количество информации, необходимое для кодирования одного символа.

К = 1000*27*60 /16 = 1000*27*60 /24= 480 000

Ответ: 480000

Задача 3: Скорость передачи данных через ADSL-соединение равна 128000 бит/с. Сколько времени (в секундах) займет передача файла объемом 625 Кбайт по этому каналу?

Решение:

Объем переданной информации I вычисляется по формуле  I=q*t, где  – пропускная способность канала (в битах в секунду или подобных единицах), а  – время передачи.

Найдем время передачи файла:

t=I/q = 625Кбайт/ 1000 *27=(1Кбайт=213бит)= 625*213/1000 *27=625*64/1000=40 сек

Ответ: 40

Задача 4: У Васи есть доступ к Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения им информации 217 бит в секунду. У Пети нет скоростного доступа в Интернет, но есть возможность получать информацию от Васи по низкоскоростному телефонному каналу со средней скоростью 216 бит в секунду. Петя договорился с Васей, что тот будет скачивать для него данные объемом 8 Мбайт по высокоскоростному каналу и ретранслировать их Пете по низкоскоростному каналу. Компьютер Васи может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах), с момента начала скачивания Васей данных, до полного их получения Петей? В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Решение:

Объем переданной информации I вычисляется по формуле  I=q*t, где  – пропускная способность канала (в битах в секунду или подобных единицах), а  – время передачи.

t = I/q

Первые 1024 Кбайт Вася скачивает со скоростью 217 бит в секунду, тогда время передачи: t1= 1024 Кб/217 = (1Кбайт=213 бит) = 210 *213/ 217= 26=64 сек

Петя скачивает данные объемом 8 Мбайт со скоростью 216 бит в секунду, тогда время передачи: t2= 8Мб/216 = (1Мбайт=223 бит) = 8*223/ 216= 8*27=8*128=1024 сек

Общее время: t1+t2=64+1024=1088 сек

Ответ: 1088

Домашняя работа

1. На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Укажите номера, которые могут соответствовать пунктам Д и Е. В ответе запишите эти номера в порядке возрастания без пробелов и знаков препинания.

2. Логическая функция F задаётся выражением (x ∨ y) ∧ ¬(y ≡ z) ∧ ¬w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала  — буква, соответствующая первому столбцу; затем  — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

3. Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А  — 000, Б  — 1, В  — 011.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

4. Автомат обрабатывает натуральное число N по следующему алгоритму:

1.  Строится двоичная запись числа N.

2.  В конец записи (справа) добавляется (дублируется) последняя цифра.

3.  Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.

4.  Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число N = 13. Алгоритм работает следующим образом:

1.  Двоичная запись числа N: 1101.

2.  Дублируется последняя цифра, новая запись 11011.

3.  Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.

4.  На экран выводится число 54.

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

5.  Черепахе был дан для исполнения следующий алгоритм:

Повтори 6 [Направо 36 Вперёд 10 Направо 36]

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

6. В информационной системе хранятся изображения размером 224 x 128 пикселей, содержащие не более 64 различных цветов. Коды пикселей записываются подряд, никакая дополнительная информация об изображении не сохраняется, данные не сжимаются. Сколько Кбайт нужно выделить для хранения одного изображения? В ответе укажите только целое число  — количество Кбайт, единицу измерения указывать не надо.

7.  Все 4-буквенные слова, составленные из букв М, С, Т, Ф, записаны

в алфавитном порядке.

Вот начало списка:

1.  ММММ

2.  МММС

3.  МММТ

4.  МММФ

5.  ММСМ

……

Запишите слово, которое стоит на 138-м месте от начала списка.

8. Откройте файл электронной таблицы, содержащей вещественные числа  — результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев.

Сколько раз встречалась температура, ниже округленного до десятых среднего арифметического значения всех чисел в таблице? Файл 9.xlsx

9. С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «вы» или «Вы» в тексте романа в стихах А. С. Пушкина «Евгений Онегин». Другие формы слова «вы» учитывать не следует. В ответе укажите только число. Файл 10.docx

10. Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника и срок действия пропуска. Личный код состоит из 14 символов, каждый из которых может быть одной из 26 заглавных латинских букв или 10 цифр. Для записи кода на пропуске используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов. Срок действия записывается как номер года (число от 0 до 80, означающее год от 2000 до 2080) и номер месяца (число от 1 до 12). Номер года и номер месяца записаны на пропуске как двоичные числа, каждое из них занимает минимально возможное количество битов.

Вся информация на пропуске упакована так, чтобы занимать минимально возможное количество байтов. Сколько байтов занимает вся информация на пропуске? В ответе запишите только целое число  — количество байтов.

11. Дана программа для редактора:

НАЧАЛО

    ПОКА нашлось (1111)

        заменить (1111, 22)

        заменить (222, 1)

    КОНЕЦ ПОКА

КОНЕЦ

Известно, что исходная строка содержала больше 200 единиц и не содержала других цифр. При какой наименьшей длине исходной строки результат работы данной программы будет содержать наибольшее возможное число единиц?

12. На рисунке  — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Е и при этом не проходящих через пункт Л?

13.  Операнды арифметического выражения записаны в системе счисления с основаниями 13 и 18:

xA0413 + 1Dx318

В записи чисел переменной x обозначена неизвестная цифра из алфавита десятичной системы счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 184. Для найденного значения x вычислите частное от деления значения арифметического выражения на 184 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.

(переводим слагаемые в 10с/с и подбираем х)

14. Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5  =  11102&01012  =  01002  =  4.

Для какого наибольшего целого числа А формула

(x&51 = 0) ∨ ((x&41 = 0) → (x&А = 0))

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

15. Алгоритм вычисления значения функции F(n), где n  — натуральное число, задан следующими соотношениями:

 F(n) = n + 1 при n ≤ 2;

F(n) = 2 · F(n − 1) + F(n − 2) при n > 2.

Чему равно значение функции F(4)? В ответе запишите только натуральное число.

16. Назовём натуральное число подходящим, если ровно два из его делителей входят в список (5, 11, 17, 19). Найдите все подходящие числа, принадлежащих отрезку [10 000; 20 000] В ответе запишите два целых числа: сначала количество, затем наименьшее число.

17. Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх  — в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

Откройте файл 18.xlsx. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответ запишите два числа друг за другом без разделительных знаков  — сначала максимальную сумму, затем минимальную.

18.  Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 36 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 35.

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 36 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 35.

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

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

20.  Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 36 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 35.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

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

21.  Исполнитель РазДваТри преобразует число на экране.

У исполнителя есть три команды, которым присвоены номера:

1.  Прибавить 1

2.  Умножить на 2

3.  Умножить на 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья умножает на 3.

Программа для исполнителя РазДваТри  — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 50, и при этом траектория вычислений содержит число 14 и не содержит числа 16?

Траектория вычислений  — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 3 траектория будет состоять из чисел 9, 10, 20.

Домашнее задание.

Задание 8

Вася составляет 4-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задание 9

Откройте файл электронной таблицы 9-0.xls, содержащей вещественные числа – результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. Определите, сколько раз в июне средняя температура с 19:00 до 22:00 оказывалась выше средней температуры с 05:00 до 08:00 на 5 и более градусов. В ответе введите только одно число – количество таких дней.

Задание 10

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается предлог «При» (с заглавной буквы) в тексте романа А.С. Пушкина «Капитанская дочка» (файл 10-34.docx). В ответе укажите только число.

Задание 12.

Ребята, простым числом называется число, которое делится на 1 и на само себя, например 3, 7, 11….

Задание 13

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.

Задание 14

Значение выражения 13∙6251320 + 12∙1251230 – 14∙251140 – 13∙51050 – 2500 записали в системе счисления с основанием 25. Определите количество значащих нулей в этой записи.

Задание 18

Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку влево или на одну клетку вниз. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из правого верхнего угла в левый нижний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную.