Ответы на билеты по информатике 2006-2008 гг. (базовый уровень)

Билет 1
Понятиеинформации. Виды информационных процессов. Поиск и систематизация
информации.Хранение информации; выбор способа хранения информации. Передача
информации всоциальных, биологических и технических системах.
1. Компьютер —это электронный прибор, предназначенный для работы с информацией
посредствомавтоматизированной регистрации, хранения, приема, передачи,
обработки ивоспроизведения данных.
Понятие данных.Все явления природы сопровождаются энергетическим обменом. В его
ходе телавыделяют и поглощают энергию. Энергетический обмен свойствен всем
известнымприродным процессам: физическим, химическим, биологическим и их
комбинациям.
Энергияраспространяется в форме сигналов. При взаимодействии сигналов с
веществомпроисходит изменение состояний и свойств материальных тел. Если
изменениезафиксировано, говорят о том, что произошла регистрация сигнала. Так
образуютсяданные. Данные -это зарегистрированные сигналы любой физической
природы.
Текст на бумаге —это зарегистрированный результат взаимодействия бумаги и
красителя. Записьна магнитной ленте — это зарегистрированные результаты
изменениямагнитного поля вблизи записывающей магнитной головки. Кратеры на Луне
— этозарегистрированные результаты взаимодействия космических тел с ее
поверхностью. Кратерына Земле — это зарегистрированные результаты активности
внутреннеговещества планеты.
Информация. Когдаговорят о том, что компьютеры предназначены для работы с
информацией,имеют в виду, что информация содержится в данных. Компьютеры
работают только сданными, а информация образуется в момент взаимодействия
данных синформационными методами.
Слово«информация» происходит от латинского слова informatio, что в переводе
означаетсведение, разъяснение, ознакомление. Понятие «информация» является
базовым в курсеинформатики, невозможно дать его определение через другие, более
«простые»понятия. В геометрии, например, невозможно выразить содержание базовых
понятий «точка»,«луч», «плоскость» через более простые понятия. Содержание
основных, базовыхпонятий в любой науке должно быть пояснено на примерах или
выявлено путем ихсопоставления с содержанием других понятий.
В случае спонятием «информация» проблема его определения еще более сложная, так
как оно являетсяобщенаучным понятием. Данное понятие используется в различных
науках(информатике, кибернетике, биологии, физике и др.), при этом в каждой
науке понятие«информация» связано с различными системами понятий.
Информация вбиологии. В биологии, которая изучает живую природу, понятие
«информация»связывается с целесообразным поведением живых организмов. Такое
поведениестроится на основе получения и использования организмом информации об
окружающей среде.
Понятие«информация» в биологии используется также в связи с исследованиями
механизмовнаследственности. Генетическая информация передается по наследству и
хранится во всехклетках живых организмов. Гены представляют собой сложные
молекулярныеструктуры, содержащие информацию о строении живых организмов.
Последнееобстоятельство позволило проводить научные эксперименты по
клонированию, тоесть созданию точных копий организмов из одной клетки.
Информация вкибернетике. В кибернетике (науке об управлении) понятие
«информация»связано с процессами управления в сложных системах (живых
организмах илитехнических устройствах). Жизнедеятельность любого организма или
нормальноефункционирование технического устройства зависит от процессов
управления,благодаря которым поддерживаются в необходимых пределах значения их
параметров.Процессы управления включают в себя получение, хранение,
преобразование ипередачу информации.
Информация вобществе. Человек – существо социальное, для общения с другими
людьми он долженобмениваться с ними информацией. В обыденной жизни информация –
это сведения,сообщение, осведомленность о положении дел.
Таким образом,информация в информатике – это:
Информация – этознания человека (декларативные – «Я знаю, что…» и процедурные –
«Я знаю как…»),которые он получает из окружающего мира и которые реализует с
помощьювычислительной техники.

