Задачи вступительных экзаменов по информатике в вуз
Яковлева Л.Л., доцент кафедры информатики и прикладной математики ЧитГУ
Экзамен по информатике включен в программу вступительных испытаний очень немногих высших учебных заведений. Тем не менее в ряде вузов такой экзамен есть, и при отсутствии единых стандартов каждый конкретный вуз сам определяет его содержание. В настоящее время требования вузов различаются настолько сильно, что без точного знания специфики конкретного вуза сдать экзамен по информатике практически невозможно. Единственный эффективный путь для абитуриента в такой ситуации — это занятия на специальных учебных курсах, организованных на базе самого вуза или среднего учебного заведения, имеющего с вузом договорные отношения и обладающего доступом к необходимым учебно-методическим материалам. Значительную роль может сыграть обучение в профильных классах. Практика показывает, что в классах математического профиля можно получить неплохие результаты. При этом от учителя требуется грамотное планирование учебной нагрузки, соответствие учебных программ специальным требованиям вступительного экзамена.
Многолетние наблюдения автора показывают, что на экзамене по информатике абитуриент должен продемонстрировать знания и умения прежде всего в тех областях, где требуется сочетание теоретических знаний и практических навыков, где все результаты могут быть представлены в точном формализованном виде и при этом могут надежно диагностировать качество знаний и умений, гарантировать от влияния какой-либо случайности. Очевидно, что эти требования могут быть выполнены в полной мере только при решении хорошо формализованных задач. Обычно это задания по машинной логике и арифметике, теории информации и кодированию, алгоритмизации и программированию. Именно эти направления лежат в основе экзаменационных заданий в вуз.
Читинский государственный университет практикует вступительный экзамен по информатике на технические специальности на протяжении ряда лет. При этом не только для тех, кто определил информатику как сферу своих будущих профессиональных интересов.
Экзамен проводится в тестовой форме, в соответствии с обязательным минимумом содержания среднего (полного) общего образования по предмету и приказом о порядке приема в государственные образовательные учреждения высшего профессионального образования.
Для того чтобы успешно выдержать вступительные испытания, абитуриент должен успешно освоить и свободно ориентироваться в содержании следующих тем:
- Представление информации.
Язык как способ представления информации. Кодирование. Двоичная форма представления информации. Вероятностный подход к определению количества информации. Единицы измерения информации.
- Системы счисления и основы логики.
Системы счисления. Двоичная система счисления. Двоичная арифметика. Системы счисления, используемые в компьютере. Алгебра логики. Основные логические функции. Формы записи логических функций. Основы теории множеств. Диаграммы Эйлера-Венна. Структурные и комбинационно-логические схемы. Представление чисел в памяти ЭВМ. Машинные коды.
- Алгоритмизация и программирование.
Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное исполнение алгоритмов. Основные алгоритмические конструкции. Вспомогательные алгоритмы.
Различные технологии программирования (алгоритмическое, объектно-ориентированное, логическое). Алгоритмическое программирование: основные типы данных, процедуры и функции. Объектно-ориентированное программирование: объект, свойства объекта, операции над объектом.
- Технология обработки числовой информации.
К сожалению, во многих учебных заведениях общего образования подготовка учащихся по дисциплине «Информатика» оставляет желать лучшего. Причины этого, скорее всего, связаны с небольшим количеством часов, выделяемых на дисциплину, с отсутствием должных знаний у преподавателей, а также с тем, что данные темы носят не технологический характер и попросту не очень интересны детям. Кроме этого, задания вступительного экзамена имеют нетрадиционные формулировки, уникальные алгоритмы решения и трудоемкие вычисления.
Хотелось бы привести решения задачи, представляющей наибольшую сложность.
Задача: В сейфе банкира Богатеева лежат банкноты достоинством 1, 10 или 100 талеров каждая. Из них 8 достоинством не в 1 талер. Банкир раскрыл свой сейф и наугад вытащил из него одну банкноту. Информационный объем сообщения «Из сейфа взята банкнота достоинством в 100 талеров» равен 5 бит. Количество информации, содержащееся в сообщении «Из сейфа взята банкнота достоинством в 10 талеров», равно 5-log27 бит. Общая сумма денег в талерах, лежащая в сейфе равна ____.
Решение:
Необходимые теоретические сведения. Задача относится к теме «Вероятностный подход к определению количества информации», которая традиционно вызывает трудности.
В настоящее время получили распространение подходы к определению понятия «количество информации», основанные на том, что информацию, содержащуюся в сообщении, можно нестрого трактовать в смысле её новизны или, иначе, уменьшения неопределённости наших знаний об объекте. Эти подходы используют математические понятия вероятности и логарифма.
Подходы к определению количества информации. Формулы Хартли и Шеннона. Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равно-вероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N.
Формула Хартли: I = log2N.
Допустим, нужно угадать одно число из набора чисел от единицы до ста. По формуле Хартли можно вычислить, какое количество информации для этого требуется: I = log2100 ? 6,644. Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 единицам информации.
Другие примеры равновероятных сообщений:
· при бросании монеты: «выпала решка», «выпал орел» (количество информации 1 бит (1-log22);
· на странице книги: «количество букв чётное», «количество букв нечётное».
Определим теперь, являются ли равновероятными сообщения «первой выйдет из дверей здания женщина» и «первым выйдет из дверей здания мужчина». Однозначно ответить на этот вопрос нельзя. Все зависит от того, о каком именно здании идет речь. Если это, например, станция метро, то вероятность выйти из дверей первым одинакова для мужчины и женщины, а если это военная казарма, то для мужчины эта вероятность значительно выше, чем для женщины.
Для задач такого рода американский учёный Клод Шеннон предложил в 1948 г. другую формулу определения количества информации, учитывающую возможную неодинаковую вероятность сообщений в наборе.
Формула Шеннона:
I = — ( p1log2 p1 + p2 log2 p2 + . . . + pN log2 pN),
где pi — вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.
Легко заметить, что если вероятности p1, ..., pN равны, то каждая из них равна 1/N, и формула Шеннона превращается в формулу Хартли.
Помимо двух рассмотренных подходов к определению количества информации, существуют и другие. Важно помнить, что любые теоретические результаты применимы лишь к определённому кругу случаев, очерченному первоначальными допущениями.
В качестве единицы информации Клод Шеннон предложил принять один бит (англ. bit — binary digit — двоичная цифра).
Бит в теории информации — количество информации, необходимое для различения двух равновероятных сообщений (типа “орел”—”решка”, “чет”—”нечет” и т.п.).
В вычислительной технике битом называют наименьшую «порцию» памяти компьютера, необходимую для хранения одного из двух знаков «0» и «1», используемых для внутримашинного представления данных и команд.
Алгоритм решения.
1) Вводим условные обозначения:
К1 – количество монет достоинством в 1 талер.
К10 – количество монет достоинством в 10 талеров.
К100 – количество монет достоинством в 100 талеров.
2) Сообщение о том, что достоинством не в 1 талер 8 монет выражается равенством:
К10+К100=8
3) Поскольку события не равновероятны, используем формулу Шеннона:
а) вероятность события «Из сейфа взята банкнота достоинством в 100 талеров» (обозначим её p100):
Следовательно, количество информации в этом сообщении, исходя из условий задачи, выражается формулой:
б) вероятность события «Из сейфа взята банкнота достоинством в 10 талеров» (обозначим её p10):
Следовательно, количество информации в этом сообщении, исходя из условий задачи, выражается формулой:
4) Учитывая, что К10+К100=8, получаем систему уравнений:
По свойству логарифмов
Решаем систему уравнений:
В результате K1=24, K10=7, K100=1.
Общая сумма денег, лежащая в сейфе, равна 24*1+7*10+1*100=194 талера.
Ответ: 194.
|
