Кодирование информации

На самом деле задача понята только тогда, когда найдено такое представление, в котором все элементы задачи представлены без избыточности и многозначности. Условие задачи при этом записываются в формализованном виде. Задача становится одновременно и более абстрактной и более строгой. В этом случае говорят о задаче в замкнутой форме или о замкнутой формулировке задачи.

С математической точки зрения можно предложить такой общий шаблон для задачи в замкнутой форме: Найти в заданном множестве X элементы x, удовлетворяющие заданным ограничениям K (x). Примером такой задачи может служить задача решения уравнения: «из множества натуральных чисел x выбрать такие числа, которые удовлетворяют уравнению x3+84=37x».

Для одной и той же задачи всегда можно привести несколько разных замкнутых формулировок. Не всегда при этом есть одна наиболее «естественная» формулировка. (Слово «естественная» в данном случае надо понимать не как «напрашивающаяся», а скорее как «наиболее простая».) Если даже такая формулировка одна, не всегда просто её найти. Иногда нахождение такой формулировки — основное в решении задачи.

Подход человека к решению задачи включает следующие основные этапы:

1. Выяснение смысла условий задачи.

2. Первые выводы из условий задачи.

3. Проигрывание ситуации, обдумывание.

4. Выбор наилучшего представления — поиск замкнутой формулировки задачи.

5. Частичное (возврат к пункту 2) или общее решение.

6. Проверка и обобщение решения.

2.

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

Задачу имеет смысл называть комбинаторной, если ее решение состоит в переборе элементов x множества X. (При этом наравне с термином «комбинаторная» вполне подходит термин «переборная».) Такое определение описывает не саму задачу, а скорее её решение. Ведь, подходя формально, любую задачу можно пытаться решать таким методом. Надо заметить, что никакого парадокса здесь нет. Действительно, очень большое количество реальных задач — задачи переборные и только для некоторых найдены способы избегать перебора, например, вычисление числа сочетаний, размещений.

2.3 Пространство перебора Итак, предположим, мы решаем задачу с помощью перебора. При этом решение будет состоять в переборе элементов множества X и проверке условий K (x) для каждого такого элемента. Множество X в данном случае называется пространством перебора. Для полного решения задачи необходимо выполнить, по крайней мере, -X-· -Kшагов (не считая шагов, необходимых для порождения элементов множества X), гдеX- - количество элементов множества X, аK- - количество шагов, необходимых для проверки одного элемента. Понятно, что размер множества X очень важен для эффективного решения задачи. Часто множество X является декартовым произведением множеств X1,…, Xn (т.е. состоит из наборов элементов (x1,…, xn), где xi Xi). При этом, сократив множество перебора для каждого Xi в два раза, мы сократим общий объём перебора в 2n раз.

Таким образом, очень важно получить замкнутую формулировку с небольшим пространством перебора. Иногда, переходя от формулировки к формулировке и сокращая перебор, удаётся полностью его избежать и решить задачу «прямым» методом.

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

Например, в соревновании пяти спортсменов призовые места (первые три) могут распределиться 60 способами, поскольку

2.

4. Система Turbo Pascal и вычислительные задачи Реализация любой задачи с использованием компьютера делится на следующие этапы

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

2. Разработка или выбор алгоритма. Здесь необходимо определить последовательность действий, которые необходимо выполнить для получение результата. Этот этап является наиболее сложным в разработке программы.

3. Программирование, т. е. запись разработанного алгоритма на конкретном языке программирования

4. Ввод программы и исходных данных в компьютер

5. Тестирование и отладка программы. На этом этапе программа прогоняется на компьютере, устраняются ошибки. Отладка заключается в тестировании программы на контрольных примерах

6. Выполнение отлаженной программы и анализ исходных результатов.

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

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

Для реализации поставленной задачи — вычисления числа выбора m элементов из n, следует использовать классический алгоритм вычисления конечного произведения (см. рис. 2.1), который реализуется с использованием оператора арифметического цикла.

При организации циклов необходимо:

— определить параметр цикла и его начальное значение;

— изменять значение параметра цикла на каждом шаге итерации;

— проверка на выход из цикла.

FOR i: = N TO K DO Q

(для) (до) (выполнять) где i — параметр цикла;

N, K — его начальное и конечное значение;

Qпростой или составной оператор;

i, N, K — переменные или константы целого типа.

Шаг изменения i — равен 1.

Рис. 2.

1. Блок-схема вычисления конечного произведения Если K

FOR i: =N DOWNTO K DO P

Оператор for применяют в тех случаях, когда значения параметра цикла целые и меняются с шагом +1, -1.