2. Информационныепроцессы.
Процессы,связанные со сбором, хранением, поиском, обработкой, кодированием и
передачейинформации, называют информационными процессами.
Поиск информации– это процесс получения информации из внешнего мира и
приведение ее кстандарту для данной информационной системы. Обмен информацией
междувоспринимающей ее системой и окружающей средой осуществляется посредством
сигналов илизнаков.
Сигналы можноразделить на несколько типов:
- по физическойприроде (электромагнитный, световой, тепловой, звуковой,
механический,биохимический);
- по способувосприятия (зрительный, слуховой, осязательный, вкусовой, болевой,
физиологический).
Знаками можносчитать алфавит любого языка, знаки языка жестов, любые коды или
шифры, ноты ит.д.
Обработкаинформации – это получение одних информационных объектов из других
путем выполнениянекоторых действий


Входнаяинформация
Обработкаинформации
Выходнаяинформация



Хранениеинформации – это ее накопление на различных носителях.
Носительинформации – среда для записи и хранения информации:
- любойматериальный предмет;
- волны различнойприроды;
- акустическиеносители;
-электромагнитные носители;
- гравитационныеносители;
- компьютерныеносители.
Носителиинформации характеризуются информационной емкостью, то есть количеством
информации,которое они могут хранить. Наиболее информационно емкими являются
молекулы ДНК,которые имеют очень малый размер и плотно упакованы. Это позволяет
хранить огромноеколичество информации (до 1021 битов в 1 см3), что дает
возможностьорганизму развиваться из одной-единственной клетки, содержащей всю
необходимуюгенетическую информацию.
Современныемикросхемы памяти позволяют хранить в 1 см3 до 1010 битов
информации,однако это в 100 миллиардов раз меньше, чем в ДНК. Можно сказать,
что современныетехнологии пока существенно проигрывают биологической эволюции.
Однако еслисравнивать информационную емкость традиционных носителей информации
(книг) исовременных компьютерных носителей, то прогресс очевиден. На каждом
гибком магнитномдиске может храниться книга объемом около 600 страниц, а на
жестком магнитномдиске или DVD — целая библиотека, включающая десятки тысяч
книг.
Большое значениеимеет надежность и долговременность хранения информации.
Большуюустойчивость к возможным повреждениям имеют молекулы ДНК, так как
существуетмеханизм обнаружения повреждений их структуры (мутаций) и
самовосстановления.
Надежность(устойчивость к повреждениям) достаточно высока у аналоговых
носителей,повреждение которых приводит к потери информации только на
поврежденномучастке. Поврежденная часть фотографии не лишает возможности видеть
оставшуюся часть,повреждение участка магнитной ленты приводит лишь к временному
пропаданию звукаи так далее.
Цифровые носителигораздо более чувствительны к повреждениям, даже утеря одного
бита данных намагнитном или оптическом диске может привести к невозможности
считать файл, тоесть к потере большого объема данных. Именно поэтому необходимо

3. Передачаинформации в биологических системах. Общими для живой природы
являются прнципынаследования, связанные с передачей информации от предков
потомкам черезданные, хранящиеся в цепочках ДНК.
Передачаинформации в социальных системах. Символьная информация передается в
речевой иписьменных формах. В тех случаях, когда человеку недостаточно
естественныхметодов для работы с данными, он может использовать искусственные
методы. Широкоизвестно использование телескопов, микроскопов, радиоприемников,
телевизионныхприемников, магнитофонов и других устройств. Например, человек не
обладаетестественными органами чувств, способными регистрировать радиоволны. В
этом случае ониспользует радиоприемник, с помощью которого получает информацию
из данных,регистрируемых антенной.
Передачаинформации в технических системах. Любая техническая система передачи
информациисостоит из источника, приемника, устройств кодирования и
декодирования иканала связи. Под кодированием понимается преобразование
информации,идущей от источника, в форму, пригодную для ее передачи по каналу
связи.Декодирование – это обратное преобразование. Передача информации
происходит последующей схеме:

Информация
Канал связи
Помехи
Информация


Виды информации:
1)     аналоговая –непрерывная (воспринимаетсячеловеком);
2)     Дискретная – скачкообразная (воспринимаетсявычислительной техникой –
информациякодируется в двоичную форму, а затем декодируется в текст,
изображение извук).

