close

Вход

Забыли?

вход по аккаунту

?

andreev molchanov

код для вставкиСкачать
Федеральное агенТство по образованию
Государственное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ИНФОРМАТИКА И ИКТ
Методические материалы
для подготовки к сдаче
единого государственного экзамена
Санкт-Петербург
2009
Составители: Андреев С. Д., Молчанова М. А., Шарапова О. М.,
Шевяков К. В.
Рецензент кандидат технических наук, доцент Беззатеев С. В.
Верстальщик А. Н. Колешко
Сдано в набор 12.10.09. Подписано к печати 23.11.09.
Формат 60×84 1/16. Бумага офсетная. Печ. л. 6,0.
Тираж 200 экз. Заказ № 750.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© ГУАП, 2009
Введение
Для поступления в высшее учебное заведение (вуз) абитуриенту необходимо пройти вступительные испытания в форме Единого государственного экзамена (ЕГЭ). На сегодняшний день обязательны сдача ЕГЭ по математике и русскому языку, а также по профильным школьным дисциплинам. Список вступительных экзаменов утверждается Министерством Образования РФ и содержит,
как правило, три-четыре экзамена для каждой специальности. При
этом один из экзаменов является профильным. Информатика как
профильный вступительный экзамен указана в большом числе специальностей.
Согласно спецификации ЕГЭ по информатике, подготовленной
Федеральным институтом педагогических измерений (ФИПИ), назначение экзаменационной работы – оценить общеобразовательную
подготовку по информатике выпускников XI (XII) классов общеобразовательных учреждений с целью зачисления в учреждения среднего и высшего профессионального образования.
Структура экзамена
Экзаменационная работа содержит всего 32 задания и состоит из
трех частей:
Часть 1 (А) содержит 18 заданий базового, повышенного и высокого уровней сложности. В этой части собраны задания с выбором
ответа, подразумевающие выбор одного правильного ответа из четырех предложенных. Задания выполняются на черновике, а ответы заносятся в специальный бланк для ответов Части А.
Часть 2 (В) содержит 10 заданий базового, повышенного и высокого уровней сложности. В этой части собраны задания с краткой
формой ответа, подразумевающие самостоятельное формулирование и ввод ответа в виде последовательности символов. Задания выполняются на черновике, а ответы заносятся в специальный бланк
для ответов Части В.
Часть 3 (С) содержит 4 задания, первое из которых повышенного
уровня сложности, остальные три задания – высокого уровня слож3
ности. Задания этой части подразумевают запись в произвольной
форме развернутого ответа на специальном бланке.
Содержание экзаменационной работы охватывает основное содержание курса информатики, а также информационных и коммуникационных технологий (ИКТ), важнейшие его темы, наиболее значимый в них материал, однозначно трактуемый в большинстве преподаваемых в школе вариантов курса информатики и
ИКТ. В работе представлены задания из следующих тематических
блоков:
1. «Информация и ее кодирование»
2. «Алгоритмизация и программирование»
3. «Основы логики»
4. «Моделирование и компьютерный эксперимент»
5. «Программные средства информационных и коммуникационных технологий»
6. «Технология обработки графической и звуковой информации»
7. «Технология обработки информации в электронных таблицах»
8. «Технология хранения, поиска и сортировки информации в
базах данных»
9. «Телекоммуникационные технологии»
10. «Технологии программирования»
Часть 1 содержит задания из всех тематических блоков, кроме
заданий по телекоммуникационным технологиям и технологии
программирования. В этой части имеются задания всех уровней
сложности, однако большинство заданий рассчитаны на небольшие
временные затраты и базовый уровень знаний экзаменуемых.
Часть 2 включает задания по темам «Информация и ее кодирование», «Основы логики», «Алгоритмизация и программирование»,
«Телекоммуникационные технологии». В части 2 большинство заданий относится к повышенному уровню, а также имеется одно задание высокого уровня, поэтому выполнение заданий части 2 в целом потребует большего времени и более глубокой подготовки.
Задания части 3 направлены на проверку сформированности
важнейших умений записи и анализа алгоритмов, предусмотренных требованиями к обязательному уровню подготовки по информатике и ИКТ учащихся средних общеобразовательных учреждений. Эти умения проверяются на повышенном и высоком уровне
сложности. Также на высоком уровне сложности проверяются умения по теме «Технологии программирования».
Распределение заданий по частям экзаменационной работы представлено в табл. 1.
4
Таблица 1
Распределение заданий по частям экзаменационной работы
Части
работы
Процент максимального первичЧисло Максимального балла за задания данной чазада- ный первичсти от максимального первичного
ний
ный балл
балла за всю работу (40)
Часть
1
Часть
2
Часть
3
18
18
45%
10
10
25%
4
12
30%
Итого:
32
40
100%
Тип заданий
С выбором
ответа
С кратким
ответом
С развернутым ответом
Отбор содержания, подлежащего проверке в экзаменационных
работах ЕГЭ, осуществляется на основе обязательного минимума
содержания среднего (полного) общего образования федерального
компонента государственного образовательного стандарта. Распределение заданий по разделам курса информатики и ИКТ представлено в табл. 2.
Таблица 2
Распределение заданий по разделам курса информатики
№
1
2
3
4
5
6
7
Название раздела
Информация и ее кодирование
Алгоритмизация и программирование
Основы логики
Моделирование и компьютерный эксперимент
Программные средства
ИКТ
Технология обработки
графической и звуковой
информации
Технология обработки информации в электронных
таблицах
Число
заданий
Максимальный
первичный балл
Процент максимального первичного балла за
задания данного вида
деятельности от максимального первичного
балла за всю работу (40)
8
8
20%
9
13
32,5%
5
5
12,5%
1
1
2,5%
1
1
2,5%
1
1
2,5%
2
2
5%
5
Окончание табл. 2
№
8
9
10
Название раздела
Технология хранения, поиска и сортировки информации в базах данных
Телекоммуникационные
технологии
Технологии программирования
Итого:
Число
заданий
Максимальный
первичный балл
Процент максимального первичного балла за
задания данного вида
деятельности от максимального первичного
балла за всю работу (40)
1
1
2,5%
2
2
5%
2
6
15%
32
40
100%
Некоторые темы, представленные в кодификаторе элементов содержания по информатике и ИКТ для составления контрольных
измерительных материалов (КИМ) и входящие в обязательный минимум содержания образования, такие как «Социальная информатика», «Основные устройства информационных и коммуникационных технологий», «Технология обработки текстовой информации»,
не вошли в содержание ЕГЭ по ряду причин. Во-первых, знания по
этим вопросам достаточно трудно формализуются и плохо проверяются методами, принятыми в едином государственном экзамене,
и, во-вторых, предыдущие результаты ЕГЭ показывают, что на базовом уровне эти темы усваиваются очень хорошо и ответы на эти
задания недостаточно дифференцируют учащихся с точки зрения
вступительного экзамена в вуз.
В КИМ по информатике и ИКТ не включены задания, требующие простого воспроизведения знания терминов, понятий, величин, правил (такие задания слишком просты для выполнения). При
выполнении любого из заданий КИМ от экзаменуемого требуется
решить какую-либо задачу: либо прямо использовать известное
правило, алгоритм, умение, либо выбрать из общего количества изученных понятий и алгоритмов наиболее подходящее и применить
его в известной либо новой ситуации.
На уровне воспроизведения знаний проверяется такой фундаментальный теоретический материал, как:
• единицы измерения информации;
• принципы кодирования;
• системы счисления;
• моделирование;
6
• понятие алгоритма, его свойств, способов записи;
• основные алгоритмические конструкции;
• основные элементы программирования;
• основные элементы математической логики;
• основные понятия, используемые в информационных и коммуникационных технологиях.
Материал на проверку сформированности умений применять
свои знания в стандартной ситуации входит во все три части экзаменационной работы. Это следующие умения:
• подсчитывать информационный объем сообщения;
• осуществлять перевод из одной системы счисления в другую;
• осуществлять арифметические действия в двоичной, восьмеричной и шестнадцатеричной системах счисления;
• использовать стандартные алгоритмические конструкции при
программировании;
• формально исполнять алгоритмы, записанные на естественных и алгоритмических языках, в том числе на языках программирования;
• создавать и преобразовывать логические выражения;
• формировать для логической функции таблицу истинности и
логическую схему;
• оценивать результат работы известного программного обеспечения;
• формулировать запросы к базам данных и поисковым системам.
Материал на проверку сформированности умений применять
свои знания в новой ситуации входит во все три части экзаменационной работы. Это следующие сложные умения:
• решать логические задачи;
• анализировать текст программы с точки зрения соответствия
записанного алгоритма поставленной задаче и изменять его в соответствии с заданием;
• реализовывать сложный алгоритм с использованием современных систем программирования.
Распределение заданий по видам проверяемой деятельности
представлено в табл. 3.
Часть 1 (A) экзаменационной работы содержит задания, большинство из которых относятся к базовому и повышенному уровням
сложности, и одно задание высокого уровня.
Часть 2 (B) содержит в основном задания повышенного уровня, а
также по одному заданию базового и высокого уровней сложности.
7
Таблица 3
Распределение заданий по видам проверяемой деятельности
Код
1
2
3
МаксиЧисло
мальный
Виды деятельности задапервичный
ний
балл
Процент максимального первичного балла за задания данного
вида деятельности от максимального первичного балла за
всю работу (40)
Воспроизведение
представлений
или знаний
Применение
знаний и умений
в стандартной
ситуации
Применение знаний и умений в
новой ситуации
6
6
15%
17
18
45%
9
16
40%
Итого:
32
40
100%
Задания Части 3 (С) относятся к повышенному и высокому уровням.
Предполагаемый процент выполнения заданий базового уровня – 60–90%.
Предполагаемый процент выполнения заданий повышенного
уровня – 40–60%.
Предполагаемый процент выполнения заданий части С – менее
40%.
Для оценки достижения базового уровня используются задания
с выбором ответа и кратким ответом. Достижение уровня повышенной подготовки проверяется с помощью заданий с выбором ответа,
Таблица 4
Распределение заданий по уровням сложности
Уровень сложности заданий
Число
заданий
Максимальный первичный балл
Процент максимального первичного балла за задания данного вида деятельности
от максимального первичного балла за
всю работу (40)
Базовый (Б)
17
17
42,5%
Повышенный (П)
10
12
30%
Высокий (В)
5
11
27,5%
Итого:
32
40
100%
8
с кратким и развернутым ответом. Для проверки достижения высокого уровня подготовки в экзаменационной работе используются
задания с кратким и развернутым ответом. Распределение заданий
по уровням сложности представлено в табл. 4.
Проведение экзамена
На выполнение экзаменационной работы отводится 4 часа (240
минут). На выполнение заданий Части 1 (А) и Части 2 (В) рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий Части
3 (С) рекомендуется отводить 2,5 часа (150 минут).
Параллельность (эквивалентность) различных вариантов работы
обеспечивается за счет подбора определенного количества однотипных, примерно одинаковых по уровню сложности заданий по конкретной теме курса информатики и ИКТ, расположенных на одних
и тех же местах в различных вариантах проверочной работы.
Задания в экзаменационной работе оцениваются разным числом
баллов в зависимости от их типа и уровня сложности.
Выполнение каждого задания Части 1 (А) и Части 2 (В) оценивается в один балл. Задание Части 1 (А) считается выполненным, если
экзаменуемый дал ответ, соответствующий коду верного ответа.
За выполнение каждого задания присваивается (в дихотомической системе оценивания) либо ноль баллов («задание не выполнено»), либо один балл («задание выполнено»). Ответы на задания Части 1 (А) и Части 2 (В) автоматически обрабатываются после сканирования бланков ответов. Максимальное количество первичных
баллов, которое можно получить за выполнение заданий Части 1
(А), – 18.
За выполнение каждого задания Части 2 (В) присваивается (в дихотомической системе оценивания) либо ноль баллов («задание не
выполнено»), либо один балл («задание выполнено»). Максимальное
количество баллов, которое можно получить за выполнение заданий Части 2 (В), – 10.
Выполнение заданий Части 3 (С) оценивается от нуля до четырех
баллов. Ответы на задания Части 3 (С) проверяются и оцениваются экспертами (устанавливается соответствие ответов определенному перечню критериев). Максимальное количество баллов, которое
можно получить за выполнение заданий Части 3 (С), – 12.
Максимальное количество первичных баллов, которое можно получить за выполнение всех заданий экзаменационной работы, – 40.
Работа выполняется учащимися без использования компьютеров и других технических средств. Вычислительная сложность за9
даний не требует использования калькуляторов, поэтому в целях
обеспечения равенства всех участников экзамена использование
калькуляторов на экзаменах не разрешается.
На экзамене в аудиторию не допускаются преподаватели информатики и ИКТ. Соблюдение единой инструкции по проведению экзамена позволяет обеспечить соблюдение единых условий без привлечения лиц с профильным образованием по информатике и ИКТ.
Проверку ответов на задания Части 3 (С) осуществляют эксперты, прошедшие специальную подготовку для проверки заданий
ЕГЭ в соответствии с Методическими рекомендациями по оцениванию заданий с развернутым ответом, подготовленными ФИПИ.
Материалы для подготовки
К экзамену можно готовиться по учебникам, включенным в «Федеральный перечень учебников, рекомендованных (допущенных)
Министерством образования и науки Российской Федерации к использованию в образовательном процессе в общеобразовательных
учреждениях». Перечень учебников размещен на сайте Министерства образования и науки Российской Федерации (www.mon.gov.ru)
в разделе «Документы министерства».
ФИПИ рекомендует также использовать пособия, имеющие гриф
ФИПИ, и пособия, подготовленные авторскими коллективами ФИПИ в рамках совместных проектов с издательствами. Информация
об этих изданиях оперативно размещается на сайте www.fipi.ru в
разделе «Экспертный совет ФИПИ».
Настоящее пособие также может быть использовано как для самостоятельной подготовки к единому государственному экзамену
по информатике, так и для закрепления лекционного материала соответствующих курсов подготовки. Основная часть методического
пособия содержит 10 разделов, каждый из которых соответствует
одному тематическому блоку курса информатики и ИКТ, включенному в ЕГЭ. В начале каждого раздела указывается число задач ЕГЭ
по данной тематике. Объем раздела пропорционален указанному
числу задач.
Каждый раздел содержит выдержку из кодификатора элементов
содержания по информатике и ИКТ, составленного ФИПИ. В кодификаторе каждый контролируемый элемент содержания имеет
свой порядковый номер. Жирным шрифтом указаны крупные блоки содержания, которые ниже разбиты на более мелкие элементы.
Каждому заданию ЕГЭ присвоен номер того элемента содержания в
10
кодификаторе, на проверку которого, прежде всего, оно нацелено.
Если задание проверяет содержание всего крупного блока, указывается сокращенный номер элемента.
Далее следует подраздел, содержащий краткие теоретические
сведения по данной теме, который завершается выдержкой из обобщенного плана экзаменационной работы по информатике. План ставит в соответствие каждой задаче ЕГЭ проверяемый элемент кодификатора и его код, код вида деятельности согласно таблицы 3, уровень сложности задания (Б – базовый, П – повышенный, В – высокий), максимальный балл за выполнение задания и примерное время его выполнения. В заключение каждого раздела в соответствии с
планом экзамена даются примеры заданий ЕГЭ с разбором. Примеры подготовлены из фактического материала ЕГЭ прошлых лет.
Заключительный раздел методического пособия содержит демонстрационный вариант единого государственного экзамена по
информатике за 2009 год с ответами на задания из Части 1 (A) и
2 (B). Список литературы содержит материалы, которые могут быть
использованы в процессе самостоятельной подготовки к ЕГЭ.
11
Информация и ее кодирование
Число заданий: 8
Кодификатор
Код
блока
Код контролируемого
элемента
1
1.1
1.1.1
1.1.2
1.1.3
1.1.4
1.1.5
1.1.6
1.1.7
1.1.8
Элементы содержания,
проверяемые заданиями КИМ
Информационные процессы и системы
Информация и ее кодирование
Различные подходы к определению понятия «информация». Виды информационных процессов.
Информационный аспект в деятельности человека;
информационное взаимодействие в простейших социальных, биологических и технических системах.
Язык как способ представления и передачи информации.
Методы измерения количества информации: вероятностный и алфавитный.
Единицы измерения количества информации.
Числовые параметры информационных объектов и
процессов: объем памяти, необходимый для хранения
информации, скорость обработки информации.
Процесс передачи информации. Виды и свойства
источников и приемников информации. Сигнал,
кодирование и декодирование, причины искажения
информации при передаче.
Скорость передачи информации и пропускная способность канала связи.
Представление числовой информации. Сложение и
умножение в разных системах счисления.
Кодирование текстовой информации. Кодировка
ASCII. Основные используемые кодировки кириллицы.
Теоретические сведения
Информация относится к фундаментальным, неопределяемым
понятиям науки информатики. Тем не менее, смысл этою понятия
должен быть разъяснен. Термин информация происходит от латинского слова informatio, что означает сведения, разъяснения, изложение. В настоящее время наука пытается найти общие свойства и
закономерности, присущие многогранному понятию информация,
но пока это понятие во многом остается интуитивным и получает
12
различные смысловые наполнения в различных отраслях человеческой деятельности:
• в быту информацией называют любые данные, сведения, знания, которые кого-либо интересуют. Например, сообщение о какихлибо событиях, о чьей-либо деятельности и т.п.;
• в технике под информацией понимают сообщения, передаваемые в форме знаков или сигналов (в этом случае имеется источник
сообщений, получатель (приемник) сообщений, канал связи);
• в кибернетике под информацией понимают ту часть знаний,
которая используется для ориентирования, активного действия,
управления, т.е. в целях сохранения, совершенствования, развития
системы;
• в теории информации под информацией понимают сведения
об объектах и явлениях окружающей среды, их параметрах, свойствах и состоянии, которые уменьшают степень неопределенности,
неполноты имеющихся о них знаний.
Применительно к компьютерной обработке данных под информацией понимают некоторую последовательность символических
обозначений (букв, цифр, закодированных графических образов и
звуков и т.п.), несущую смысловую нагрузку и представленную в
понятном компьютеру виде. Каждый новый символ в такой последовательности символов увеличивает информационный объем сообщения.
Информация может существовать в виде:
• текстов, рисунков, чертежей, фотографий;
• световых или звуковых сигналов;
• радиоволн;
• электрических и нервных импульсов;
• магнитных записей;
• жестов и мимики;
• запахов и вкусовых ощущений;
• хромосом, посредством которых передаются по наследству
признаки и свойства организмов.
Свойства информации (с точки зрения бытового подхода к определению информации):
• релевантность – способность информации соответствовать
нуждам (запросам) потребителя;
• полнота – свойство информации исчерпывающе (для данного
потребителя) характеризовать отображаемый объект или процесс;
• своевременность – способность информации соответствовать
нуждам потребителя в нужный момент времени;
13
• достоверность – свойство информации не иметь скрытых ошибок. Достоверная информация со временем может стать недостоверной, если устареет и перестанет отражать истинное положение дел;
• доступность – свойство информации, характеризующее возможность ее получения данным потребителем;
• защищенность – свойство, характеризующее невозможность несанкционированного использования или изменения информации;
• эргономичность – свойство, характеризующее удобство формы
или объема информации с точки зрения данного потребителя.
1 бит – минимальная единица измерения информации. При вероятностном подходе к измерению информации это количество
информации, уменьшающее неопределенность знаний в 2 раза. Количество информации (i), содержащееся в сообщении о том, что произошло одно из N равновесных событий, определяется из решения
уравнения 2i = N. Прологарифмировав это равенство по основанию
2, получим: i · log22 = log2N, следовательно, i = log2N.
Связь между единицами измерения информации:
• 1 байт = 8 бит;
• 1 Кбайт (килобайт) = 210 (1024) байт = 213 бит;
• 1 Мбайт (мегабайт) = 210 (1024) Кбайт = 220 (1 048 576) байт =
= 223 бит;
• 1 Гбайт (гигабайт) = 210 Мбайт = 220 Кбайт = 230 байт =
= 233 бит;
• 1 Тбайт (терабайт) = 210 Гбайт = 220 Мбайт = 230 Кбайт =
= 240 байт = 243 бит.
При объемном подходе к измерению информации информативность сообщения определяется количеством символов, его составляющих. Например, в алфавит мощностью N = 256 символов можно
поместить все необходимые символы: латинские и русские буквы,
цифры, знаки арифметических операций, знаки препинания и т. д.
Представим себе, что текст, состоящий из 256 символов, поступает
последовательно, и в каждый момент времени может появиться любой из них. Тогда 2i = 256, т.е. i = 8 бит.
Кодирование информации подразумевает преобразование знаков
одной знаковой системы в знаки или группы знаков другой знаковой системы. Обратное преобразование называют декодированием.
Кодирующим отображением называется такое отображение F
множества слов в некотором алфавите на множество слов в том же
или каком-то другом фиксированном алфавите. Обычно исходное
множество для кодирующего отображения F называется входным
алфавитом, а результат отображения – выходным алфавитом.
14
Применение кодирующего отображения F к любому слову из
входного алфавита называется кодированием, а само кодирующее
отображение F – кодом. То есть код – это правило, по которому осуществляется кодирование.
Кодирование может быть равномерное и неравномерное: при
равномерном кодировании все символы кодируются кодами равной
длины, а при неравномерном кодировании разные символы могут
кодироваться кодами разной длины, это затрудняет декодирование.
При кодировании информации для представления ее в памяти
компьютера используется двоичный способ, т.е. любая информация – будь то числа, текст, графическое изображение, звук или видео – представляется универсальным двоичным кодом. Алфавит
этого кода составляют символы 0 и 1. Каждая цифра машинного
кода несет 1 бит информации.
Системой счисления называется совокупность приемов наименования и записи чисел. В любой системе счисления для представления чисел выбираются некоторые символы (их называют цифрами), и числа получаются в результате каких-либо операций над
цифрами данной системы счисления.
Если значение цифры не зависит от ее местоположения в записи числа, то такая система счисления называется непозиционной.
Наиболее известным примером непозиционной системы счисления
является римская. Система называется позиционной, если значение
каждой цифры (ее вес) изменяется в зависимости от ее положения
(позиции) в последовательности цифр, изображающих число. Число
единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления. Если количество таких цифр равно Р, то система счисления называется Р-ичной. Основание системы счисления совпадает с количеством цифр, используемых для записи чисел в этой системе счисления.
Арифметические действия над числами в любой позиционной
системе счисления производятся по тем же правилам, что и в десятичной системе, так как все они основываются на правилах выполнения действий над соответствующими многочленами. При этом
можно пользоваться таблицами сложения и умножения, соответствующими данному основанию Р системы счисления.
При переводе чисел из десятичной системы счисления в систему
с основанием Р > 1 обычно используют следующий алгоритм: число делится на Р, после чего запоминается остаток от деления. Полу15
ченное частное вновь делится на Р, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю.
Остатки от деления на Р выписываются в порядке, обратном их получению.
При переводе чисел из системы счисления с основанием Р в десятичную систему счисления необходимо пронумеровать разряды
числа справа налево, начиная с нулевого. Затем вычислить сумму
произведений соответствующих значений разрядов на основание
системы счисления в степени, равной номеру разряда. Это и есть
представление исходного числа в десятичной системе счисления.
Рассмотрим системы счисления кратные 2. К ним относятся:
4 (22), 8 (22), 16 (22), 32 (22) и т.д. Эти системы счисления часто используются в архитектуре компьютера. Приведем таблицу, которая
позволяет представить числа в диапазоне от 1 до 20 в разных системах счисления и сэкономить время для перевода чисел из одной системы счисления (с.с.) в другую. Диапазон рассматриваемых чисел
может быть любым, а таблица формируется достаточно просто.
10 с.с.
2 с.с.
4 с.с.
8 с.с.
16 с.с.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
10000
10001
10010
10011
10100
1
2
3
10
11
12
13
20
21
22
23
30
31
32
33
100
101
102
103
110
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
20
21
22
23
24
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
10
11
12
13
14
Числовая информация была первым видом информации, который начали обрабатывать компьютеры, и долгое время она остава16
17
Обозначение задания
в работе
A1
A2
A3
A4
A11
B1
B3
B7
№
1
2
3
4
5
6
7
8
1.1.8
1.1.4
1.1.7
1.1.7
1.1.5
1.1.3
1.1.7
1.1.6
Умение подсчитывать информационный
объем сообщения
Знания о системах счисления и двоичном
представлении информации в памяти
компьютера
Умения выполнять арифметические
операции в двоичной, восьмеричной и
шестнадцатеричной системах счисления
Умение кодировать и декодировать информацию
Знания о методах измерения количества
информации
Представление числовой информации в
памяти компьютера. Перевод, сложение
и умножение в разных системах счисления
Умение определять скорость передачи
информации при заданной пропускной
способности канала
Коды проверяемых
элементов
содержания
по кодификатору
Кодирование текстовой информации.
Кодировка ASCII. Основные кодировки
кириллицы
Проверяемые элементы содержания
Коды видов
деятельности (табл. 3)
3
2
1
2
2
1
3
1
Уровень
сложности
задания
П
П
Б
Б
Б
Б
П
Б
Макс. балл
за выполнение задания
1
1
1
1
1
1
1
1
3
5
1
1
2
1
3
1
Примерное
время выполнения
задания
(мин.)
лась единственным видом. Для того чтобы различать положительные и отрицательные числа, в их двоичном представлении выделяется знаковый разряд. По традиции используется самый старший
(левый) бит, причем нулевое значение в нем соответствует знаку
плюс, а единичное – минусу.
Из сказанного следует, что положительные числа представляют
собой обычное двоичное изображение числа (с нулем в знаковом бите). А вот для записи отрицательных чисел используется специальный код, называемый в литературе дополнительным. Для практического получения кода отрицательных чисел используется следующий алгоритм:
• модуль числа перевести в двоичную форму;
• проинвертировать каждый разряд получившегося кода, т.е.
заменить единицы нулями, а нули – единицами;
• к полученному результату обычным образом прибавить единицу.
Примеры заданий
Задание A1. Кодирование текстовой информации. Кодировка
ASCII. Основные кодировки кириллицы
Определите информационный объем текста
Бамбарбия! Кергуду!
1) 38 бит
2) 144 бита
3) 152 бита
4) 19 бит
Решение:
• в этом тексте 19 символов (обязательно считать пробелы и знаки препинания);
• если нет дополнительной информации, считаем, что используется 8-битная кодировка (чаще всего явно указано, что кодировка
8- или 16-битная);
• поэтому в сообщении 19 · 8 = 152 бита информации (ответ 3).
Задание A2. Умение подсчитывать информационный объем сообщения
В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт.
Определите объем памяти, необходимый для хранения 20 автомобильных номеров.
1) 20 байт
2) 105 байт
3) 120 байт
4) 140 байт
18
Решение:
• всего используется 26 букв + 10 цифр = 36 символов;
• для кодирования 36 вариантов необходимо использовать 6 бит,
так как 25 = 32 < 36 £ 26 = 64 , т.е. пяти бит еще не достаточно (они
позволяют кодировать только 32 варианта), а шести уже достаточно;
• таким образом, на каждый символ нужно 6 бит (минимально
возможное количество бит);
• полный номер содержит 7 символов, каждый по 6 бит, поэтому
на номер требуется 6 ×7 = 42 бита;
• по условию каждый номер кодируется целым числом байт
(в каждом байте – 8 бит), поэтому требуется 6 байт на номер
( 5 × 8 = 40 < 42 £ 6 × 8 = 48), пяти байтов не достаточно, а шесть – минимально возможное количество;
• на 20 номеров нужно выделить 20 × 6 = 120 байт (ответ 3).
Задание A3. Знания о системах счисления и двоичном представлении информации в памяти компьютера
Для хранения целого числа со знаком используется один байт.
Сколько единиц содержит внутреннее представление числа (–78)?
1) 3
2) 4
3) 5
4) 6
Решение:
• переводим число 78 в двоичную систему счисления:
78 = 64 + 8 + 4 + 2 = 26 + 23 + 22 + 21 = 10011102;
• по условию число занимает в памяти 1 байт = 8 бит, поэтому
нужно представить число с помощью 8 разрядов;
• чтобы получилось всего 8 разрядов (бит), добавляем впереди
один ноль:
78 = 010011102;
• делаем инверсию битов (заменяем везде 0 на 1 и 1 на 0):
010011102 → 101100012;
• добавляем к результату единицу
101100012 + 1 = 101100102;
• это и есть число (–78) в двоичном дополнительно коде. В записи
этого числа 4 единицы (ответ 2).
Задание A4. Умения выполнять арифметические операции в двоичной, восьмеричной и шестнадцатеричной системах счисления
Вычислите сумму чисел x и y, при x = 1D16, y = 728 . Результат
представьте в двоичной системе счисления.
1) 100011112 2) 11001012
3) 1010112 4) 10101112
19
Решение:
• Переведем числа х и у в двоичную систему:
x = 1D16 = 111012,
y = 728 = 1110102;
• Выполним сложение: 111012 + 1110102 = 10101112 (ответ 4).
Задание A11. Умение кодировать и декодировать информацию
Для 5 букв латинского алфавита заданы их двоичные коды (для
некоторых букв – из двух бит, для некоторых – из трех). Эти коды
представлены в таблице:
A
000
B
01
C
100
D
10
E
011
Определить, какой набор букв закодирован двоичной строкой
0110100011000.
1) EBCEA
2) BDDEA
3) BDCEA
4) EBAEA
Решение:
• для кода 0110100011000 последней буквой может быть только
А (код 000), тогда остается цепочка 0110100011;
• для 0110100011 последней может быть только буква E (011),
тогда остается цепочка 0110100;
• для 0110100 последней может быть только буква C (100), тогда
остается цепочка 0110;
• для 0110 последней может быть только буква D (10), тогда остается 01 – это код буквы B;
• таким образом, получилась цепочка BDCEA (ответ 3).
Задание B1. Знания о методах измерения количества информации
В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько
бит информации несет сообщение о том, что достали клубок красной шерсти?
Решение:
• красные клубки шерсти составляют 1/8 от всех;
• сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов;
• выбор 1 из 8 вариантов – это информация в 3 бита (ответ 3).
Задание B3. Представление числовой информации в памяти компьютера. Перевод, сложение и умножение в разных системах счисления
Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2.
20
Решение:
• нужно найти все целые числа N ³ 3 , такие что остаток от деления 23 на N равен 2:
23 = k × N + 2 ,
(*)
где k  – целое неотрицательное число (0, 1, 2, …);
• k и N неизвестны, однако здесь нужно учесть то, что это целые неотрицательные числа;
• из формулы (*) получаем k × N = 21 , так что задача сводится к
тому, чтобы найти все делители числа 21, которые больше 2;
• в этой задаче есть только три таких делителя: N=3,7 и 21 (ответ 3, 7, 21).
Задание B7. Умение определять скорость передачи информации
при заданной пропускной способности канала
Скорость передачи данных через ADSL-соединение равна
512 000 бит/c. Передача файла через это соединение заняла 1 минуту. Определить размер файла в килобайтах.
Решение:
• выделим в заданных больших числах степени двойки и переведем время в секунды (чтобы «согласовать» единицы измерения), а
скорость передачи – в Кбайты/с, поскольку ответ нужно получить в
Кбайтах:
t = 1 мин = 60 с = 4 · 15 с = 22 · 15 с
q = 512000 бит/c = 512 · 1000 бит/с =
= 29 · 125 · 8 бит/с = 29 · 53 · 23 бит/с
= 212 · 53 бит/с = 29 · 53 байт/с =
29 × 53
210
Кбайт/с =
53
Кбайт/с;
2
• чтобы найти объем файла, нужно умножить время передачи
на скорость передачи:
Q = t × q = 22 ×15 с ×
53
Кбайт/с = 30 ×125 Кбайт=
2
= 3750 Кбайт (ответ 3750).
21
Алгоритмизация и программирование
Число заданий: 9
Кодификатор
Код
блока
Код контролируемого элемента
Элементы содержания,
проверяемые заданиями КИМ
1
Информационные процессы и системы
1.2
Алгоритмизация и программирование
1.2.1
Алгоритмы, виды алгоритмов, описания алгоритмов. Формальное исполнение алгоритма.
1.2.2
Использование основных алгоритмических конструкций: следование, ветвление, цикл.
1.2.3
Использование переменных. Объявление переменной (тип, имя, значение). Локальные и
глобальные переменные.
1.2.4
Работа с массивами (заполнение, считывание,
поиск, сортировка, массовые операции и др.).
1.2.5
Структурирование задачи при ее решении для
использования вспомогательного алгоритма.
Вспомогательные алгоритмы: функции и процедуры.
Теоретические сведения
В старой трактовке алгоритм – это точный набор инструкций,
описывающих последовательность действий исполнителя для достижения результата решения задачи за конечное время. По мере
развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что какие-то действия алгоритма должны быть выполнены только друг за другом, но какие-то могут быть и независимыми.
Блок-схемы являются одним из графических способов представления алгоритмов. Блок-схема состоит из блоков, соединенных линиями. Чаще всего используются блоки следующих типов:
– выполнение операции;
22
– выбор направления выполнения алгоритма в зависимости от выполнения условия;
– ввод/вывод данных;
– начало и конец алгоритма.
Группа шагов алгоритма, выполняемых последовательно друг
за другом без каких-либо условий, называется линейной последовательностью.
Äåéñòâèå 1
Äåéñòâèå 2
Ветвление представляет собой алгоритмическую конструкцию,
в которой выполнение того или иного шага зависит от истинности
условия. Говорят, что конструкция «ветвление» записана в полной
форме, если в ней присутствуют команды как для случая истинного
условия, так и для его ложности.
äà
Äåéñòâèå 1
Óñëîâèå
íåò
Äåéñòâèå 2
Конструкция ветвления в полной форме реализуется следующим образом. Если условие истинно, то выполняется действие 1,
если условие ложно, то выполняется действие 2. Если в ветвлении
присутствуют действия только для истинности или только для ложности условия, то говорят, что она записана в сокращенной форме.
Конструкция ветвления в сокращенной форме реализуется следующим образом. Если выбрано направление, в котором отсутствует
23
действие, то конструкция ветвления не выполняется и управление
получает конструкция, следующая за ветвлением.
Цикл представляет собой алгоритмическую конструкцию, в которой многократно выполняется одна и та же последовательность
шагов, называемая телом цикла. Каждое однократное исполнение
цикла называется итерацией. Если тело цикла будет выполнено N
раз, говорят, что произведено N итераций. Различают два вида циклов: циклы с заранее известным числом повторений и циклы с заранее неизвестным числом повторений. Цикл с заранее известным
числом повторений называют циклом с параметром.
В циклах с заранее неизвестным числом повторений для того,
чтобы определить момент прекращения выполнения тела цикла,
используется условие цикла. Если при истинности условия цикл
продолжается, то такое условие называется условием продолжения цикла. Если при истинности условия цикл завершается, то такое условие называется условием завершения цикла. В этом случае
цикл продолжается до тех пор, пока условие не станет истинным.
Различают циклы с проверкой условия перед выполнением очередной итерации и циклы с проверкой условия после выполнения очередной итерации. Первые называются циклами с предусловием,
вторые – с постусловием. Алгоритмическая конструкция называется вложенной, если она содержится внутри другой алгоритмической конструкции.
Çàäàíèå íà÷àëüíûõ
ïàðàìåòðîâ öèêëà
Äà
Óñëîâèå
îêîí÷àíèÿ
öèêëà
Íåò
Òåëî öèêëà
Çàäàíèå íîâûõ
çíà÷åíèé
ïàðàìåòðîâ
Âûõîä èç öèêëà
24
25
Обозначение
задания в
работе
A5
A6
A12
A18
B2
B5
B8
C2
C3
№
1
2
3
4
5
6
7
8
9
Коды проверяемых
элементов
содержания
по кодификатору
Использование переменных. Объявление переменной (тип, имя, значение). Локальные и гло1.2.3
бальные переменные
Работа с массивами (заполнение, считывание, по1.2.4
иск, сортировка, массовые операции и др.)
Формальное исполнение алгоритма, записанного
1.2.1
на естественном языке
Умение исполнить алгоритм для конкретного ис1.2.1/1.2.2
полнителя с фиксированным набором команд
Знание и умение использовать основные алгоритмические конструкции: следование, ветвление,
1.2.2
цикл
Умение исполнять алгоритм в среде формального
1.2.2
исполнителя
Умение исполнять алгоритм, записанный на есте1.2.1
ственном языке
Умения написать короткую (10 – 15 строк) простую программу обработки массива на языке
1.2.4/2.8.3
программирования или записать алгоритм на
естественном языке
Умение построить дерево игры по заданному алго1.2.1
ритму и обосновать выигрышную стратегию
Проверяемые элементы содержания
Коды видов
деятельности (табл. 3)
3
2
2
2
2
2
2
3
2
Уровень
сложности
задания
В
В
П
Б
Б
В
Б
П
Б
Макс. балл
за выполнение задания
3
2
1
1
1
1
1
1
1
30
30
10
6
1
5
2
4
2
Примерное
время выполнения
задания
(мин.)
Переменная – это величина, которая имеет имя, тип и значение;
переменная может изменяться во время выполнения программы.
Оператор присваивания служит для записи значения в переменную. Знаки +, –, · , / используются для обозначения операций сложения, вычитания, умножения и деления соответственно. Запись
вида a div b означает результат целочисленного деления a на b (остаток отбрасывается). Запись вида a mod b означает остаток от деления a на b.
Массив – это набор однотипных элементов, имеющих общее имя
и расположенных в памяти рядом друг с другом. Для обращения к
элементу массива используют квадратные скобки, запись A[i] обозначает элемент массива A с номером (индексом) i. Матрица (двумерный массив) – это прямоугольная таблица однотипных элементов. Если матрица имеет имя A, то обращение A[i,j] обозначает элемент, расположенный на пересечении строки i и столбца j.
Каждая строка матрицы – это обычный (одномерный, линейный)
массив. Для того, чтобы обработать строку i в матрице из M столбцов,
нужно использовать цикл, в котором меняется номер столбца j:
for j:=1 to M do begin
{действия с элементом A[i,j]}
end;
Каждый столбец матрицы – это обычный (одномерный, линейный) массив. Для того, чтобы обработать столбец j в матрице из N
строк, нужно использовать цикл, в котором изменяется номер строки i:
for i:=1 to N do begin
{действия с элементом A[i,j]}
end;
Примеры заданий
Задание A5. Использование переменных. Объявление переменной (тип, имя, значение). Локальные и глобальные переменные
В результате выполнения фрагмента программы
while n < > 0 do begin
write (2 * (n mod 10)+1);
n := n div 10;
end;
на экран выведено число 13717. Какое число хранилось до этого в
переменной n?
1) 716
2) 638
3) 386
4) 836
26
Решение:
• анализируя алгоритм, можно сделать вывод о том, что этот
фрагмент программы выводит на экран числа 2d1 + 1, 2d2 + 1,  , где
di  – это i-я цифра с конца числа;
• теперь можно построить такие цепочки для всех четырех ответов
716: 13315
638:
17713
386:
13177
836:
13717 совпадает с заданной (ответ 4).
Задание A6. Работа с массивами (заполнение, считывание, поиск, сортировка, массовые операции и др.)
Значения двух массивов A[1..100] и B[1..100] задаются с помощью следующего фрагмента программы:
for n:=1 to 100 do
A[n] := (n–80) * (n–80);
for n:=1 to 100 do
B[101–n] := A[n];
Какой элемент массива B будет наибольшим?
1) B[1]
2) B[21]
3) B[80]
4) B[100]
Решение:
• здесь два цикла, в первом из них заполняется массив А, во втором – массив В;
• в элемент массива A[n] записывается квадрат числа n–80; все
элементы массива А неотрицательны (как квадраты чисел);
• посмотрим, чему равны некоторые элементы массива А:
A[1] = (1–80)2 = (–79)2 = 792
A[2] = (2–80)2 = (–78)2 = 782
...
A[80] = (80–80)2 = (0)2 = 0
A[81] = (81–80)2 = (1)2 = 1
...
A[99] = (99–80)2 = 192A[100] = (100–80)2 = 202;
• таким образом, при увеличении n от 1 до 80 значение A[n]
уменьшается от 792 до нуля, а потом (для n > 80) возрастает до 202;
• отсюда следует, что максимальное значение в массиве A – это
A[1] = 792;
• во втором цикле для всех номеров n от 1 до 100 выполняется
оператор B[101–n] := A[n]; который просто переписывает элементы
массива A в массив В, «разворачивая» его в обратном порядке (элемент A[1] будет записан в B[100], а A[100] – в B[1]);
27
• A[1], наибольший элемент массива А, будет записан в B[100],
поэтому B[100] – наибольший элемент в массиве В (ответ 4).
Задание A12. Формальное исполнение алгоритма, записанного
на естественном языке
Сколько существует различных четырехзначных чисел, в записи которых используются только четные цифры?
1) 125
2) 250
3) 500
4) 625
Решение:
• первой цифрой может быть любая четная цифра, кроме нуля
(иначе число не будет четырехзначным) – это 2, 4, 6 или 8, всего 4
варианта
x
Вариантов:
?
?
?
4;
• предположим, что первая цифра выбрана; независимо от нее
на втором месте может стоять любая из четных цифр – 0, 2, 4, 6 или
8, всего 5 вариантов:
Вариантов:
x
y
4
5;
?
?
• аналогично находим, что последние две цифры также могут
быть выбраны 5-ю способами каждая, независимо друг от друга и от
других цифр (первой и второй):
Вариантов:
x
y
z
w
4
5
5
5;
• общее количество комбинаций равно произведению
4·5·5·5 = 500 (ответ 4).
Задание A18. Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд
В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции:
Длина(a) – возвращает количество символов в строке a. (Тип «целое»)
Извлечь(a,i) – возвращает i-й (слева) символ в строке a. (Тип
«строка»)
Склеить(a,b) – возвращает строку, в которой записаны сначала
все символы строки a, а затем все символы строки b. (Тип «строка»)
Значения строк записываются в одинарных кавычках (Например, a:=’дом’). Фрагмент алгоритма:
28
i := Длина(a)
k := 2
b := ‘А’
пока i > 0
нц
c := Извлечь(a,i)
b := Склеить(b,c)
i := i – k
кц
b := Склеить(b,’Т’)
Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a
было ‘ПОЕЗД’?
1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 3) ‘АДТЕТПТ’ 4) ‘АДЗОТ’
Решение:
• заметим, что последняя команда алгоритма, b := Склеить(b,’Т’),
добавляет букву ‘Т’ в конец строки b, поэтому ответ 2 – явно неверный (строка должна оканчиваться на букву ‘Т’, а не на ‘П’);
• для решения будем использовать трассировку; здесь пять переменных: a, b, c, i, k, для каждой из них выделим столбец, где будем записывать изменение ее значения
• перед выполнением заданного фрагмента мы знаем только значение a, остальные неизвестны (обозначим их знаком вопроса):
a
b
c
i
k
‘ПОЕЗД’
?
?
?
?
• первой командой длина строки a (равна 5 символам) записывается в переменную i:
a
b
c
i
k
‘ПОЕЗД’
?
?
?
?
i:=Длина(a)
5
• следующие два оператора записывают начальные значения
в k и b:
a
b
c
i
k
‘ПОЕЗД’
?
?
?
?
i:=Длина(a)
5
k:=2
b:=’А’
2
‘A’
29
• далее следует цикл пока с проверкой условия i>0 в начале цикла; сейчас i=5>0, то есть, условие выполняется, цикл начинает работать и выполняются все операторы в теле цикла:
a
b
c
‘ПОЕЗД’
?
?
i:=Длина(a)
i
k
?
?
5
k:=2
2
b:=’А’
‘A’
i > 0?
да
c:=Извлечь(a,i)
i:=Длина(a)
b:=Cклеить(b,c)
k:=2
5
i:=i–k
3
• поскольку i=5, вызов функции Извлечь(a,i) выделяет из строки a символ с номером 5, это ‘Д’;
• следующей командой этот символ приписывается в конец строки b, теперь в ней хранится цепочка ‘АД’;
• в команде i:=i–k значение переменной i уменьшается на k (то
есть, на 2);
• далее нужно перейти в начало цикла и снова проверить условие
i>0, оно опять истинно, поэтому выполняется следующий шаг цикла, в котором к строке b добавляется 3-й символ строки a, то есть ‘Е’:
...
a
b
‘ПОЕЗД’
‘АД’
c
i
k
…
3
2
i > 0?
да
c:=Извлечь(a,i)
‘Е’
b:=Cклеить(b,c)
‘АДЕ’
i:=i–k
1
• условие i>0 истинно, поэтому тело цикла выполняется еще
один раз, к строке b добавляется 1-й символ строки a, то есть ‘П’:
a
b
c
i
k
...
‘ПОЕЗД’ ‘АДЕ’
…
1
2
i > 0?
да
c:=Извлечь(a,i)
b:=Cклеить(b,c)
i:=i–k
30
‘П’
‘АДЕП’
–1
• теперь i=–1, поэтому при очередной проверке условие i>0 в начале цикла оказывается ложным, выполнение цикла заканчивается, и исполнителю остается выполнить единственную строчку после цикла, которая дописывает в конец строки b букву ‘Т’:
...
a
b
c
i
k
‘ПОЕЗД’
‘АДЕП’
…
–1
2
i > 0?
нет
b:=Склеить(b,’Т’)
‘АДЕПТ’
• получилось, что в конце выполнения фрагмента алгоритма в
переменной b будет записана последовательность символов ‘АДЕПТ’
(ответ 1).
Задание B2. Знание и умение использовать основные алгоритмические конструкции: следование, ветвление, цикл
Определите значение переменной m после выполнения фрагмента алгоритма
m:=54;
n:=16;
m = n?
да
нет
нет
n:=n m;
m > n?
да
m:=m n;
Решение:
• можно заметить, что выполнение алгоритма прекращается,
когда переменные m и n становятся равны между собой;
• проведем трассировку алгоритма относительно этих переменных;
• видно, что первые 3 итерации цикла приведут к уменьшению
значения m до 6 (3 раза по 16);
• следующие 2 итерации цикла приведут к уменьшению значения n до 4 (2 раза по 6);
31
• далее значение m снова будет уменьшено до 2 (1 раз по 4), что, в
свою очередь, приведет к уменьшению n до 2 (1 раз по 2) и к выходу
из цикла (ответ 2).
Задание B5. Умение исполнять алгоритм в среде формального
исполнителя
У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:
1. сдвинь влево
2. вычти 1
Выполняя первую из них, исполнитель сдвигает число на один
двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд 11221. Запишите результат в десятичной системе.
Решение:
• важно, что числа однобайтовые – на число отводится 1 байт
или 8 бит;
• «сдвиг влево» – это операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается
нуль, а старший бит попадает в специальную ячейку – бит переноса:
7
6
5
4
3
2
1
0
0
0
1
0
1
1
0
1
0
0
бит
переноса
1
0
1
1
0
1
0
?
= 45
0
90
• можно показать, что в большинстве случаев результат этой
операции – умножение числа на 2, поэтому последовательность команд 11221 выполняется следующим образом
Код команды
Действие
Результат
1
умножь на 2
208
1
умножь на 2
160
2
вычти 1
159
2
вычти 1
158
1
умножь на 2
60
Примечание
104
(ответ 60).
32
остаток от деления 208 · 2 на
256
остаток от деления 158 · 2 на
256
Задание B8. Умение исполнять алгоритм, записанный на естественном языке
Упаковка информации методом RLE-кодирования состоит в следующем. Упакованная последовательность содержит управляющие
байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1,
то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах
управляющего байта. Если же старший бит управляющего байта
равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно – записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10000111 говорит о
том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 – о том, что следующие за ним 4 байта надо
взять без изменений.
После кодирования методом RLE получилась следующая последовательность байтов (первый байт – управляющий):
10000011 10101010 00000010 10101111 11111111 10000101 10101010.
Сколько байт будет содержать данная последовательность после
распаковки? Впишите в бланк только число.
Решение:
• следует обратить внимание на то, что в этой задаче НЕ нужно
распаковывать последовательность, а нужно просто определить ее
длину;
• проанализируем первый управляющий байт, 10000011; он начинается с 1 – это команда на повторение следующего символа; количество повторений записано в семи младших битах: 112 = 3 раза;
значит, раскодирование первых двух байт дает 3 символа;
• следующий управляющий байт – третий, 00000010; его старший бит 0 говорит о том, что следующие 102 = 2 символа повторяются 1 раз; получаем еще 2 символа
• следующий управляющий байт – шестой, 10000101; он говорит о том, что следующий за ним символ нужно повторить 1012 =5
раз; получаем еще 5 символов
• полная длина распакованной последовательности равна
3 + 2 + 5 = 10 символов (ответ 10).
Задание C2. Умения написать короткую (10 – 15 строк) простую
программу обработки массива на языке программирования или записать алгоритм на естественном языке
33
Дан целочисленный квадратный массив 10×10. Опишите на русском языке или на одном из языков программирования алгоритм
вычисления суммы максимальных элементов из каждой строки.
Напечатать значение этой суммы. Предполагается, что в каждой
строке такой элемент единственный.
Решение:
• суть задачи: среди элементов каждой строки нужно выбрать
максимальный, и все эти выбранные значения сложить;
• несложно сразу написать алгоритм на русском языке:
«Чтобы накапливать сумму, нужно ввести целую переменную Sum,
в которую в самом начале записываем 0; далее в цикле просматриваем все строки, для каждой строки находим максимальный элемент
и прибавляем его значение к Sum. Для определения максимального
элемента в строке вводим переменную max и сначала записываем в
нее значение первого элемента этой строки. Затем в цикле просматриваем все остальные элементы, начиная со второго до конца массива. Если очередной элемент больше значения max, записываем в
max значение этого элемента».
• сначала напишем программу в псевдокоде:
const N=10;
{ ввод матрицы N на N }
Sum := 0;
for i:=1 to N do
begin
{ max := максимальный элемент в i-ой строке }
Sum := Sum + max;
end;
• остается записать на Паскале те части, которые взяты в фигурные скобки, и до конца оформить программу; по правилам ЕГЭ
можно не писать в программе команды для ввода массива, поэтому
мы оставим на этом месте комментарий:
const N=10;
var A: array[1..N,1..N] of integer;
i, k, max, Sum: integer;
begin
{ ввод матрицы N на N }
Sum := 0;
for i:=1 to N do
begin
max := A[i,1];
for k:=2 to N do
34
if A[i,k] > max then
max := A[i,k];
Sum := Sum + max;
end;
writeln(Sum);
end.
Задание C3. Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию
Два игрока играют в следующую игру. Сначала в кучке лежит
5 спичек; два игрока убирают спички по очереди, причем за 1 ход
можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй
ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение:
• первый игрок может убрать одну спичку (в этом случае их
останется 4), или сразу 2 (останется 3), эти два варианта можно показать на схеме:
5
1 игрок
4
3
• если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички,
второй игрок может выиграть, взяв две спички и оставив одну:
5
1 игрок
2 игрок
4
3
3
2
1
• если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:
5
1 игрок
2 игрок
1 игрок
4
3
3
2
1
1
1
35
• простроенная схема называется «деревом игры», она показывает все возможные варианты, начиная с некоторого начального положения (для того, чтобы не загромождать схему, мы не рисовали
другие варианты, если из какого-то положения есть выигрышный
ход);
• в любой ситуации у игрока есть два возможных хода, поэтому от каждого узла этого дерева отходят две ветви, такое дерево называется двоичным (если из каждого положения есть три варианта
продолжения, дерево будет троичным);
• проанализируем эту схему: если первый игрок своим первым
ходом взял две спички, то второй сразу выигрывает; если же он взял
одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока;
• кто же выиграет при правильной игре? для этого нужно ответить на вопросы:
1) «Может ли первый игрок выиграть, независимо от действий
второго?», и
2) «Может ли второй игрок выиграть, независимо от действий
первого?»
• ответ на первый вопрос – «да»; действительно, убрав всего одну спичку первым ходом, 1-й игрок всегда может выиграть на следующем ходу;
• ответ на второй вопрос – «нет», потому что если первый игрок
сначала убрал одну спичку, второй всегда проиграет, если первый
не ошибется;
• таким образом, при безошибочной игре выиграет первый
игрок; для этого ему достаточно первым ходом убрать всего одну
спичку;
• в демо-вариантах ЕГЭ рекомендуется записывать дерево в виде
таблицы (фактически, повернув его на 90 градусов), так получается
более компактно:
1 игрок
5
4
3
36
2 игрок
1 игрок
3
1
2
1
1
Основы логики
Число заданий: 5
Кодификатор
Код
блока
Код контролируемого элемента
1
Элементы содержания,
проверяемые заданиями КИМ
Информационные процессы и системы
1.3
Основы логики
1.3.1
Алгебра логики.
1.3.2
Логические выражения и их преобразование.
1.3.3
Построение таблиц истинности логических выражений.
Теоретические сведения
Основной объект изучения логики – элементарные высказывания. Из них с помощью логических связок (элементарных операций)
строятся сложные высказывания. При алгебраическом подходе эти
высказывания рассматриваются как формулы, которые можно вычислять и преобразовывать. Логическими переменными обозначают элементарные высказывания. Формулы определяют логические
функции.
Логические функции, переменные, элементарные операции образуют алгебру Буля (булеву алгебру). Для булевой алгебры справедливы определенные соотношения, тождества, правила и законы. Основополагающим законом булевой алгебры является закон
исключения третьего, согласно которому логические переменные,
в отличие от переменных обычной алгебры, могут принимать только два значения {«да», «нет»}, {«истинно», «ложно»} и т.д.
Булева функция – функция, как и ее аргументы принимающая
только два значения: 0 и 1. Операции над переменными записываются с помощью символов: ∧, ∨, ¬, → и т.д. Совокупность значений
аргументов называется набором. Функция может быть задана таблично (таблица истинности), числовым способом, аналитически
или графически.
При задании булевой функции в виде таблицы истинности в левой части выписываются все возможные наборы значений ее аргу37
ментов х1, ..., хn, а правая часть представляет собой столбец значений функций, соответствующих этим наборам. Набор значений переменных, на котором функция принимает значение f = 1, называется единичным набором функции f. Аналогично набор значений,
на котором f = 0, называется нулевым набором функции f. В общем
случае таблица истинности для функции от n переменных должна
иметь 2n строк.
Переменная х в функции f называется фиктивной (несущественной), если значение переменной х не влияет на значение булевой
функции. Фиктивные переменные могут быть удалены или введены
в набор переменных функций. Количество булевых функций опреn
деляется числом n переменных. Например, P2 (n) = 22 .
Множество всех логических функций одной переменной – унарные логические операции – представлено в следующей таблице.
1
Число таких функций P2 (1) = 22 = 4 .
х
j0
j1
j2
j3
0
0
0
1
1
1
0
1
0
1
Обозначения
0
х
¬х
1
В таблице представлены следующие функции:
• j0, j3 – функции констант 0 и 1, значения которых не зависят
от переменной (х –фиктивная переменная);
• j1 = х – повторяет значение х;
• j2 = ¬х – инверсия (отрицание переменной, функция НЕ).
Множество всех логических функций двух переменных – бинарные логические операции – представлено
в следующей таблице.
2
Число таких функций P2 (1) = 22 = 16 .
х1
х2
Ψ0
Ψ1
Ψ2
Ψ3
Ψ4
Ψ5
Ψ6
Ψ7
Ψ8
Ψ9 Ψ10 Ψ11 Ψ12 Ψ13 Ψ14 Ψ15
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
1
0
1
0
0
1
1
0
1
0
0
1
1
0
1
0
0
1
1
1
0
0
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
0
0
1
0
1
0
0
1
1
0
1
0
1
х1 х2 ¬х1 ¬х2 ∨
↓
∧
|
Å
~
→ ¬→ ← ¬← 1
Обозна0
чения
В таблице представлены следующие функции:
• Ψ0, Ψ15 – функции констант 0 и 1;
38
• Ψ1 – повторение х1 (х2 – фиктивная переменная);
• Ψ2 – повторение х2 (х1 – фиктивная переменная);
• Ψ3 = ¬х1 (х2 – фиктивная переменная);
• Ψ4 = ¬х2 (х1 – фиктивная переменная);
• Ψ5 = х1 ∨ х2 – дизъюнкция (логическая функция ИЛИ);
• Ψ6 = ¬(х1 ∨ х2); х1 ↓ х2 – стрелка Пирса (логическая функция
ИЛИ-НЕ);
• Ψ7 = х1 ∧ х2 – конъюнкция (логическая функция И);
• Ψ8 = ¬(х1 ∧ х2); х1 | х2 – штрих Шеффера (логическая функция
И-НЕ);
• Ψ9 = х1 Å х2 – сложение по модулю 2 (функция неравнозначности);
• Ψ10 = ¬(х1 Å х2); х1 ~ х2 – эквивалентность, равнозначность;
• Ψ11 = х1 → х2 – импликация (х1 влечет за собой х2);
• Ψ12 = ¬(х1 → х2) – отрицание импликант (функция запрета);
• Ψ13 = х2 → х1 – импликация (х2 влечет за собой х1);
• Ψ14 = ¬(х2 → х1) – отрицание импликант (функция запрета).
Логические функции трех и более переменных обычно задаются (наряду с таблицами истинности) также формулами, состоящими из символов переменных и знаков унарных и бинарных операций. Значение любой логической формулы, содержащей знаки логических операций, можно вычислить для любого набора значений
переменных, используя приведенные выше таблицы. Чтобы решить
логическую задачу, необходимо найти истинное высказывание, отвечающее на поставленный в задаче вопрос.
Формулы, представляющие одну и ту же функцию, называются
эквивалентными или равносильными.
1. Ассоциативность конъюнкции и дизъюнкции (сочетательный закон):
а) x1 ∧ (x2 ∧ x3) = (x1 ∧ x2) ∧ x3 = x1 ∧ x2 ∧ x3;
б) x1 ∨ (x2 ∨ x3) = (x1 ∨ x2) ∨ x3 = x1 ∨ x2 ∨ x3.
2. Коммутативность конъюнкции и дизъюнкции (переместительный закон):
а) x1 ∧ x2= x2 ∧ x1;
б) x1 ∨ x2= x2 ∨ x1.
3.Дистрибутивность (распределительный закон):
а) x1 ∧ (x2 ∨ x3) = x1 ∧ x2 ∨ x1 ∧ x3;
б) x1 ∨ (x2 ∧ x3) = (x1 ∨ x2) ∧ (x1 ∨ x3).
4. Идемпотентность (правило повторения):
а) х ∧ х = х;
б) x ∨ x = x.
39
5.Закон двойного отрицания: ¬(¬х) = х.
6. Свойства констант 0 и 1:
а) х ∧ 1 = х;
б) х ∧ 0 = 0;
в) x ∨ 1 = 1;
г) x ∨ 0 = x;
д) ¬0 = 1;
е) ¬1 = 0.
7. Теорема двойственности (правила де Моргана):
а) ¬(x1∧x2) = ¬x1 ∨ ¬x2;
б) ¬(x1 ∨ x2) = ¬x1 ∧ ¬x2.
8.Закон противоречия:
x ∧ ¬х = 0.
9.Закон исключенного третьего:
x ∨ ¬х = 1.
Все эти равенства остаются справедливыми при подстановке
вместо переменных любых логических функций и, следовательно,
любых формул, представляющих эти функции. Наряду с основными соотношениями для упрощения формул часто используются следующие правила:
1. Правила поглощения:
а) x1∨ x1 ∧ x1 = x1;
б) x1∧ (x1 ∨ x2) = x1.
2. Правила склеивания:
а) x1 ∧ x2 ∨ x1 ∧ ¬x2 = x1;
б) x1 ∨ ¬x1 ∧ x2 = x1 ∨ x2.
3. Правило обобщенного склеивания:
x1 ∧ x3 ∨ x2 ∧ ¬x3 ∨ x1 ∧ x2 = x1 ∧ x3 ∨ x2 ∧ ¬x3.
В заключение следует заметить, что логическую функцию «импликация» можно выразить через функции ИЛИ и НЕ:
A → B = ¬A ∨ B.
40
41
Обозначение
задания в
работе
A7
A8
A9
B4
B6
№
1
2
3
4
5
Коды проверяемых
элементов
содержания по
кодификатору
1.3.1
1.3.2
1.3.3
1.3.2
1.3.2
Проверяемые элементы содержания
Знание основных понятий
и законов математической
логики
Умение строить и преобразовывать логические
выражения
Умения строить таблицы
истинности и логические
схемы
Умение строить и преобразовывать логические
выражения
Умение строить и преобразовывать логические
выражения
2
3
2
2
3
Коды видов
деятельности
(табл. 3)
П
В
Б
Б
П
Уровень
сложности
задания
1
1
1
1
1
Макс. балл
за выполнение
задания
8
10
2
1
3
Примерное
время выполнения
задания
(мин.)
Примеры заданий
Задание A7. Знание основных понятий и законов математической логики
Для какого из указанных значений X истинно высказывание
(X > 4) ∨ ((X > 1) → (X > 4))
1) 1
2) 2
3) 3
4) 4
Решение:
• заметим, что выражение (X > 4) в левой части дизъюнкции
ложно при всех указанных значениях аргумента X;
• таким образом, результирующая дизъюнкция будет истинна,
когда ее правая часть истинна;
• импликация ((X > 1) → (X > 4)) содержит в правой части выражение (X > 4), которое, как уже указывалось, ложно при всех указанных значениях аргумента X;
• импликация истинна, только когда выражение (X > 1) ложно,
то есть при X = 1 (ответ 1).
Задание A8. Умение строить и преобразовывать логические выражения
Какое логическое выражение эквивалентно выражению
¬(¬A ∨ B) ∨ ¬C
1) (A ∧ ¬B) ∨ ¬C
2) ¬A ∨ B ∨ ¬C
3) A ∨ ¬B ∨ ¬C
4) (¬A ∧ B) ∨ ¬C
Решение:
• Воспользуемся законом де Моргана, преобразуя исходное выражение ¬(¬A ∨ B) ∨ ¬C = (¬¬A ∧ ¬B) ∨ ¬C;
• Для дальнейшего преобразования используем закон двойного
отрицания: (¬¬A ∧ ¬B) ∨ ¬C = (A ∧ ¬B) ∨ ¬C (ответ 1).
Задание A9. Умения строить таблицы истинности и логические
схемы
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:
X
1
0
1
Y
0
0
1
Z
0
0
1
F
1
0
0
Какое выражение соответствует F?
1) ¬X ∧ ¬Y ∧ ¬Z 2) X ∧ Y ∧ Z 3) X ∧ ¬Y ∧ ¬Z 4) X ∨ ¬Y ∨ ¬Z
42
Решение:
• в столбце F есть единственная единица для комбинации X = 1,
Y = Z = 0;
• простейшая функция, истинная только для этого случая, имеет вид X ∧ ¬Y ∧ ¬Z (ответ 3).
Задание B4. Умение строить и преобразовывать логические выражения
Сколько различных решений имеет уравнение
((K ∨ L) → (L ∧ M ∧ N)) = 0
где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых
выполнено данное равенство. В качестве ответа Вам нужно указать
количество таких наборов.
Решение:
• из таблицы истинности операции «импликация» следует, что
рассматриваемое равенство верно тогда и только тогда, когда одновременно
K ∨ L = 1 и L ∧ M ∧ N = 0;
• из первого уравнения следует, что хотя бы одна из переменных,
K или L равна 1 (или обе вместе), поэтому рассмотрим три случая:
• если K = 1 и L = 0, то второе равенство выполняется при любых
М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения;
• если K = 1 и L = 1, то второе равенство выполняется при М ∧ N
= 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения;
• если K = 0, то обязательно L = 1 (из первого уравнения); при
этом второе равенство выполняется при М ∧ N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения;
• таким образом, всего получаем: 4 + 3 + 3 = 10 решений (ответ
10).
Задание B6. Умение строить и преобразовывать логические выражения
Мама, прибежавшая на звон разбившейся вазы, застала всех
трех своих сыновей в совершенно невинных позах: Саша, Ваня и
Коля делали вид, что происшедшее к ним не относится. Однако
футбольный мяч среди осколков явно говорил об обратном.
– Кто это сделал? – спросила мама.
– Коля не бил по мячу, – сказал Саша. – Это сделал Ваня.
43
Ваня ответил: – Разбил Коля, Саша не играл в футбол дома.
– Так я и знала, что вы друг на дружку сваливать будете, рассердилась мама. Ну, а ты что скажешь? – спросила она Колю.
– Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А
я сегодня еще не сделал уроки, – сказал Коля.
Оказалось, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду. Кто разбил вазу?
Решение:
• запишем высказывания трех мальчиков в краткой форме:
Саша: 1. это не Коля
2. это Ваня
Ваня: 1. это Коля
2. это не Саша
Коля: 1. это не Ваня
• следует обратить внимание, что у Коли всего одно высказывание, которое относится к задаче; то, что он сделал или не сделал уроки, никак не проясняет ситуацию с разбитой вазой;
• итак, двое мальчиков сказали правду;
• это не могут быть Саша и Ваня, потому что их первые высказывания противоречат одно другому;
• это не могут быть Саша и Коля, поскольку высказывание Коли
противоречит второму высказыванию Саши;
• поэтому правду сказали Ваня и Коля, а Саша – солгал;
• таким образом, вазу разбил Коля (ответ Коля).
44
Моделирование и компьютерный эксперимент
Число заданий: 1
Кодификатор
Код
блока
Код контролируемого
элемента
1
Элементы содержания,
проверяемые заданиями КИМ
Информационные процессы и системы
1.4
Моделирование и компьютерный эксперимент
1.4.1
Общая структура деятельности по созданию компьютерных моделей.
1.4.2
Представление и считывание данных в разных типах
информационных моделей (схемы, карты, таблицы,
графики и формулы).
1.4.3
Математические модели (графики, исследование
функций).
1.4.4
Построение и использование информационных моделей реальных процессов (физических, химических,
биологических, экономических).
Теоретические сведения
Аспектами моделирования могут быть внешний вид, структура,
поведение объекта моделирования, а также их всевозможные комбинации. Структурой объекта называют совокупность его элементов и существующих между ними связей. Поведением объекта называют изменения его внешнего вида и структуры с течением времени в результате взаимодействия с другими объектами.
Моделирование внешнего вида объекта используется для:
• идентификации (узнавания) объекта;
• долговременного хранения образа.
Моделирование структуры объекта используется для:
• ее наглядного представления;
• изучения свойств объекта;
• выявления значимых связей;
• изучения стабильности объекта.
Моделирование поведения применяется при:
• планировании, прогнозировании;
• установлении связей с другими объектами;
• выявлении причинно-следственных связей;
45
Коды видов деятельности
(табл. 3)
Уровень сложности задания
Макс. балл за выполнение
задания
Примерное время выполнения задания (мин.)
1
Умение представлять и
считывать данные в разных
A10 типах информационных моделей (схемы, карты, таблицы, графики и формулы)
Коды проверяемых элементов содержания по
кодификатору
№
Обозначение задания в
работе
Проверяемые элементы
содержания
• управлении;
• конструировании технических устройств и т. п.
В процессе моделирования каждый аспект моделирования раскрывается через совокупность свойств. В моделях отражаются не
все свойства объекта, а только существенные с точки зрения цели
моделирования. Каждый аспект моделирования характеризуется
своим набором свойств:
• внешний вид — набором признаков;
• структура — перечнем элементов и указанием отношений между ними;
• поведение — изменением внешнего вида и структуры с течением времени.
Некоторые свойства объекта моделирования могут быть выражены величинами, принимающими численные значения. Такие величины носят название параметров модели.
1.4.2
2
Б
1
2
Примеры заданий
Задание A10. Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)
Грунтовая дорога проходит последовательно через населенные
пункты А, B, С и D. При этом длина дороги между А и В равна 80
км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт
46
В, если его скорость по грунтовой дороге – 20 км/час, по шоссе –
40 км/час.
1) 1 час
2) 1,5 часа 3)3,5 часа 4) 4 часа
Решение:
• нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе):
80
20
B
50
20
A
40
40
C
D
10
20
• разделив числитель на знаменатель, получим время движения по каждой дороге
B
B
2,5
2,5
4
4
A
A
1
1
C
C
D
D
0,5
0,5
• проехать из А в B можно напрямую, это займет 4 часа;
• или через пункт C, это займет 1 час по шоссе (из А в С) и 2,5
часа по грунтовой дороге (из В в С), всего 1 + 2,5 = 3,5 часа (ответ 3).
47
Программные средства информационных
и коммуникационных технологий
Число заданий: 1
Кодификатор
Код
блока
Код контролируемого
элемента
2
Элементы содержания,
проверяемые заданиями КИМ
Информационные и коммуникационные технологии
Программные средства информационных и коммуникационных технологий
2.2
2.2.1
Операционная система: назначение и функциональные возможности.
2.2.2
Графический интерфейс (основные типы элементов
управления).
2.2.3
Файлы и файловые системы (файловые менеджеры и
архиваторы).
2.2.4
Оперирование информационными объектами с
использованием знаний о возможностях информационных и коммуникационных технологий (выбор
адекватного программного средства для обработки
различной информации).
2.2.5
Технологии и средства защиты информации от разрушения и несанкционированного доступа (антивирусные программы, межсетевые экраны и др.).
Теоретические сведения
Файловая система определяет способ организации, хранения
и именования данных на носителях информации. Она определяет
формат физического хранения информации, которую принято группировать в виде файлов. Конкретная файловая система определяет
размер имени файла, максимальный возможный размер файла, набор атрибутов файла.
С точки зрения операционной системы весь диск представляет
собой набор кластеров. Драйверы файловой системы организуют
кластеры в файлы и каталоги. Эти же драйверы отслеживают, какие из кластеров в настоящее время используются, какие свободны,
какие помечены как неисправные.
В операционной системе Windows каталоги организованы в многоуровневую (иерархическую) структуру, которая называется «де48
Уровень сложности задания
Макс. балл за
выполнение задания
Примерное время выполнения
задания (мин.)
Знания о файловой
A13 системе организации данных
Коды видов
деятельности
(табл. 3)
1
Коды проверяемых элементов
содержания по
кодификатору
№
Обозначение задания в работе
Проверяемые
элементы содержания
ревом каталогов». Каждый каталог кроме корневого имеет единственный «родительский» каталог – тот каталог, внутри которого
он находится. Полный адрес каталога – это перечисление каталогов, в которые нужно войти, чтобы попасть в этот каталог (начиная
с корневого каталога диска).
Полный адрес файла состоит из адреса каталога, в котором он
находится, символа «\» и имени файла. Маска служит для обозначения (выделения) группы файлов, имена которых имеют общие
свойства, например, общее расширение. В масках, кроме «обычных» символов (допустимых в именах файлов) используются два
специальных символа: «*» и «?». Звездочка «*» обозначает любое
количество любых символов, в том числе может обозначать пустую
последовательность. Знак вопроса «?» обозначает ровно один любой
символ. При выводе списка имен файлов они могут быть отсортированы по имени, типу (расширению), дате последнего изменения,
размеру. Сортировка не меняет их размещения на диске. Если установлена сортировка по имени или типу, сравнение идет по кодам
символов, входящих в имя или в расширение.
2.2.3
1
Б
1
1
Примеры заданий
Задание A13. Знания о файловой системе организации данных
Перемещаясь из одного каталога в другой, пользователь последовательно посетил каталоги DOC, USER, SCHOOL, A:\, LETTER,
INBOX. При каждом перемещении пользователь либо спускался в
каталог на уровень ниже, либо поднимался на уровень выше. Каково полное имя каталога, из которого начал перемещение пользователь?
1) A:\DOC
2) A:\LETTER\INBOX
3) А:\SCHOOL\USER\DOC
4) А:\DOC\USER\SCHOOL
49
Решение:
• в задачах, где нужно определить полный адрес файла или каталога, нужно начинать с поиска имени диска, в данном случае каталог находится на диске A:\ (так обозначается корневой каталог);
• поскольку в списке посещенных каталогов перед A:\ стоит
SCHOOL, пользователь мог попасть в корень диска A:\ только через
каталог SCHOOL, поэтому адрес стартового каталога начинается с
A:\SCHOOL;
• так как среди предложенных вариантов только один удовлетворяет этому условию, можно остановиться (ответ 3), однако, давайте все же доведем процедуру до конца, это позволит выяснить некоторые интересные моменты, которые не сработали здесь, но могут
сработать в других задачах;
• как пользователь попал в каталог SCHOOL? по условию он мог
как подниматься, так и спускаться по дереву каталогов;
• очевидно, что он не мог спуститься из USER в SCHOOL, потому что SCHOOL находится в корневом каталоге и каждый каталог
имеет только одного «родителя»; значит, пользователь поднялся из
USER в SCHOOL, и начальная часть полного адреса А:\SCHOOL\
USER;
• аналогично можно показать, что пользователь поднялся в каталог USER из каталога DOC (ответ 3).
50
Технология обработки графической
и звуковой информации
Число заданий: 1
Кодификатор
Код
блока
Код контролируемого
элемента
2
Элементы содержания,
проверяемые заданиями КИМ
Информационные и коммуникационные технологии
Технология обработки графической и звуковой информации
2.4
2.4.1
Растровая графика. Графические объекты и операции над ними.
2.4.2
Векторная графика. Графические объекты и операции над ними.
2.4.3
Компьютерное черчение. Выделение, объединение,
перемещение и геометрические преобразования
фрагментов и компонентов чертежа.
2.4.4
Создание и редактирование цифровых звукозаписей.
2.4.5
Компьютерные презентации: типы слайдов, мультимедиа эффекты, организация переходов между
слайдами.
Теоретические сведения
Компьютерная графика – раздел информатики, предметом которого является работа на компьютере с графическими изображениями (рисунками, чертежами, фотографиями, видеокадрами и пр.).
Пиксель – наименьший элемент изображения на экране (точка на
экране). Растр – прямоугольная сетка пикселей на экране. Разрешающая способность экрана – размер сетки растра, задаваемого в
виде произведения nг · nв, где nг – число точек по горизонтали, nв –
число точек по вертикали (число строк). Часто устанавливаются
следующие разрешающие способности экрана: 640×480, 800×600,
1024×768, 1280×1024.
Видеоинформация – информация об изображении, воспроизводимом на экране компьютера, хранящаяся в компьютерной памяти.
Видеопамять – оперативная память, хранящая видеоинформацию
во время ее воспроизведения в изображение на экране. Графический
файл – файл, хранящий информацию о графическом изображении.
51
Коды видов деятельности (табл. 3)
Уровень сложности
задания
Макс. балл за выполнение задания
Примерное время
выполнения задания
(мин.)
A15
Знание
технологии
обработки
графической
информации
Коды проверяемых
элементов содержания
по кодификатору
1
Проверяемые элементы содержания
№
Обозначение задания в
работе
Число цветов используемой палитры, воспроизводимых на экране
дисплея (N), и число битов, отводимых в видеопамяти под каждый
пиксель (i), связаны формулой: N = 2i.
Для того чтобы на экране монитора формировалось изображение, информация о каждой его точке (код цвета точки) должна храниться в видеопамяти компьютера. Рассчитать необходимый объем
видеопамяти можно, найдя произведение количества точек по горизонтали на количество точек по вертикали и на глубину цвета:
nг · nв · i.
Частота дискретизации звуковой информации – это количество измерений входного сигнала за 1 секунду. Частота измеряется
в герцах (Гц). Одно измерение за одну секунду соответствует частоте в 1 Гц. Характерные частоты дискретизации аудиоадаптеров: 11
кГц, 22 кГц, 44,1 кГц и др. Разрядность регистра – число битов в
регистре аудиоадаптера. Разрядность определяет точность измерения входного сигнала. Если разрядность равна 8, то при измерении
входного сигнала может быть получено 28 = 256 различных значений. Очевидно, 16-разрядный аудиоадаптер точнее кодирует и воспроизводит звук, чем 8-разрядный. Звуковой файл – файл, хранящий звуковую информацию в числовой двоичной форме. Как правило, информация в звуковых файлах подвергается сжатию.
2.4.1/2.4.2/2.4.3
1
П
1
2
Примеры заданий
Задание A15. Знание технологии обработки графической информации
Для хранения растрового изображения размером 32×32 пикселя
отвели 512 байтов памяти. Каково максимально возможное число
цветов в палитре изображения?
52
1) 256
2) 2
3)16
4) 4
Решение:
• находим общее количество пикселей Q = 32 × 32 = 25 × 25 = 210 ;
• находим объем памяти в битах M = 512 байт = 29 байт = 29 × 23
бит = 212 бит;
212
• определяем количество бит на пиксель: K = 10 = 22 = 4 бита
2
на пиксель;
• по таблице степеней двойки находим, что 4 бита позволяют закодировать 24 = 16 цветов (ответ 3).
53
Технология обработки информации
в электронных таблицах
Число заданий: 2
Кодификатор
Код
блока
Код контролируемого
элемента
2
Элементы содержания,
проверяемые заданиями КИМ
Информационные и коммуникационные технологии
Технология обработки информации в электронных
таблицах
2.5
2.5.1
Ввод и редактирование данных в электронных таблицах, операции над данными. Экспорт и импорт
данных.
2.5.2
Типы и формат данных. Работа с формулами. Абсолютная и относительная ссылки. Использование
функций. Статистическая обработка данных.
2.5.3
Визуализация данных с помощью диаграмм и графиков. Построение графиков элементарных функций.
Теоретические сведения
Табличные процессоры (ТП) позволяют создавать таблицы, которые (в отличие от баз данных) являются динамическими. Они содержат так называемые «вычисляемые поля», значения которых
автоматически пересчитываются по заданным формулам при изменении значений исходных данных, содержащихся в других полях.
При работе с табличными процессорами создаются документы –
электронные таблицы (ЭТ). Электронная таблица создается в памяти компьютера. ТП имеет несколько режимов работы: формирование таблицы (ввод данных в ячейки), редактирование (изменение
значений данных), вычисление по формулам, сохранение информации в памяти, построение графиков и диаграмм, статистическая обработка данных, упорядочение.
Рабочим полем ТП является экран дисплея, на котором ЭТ представляется в виде матрицы. ЭТ, подобно шахматной доске, разделена на клетки, которые называют ячейками таблицы. Строки и
столбцы имеют обозначения. Строки имеют числовую нумерацию,
а столбцы – буквенные (буквы латинского алфавита) обозначения.
Как и на шахматной доске, каждая клетка имеет свое имя (адрес,
54
ссылку), состоящее из имени столбца и номера строки, например:
А1, С13 и т.д. У табличного процессора Excel таблица максимально
содержит 256 столбцов. Поскольку в латинском алфавите всего 26
букв, то, начиная с 27-го, столбца используется двухбуквенное обозначения, также в алфавитном порядке. Последний, 256-й столбец,
имеет имя IV. Значит, существуют ячейки с такими именами: DL67,
HZ10234 и т. п.
На экране дисплея видна не вся ЭТ, а только ее часть. Документ
в полном объеме хранится в оперативной памяти, а экран можно
считать окном, через которое пользователь имеет возможность просматривать его. Данные в таблицах можно не только хранить, но и
обрабатывать. Данные, которые нельзя определить по другим ячейкам таблицы, называют основными. С другой стороны, очень часто
значения одних ячеек таблицы определяются по значениям других
ячеек при помощи вычислений. Такие данные называют производными или вычисляемыми. Все данные таблицы размещаются в
ячейках. Содержимым ячейки может быть текст, а в ячейках числового типа может находиться числовое значение или формула.
Текстовые данные представляют собой строку текста произвольной длины. Программа Excel воспроизводит такие данные точно в
том виде, в каком они были введены. Ячейка, содержащая текстовые данные, не может использоваться в вычислениях. Если Excel не
может интерпретировать данные в ячейке как число или как формулу, программа считает, что это текстовые данные.
Числовые данные – это отдельное число, введенное в ячейку.
Excel рассматривает данные как число, если формат данных позволяет это сделать. Как числа рассматриваются данные, определяющие даты или денежные суммы. Ячейки, содержащие числовые
данные, могут использоваться в вычислениях. Числовая ячейка не
может содержать текстовые данные (кроме названий встроенных
функций). Если ячейка содержит формулу, значит эта ячейка вычисляемая, то есть значение ячейки может зависеть от значений
других ячеек таблицы. Формула – это выражение, определяющее
способ вычисления значения ячейки. Содержимое ячейки рассматривается как формула, если оно начинается со знака равенства (=).
Формулы в ячейках таблицы не отображаются. Вместо формулы
воспроизводится результат, полученный при ее вычислении. Текст
и числа рассматриваются как константы. Изменить их можно только путем редактирования соответствующих ячеек. Формулы же
автоматически пересчитывают свои значения, как только хотя бы
один их операнд был изменен.
55
При работе с ЭТ пользователь может использовать и так называемые встроенные функции, которые заранее подготовлены для
определенных расчетов. Правила записи формул подобны правилам
записи арифметических выражений в языках программирования.
Однако в качестве идентификаторов (имен) переменных выступают
имена ячеек таблицы. Кроме арифметических операций формулы
могут содержать стандартные функции. У каждого ТП свой набор
стандартных функций. Данные в числовой ячейке могут иметь различный формат отображения: целый, вещественный, денежный,
процентный и т.д.
В ЭТ можно работать с группой ячеек, т.е. с прямоугольной частью таблицы (в таких случаях употребляют термин диапазон
ячеек). На работу с группой ячеек рассчитаны многие встроенные
функции. Адрес группы ячеек (ссылка на группу ячеек) – это указание адресов левой верхней и правой нижней ячеек группы, разделенные двоеточием. Например, А3:С6 – адрес группы, состоящей
из 12 ячеек.
В формулах используются ссылки на адреса ячеек. Существуют
два основных типа ссылок: относительные и абсолютные. Различия между ними проявляются при копировании формулы из активной ячейки в другую ячейку. Относительная ссылка изменяется при копировании формулы. Это изменение происходит «относительно» направления копирования формулы. То есть при перемещении или копировании формулы из активной ячейки относительные
ссылки автоматически обновляются в зависимости от нового положения формулы. При копировании в пределах одного столбца в обозначении ссылки изменяется номер строки, при копировании же в
пределах одной строки – меняется соответствующим образом обозначение столбца. Относительные ссылки имеют вид А1, ВЗ, Е25.
Абсолютная (или фиксированная) ссылка в формуле используется для указания фиксированного адреса ячейки. При перемещении или копировании формулы абсолютные ссылки не изменяются. В абсолютных ссылках перед неизменяемым значением адреса
ячейки ставится знак фиксации – знак доллара (например, $А$1).
Если символ $ стоит перед обозначением столбца (например: $A1),
то координата столбца абсолютная, а строки – относительная. Если символ доллара стоит перед номером строки (например, А$1), то,
наоборот, координата столбца относительная, а строки — абсолютная. Такие ссылки называются смешанными. Пусть, например, в
ячейке С1 записана формула =А$1+$В1, которая при копировании
в ячейку D2 приобретает вид =В$1+$В2.
56
Макс. балл за выполнение задания
Примерное время
выполнения задания
(мин.)
A17
Уровень сложности
задания
2
Знание технологии обработки информации в 2.5.1/2.5.2
электронных таблицах
Знания о визуализации
данных с помощью диа2.5.3
грамм и графиков
Коды видов деятельности (табл. 3)
A16
Коды проверяемых
элементов содержания по кодификатору
1
Проверяемые элементы содержания
№
Обозначение задания
в работе
Электронные таблицы позволяют представлять числовые данные в виде диаграмм или графиков. Диаграммы бывают различных
типов (столбчатые – гистограммы, круговые, точечные и т. д.). Выбор типа диаграммы зависит от характера данных и требуемой степени наглядности.
1
Б
1
1
2
Б
1
3
Примеры заданий
Задание A16. Знание технологии обработки информации в электронных таблицах
Дан фрагмент электронной таблицы:
1
2
3
А
1
2
В
2
6
С
=СЧЁТ(A1:B2)
=СРЗНАЧ(A1:C2)
Как изменится значение ячейки С3, если после ввода формул переместить содержимое ячейки В2 в В3? («+1» означает увеличение
на 1, а «–1» – уменьшение на 1)
1) –2
2) –1
3) 0
4) +1
Решение:
• это задача на знание особенностей функций СЧЕТ и СРЗНАЧ,
которые не учитывают пустые ячейки;
• после ввода формул в С2 окажется количество непустых ячеек
диапазона А1:В2, равное 4;
• в С3 будет выведено среднее значение диапазона А1:С2 равное
(1+2+2+6+4)/5 = 3;
57
• после перемещения (не копирования!) содержимого ячейки В2
в В3 ячейка В2 окажется пустой, поэтому в С2 выводится число 3 –
количество непустых ячеек диапазона А1:В2;
• в С3 будет выведено среднее значение диапазона А1:С2 равное
(1+2+2+3)/4 = 2;
• то есть значение С3 уменьшится на 1 (ответ 2).
Задание A17. Знания о визуализации данных с помощью диаграмм и графиков
В цехе трудятся рабочие трех специальностей – токари (Т), слесари (С) и фрезеровщики (Ф). Каждый рабочий имеет разряд не меньший второго и не больший пятого. На диаграмме I отражено количество рабочих с различными разрядами, а на диаграмме II – распределение рабочих по специальностям. Каждый рабочий имеет
только одну специальность и один разряд.
Имеются четыре утверждения:
А) Все рабочие третьего разряда могут быть токарями
Б) Все рабочие третьего разряда могут быть фрезеровщиками
В) Все слесари могут быть пятого разряда
Г) Все токари могут быть четвертого разряда
Какое из этих утверждений следует из анализа обеих диаграмм?
1) А
2) Б
3) В
4) Г
Решение:
• в условии даны столбчатая диаграмма, по которой можно
определить все числовые данные, и круговая диаграмма, по которой можно определить только доли отдельных составляющих в общей сумме;
• по данным столбчатой диаграммы определим, сколько рабочих имеют 2-ой, 3-й, 4-й и 5-й разряды:
2-ой разряд:
25 чел.
3-й разряд:
40 чел.
58
4-й разряд:
20 чел.
5-й разряд:
15 чел.
• сложив все эти числа, определим, что всего в цехе
25 + 40 + 20 + 15 = 100 рабочих;
• по круговой диаграмме видим, что половина из них – токари
(значит их 50 человек), четверть – слесари (25 чел.) и еще четверть –
фрезеровщики (25 чел.);
• теперь последовательно рассмотрим все утверждения-ответы:
А: Все рабочие третьего разряда (их 40 чел.) МОГУТ быть токарями, потому в цехе 50 токарей;
Б: Все рабочие третьего разряда (их 40 чел.) НЕ могут быть фрезеровщиками, потому в цехе всего 25 фрезеровщиков;
В: Все слесари (их 25 чел.) НЕ могут быть 5-ого разряда, потому в
цехе только 15 рабочих имеют 5-й разряд;
Г: Все токари (их 50 чел.) НЕ могут быть четвертого разряда, потому в цехе только 20 рабочих имеют 4-й разряд (ответ 1).
59
Технология хранения, поиска
и сортировки информации в базах данных
Число заданий: 1
Кодификатор
Код
блока
Код контролируемого
элемента
2
Элементы содержания,
проверяемые заданиями КИМ
Информационные и коммуникационные технологии
Технология хранения, поиска и сортировки информации в базах данных
2.6
2.6.1
Структура базы данных (записи и поля).
2.6.2
Табличное и картотечное представление баз данных.
2.6.3
Сортировка и отбор записей.
2.6.4
Использование различных способов формирования
запросов к базам данных.
Теоретические сведения
База данных – это инструмент для хранения и организации информации. Примером баз данных могут служить справочники, словари, картотеки, записные книжки и т.д. Задача базы данных состоит в хранении всех представляющих интерес данных в одном
или нескольких местах, причем таким способом, который заведомо
исключает ненужную избыточность. В хорошо спроектированной
базе данных избыточность данных исключается и минимизируется
вероятность сохранения противоречивых данных. Таким образом,
создание баз данных преследует две основные цели:
• понизить избыточность данных;
• повысить их надежность.
Компьютеры и созданные на их основе системы управления
базами данных (СУБД) привели к тому, что при работе с большими объемами данных бумажные носители используются все реже.
Особенно широкое распространение СУБД получили с почти повсеместным появлением персональных компьютеров. На современных
компьютерах чаще всего используются СУБД MS ACCESS, Paradox,
Visual dBase, MS Visual FoxPro, MS SQL и Oracle.
Четыре основных требования, которым должна удовлетворять
хорошо спроектированная база данных:
60
Макс. балл за выполнение задания
Примерное время
выполнения задания
(мин.)
Коды проверяемых
элементов содержания по кодификатору
Уровень сложности
задания
A14
Знание технологии
хранения, поиска и
2.6.1/2.6.2/
сортировки информа- 2.6.3/2.6.4
ции в базах данных
Коды видов деятельности (табл. 3)
1
Проверяемые элементы содержания
№
Обозначение задания
в работе
• Удовлетворять всем требованиям пользователей к содержимому базы данных.
• Гарантировать непротиворечивость и целостность данных.
• Обеспечивать естественное, легкое для восприятия структурирование информации.
• Удовлетворять требованиям пользователей к производительности базы данных.
В большинстве случаев предполагается, что данные представлены в виде файлов, состоящих из записей. Структура всех записей
в файлах одинакова, а количество записей в файле является переменным. Элементы данных, из которых состоит каждая запись, называются полями. Поскольку во всех записях имеются одни и те
же поля (с разными значениями), полям удобно давать уникальные
имена.
Большинство СУБД поддерживают, кроме того, механизм связей
между различными файлами, входящих в базу. Например, связь
может установиться явным образом, когда значением некоторых
полей является ссылка на другой файл, такие СУБД называются сетевыми, или же связь может установиться неявным образом, например, по совпадению значений полей в различных файлах. Такие
СУБД называются реляционными.
2
Б
1
2
Примеры заданий
Задание A14. Знание технологии хранения, поиска и сортировки
информации в базах данных
Из правил соревнования по тяжелой атлетике: Тяжелая атлетика – это прямое соревнование, когда каждый атлет имеет три попытки в рывке и три попытки в толчке. Самый тяжелый вес поднятой штанги в каждом упражнении суммируется в общем зачете.
61
Если спортсмен потерпел неудачу во всех трех попытках в рывке, он
может продолжить соревнование в толчке, но уже не сможет занять
какое-либо место по сумме 2-х упражнений. Если два спортсмена
заканчивают состязание с одинаковым итоговым результатом, высшее место присуждается спортсмену с меньшим весом. Если же вес
спортсменов одинаков, преимущество отдается тому, кто первым
поднял победный вес. Таблица результатов соревнований по тяжелой атлетике:
Кто победил в общем зачете (по сумме двух упражнений)?
1) Айвазян Г.С. 2) Викторов М.П. 3) Михальчук М.С. 4) Пай С.В.
Решение:
• можно убрать из таблицы всех участников, кроме тех, которые
упомянуты в ответах;
• в условии читаем первое правило для определения победителя:
«Самый тяжелый вес поднятой штанги в каждом упражнении суммируется в общем зачете», поэтому добавим в таблицу столбец «Общий зачет», в котором для каждого спортсмена сложим веса, взятые
в рывке и в толчке
Вес
спортсмена
Взято в
рывке
Рывок с
попытки
Взято в
толчке
Толчок с
попытки
Общий
зачет
Айвазян Г.С.
77,1
150,0
3
200,0
2
350,0
Викторов М.П.
79,1
147,5
1
202,5
1
350,0
Михальчук М.С.
78,2
147,5
2
202,5
3
350,0
Пай С.В.
79,5
150,0
1
200,0
1
350,0
Фамилия И.О.
• все интересующие нас участники набрали одинаковый результат, поэтому по данному критерию выявить победителя не удалось;
читаем далее: «Если два спортсмена заканчивают состязание с одинаковым итоговым результатом, высшее место присуждается спортсмену с меньшим весом»; отсюда сразу следует, что победитель –
Айвазян Г.С., поскольку его вес – наименьший среди всех участников (ответ 1).
62
Телекоммуникационные технологии
Число заданий: 2
Кодификатор
Код
блока
Код контролируемого
элемента
2
Элементы содержания,
проверяемые заданиями КИМ
Информационные и коммуникационные технологии
2.7
Телекоммуникационные технологии
2.7.1
Базовые принципы организации и функционирования компьютерных сетей. Локальные и глобальные
сети. Адресация в сети.
2.7.2
Услуги компьютерных сетей: World Wide Web
(WWW), электронная почта, файловые архивы, поисковые системы, чат и пр.
2.7.3
Поиск информации в Интернет.
2.7.4
Методы и средства создания и сопровождения сайта
(основы HTML).
Теоретические сведения
Электронные страницы Интернет размещаются на Web-серверах
в виде текстовых файлов. Входящие в состав страниц изображения,
звуковые файлы и другие компоненты также размещаются на удаленном сервере в виде отдельных файлов. Файлы страниц и их компонентов имеют свои адреса (идентификаторы), называемые унифицированными указателями ресурсов (URL, Uniform Resource
Locator). Пример URL-адреса: http://www.mail.ru/chair806/index.
htm
URL-адрес начинается с обозначения протокола Интернет, по
которому осуществляется доступ к ресурсу. В данном случае указан http-протокол передачи гипертекста. После названия протокола следуют двоеточие и две наклонные черты. Далее указывается
имя удаленного сервера (www.mail.ru). После имени сервера следует полное имя файла с ресурсом. Символы «/» разделяют названия
каталогов, которые нужно посетить, чтобы добраться до файла. В
данном случае страница хранится на сервере в файле index.htm каталога chair806.
Для более точной формулировки запросов к поисковому серверу
используются логические связки «И» и «ИЛИ». Связка «И» между
63
Умение осуществлять поиск
информации в Интернет
Примерное время
выполнения задания
(мин.)
B10
Макс. балл за выполнение задания
2
Уровень сложности
задания
B9
Коды видов деятельности (табл. 3)
1
Знание базовых принципов
организации и функционирования компьютерных сетей,
адресации в сети
Коды проверяемых
элементов содержания
по кодификатору
Проверяемые элементы содержания
№
Обозначение задания
в работе
двумя словами означает, что требуется найти страницы, содержащие одновременно и первое, и второе слово. Связка «ИЛИ» – что запрашиваются страницы, включающие хотя бы одно из указанных
слов. Если в выражении нет скобок, сначала выполняются все операции «И», затем – «ИЛИ». Операция «И» всегда ограничивает поиск, тогда как операция «ИЛИ» всегда расширяет его.
Каждый компьютер, подключенный к сети Интернет, должен иметь собственный адрес, который называют IP-адресом (IP,
Internet Protocol). IP-адрес состоит из четырех однобайтных чисел,
разделенных точками. Каждое из этих чисел находится в интервале
0…255, например, 192.168.85.210.
2.7.1
2
Б
1
3
2.7.3
3
П
1
5
Примеры заданий
Задание B9. Знание базовых принципов организации и функционирования компьютерных сетей, адресации в сети
Доступ к файлу htm.net, находящемуся на сервере com.edu, осуществляется по протоколу ftp. В таблице фрагменты адреса файла
закодированы буквами от А до Ж. Запишите последовательность
этих букв, кодирующую адрес указанного файла в сети Интернет.
A
Б
В
Г
Д
Е
Ж
64
/
com
.edu
://
.net
htm
ftp
Решение:
• адрес файла начинается с протокола, после этого ставятся знаки «://», имя сервера, каталог и имя файла;
• каталог здесь не указан, поэтому сразу получаем
ftp://com.edu/htm.net;
• такой адрес можно собрать из приведенных в таблице фрагментов (ответ ЖГБВАЕД).
Задание B10. Умение осуществлять поиск информации в Интернет
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент:
Ключевое слово
Количество сайтов,
для которых данное
слово является ключевым
сканер
принтер
монитор
200
250
450
Сколько сайтов будет найдено по запросу
(принтер | сканер) & монитор
если по запросу принтер | сканер было найдено 450 сайтов, по запросу принтер & монитор – 40, а по запросу сканер & монитор – 50.
Решение:
• запишем количество сайтов по каждому запросу
сканер
200
принтер
250
принтер | сканер
450
• поскольку последнее число равно сумме двух предыдущих, получаем, что в этом сегменте сети нет сайтов с ключевыми словами
принтер и сканер одновременно:
принтер & сканер
0
• для того чтобы определить сколько сайтов удовлетворяют заданному условию достаточно просто сложить числа, соответствующие запросам принтер & монитор (40) и сканер & монитор (50), что в
сумме дает 90 (ответ 90).
65
Технологии программирования
Число заданий: 2
Кодификатор
Код
блока
Код контролируемого
элемента
2
Элементы содержания,
проверяемые заданиями КИМ
Информационные и коммуникационные технологии
2.8
Технологии программирования
2.8.1
Чтение короткой (30 – 50 строк) простой программы
на алгоритмическом языке (языке программирования).
2.8.2
Поиск и исправление ошибок в небольшом фрагменте (10 – 20 строк) программы.
2.8.3
Создание собственной программы (30 – 50 строк) для
решения простых задач.
Теоретические сведения
Основные теоретические сведения к данному разделу были изложены в разделе «Алгоритмизация и программирование». Тем не менее, следует дополнительно пояснить вопросы, связанные с обработкой символьных строк и записей, поскольку именно они составляют наибольшую трудность при выполнении задания C4 экзамена.
Символьная строка – это цепочка символов, которая может обрабатываться как единое целое. Для обращения к символу с номером i строки s используется запись s[i]. Это говорит о том, что строка – особый вариант массива, в котором хранятся символы. Знак
сложения при работе с символьными строками означает сцепку,
объединение двух строк в одну (добавление второй строки в конец
первой), например:
s := ‘123’ + ‘456’; { получили ‘123456’ }.
С помощью функции Ord можно получить код символа. Цифры
имеют коды от 48 (цифра 0) до 57 (цифра 9), например
k := Ord(‘1’); { получили 49 }.
С помощью функции Chr можно сделать обратный переход: получить символ по его коду, например
c := Chr(49); { получили символ ‘1’ }
66
Для работы со строками в наиболее распространенных Паскальсредах используют стандартные функции (здесь s – это переменная
типа string; n и r – целые переменные)
n := Length(s);
записать длину строки s в целую переменную n
записать в символьную строку s1 подстроку строки
s, которая начинается с символа с номером 2 и состоит из 5 символов
записать в целую переменную n номер символа, с
которого в строке s начинается подстрока ‘Вася’
n := Pos(‘Вася’, s);
(если ее нет, в переменную n записывается 0); так
же можно искать отдельные символы
s1 := Copy(s, 2, 5);
n := StrToInt(s);
преобразовать строку s в целое число и записать
результат в переменную n (PascalABC, Delphi)
и процедуры
удалить из строки s 5 символов, начиная со второго
вставить в строку s фрагмент ‘Вася’, начиная с
Insert(‘Вася’, s, 3);
третьего символа
преобразовать строку s в целое число и записать
результат в переменную n; если при этом произоVal(s, n, r);
шла ошибка, в переменной r будет ноль, иначе –
ненулевое значение
Delete(s, 2, 5);
Структура (иногда она называется «запись», record) – это сложный тип данных, который может включать в себя несколько элементов – полей. Поля могут иметь различный тип. Записи в Паскале объявляются с помощью ключевого слова record. В простейшем
случае можно выделить память под одну запись так:
var x: record
name: string;
code: integer;
end;
Эта запись состоит из двух полей: символьной строки name и целого числа code. Записи очень удобны для работы, когда все данные
представляют собой единый блок информации, например, данные
об ученике. Если не использовать записи, было бы необходимо выделять в памяти отдельно символьную строку и отдельно целую переменную, причем эти данные внешне были бы никак не связаны,
поэтому программа с записями часто получается логичнее и понятнее как для автора, так и для того, кто будет в ней разбираться. Для
обращения к полям записи используют точку, например x.name
означает «поле name записи x». Можно сразу объявить массив записей:
67
var Info: array[1..100] of record
name: string;
code: integer;
end;
Это 100 одинаковых записей, имеющих общее имя Info и расположенных в памяти рядом друг с другом. В каждой структуре
есть поля nаme и code. Чтобы работать с полями записи с номером
k используют обращения вида Info[k].name и Info[k].code.
В заключение остановимся на вопросах сложности алгоритмов.
Обозначение O(N) говорит о том, что при увеличении в 2 раза размера массива данных количество операций тоже увеличивается
примерно в 2 раза (для больших N). Сложность O(N) имеет алгоритм с одним или несколькими простыми циклами, в каждом из
которых выполняется N шагов (например, при поиске минимального элемента). Количество операций для алгоритма, имеющего сложность O(N) , вычисляется по формуле p = a × N + b , где a и
b – некоторые постоянные. Если в одном алгоритме решения задачи используется несколько циклов от 1 до N, а во втором – только
один цикл, то алгоритм с одним циклом, как правило, эффективнее (хотя оба алгоритма имеют сложность O(N) , постоянная a в
каждом случае своя и для алгоритма с несколькими циклами она
будет больше).
Для алгоритма, имеющего сложность O(N 2 ) , количество операций пропорционально квадрату размера массива, то есть если N увеличить в 2 раза, то количество операций увеличивается
примерно в 4 раза (например, в программе используется два вложенных цикла, в каждом из которых N шагов). Сложность O(N 2 )
имеют простые способы сортировки массивов: метод «пузырька»,
метод выбора. При больших N функция f1 (N) = a1N 2 растет значительно быстрее, чем f2 (N) = a2 N , поэтому алгоритм, имеющий
сложность O(N 2 ) , всегда менее эффективен, чем алгоритм сложности O(N) .
Встречаются также алгоритмы сложности O(N 3 ) (три вложенных цикла от 1 до N). При больших N они работают существенно
медленнее, чем любой алгоритм сложности O(N 2 ) , то есть менее
эффективны. Для многих задач известны только алгоритмы экспоненциальной сложности, когда размер массива входит в показатель степени, например O(2N ) . Для больших N такие задачи не
решаются за приемлемое время (например, «взламывание» шифров).
68
3
C4
Коды проверяемых
элементов содержания по кодификатору
Примерное время
выполнения задания (мин.)
C2
Макс. балл за выполнение задания
2
Уровень сложности
задания
C1
Умение прочесть
фрагмент программы
на языке программи2.8.1/2.8.2
рования и исправить
допущенные ошибки
Умения написать короткую (10 – 15 строк)
простую программу
обработки массива на
1.2.4/2.8.3
языке программирования или записать
алгоритм на естественном языке
Умения создавать
собственные программы (30 – 50 строк) для
2.8.3
решения задач средней
сложности
Коды видов деятельности (табл. 3)
1
Проверяемые элементы содержания
Обозначение задания в работе
№
3
П
3
30
2
В
2
30
3
В
4
60
Примеры заданий
Задание C1. Умение прочесть фрагмент программы на языке программирования и исправить допущенные ошибки
Требовалось написать программу, которая решает неравенство
ax + b > 0 относительно x для любых чисел a и b , введенных с клавиатуры. Программист допустил в программе ошибку.
var a, b, x: real;
begin
readln(a, b, x);
if a = 0 then
if b > 0 then
write(‘Любое число’)
else
write(‘Нет решений’)
else
write( ‘ x > ‘, –b / a);
end.
69
Последовательно выполните три задания:
1) Укажите числа a, b, x, при которых программа неверно решает
поставленную задачу.
2) Укажите, какая часть программы является лишней.
3) Укажите, как нужно доработать программу, чтобы не было
случаев ее неправильной работы (можно указать любой способ доработки исходной программы).
Решение:
• программа неверно решает поставленную задачу при a = 0 и
b = 0;
• при этом значение x можно не указывать (допустимо x = 0 и
x – любое число);
• лишней является часть программы, связанная с вводом x
с клавиатуры; верно было бы записать readln(a, b);
• возможная доработка программы может быть произведена следующим образом:
readln(a, b);
if a = 0 then
if b = 0 then
write(‘Любое число’)
else
write(‘Нет решений’)
else
write( ‘ x > ‘, –b / a);
Задание C4. Умения создавать собственные программы (30 – 50
строк) для решения задач средней сложности
На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат:
<Фамилия> <Имя> <оценки>,
где <Фамилия> – строка, состоящая не более чем из 20 символов,
<Имя> – строка, состоящая не более чем из 15 символов, <оценки> – через пробел три целых числа, соответствующие оценкам
по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и
<оценки> разделены одним пробелом. Пример входной строки:
Иванов Петр 4 5 3
Требуется написать как можно более эффективную программу
(укажите используемую версию языка программирования, напри70
мер, Borland Pascal 7.0), которая будет выводить на экран фамилии и имена трех худших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и
один из трех худших, то следует вывести и их фамилии и имена.
Решение:
• сначала составим программу в самом общем виде на псевдокоде, чтобы определить ее основные блоки, а потом будем их постепенно описывать на языке программирования:
{ читаем все данные и запоминаем их }
{ находим три худших результата }
{ выводим фамилии и имена тех, чей результат меньше или равен
«третьему худшему» }
• до того, как начать писать код, нужно определить, как хранить данные; в данном случае нужно запомнить несколько элементов данных по каждому ученику, их удобнее объединить в запись с
двумя полями (фамилия-имя и сумма баллов); таких записей нужно
выделить в памяти не менее 100 (по условию), то есть, массив из 100
элементов:
const
LIM=100;
var
Info: array[1..LIM] of record
name: string;
sum: integer;
end;
Чтение данных:
• после того, как мы прочитали фактическое число учеников N,
в цикле считываем и расшифровываем информацию о них, сохраняя все данные в структурах
for i:=1 to N do begin
{ считываем строку данных }
Info[i].name := { фамилия и имя };
Info[i].sum := { сумма баллов };
end;
• будем читать информацию посимвольно, то есть, считывая по
одному символу в переменную c типа char;
• сначала в поле name очередной структуры записываем пустую
строку ‘’ (в которой нет ни одного символа, длина равна нулю)
Info[i].name := ‘’; { пустая строка }
71
• затем считываем символы фамилии и сразу приписываем их в
конец поля name:
repeat
read ( c );
Info[i].name := Info[i].name + c;
until c = ‘ ‘; { пока не прочитали пробел }
• затем так же читаем из входного потока имя, до пробела, и записываем его в конец того же поля name:
repeat
read ( c );
Info[i].name := Info[i].name + c;
until c = ‘ ‘; { пока не прочитали пробел }
• заметьте, что эти два цикла одинаковы, поэтому ввод имени и
фамилии можно записать в виде вложенного цикла так:
Info[i].name := ‘’; { пустая строка }
for k:=1 to 2 do
repeat
read ( c );
Info[i].name := Info[i].name + c;
until c = ‘ ‘; { пока не прочитали пробел }
• обратите внимание, что для организации внутреннего цикла
используется другая переменная, k (а не i, потому что i – переменная главного цикла, она обозначает номер текущего ученика);
• теперь во входном потоке остались три числа, которые мы можем последовательно считывать в целую переменную mark, а затем – добавлять к полю Info[i].sum:
Info[i].sum := 0;
for k:=1 to 3 do
begin
read(mark);
Info[i].sum := Info[i].sum + mark;
end;
readln;
• последняя команда readln пропускает все оставшиеся символы до новой строки (из этой мы прочитали все, что нужно);
• вот полный цикл ввода данных, после его окончания все исходные данные будут записаны в первые N записей массива Info:
for i:=1 to N do
begin
{ ввод имени и фамилии }
Info[i].name := ‘’;
72
for k:=1 to 2 do
repeat
read(c);
Info[i].name := Info[i].name + c;
until c = ‘ ‘;
{ ввод и суммирование оценок }
Info[i].sum := 0;
for k:=1 to 3 do begin
read(mark);
writeln(mark);
Info[i].sum := Info[i].sum + mark;
end;
readln;
end;
Поиск трех худших данных:
• теперь нужно придумать, как за один проход по массиву найти
три худших результата;
• выделим в памяти три целых переменных: min1 (минимальный), min2 («второй минимальный»), min3 («третий минимальный»), в виде начальных значений запишем в каждую из них число, заведомо превышающее максимальную возможную сумму трех
оценок, например, 20 (>5+5+5);
• полный цикл поиска выглядит так:
min1 := 20;
min2 := 20;
min3 := 20;
for i:=1 to N do
begin
if Info[i].sum < min1 then
begin { новый min1 }
min3 := min2;
min2 := min1;
min1 := Info[i].sum;
end
else if Info[i].sum < min2 then
begin { новый min2 }
min3 := min2;
min2 := Info[i].sum;
end
else if Info[i].sum < min3 then
{ новый min3 }
73
min3 := Info[i].sum;
end;
• итак, мы нашли три минимальных результата, и остается вывести на экран фамилии и имена тех, у кого сумма баллов меньше
или равна min3:
for i:=1 to N do
if Info[i].sum <= min3 then
writeln(Info[i].name);
74
Единый государственный экзамен
по информатике и ИКТ
Пояснения к демонстрационному варианту
При ознакомлении с Демонстрационным вариантом 2009 года
следует иметь в виду, что задания, включенные в демонстрационный вариант, не отражают всех вопросов содержания, которые будут проверяться с помощью вариантов КИМ в 2009 году. Полный
перечень вопросов, которые могут контролироваться на едином государственном экзамене 2009 года, приведен в кодификаторе, помещенном на сайте www.fipi.ru, и в соответствующих разделах настоящего методического пособия.
Назначение демонстрационного варианта заключается в том,
чтобы дать возможность любому участнику ЕГЭ и широкой общественности составить представление о структуре будущих КИМ, количестве заданий, их форме, уровне сложности: базовом, повышенном и высоком.
Эти сведения позволят выпускникам выработать стратегию подготовки и сдачи ЕГЭ в соответствии с целями, которые они ставят
перед собой.
Демонстрационный вариант 2009 г.
Инструкция по выполнению работы
На выполнение экзаменационной работы по информатике и ИКТ
отводится 4 часа (240 минут). Экзаменационная работа состоит из 3
частей, включающих 32 задания. На выполнение частей 1 и 2 работы рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий части 3 – 2,5 часа (150 минут).
Часть 1 включает восемнадцать заданий с выбором ответа. К
каждому заданию дается четыре ответа, из которых только один
правильный.
Часть 2 состоит из десяти заданий с кратким ответом (к этим заданиям вы должны самостоятельно сформулировать и записать ответ).
Часть 3 состоит из четырех заданий. Для выполнения заданий
этой части вам необходимо написать развернутый ответ в произвольной форме.
Выполняйте задания в том порядке, в котором они даны. Если
какое-то задание вызывает у вас затруднение, пропустите его и постарайтесь выполнить те, в ответах на которые вы уверены. К пропущенным заданиям можно будет вернуться, если останется время.
75
За каждый правильный ответ в зависимости от сложности задания дается один или более баллов. Баллы, полученные вами за все
выполненные задания, суммируются. Постарайтесь выполнить как
можно больше заданий и набрать как можно больше баллов.
Желаем успеха!
В экзаменационных заданиях используются следующие соглашения:
1.Обозначения для логических связок (операций):
a)отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);
b)конъюнкция (логическое умножение, логическое И) обозначается ∧ (например, А ∧ В) либо & (например, А & В);
c)дизъюнкция (логическое сложение, логическое ИЛИ) обозначается ∨ (например, А ∨ В) либо | (например, А | В);
d)следование (импликация) обозначается → (например, А → В);
e)символ 1 используется для обозначения истины (истинного высказывания);
символ 0 – для обозначения лжи (ложного высказывания).
2.Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) ∨ В равносильны, а А ∨ В и А ∧ В – нет (значения
выражений разные, например, при А = 1, В = 0).
3.Приоритеты логических операций: инверсия (отрицание),
конъюнкция (логическое умножение), дизъюнкция (логическое
сложение), импликация (следование). Таким образом, ¬А ∧ В ∨ С ∧ D
совпадает с ((¬А) ∧ В) ∨ (С ∧ D). Возможна запись А ∧ В ∧ С вместо
(А ∧ В) ∧ С. То же относится и к дизъюнкции: возможна запись
А ∨ В ∨ С вместо (А ∨ В) ∨ С.
76
Часть 1
При выполнении заданий этой части в бланке ответов № 1 под
номером выполняемого вами задания (А1–А18) поставьте знак
«×» в клеточку, номер которой соответствует номеру выбранного
вами ответа.
Al. Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8.
При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?
1) 30
2) 60
3) 120
4) 480
A2. В велокроссе участвуют 119 спортсменов. Специальное
устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого
спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70
велосипедистов?
1) 70 бит
2) 70 байт
3) 490 бит
4) 119 байт
A3. Дано: а=D716, b=3318. Какое из чисел c, записанных в двоичной системе, отвечает условию a<c<b?
1) 11011001
2) 11011100
3) 11010111
4) 11011000
A4. Чему равна сумма чисел 438 и 5616?
1) 1218
2) 1718
3) 6916
4) 10000012
A5. Определите значение переменной c после выполнения следующего фрагмента программы.
Бейсик
Паскаль
Алгоритмический
a=5
a:=5;
a:=5
a=a+6
a:=a+6;
a:=a+6
b = –a
b:= –a;
b:= –a
c = a–2 · b
c:=a–2 · b;
c:=a–2 · b
1) с = –11
2) c = 15
3) с = 27
4) с = 33
77
А6. Дан фрагмент программы, обрабатывающей двухмерный
массив A размера n×n.
Бейсик
Паскаль
Алгоритмический
k=1
k:=1;
k:=1
FOR i = 1 TO n
for i:=1 to n do
нц для i от 1 до n
с = A(i,i)
begin
c:=A[i,i]
A(i,i) = A(k,i)
c:=A[i,i];
A[i,i]:=A[k,i]
A(k,i) = с
A[i,i]:=A[k,i];
A[k,i]:=c
NEXT i
A[k,i]:=c
кц
end
Представим массив в виде квадратной таблицы, в которой для
элемента массива A[i,j] величина i является номером строки, а величина j – номером столбца, в котором расположен элемент. Тогда
данный алгоритм меняет местами
1) два столбца в таблице
2) две строки в таблице
3) элементы диагонали и k-й строки таблицы
4) элементы диагонали и k-го столбца таблицы
A7. Для какого из указанных значений X истинно высказывание
¬((Х>2) → (Х>3))?
1) 1
2) 2
3) 3
4) 4
А8. Укажите, какое логическое выражение равносильно выражению A ∧ ¬(¬B ∨ C).
1) ¬A ∨ ¬B ∨ ¬C
2) A ∧ ¬B ∧ ¬C
3) A ∧ B ∧ ¬C
4) A ∧ ¬B ∧ C
А9. Символом F обозначено одно из указанных ниже логических
выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
78
X
Y
Z
F
1
0
0
1
0
0
0
1
1
1
1
0
Какое выражение соответствует F?
1) ¬X ∧ ¬Y ∧ ¬Z 2) X ∧ Y ∧ Z
3) X ∨ Y ∨ Z
4) ¬X ∨ ¬Y ∨ ¬Z
А10. Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы.
Приведен фрагмент расписания перелетов между ними:
Аэропорт вылета
Аэропорт прилета
Время вылета
Время прилета
СОСНОВО
КРАСНЫЙ
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
А11. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность
символов БАВГ и записать результат шестнадцатеричным кодом,
то получится
1) 4B
2) 411
3) BACD
4) 1023
А12. Цепочка из трех бусин, помеченных латинскими буквами,
формируется по следующему правилу. В конце цепочки стоит одна
из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой
нет на третьем месте. В середине – одна из бусин А, C, E, B, не стоящая на первом месте. Какая из перечисленных цепочек создана по
этому правилу?
1) CBB
2) EAC
3) BCD
4) BCB
79
А13. Для групповых операций с файлами используются маски
имен файлов.
Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут
встречаться следующие символы:
Символ «?» (вопросительный знак) означает ровно один произвольный символ.
Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.
Определите, какое из указанных имен файлов удовлетворяет маске:
?hel*lo.c?*.
1) hello.c
2) hello.cpp
3) hhelolo.cpp
4) hhelolo.c
A14. Результаты тестирования представлены в таблице:
Фамилия
Пол Математика
Русский
язык
Химия
Информатика
Биология
Аганян
ж
82
56
46
32
70
Воронин
м
43
62
45
74
23
Григорчук
м
54
74
68
75
83
Роднина
ж
71
63
56
82
79
Сергеенко
ж
33
25
74
38
46
Черепанова
ж
18
92
83
28
61
Сколько записей в ней удовлетворяют условию
«Пол=’ж’ ИЛИ Химия>Биология»?
1) 5
2) 2
3) 3
4) 4
А15. Для кодирования цвета фона страницы Интернет используется атрибут bgcolor=”#ХХХХХХ”, где в кавычках задаются
шестнадцатеричные значения интенсивности цветовых компонент
в 24-битной RGB-модели. Какой цвет будет у страницы, заданной
тэгом <body bgcolor=”#FFFFFF”>?
1) белый
2) зеленый
3) красный
4) синий
А16. В электронной таблице значение формулы =СУММ(B1:B2)
равно 5. Чему равно значение ячейки B3, если значение формулы
=СРЗНАЧ(B1:B3) равно 3?
1) 8
80
2) 2
3) 3
4) 4
A17. На диаграмме показано количество призеров олимпиады по
информатике (И), математике (М), физике (Ф) в трех городах России.
Какая из диаграмм правильно отражает соотношение общего
числа призеров по каждому предмету для всех городов вместе?
1)
2)
3)
4)
А18. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
вверх
вниз
влево
вправо
При выполнении любой из этих команд РОБОТ перемещается на
одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у
каждой стороны той клетки, где находится РОБОТ:
сверху
снизу
слева
справа
свободно
свободно
свободно
свободно
Цикл ПОКА < условие > команда выполняется, пока условие
истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что,
выполнив предложенную ниже программу, РОБОТ остановится в
той же клетке, с которой он начал движение?
81
НАЧАЛО
ПОКА < снизу свободно > вниз
ПОКА < слева свободно > влево
ПОКА < сверху свободно > вверх
ПОКА < справа свободно > вправо
КОНЕЦ
1) 1
2) 2
3) 3
4) 0
Часть 2
Ответом к заданиям этой части (В1–В10) является набор символов, которые следует записать в бланк ответов № 1 справа от
номера соответствующего задания, начиная с первой клеточки.
Каждый символ пишите в отдельной клеточке в соответствии с
приведенными образцами.
B1. Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно
находиться на табло, чтобы с его помощью можно было передать 18
различных сигналов?
B2. Запишите значение переменной b после выполнения фрагмента алгоритма:
Примечание: знаком := обозначена операция присваивания,
знаком * обозначена операция умножения.
82
ВЗ. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11.
В4. Каково наибольшее целое число X, при котором истинно высказывание (50<X·X) → (50>(X+1) ·(X+1))?
B5. У исполнителя Калькулятор две команды, которым присвоены номера:
1.прибавь 3
2.умножь на 4
Выполняя первую из них, Калькулятор прибавляет к числу на
экране 3, а выполняя вторую, умножает его на 4. Запишите порядок
команд в программе получения из числа 3 числа 57, содержащей не
более 6 команд, указывая лишь номера команд.
(Например, программа 21211 это программа
умножь на 4
прибавь 3
умножь на 4
прибавь 3
прибавь 3
которая преобразует число 2 в 50.)
B6. Классный руководитель пожаловался директору, что у него в
классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то
ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша,
но не знает, кто из них правдив, а кто – нет. Однажды все трое прогуляли урок астрономии. Директор знает, что никогда раньше никто из них не прогуливал астрономию. Он вызвал всех троих в кабинет и поговорил с мальчиками. Коля сказал: “Я всегда прогуливаю
астрономию. Не верьте тому, что скажет Саша”. Саша сказал: “Это
был мой первый прогул этого предмета”. Миша сказал: “Все, что говорит Коля, – правда”. Директор понял, кто из них кто. Расположите первые буквы имен мальчиков в порядке: “говорит всегда правду”, “всегда лжет”, “говорит правду через раз”. (Пример: если бы
имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ)
B7. Скорость передачи данных через ADSL-соединение равна
128000 бит/c. Через данное соединение передают файл размером
625 Кбайт. Определите время передачи файла в секундах.
В8. Строки (цепочки символов латинских букв) создаются по следующему правилу.
83
Первая строка состоит из одного символа – латинской буквы «А».
Каждая из последующих цепочек создается такими действиями: в
очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется
i-я буква алфавита), к ней справа дважды подряд приписывается
предыдущая строка. Вот первые 4 строки, созданные по этому правилу:
(1) A
(2) BAA
(3) CBAABAA
(4) DCBAABAACBAABAA
Латинский алфавит (для справки):
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Запишите семь символов подряд, стоящие в восьмой строке со
126-го по 132-е место (считая слева направо).
В9. Петя записал IP-адрес школьного сервера на листке бумаги
и положил его в карман куртки. Петина мама случайно постирала
куртку вместе с запиской. После стирки Петя обнаружил в кармане
четыре обрывка с фрагментами IP-адреса. Эти фрагменты обозначены буквами А, Б, В и Г. Восстановите IP-адрес.
В ответе укажите последовательность букв, обозначающих фрагменты, в порядке, соответствующем IP-адресу.
А
Б
В
Г
В10. В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.
1
принтеры & сканеры & продажа
2
принтеры & продажа
3
принтеры | продажа
4
принтеры | сканеры | продажа
Не забудьте перенести все ответы в бланк ответов № 1.
84
Часть 3
Для записи ответов к заданиям этой части (С1–С4) используйте
бланк ответов № 2. Запишите сначала номер задания (С1 и т.д.), а
затем – полное решение. Ответы записывайте четко и разборчиво.
C1.
Требовалось написать программу, которая вводит с клавиатуры координаты
точки на плоскости (x,y – действительные числа) и определяет принадлежность точки заштрихованной области,
включая ее границы. Программист торопился и написал программу неправильно.
ПРОГРАММА
НА ПАСКАЛЕ
ПРОГРАММА
НА БЕЙСИКЕ
ПРОГРАММА
НА СИ
var x,y: real;
INPUT x, y
void main(void)
begin
IF y<=1 THEN
{ float x,y;
readln(x,y);
IF x>=0 THEN
scanf(“%f%f”,&х,&у);
if y<=1 then
IF y>=SIN(x) THEN if (у<=1)
if x>=0 then
PRINT “принадлежит”
ELSE
if (x>=0)
PRINT “не принадлежит”
ENDIF
printf(“принадлежит”);
if y>=sin(x) then
write(‘принадлежит’)
else
write(‘не принадлежит’) ENDIF
end.
ENDIF
END
if (y>=sin(x))
else
printf(“не принадлежит”);
}
Последовательно выполните следующее:
1)Приведите пример таких чисел x, y, при которых программа
неверно решает поставленную задачу.
2)Укажите, как нужно доработать программу, чтобы не было
случаев ее неправильной работы. (Это можно сделать несколькими
способами, поэтому можно указать любой способ доработки исходной программы.)
C2. Опишите на русском языке или одном из языков программирования алгоритм получения из заданного целочисленного массива
85
размером 30 элементов другого массива, который будет содержать
модули значений элементов первого массива (не используя специальной функции, вычисляющей модуль числа).
C3. Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что
игрок перемещает фишку из точки с координатами (x,y) в одну из
трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает
игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при
безошибочной игре обоих игроков – игрок, делающий первый ход,
или игрок, делающий второй ход? Каким должен быть первый ход
выигрывающего игрока? Ответ обоснуйте.
C4. На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет
формат: <Фамилия> <Инициалы> <номер школы>, где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> – строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> – не более чем двузначный номер. <Фамилия>
и <Инициалы>, а также <Инициалы> и <номер школы> разделены
одним пробелом. Пример входной строки: Иванов П.С. 57
Требуется написать как можно более эффективную программу
(укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ
может быть несколько). При этом необходимо вывести информацию
только по школам, пославшим хотя бы одного участника. Следует
учитывать, что N>=1000.
86
87
88
89
90
Ответы к демонстрационному варианту
ЧАСТЬ 1
№ задания
Ответ
№ задания
Ответ
А1
2
А10
4
А2
3
А11
1
А3
4
А12
1
А4
2
А13
3
А5
4
А14
1
А6
3
А15
1
А7
3
А16
4
А8
3
А17
1
А9
4
А18
1
ЧАСТЬ 2
№ задания
Ответ
В1
3
В2
511
В3
5,21
В4
7
В5
22111
В6
СКМ
В7
40
В8
BAAGFED
В9
ГБВА
В10
1234
91
Список литературы
1. Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. – СПб: Тригон, 2009.
2. Зорин М.В., Зорина Е.М. ЕГЭ 2010. Информатика. Сборник
заданий. – М: Эксмо, 2009.
3. Зорин М.В., Зорина Е.М. Тестирование по информатике в
формате ЕГЭ: рекомендации по решению заданий. Волгоград: Учитель, 2009.
4. Крылов С.С., Лещинер В.Р., Якушкин П.А. ЕГЭ-2009. Информатика. Универсальные материалы для подготовки учащихся. – М:
Интеллект-центр, 2009.
5. Макарова Н.В. Информатика и ИКТ: подготовка к ЕГЭ.
СПб.: Питер, 2007.
6. Молодцов В.А., Рыжикова Н.Б. Репетитор по информатике
для подготовки к ЕГЭ. Ростов-на-Дону: Феникс, 2008.
7. Молодцов В.А., Рыжикова Н.Б. Информатика: тесты, задания, лучшие методики. Ростов-на-Дону: Феникс, 2008.
8. Поляков К.Ю. ЕГЭ по информатике. http://kpolyakov.narod.
ru/school/ege.htm
9. Сафронов И.К. Готовимся к ЕГЭ. Информатика. СПб: БХВПетербург, 2009.
10. Самылкина Н.Н., Островская Е.М. ЕГЭ 2010. Информатика. Тренировочные задания. – М: Эксмо, 2009.
11. Самылкина Н.Н., Русаков С.В., Шестаков А.П., Баданина
С.В. Готовимся к ЕГЭ по информатике. Элективный курс. – М: Бином, 2008.
12. Якушкин П.А., Крылов С.С. ЕГЭ 2010. Информатика. Сборник экзаменационных заданий. – М: Эксмо, 2009.
13. Сайт Министерства образования и науки Российской Федерации http://mon.gov.ru/
14. Сайт Федерального института педагогических измерений
(ФИПИ) http://www.fipi.ru/
15.Вики-учебник для подготовки к ЕГЭ по информатике
http://letopisi.ru/index.php/Вики-учебник_для_подготовки_к_
ЕГЭ/Раздел_Информатика
16. Тесты on-line http://www.klyaksa.net/test_online/
92
Содержание
Введение................................................................... Структура экзамена................................................ Проведение экзамена.............................................. Материалы для подготовки...................................... Информация и ее кодирование..................................... Кодификатор......................................................... Теоретические сведения.......................................... Примеры заданий. ................................................. Алгоритмизация и программирование.......................... Кодификатор......................................................... Теоретические сведения.......................................... Примеры заданий. ................................................. Основы логики.......................................................... Кодификатор......................................................... Теоретические сведения.......................................... Примеры заданий. ................................................. Моделирование и компьютерный эксперимент............... Кодификатор......................................................... Теоретические сведения.......................................... Примеры заданий. ................................................. Программные средства информационных и
коммуникационных технологий.................................. Кодификатор......................................................... Теоретические сведения.......................................... Примеры заданий. ................................................. Технология обработки графической и звуковой
информации.............................................................. Кодификатор......................................................... Теоретические сведения.......................................... Примеры заданий. ................................................. Технология обработки информации в электронных
таблицах................................................................... Кодификатор......................................................... Теоретические сведения.......................................... Примеры заданий. ................................................. Технология хранения, поиска и сортировки информации
в базах данных. ......................................................... 3
3
9
10
12
12
12
18
22
22
22
26
37
37
37
42
45
45
45
46
48
48
48
49
51
51
51
52
54
54
54
57
60
93
Кодификатор.........................................................
Теоретические сведения..........................................
Примеры заданий. .................................................
Телекоммуникационные технологии............................
Кодификатор.........................................................
Теоретические сведения..........................................
Примеры заданий. .................................................
Технологии программирования....................................
Кодификатор.........................................................
Теоретические сведения..........................................
Примеры заданий. .................................................
Единый государственный экзамен по информатике
и ИКТ.......................................................................
Часть 1.................................................................
Часть 2.................................................................
Часть 3.................................................................
Ответы к демонстрационному варианту.........................
Список литературы................................................
94
60
60
61
63
63
63
64
66
66
66
69
75
77
82
85
91
92
Документ
Категория
Без категории
Просмотров
1
Размер файла
3 382 Кб
Теги
molchanov, andreev
1/--страниц
Пожаловаться на содержимое документа