Шпаргалка по "Информатике"

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

 

 

Билет 8

В ЭВМ  применяется двоичная система счисления, т.е. все числа в компьютере представляются с помощью нулей и единиц, поэтому  компьютер может обрабатывать только информацию, представленную в цифровой форме.

Для преобразования числовой, текстовой, графической, звуковой информации в цифровую необходимо применить кодирование. Кодирование – это преобразование данных одного типа через данные другого типа. В ЭВМ применяется система двоичного кодирования, основанная на представлении данных последовательностью двух знаков: 1 и 0, которые называются двоичными цифрами (binary digit – сокращенно bit).

Целые числа кодируются двоичным кодом  довольно просто (путем деления числа  на два). Для кодирования нечисловой информации используется следующий  алгоритм: все возможные значения кодируемой информации нумеруются и  эти номера кодируются с помощью  двоичного кода.

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

Растровые изображения кодируются таким образом: картинка разбивается на точки(пиксели) и каждый цвет пикселя кодируется трехбайтовым кодом(для цветовой схемы RGB) или же трехбайтовым(CMYK) и т.д.

Векторные изображения кодируются координатами линии.

Звук  оцифровывается через микрофон и  становится цифровой(дискретной информацией).

Естественные и формальные языки:

Естественными называются “обычные”, “разговорные”  языки, которые складываются стихийно и в течение долгого времени. История каждого такого языка  неотделима от истории народа, владеющего им. Естественный язык, предназначенный, прежде всего, для повседневного  общения, имеет целый ряд своеобразных черт: 

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

Формализованный (формальный) язык –– язык, характеризующийся точными правилами построения выражений и их понимания. Он строится в соответствии с четкими правилами, обеспечивая непротиворечивое, точное и компактное отображение свойств и отношений изучаемой предметной области (моделируемых объектов).

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

Большинство формальных языков (созданных конструкций) строится по следующей схеме. сначала выбирается алфавит, или совокупность исходных символов, из которых будут строиться все выражения языка; затем описывается синтаксис языка, то есть правила построения осмысленных выражений. Буквами в алфавите формального языка могут быть и буквы алфавитов естественных языков, и скобки, и специальные знаки и т.п. Из букв, по определенным правилам можно составлять слова и выражения. Осмысленные выражения получаются в формальном языке, только если соблюдены определенные в языке правила образования. Для каждого формального языка совокупность этих правил должна быть строго определена и модификация любого из них приводит чаще всего к появлению новой разновидности (диалекта) этого языка.

Общее число наиболее употребимых символов N =148. Можно оценить длину кодовой цепочки: K= log₂148 =7,21. Поскольку K должно быть целым, очевидно, K= 8. Именно такой способ кодирования принят в компьютерных системах: любому символу ставится в соответствие цепочка из 8 двоичных разрядов (8 бит). Такая цепочка получила название байт, а представление таким образом символов – байтовым кодированием.  2⁸=256, следовательно можно закодировать еще 256-148=108 символов. Это дает возможность употребить оставшуюся часть кодовой таблицы для представления дополнительных символов.

 

 

Билет 9

Эффективное кодирование – кодирование для  уменьшения передаваемой информации в  сигнале. Для кодирования используются двоичные коды переменной длины. Чем выше частота появления символа, тем короче код. Эффективность кода определяется средним числом двоичных разрядов.

2 классических  метод кодирования: метод Шеннона-Фано  и Хаффмана.

Метод Шеннона-Фано :

1) Символы первичного алфавита m₁ выписывают в порядке убывания вероятностей.

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

3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».
4. Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

Метод Хаффмана:

1) Выписываем в ряд все символы  алфавита в порядке убывания  вероятности их появления в  тексте;

2) Последовательно объединяем два  символа с наименьшими вероятностями  появления в новый составной  символ, вероятность появления которого  полагается равной сумме вероятностей  составляющих его символов; в  конце концов мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;

3) Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 1, налево - 0).

 

 

Билет 10

Алгоритм  – последовательность команд исполнителю, приводящая к решению задачи.

Алгоритмы бывают линейными, разветвленными и  циклическими.

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

- вербальный, когда алгоритм описывается на человеческом языке;

- символьный, когда алгоритм описывается с помощью набора символов;

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

Общепринятыми способами записи являются графическая  запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.

Описание  алгоритма с помощью блок схем осуществляется рисованием последовательности геометрических фигур, каждая из которых  подразумевает выполнение определенного  действия алгоритма. Порядок выполнения действий указывается стрелками. Написание  алгоритмов с помощью блок-схем регламентируется ГОСТом. Внешний вид основных блоков, применяемых при написании блок схем, приведен на рисунке:

Алгоритмический язык (как и любой  другой язык) образуют три его составляющие: алфавит,   синтаксис   и   семантика.

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

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

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

 

 

 

 

 

Билет 11

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

Именно  программа, созданная человеком, повышает “интеллектуальный” уровень машины. А каков же начальный “уровень знаний” компьютера? Этот уровень  определяется набором команд (инструкций), которые способен выполнить процессор. Это команды типа:

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

На  заре развития вычислительной техники  программы создавались непосредственно  в виде последовательности команд процессора, т.е. на машинном языке. Это была очень  трудоемкая работа, требующая, к тому же, от программиста хороших знаний архитектуры компьютера. Вскоре, возникла идея создать систему условных обозначений  для записи алгоритмов в форме, понятной для человека (т.е. алгоритмический  язык программирования) и программу-транслятор, переводящую этот алгоритм на машинный язык. Использование алгоритмических  языков существенно повышает “начальный уровень знаний” компьютера. Теперь доступны такие операции как:

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

Главным элементом кода машинной команды  является код операции (КОП), что определяет, какие действия будут выполнены по данной команде. Под него выделяется N старших разрядов формата. В остальных разрядах размещаются А₁ и А₂ - адреса операндов. А₃ - адрес результата.

Распределение полей в формате команды может  изменяться при смене способа  адресации. Длина команды зависит  от числа адресных полей. По числу  адресов команды делятся на:

	безадресные
	одно-, двух-, трехадресные

о функциональному назначению в системе команд ЭВМ различают следующие группы:

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

 

 

Билет 12

В 1948 году Джон Фон Нейман предложил архитектуру  ЭВМ, которая используется и по сей день с небольшими изменениями.

Таким образом, ЭВМ содержат следующие основные функциональные блоки (рис. 1)

1. запоминающее устройство (память);
2. арифметико-логическое устройство (АЛУ); процессор
3. управляющее устройство (УУ);
4. устройстваввода и вывода информации

Путь информации в машине начинается с устройства ввода. ЭВМ может воспринять информацию, считывая ее с карт, с перфоленты, с магнитной ленты, магнитного или лазерного диска, с телетайпа или же получая ее от оператора ЭВМ, сидящего за пультом дисплея. Введенная в ЭВМ информация поступает в оперативный накопитель. Некоторая часть ее остается здесь до поры до времени, не вступая в действие. Другая часть информации попадает в запоминающее устройство. Часть информации, которая нужна для немедленной переработки, тотчас же поступает в АЛУ, состоящее из сумматоров. Они-то и выполняют все арифметические и логические действия. Очень часто АЛУ и устройство управления объединяют в процессор. Процессор - это микросхема, которая производит все операции компьютера, осуществляет управление всеми системами и элементами компьютера.

Производительность ЭВМ зависит от:

1. Быстродействия процессора
2. Класса решаемых задач
3. Порядка прохождения задачи через ЭВМ