2
Понятие окодировании информации. Выбор способа представления информации в
соответствии споставленной задачей. Универсальность дискретного (цифрового)
представленияинформации. Двоичное кодирование.
2 билет
1. Кодированиеинформации
Преобразованиеинформации из одной формы представления (знаковой системы) в
другую называетсякодированием.
Средствомкодирования служит таблица соответствия знаковых систем, которая
устанавливаетвзаимно однозначное соответствие между знаками или группами знаков
двух различныхзнаковых систем.
В процессе обменаинформацией часто приходится производить операции кодирования
и декодированияинформации. При вводе знака алфавита в компьютер путем нажатия
соответствующейклавиши на клавиатуре происходит кодирование знака, то есть
преобразованиеего в компьютерный код. При выводе знака на экран монитора или
принтерпроисходит обратный процесс — декодирование, когда из компьютерного кода
знакпреобразуется в его графическое изображение.
2. Выбор способапредставления информации в соответствии с поставленной задачей.
Язык как знаковаясистема
Для обменаинформацией с другими людьми человек использует естественные языки
(русский,английский, китайский и др.), то есть информация представляется с
помощьюестественных языков. В основе языка лежит алфавит, то есть набор
символов(знаков), которые человек различает по их начертанию. В основе русского
языка лежит кириллица,содержащая 33 знака, английский язык использует латиницу
(26 знаков),китайский язык использует алфавит из десятков тысяч знаков
(иероглифов).
Последовательностисимволов алфавита в соответствии с правилами грамматики
образуют основныеобъекты языка — слова. Правила, согласно которым образуются
предложения изслов данного языка, называются синтаксисом. Необходимо отметить,
что вестественных языках грамматика и синтаксис языка формулируются с помощью
большогоколичества правил, из которых существуют исключения, так как такие
правиласкладывались исторически.
Наряду сестественными языками были разработаны формальные языки (системы
счисления, языкалгебры, языки программирования и др.). Основное отличие
формальных языковот естественных состоит в наличии строгих правил грамматики и
синтаксиса.
Например, системысчисления можно рассматривать как формальные языки, имеющие
алфавит (цифры) ипозволяющие не только именовать и записывать объекты (числа),
но и выполнятьнад ними арифметические операции по строго определенным правилам.
Некоторые языкииспользуют в качестве знаков не буквы и цифры, а другие символы,
напримерхимические формулы, ноты, изображения элементов электрических или
логических схем,дорожные знаки, точки и тире (код азбуки Морзе) и др.

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

3. Двоичноекодирование информации
В компьютере дляпредставления информации используется двоичное кодирование, так
как удалосьсоздать надежно работающие технические устройства, которые могут со
стопроцентнойнадежностью сохранять и распознавать не более двух различных
состояний (цифр):
·         электромагнитные реле(замкнуто/разомкнуто), широко использовались в
конструкцияхпервых ЭВМ;
·         участок поверхности магнитногоносителя информации
(намагничен/размагничен);
·         участок поверхности лазерного диска(отражает/не отражает);
·         триггер (см. п. 3.7.3), можетустойчиво находиться в одном из двух
состояний, широкоиспользуется в оперативной памяти компьютера.
Все видыинформации в компьютере кодируются на машинном языке, в виде логических
последовательностейнулей и единиц.
Цифры двоичногокода можно рассматривать как два равновероятных состояния
(события). Призаписи двоичной цифры реализуется выбор одного из двух возможных
состояний (однойиз двух цифр) и, следовательно, она несет количество
информации,равное 1 биту.
Даже сама единицаизмерения количества информации бит (bit) получила свое
название отанглийского словосочетания BInary digiT (двоичная цифра).
Важно, что каждаяцифра машинного двоичного кода несет информацию в 1 бит. Таким
образом, двецифры несут информацию в 2 бита, три цифры — в 3 бита и так далее.
Количествоинформации в битах равно количеству цифр двоичного машинного кода.

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