Кроме оператора цикла FOR в Паскале используются операторы цикла с предусловием и с постусловием. Для организации цикла необходимо:

1. Задавать перед циклом начальное значение переменной, изменяющейся в цикле.

2. Изменять значение переменной перед каждым новым повторением цикла.

3. Проверять условие окончания цикла.

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

3. Алгоритм и программа решения задачи

1. Постановка задачи и математическая модель.

Вычислить и вывести на экран число размещений из n по m по формуле:

где целые числа n и m ввести с клавиатуры (n>=m>0).

2. Исходные данные задачи, промежуточные величины и результаты представлены в таблице 3.

1.

Таблица 3.

1. Таблица переменных, используемых в программе Имя переменной Тип Назначение N, m integer Исходные данные i integer Переменная цикла A longint Результат (число размещений)

2. Блок схема решения задачи представлена на рисунке 3.

1.

Рис. 3.

1. Блок-схема алгоритма реализации задачи Листинг программы

program Komb;

uses crt;

var

m, n, i: integer;

A: longint;

Begin

{очистка экрана }

clrscr;

{проверка ввода исходных данных n>=m>0 }

repeat

write ('n='); readln (n);

write ('m='); readln (m);

until (n>=m) and (m> 0);

{задаем начальное значение произведения }

A:=1;

{организуем арифметический цикл с шагом +1 }

for i:=n-m+1 to n do

A:=A*i;

{вывод результата вычисления числа размещений }

writeln ('A=', A);

{ожидание нажатия клавиши, что-то типа задержки экрана }

readkey;

end.

Протокол работы программы (скриншот)

Заключение

В результате выполнения курсовой работы были решены следующие задачи:

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

В большинстве современных ЭВМ при кодировании каждому символу соответствует своя последовательность из восьми нулей и единиц, т. е. байт.

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

Строки символов хранятся в памяти ЭВМ в виде числа, обозначающее длину текста, затем текст, либо в виде текста, затем указывается разделитель строк.

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

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

2. Решение ряда комбинаторных задач сводится к организации вычисления конечного произведения. Реализация таких задач возможна с использованием системы программирования Turbo Pascal. В этом случае для достижения результата остаточно организовать арифметический цикл.

В программе предусмотрены необходимые типы переменных, так, например, результат вычисления числа размещений определяется как longint ввиду того, что результат выходит за пределы интервала 0. 32 767 множества чисел типа integer.

Список использованных источников

Есаян А.Р., Ефимов В. И., Лапицкая Л. П., Пащенко Э. А., Добровольский Н. М. Информатика. -М.: Изд-во Просвещение, 1991. 288 с.

Информатика: Базовый курс / С. В. Симонович и др. — СПб.: Питер, 2003. — 640 с.: ил.

Информатика: Учебник / Под общ. ред. А. В. Данчула.

М.: Изд-во РАГС, 2004. 528 с.

Информатика: Учебник / В. А. Каймин. — М.: Инфра-М, 2001. 286 с. — ISBN: 5−16−1 928;6

Информатика: Учебник / Б. В. Соболь [и др.]. — Изд. 3-е дополн. и перераб.

Ростов н/Д: Феникс, 2007; 446 с. (Высшее образование) Меняев М. Ф. Информатика и основы программирования.

М.: Омега-Л, 2007. 464 с.

Могилев, Пак, Хеннер. Информатика.

М.: Academia, 2004 -848 с.

Морозевич А.Н., Зеневич А. М. Информатика.

Минск: Высшая школа, 2006; 285 с.- ISBN: 985−06−1104−9

Степанов А. Н. Информатика. Спб.: Питер, 2006 .- 684 с.

Терехов, А. В. Информатика: учеб. пособие / А. В. Терехов, А. В. Чернышов, В. Н. Чернышов. — Тамбов: Изд-во Тамб.

гос. техн. ун-та, 2007. — 128 с. -ISBN 978−5-8265−0677−6.

Фридланд А. Я. Информатика и компьютерные технологии. — М.: Астрель, 2002. — 279 с.

Информатика: Учебник / Б. В. Соболь С. 45

Информатика: Учебник / Б. В. Соболь, С.40

Информатика: Учебник / Б. В. Соболь. С. 41

Источ-ник

Кодиров;

щик

Декодиров-щик

Прием-ник

сообщение

помехи

Р:=1

i:=N

P:=P* множитель

i:=i+1

A:=1

N, Kn

i<=K

I:=n-m+1,n

n, m

начало

A:=A*i

A

Конец

Да

Нет

Нет

Да