Дискретизация —это преобразование непрерывных изображений и звука в набор
дискретныхзначений в форме кодов.
Двоичноекодирование текстовой информации. Традиционно для кодирования одного
символаиспользуется количество информации, равное 1 байту, то есть  I = 1 байт
= 8 битов.
Для кодированияодного символа требуется 1 байт информации.
Еслирассматривать символы как возможные события, то можно вычислить, какое
количестворазличных символов можно закодировать:
N = 2I= 28 = 256.
Такое количествосимволов вполне достаточно для представления текстовой
информации,включая прописные и строчные буквы русского и латинского алфавита,
цифры, знаки,графические символы и пр.
Кодированиезаключается в том, что каждому символу ставится в соответствие
уникальныйдесятичный код от 0 до 255 или соответствующий ему двоичный код от
00000000 до 11111111.Таким образом, человек различает символы по их
начертаниям, акомпьютер — по их кодам.

3 Билет
Вероятностный иалфавитный подходы к измерению информации. Единицы измерения
информации.Скорость передачи информации. Пропускная способность канала связи.
Информация изнания. Человек получает информацию из окружающего мира с помощью
органов чувств,анализирует ее и выявляет существенные закономерности с помощью
мышления, хранитполученную информацию в памяти. Процесс систематического
научного познанияокружающего мира приводит к накоплению информации в форме
знаний (фактов,научных теорий и так далее). Таким образом, с точки зрения
процесса познанияинформация может рассматриваться как знания.
Информацию,которую получает человек, можно считать мерой уменьшения
неопределенностизнаний. Если некоторое сообщение приводит к уменьшению
неопределенностинаших знаний, то можно говорить, что такое сообщение содержит
информацию.
1. Уменьшениенеопределенности знаний (вероятностный подход). Подход к
информации какмере уменьшения неопределенности знаний позволяет количественно
измерятьинформацию, что чрезвычайно важно для информатики. Рассмотрим вопрос об
определенииколичества информации более подробно на конкретных примерах.
Пусть у насимеется монета, которую мы бросаем на ровную поверхность. С равной
вероятностьюпроизойдет одно из двух возможных событий — монета окажется в одном
из двухположений: «орел» или «решка».

Можно говорить,что события равновероятны, если при возрастающем числе опытов
количества выпадений«орла» и «решки» постепенно сближаются. Например, если мы
бросим монету 10раз, то «орел» может выпасть 7 раз, а решка — 3 раза, если
бросим монету 100раз, то «орел» может выпасть 60 раз, а «решка» — 40 раз, если
бросим монету1000 раз, то «орел» может выпасть 520 раз, а «решка» — 480 и так
далее.

В итоге при оченьбольшой серии опытов количества выпадений «орла» и «решки»
практическисравняются.
Перед броскомсуществует неопределенность наших знаний (возможны два события),
и, как упадетмонета, предсказать невозможно. После броска наступает полная
определенность,так как мы видим (получаем зрительное сообщение), что монета в
данный моментнаходится в определенном положении (например, «орел»). Это
сообщениеприводит к уменьшению неопределенности наших знаний в два раза, так
как до броска мыимели два вероятных события, а после броска — только одно, то
есть в два разаменьше.
В окружающейдействительности достаточно часто встречаются ситуации, когда может
произойтинекоторое количество равновероятных событий. Так, при бросании
равностороннейчетырехгранной пирамиды существуют 4 равновероятных события, а
при бросаниишестигранного игрального кубика — 6 равновероятных событий.
Чем большеколичество возможных событий, тем больше начальная неопределенность и
соответственнотем большее количество информации будет содержать сообщение о
результатахопыта.
3. Единицыизмерения количества информации. Для количественного выражения любой
величинынеобходимо определить единицу измерения. Так, для измерения длины в
качестве единицывыбран метр, для измерения массы — килограмм и так далее.
Аналогично, дляопределения количества информации необходимо ввести единицу
измерения.
За единицуколичества информации принимается такое количество информации,
которое содержитсообщение, уменьшающее неопределенность в два раза. Такая
единица названа«бит».
Если вернуться копыту с бросанием монеты, то здесь неопределенность как раз
уменьшается в двараза и, следовательно, полученное количество информации равно
1 биту.
Минимальной единицейизмерения количества информации является бит, а следующей
по величинеединицей является байт, причем 1 байт = 23 бит = 8 бит.
В информатикесистема образования кратных единиц измерения количества информации
несколькоотличается от принятых в большинстве наук. Традиционные метрические
системы единиц,например Международная система единиц СИ, в качестве множителей
кратных единициспользуют коэффициент 10n, где n = 3, 6, 9 и так далее, что
соответствуетдесятичным приставкам Кило (103), Мега (106), Гига (109) и так
далее.
Компьютероперирует числами не в десятичной, а в двоичной системе счисления,
поэтому в кратныхединицах измерения количества информации используется
коэффициент 2n.
Так, кратныебайту единицы измерения количества информации вводятся следующим
образом:
1 Кбайт = 210байт = 1024 байт;
1 Мбайт = 210Кбайт = 1024 Кбайт;
1 Гбайт = 210Мбайт = 1024 Мбайт.
Количествовозможных событий и количество информации. Существует формула,
которая связываетмежду собой количество возможных событий N и количество
информации I:N=2I.
По этой формулеможно легко определить количество возможных событий, если
известноколичество информации. Например, если мы получили 4 бита информации, то
количествовозможных событий составляло: N = 24= 16.
Наоборот, дляопределения количества информации, если известно количество
событий,необходимо решить показательное уравнение относительно I. Например, в
игре«Крестики-нолики» на поле 8x8 перед первым ходом существует возможных
события (64различных варианта расположения «крестика»), тогда уравнение
принимает вид: 64= 2I.
Так как 64 = 26,то получим: 26 = 2I.
Таким образом, I= 6 битов, то есть количество информации, полученное вторым
игроком послепервого хода первого игрока, составляет 6 битов.
2. Алфавитныйподход к определению количества информации.
При определенииколичества информации на основе уменьшения неопределенности
наших знаний мырассматриваем информацию с точки зрения содержания, ее
понятности иновизны для человека. С этой точки зрения в опыте по бросанию
монеты одинаковоеколичество информации содержится и в зрительном образе упавшей
монеты, и вкоротком сообщении «Орел», и в длинной фразе «Монета упала на
поверхность землитой стороной вверх, на которой изображен орел».
Однако прихранении и передаче информации с помощью технических устройств
целесообразноотвлечься от содержания информации и рассматривать ее как
последовательностьзнаков (букв, цифр, кодов цветов точек изображения и так
далее).
Набор символовзнаковой системы (алфавит) можно рассматривать как различные
возможныесостояния (события). Тогда, если считать, что появление символов в
сообщенииравновероятно, по формуле можно рассчитать, какое количество
информации несеткаждый символ.
Так, в русскомалфавите, если не использовать букву ё, количество событий (букв)
будет равно 32.Тогда: 32 = 2I, откуда I = 5 битов.
Каждый символнесет 5 битов информации (его информационная емкость равна 5
битов).Количество информации в сообщении можно подсчитать, умножив количество
информации,которое несет один символ, на количество символов.
Количествоинформации, которое содержит сообщение, закодированное с помощью
знаковой системы,равно количеству информации, которое несет один знак,
умноженному наколичество знаков.

4. Обменинформацией производится по каналам передач информации. Каналы передачи
информации могутиспользовать различные физические принципы.
Компьютеры могутбыть соединены между собой кабелями, по которым информация
распространяетсяс помощь электрических импульсов.
Общая схемапередачи информации включает в себя отправителя информации (передает
информацию),канал передачи информации и получателя информации (принимает и
формацию). Еслипроизводится двусторонний обмен информацией, то отправитель и
получательинформации могут меняться ролями.
Основнойхарактеристикой каналов передачи инфopмации является их пропускная
способность(скорость переда информации). Пропускная способность канала равна
количествуинформации, которое может передаваться по нему в единицу времени.
Обычно пропускнаяспособность измеряется в битах в се­кунду (бит/с) и кратных
единицах Кбит/с иМбит/с. Одна­ко, иногда в качестве единицы используется и байт
в секун­ду(байт/с) и кратные ему единицы Кбайт/с и Мбайт/с.
Легко догадаться,что соотношения между единицами пропускной способности канала
передачиинформации та­кие же, как между единицами измерения количества
ин­формации.
1 байт/с = 23бит/с = 8 бит/с,
1 Кбит/с = 210бит/с = 1024 бит/с,
1 Мбит/с = 210Кбит/с   = 1024 Кбит/с,
1 Гбит/с = 210Мбит/с   = 1024 Мбит/с.

Билет 4
Понятиеалгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое
исполнениеалгоритма. Основные алгоритмические структуры.
Появлениеалгоритмов связывают с зарождением математики. Более 1000 лет назад (в
825 году) ученыйиз города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса
аль-Хорезмисоздал книгу по математике, в которой описал способы выполнения
арифметическихдействий над многозначными числами. Само слово алгоритм возникло
в Европе послеперевода на латынь книги этого математика.
Алгоритм –описание последовательности действий (план), строгое исполнение
которых приводитк решению поставленной задачи за конечное число шагов.
Вы постоянносталкиваетесь с этим понятием в различных сферах деятельности
человека(кулинарные книги, инструкции по использованию различных приборов,
правила решенияматематических задач...). Обычно мы выполняем привычные действия
не задумываясь,механически. Например, вы хорошо знаете, как открывать ключом
дверь. Однако,чтобы научить этому малыша, придется четко разъяснить и сами эти
действия ипорядок их выполнения:
1. Достать ключиз кармана.
2. Вставить ключв замочную скважину.
3. Повернуть ключдва раза против часовой стрелки.
4. Вынуть ключ.
Если вывнимательно оглянитесь вокруг, то обнаружите множество алгоритмов
которые мы с вамипостоянно выполняем. Мир алгоритмов очень разнообразен.
Несмотря на это,удается выделить общие свойства, которыми обладает любой
алгоритм.
Свойстваалгоритмов:
1. Дискретность(алгоритм должен состоять из конкретных действий, следующих в
определенномпорядке);
2. Понятность(любое действие должно быть строго и недвусмысленно определено в
каждом случае);
3. Определенность(каждое действие и алгоритм в целом должны иметь возможность
завершения);
4. Массовость(один и тот же алгоритм можно использовать с разными исходными
данными);
5.Результативность (отсутствие ошибок, алгоритм должен приводить к правильному
результату длявсех допустимых входных значениях).
Для болеенаглядного представления алгоритма широко используется графическая
форма — блок-схема, которая составляется из стандартных графических объектов.
Вид стандартногографического объектаНазначение
Начало алгоритма
Конец алгоритма
Выполняемоедействие записывается внутри прямоугольника
Условиевыполнения действий записывается внутри ромба
Счетчик, кол-воповторов
Последовательностьвыполнения действий.


Основныеалгоритмические структуры

Существует четыретипа основных (базовых) алгоритмических структур:
-  Линейный алгоритм;
-  Алгоритм ветвления (полное, неполное, выбор);
-  Циклический алгоритм (со счетчиком, спредусловием, с постусловием);
-  Вспомогательный алгоритм (подпрограмма)
Любой алгоритмможет быть реализован в виде комбинации базовых алгоритмических
конструкций.
Алгоритм линейнойструктуры — алгоритм, в котором все предписываемые действия
выполняютсяпоследовательно.




Алгоритмветвления — алгоритм, в кото­ром предусмотрено разветвление выполняемой
последователь­ностидействий в зависимости от результата проверки како­го-то
условия. Условие— это некоторое логическое выраже­ние. Если условие (логическое
выражение)принимает значение «истина», то выполняется «Серия 1», в противном
случае —выполняется «Серия 2». «Серия 1» и «Серия 2» могут представлять собой
как одиночныйоператор любого типа, так и группу операторов. В случае отсутствия
«Серии 2»получаем конструкцию с неполным ветвлением.


Полноеветвление                                         Неполное
ветвление
?
Серия 1
Серия 2
Да (+)
Нет (-)
?
Серия 1
Да (+)
Нет (-)









Алгоритмциклической структуры (цикл с повторением) — алгоритм, в котором
предусмотренонеоднократное выполне­ние одной и той же последовательности
действий. Этупосле­довательность действий называют телом цикла.
В зависимости отспособа проверки окончания цикла выделяют три вида:
1) Цикл «ДЛЯ»(цикл со счетчиком).