Виды алгоритмов в информатике: примеры. Информация и ее свойства
При изучении информатики немало внимания уделяется изучению алгоритмов и их видам. Не зная основных сведений о них, нельзя написать программу или проанализировать ее работу. Изучение алгоритмов начинается еще в школьном курсе информатики. Сегодня мы рассмотрим понятие алгоритма, свойства алгоритма, виды.
Понятие
Алгоритм - это определенная последовательность действий, которая приводит к достижению того или иного результата. Составляя алгоритм, детально прописывают каждое действие исполнителя, которое в дальнейшем приведет его к решению поставленной задачи.
Довольно часто алгоритмы используют в математике для решения тех или иных задач. Так, многим известен алгоритм решения квадратных уравнений с поиском дискриминанта.
Свойства
Прежде чем рассматривать в информатике, необходимо выяснить их основные свойства.
Среди основных свойств алгоритмов необходимо выделить следующие:
- Детерминированность, то есть определенность. Заключается в том, что любой алгоритм предполагает получение определенного результата при заданных исходных.
- Результативность. Означает, что при наличии ряда исходных данных после выполнения ряда шагов будет достигнут определенный, ожидаемый результат.
- Массовость. Написанный единожды алгоритм может использоваться для решения всех задач заданного типа.
- Дискретность. Она подразумевает, что любой алгоритм можно разбить на несколько этапов, каждый из которых имеет свое назначение.
Способы записи
Вне зависимости от того, какие виды алгоритмов в информатике вы рассматриваете, существует несколько способов их записи.
- Словестный.
- Формульно-словестный.
- Графический.
- Язык алгоритма.
Наиболее часто изображают алгоритм в виде блок-схемы, используя специальные обозначения, зафиксированные ГОСТами.
Основные виды
Выделяют три основных схемы:
- Линейный алгоритм.
- Ветвящийся алгоритм, или разветвленный.
- Циклический.
Линейный
Наиболее простым в информатике считается Он предполагает последовательность выполнения действий. Приведем наиболее простой пример алгоритма такого вида. Назовем его «Сбор в школу».
1. Встаем, когда звенит будильник.
2. Умываемся.
3. Чистим зубы.
4. Делаем зарядку.
5. Одеваемся.
6. Кушаем.
7. Обуваемся и идем в школу.
8. Конец алгоритма.
Разветвляющийся алгоритм
Рассматривая виды алгоритмов в информатике, нельзя не вспомнить о разветвляющейся структуре. Данный вид предполагает наличие условия, при котором в случае его выполнения действия выполняются в одном порядке, а в случае невыполнения - в другом.
Например, возьмем следующую ситуацию - переход дороги пешеходом.
1. Подходим к светофору.
2. Смотрим на сигнал светофора.
3. Он должен быть зеленым (это условие).
4. Если условие выполняется, мы переходим дорогу.
4.1 Если нет - ждем, пока загорится зеленый.
4.2 Переходим дорогу.
5. Конец алгоритма.
Циклический алгоритм
Изучая виды алгоритмов в информатике, детально следует остановиться на Данный алгоритм предполагает участок вычислений или действий, который выполняется до выполнения определенного условия.
Возьмем простой пример. Если ряд чисел от 1 до 100. Нам необходимо найти все то есть те, которые делятся на единицу и себя. Назовем алгоритм «Простые числа».
1. Берем число 1.
2. Проверяем, меньше ли оно 100.
3. Если да, проверяем простое ли это число.
4. Если условие выполняется, записываем его.
5. Берем число 2.
6. Проверяем, меньше ли оно 100.
7. Проверяем, простое ли оно.
…. Берем число 8.
Проверяем, меньше ли оно 100.
Проверяем, простое ли число.
Нет, пропускаем его.
Берем число 9.
Таким образом перебираем все числа, до 100.
Как видите, шаги 1 - 4 будут повторяться некоторое число раз.
Среди циклических выделяют алгоритмы с предусловием, когда условие проверяется в начале цикла, или с постусловием, когда проверка идет в конце цикла.
Другие варианты
Алгоритм может быть и смешанным. Так, он может быть циклическим и разветвленным одновременно. При этом используются разные условия на разных отрезках алгоритма. Такие сложные структуры приеняются при написании сложных программ и игр.
Обозначения в блок-схеме
Мы с вами рассмотрели, какие виды алгоритмов есть в информатике. Но мы не рассказали о том, какие обозначения используются при их графической записи.
- Начало и конец алгоритма записываются в овальной рамке.
- Каждая команда фиксируется в прямоугольнике.
- Условие прописывается в ромбе.
- Все части алгоритма соединяются при помощи стрелок.
Выводы
Мы с вами рассмотрели тему "Алгоритмы, виды, свойства". Информатика уделяет немало времени изучению алгоритмов. Их используют при написании различных программ как для решения математических задач, так и для создания игр и различного рода приложений.
Задание 1.
Алфавит племени содержит всего 8 букв. Какое количество информации несет одна буква этого алфавита?
Решение.
Известен информационный объем теста и информационный «вес» одного символа в нем. Найдем объем одной страницы: 40648 бит. 20 Кбайт = 201024 байт = 2010248 бит. Найдем количество страниц: 2010248/(40648) = 8 (стр.) (Ответ № 4)
Ответ : 4.
Задание 3.
В пяти килобайтах:
Решение.
32Гб = 25 Гб = 25210 Мб = 25210 210 Кб =25210 210210 байт = 235 байт, что соответствует ответу №1.
Ответ : 1.
Задание 5.
Считая, что один символ кодируется одним байтом, подсчитать в байтах количество информации, содержащееся в фразе: “Терпение и труд все перетрут.”
Решение.
В фразе 29 символов (включая точку и пробелы), 1 символ несет 1 байт информации, значит фраза содержит 29 байт.
Ответ : 29.
Задание 6. ( А4 демоверсии 2004 г.)
Получено сообщение, информационный объём которого равен 32 битам. Чему равен этот объём в байтах?
Решение.
Предложенная строка содержит ровно 108 символов, включая кавычки, пробелы и знаки препинания. При кодировании каждого символа одним байтом на символ будет приходиться по 8 бит, поэтому объём этого предложения составит 108 байт или 108х8=864 бит, что соответствует ответу №2.
Ответ : 2.
Задание 8. (Задание А3 демоверсии 2004 г.)
Шахматная доска состоит из 64 полей: 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?
Решение.
Для того, чтобы различить 64 клетки шахматного поля потребуются 64 значения двоичного кода. Поскольку 64=26, то в двоичном коде потребуется шесть разрядов. Верный ответ№3.
Ответ : 3.
Задание 9.
Каждое показание счётчика, фиксируемое в памяти компьютера, занимает 10 бит. Записано 100 показаний этого датчика. Каков информационный объём снятых значений в байтах?
Решение.
10 бит100= 1000 бит, 1 байт = 8 бит, следовательно: 1000/8=125 байт. Значит, верный ответ №3.
Ответ : 3.
Задание 10.
В коробке 32 карандаша, все карандаши разного цвета. Наугад вытащили красный. Какое количество информации при этом было получено?
Решение.
Так как вытаскивание карандаша любого цвета из имеющихся в коробке 32 карандашей является равновероятным, то число возможных событий
N = 2I, 32 = 25, I = 5 бит.
Свойства информации
Предметное содержание информации позволяет уяснить ее основные свойства:
Объективность информации - Информация – это отображение окружающего мира, а он существует независимо от нашего сознания, знаний и мыслей о нем.
ПРИМЕРЫ:
1) Фома неверующий
2) Игра «Глухой телефон»
Информация достоверна , если она отражает истинное положение дел. Недостоверная информация может привести к неправильному пониманию или принятию неправильных решений.
ПРИМЕРЫ:
1) Пропущено занятие, подруга говорит, что ничего не задано.
2) Скачали информацию в Интернете
Информация полна , если ее достаточно для понимания и принятия решений. Неполнота информации сдерживает принятие решений или может повлечь ошибки.
ПРИМЕРЫ:
1) Пропущено занятие, подруга говорит, что задан только параграф и забывает про задачи.
2) На улице 20 0 С (не понятно + или -)
Актуальность (своевременность) – важность, необходимость для данного времени. Актуальную информацию важно иметь при работе в изменившихся условиях.
ПРИМЕРЫ:
1) Предупреждение накануне о контрольной работе
2) Прогноз погоды на завтра актуальнее прогноза на вчера
Полезность (ценность) зависит от потребностей конкретных людей и от тех задач, которые можно решать с помощью полученной информации.
ПРИМЕРЫ:
1) В расписании уроков указаны занятия для всех классов, для вас ценна информация лишь о ваших уроках
2) Просмотрен документальный фильм про Петра 1. На уроке информатике он ценности не имеет, но на уроке истории - имеет.
Понятность . Если ценная и актуальная информация выражена непонятными словами, она может стать бесполезной. Информация становится понятной , если она выражена языком, на котором говорят те, кому предназначена эта информация.
ПРИМЕРЫ:
1) Дошкольник спрашивает у старшеклассника: "Как светит лампочка?". В ответ слышит: "Существует две теории света – волновая и корпускулярная. Согласно первой …".
2) Объяснять материал на китайском языке.
В следующих примерах определите свойства встречающейся информации:
q На следующий день учительница вывесила правильные решения всех задач…
q Идет контрольная работа по математике. Вы попросили у соседа решение задачи. Шпаргалка содержала полное и правильное решение, но... на японском языке.
q Один персидский царь, собираясь завоевать соседнее государство, обратился к оракулу с вопросом: “Что произойдет, если я со своим войском переправлюсь через пограничную реку?” Оракул ответил: “Государь, ты разрушишь великое царство”. Удовлетворившись таким предсказанием, завоеватель переправился со своим войском через реку и был разгромлен войском противной стороны. В гневе он обратился к оракулу, обвиняя того в обмане. На что оракул ответил: “Государь, а разве твое царство было не велико?”
Приведите примеры:
ь достоверной, но неактуальной информации;
ь актуальной, но недостоверной информации;
ь полной, достоверной, но бесполезной информации;
ь актуальной, но непонятной информации.
РЕШЕНИЕ ЗАДАЧ
При хранении и передаче информации с помощью технических устройств информацию следует рассматривать как последовательность символов - знаков (букв, цифр, кодов цветов точек изображения и т.д.).
Набор символов знаковой системы (алфавит) можно рассматривать как различные возможные состояния (события).
Тогда, если считать, что появление символов в сообщении равновероятно, количество возможных событийN
можно вычислить как N=2 i
Количество информации в сообщении I
можно подсчитать умножив количество символов K
на информационный вес одного символа i
Итак, мы имеем формулы, необходимые для определения количества информации в алфавитном подходе:
Возможны следующие сочетания известных (Дано) и искомых (Найти) величин:
| Тип | Дано | Найти | Формула |
|---|---|---|---|
| 1 | i | N | N=2 i |
| 2 | N | i | |
| 3 | i,K | I | I=K*i |
| 4 | i,I | K | |
| 5 | I, K | i | |
| 6 | N, K | I | Обе формулы |
| 7 | N, I | K | |
| 8 | I, K | N |
Если к этим задачам добавить задачи на соотношение величин, записанных в разных единицах измерения, с использованием представления величин в виде степеней двойки мы получим 9 типов задач.
Рассмотрим задачи на все типы. Договоримся, что при переходе от одних единиц измерения информации к другим будем строить цепочку значений. Тогда уменьшается вероятность вычислительной ошибки.
Задача 1 . Получено сообщение, информационный объем которого равен 32 битам. чему равен этот объем в байтах?
Решение: В одном байте 8 бит. 32:8=4
Ответ: 4 байта.
Задача 2 . Объем информацинного сообщения 12582912 битов выразить в килобайтах и мегабайтах.
Решение: Поскольку 1Кбайт=1024 байт=1024*8 бит, то 12582912:(1024*8)=1536 Кбайт и
поскольку 1Мбайт=1024 Кбайт, то 1536:1024=1,5 Мбайт
Ответ:1536Кбайт и 1,5Мбайт.
Задача 3. Компьютер имеет оперативную память 512 Мб. Количество соответствующих этой величине бит больше:
1) 10 000 000 000бит 2) 8 000 000 000бит 3) 6 000 000 000бит 4) 4 000 000 000бит Решение: 512*1024*1024*8 бит=4294967296 бит.Ответ: 4.
Задача 4.
Определить количество битов в двух мегабайтах, используя для чисел только степени 2.
Решение: Поскольку 1байт=8битам=2 3 битам, а 1Мбайт=2 10 Кбайт=2 20 байт=2 23 бит. Отсюда, 2Мбайт=2 24 бит.
Ответ: 2 24 бит.
Задача 5.
Сколько мегабайт информации содержит сообщение объемом 2 23 бит?
Решение: Поскольку 1байт=8битам=2 3 битам, то
2 23 бит=2 23 *2 23 *2 3 бит=2 10 2 10 байт=2 10 Кбайт=1Мбайт.
Ответ: 1Мбайт
Задача 6.
Один символ алфавита "весит" 4 бита. Сколько символов в этом алфавите?
Решение:
Дано:
Ответ: 16
Задача 7.
Каждый символ алфавита записан с помощью 8 цифр двоичного кода. Сколько символов в этом алфавите?
Решение:
Дано:
Ответ: 256
Задача 8.
Алфавит русского языка иногда оценивают в 32 буквы. Каков информационный вес одной буквы такого сокращенного русского алфавита?
Решение:
Дано:
Ответ: 5
Задача 9.
Алфавит состоит из 100 символов. Какое количество информации несет один символ этого алфавита?
Решение:
Дано:
Ответ: 5
Задача 10.
У племени "чичевоков" в алфавите 24 буквы и 8 цифр. Знаков препинания и арифметических знаков нет. Какое минимальное количество двоичных разрядов им необходимо для кодирования всех символов? Учтите, что слова надо отделять друг от друга!
Решение:
Дано:
Ответ: 5
Задача 11.
Книга, набранная с помощью компьютера, содержит 150 страниц. На каждой странице — 40 строк, в каждой строке — 60 символов. Каков объем информации в книге? Ответ дайте в килобайтах и мегабайтах
Решение:
Дано:
Ответ: 351Кбайт или 0,4Мбайт
Задача 12.
Информационный объем текста книги, набранной на компьютере с использованием кодировки Unicode, — 128 килобайт. Определить количество символов в тексте книги.
Решение:
Дано:
Ответ: 65536
Задача 13.
Информационное сообщение объемом 1,5 Кб содержит 3072 символа. Определить информационный вес одного символа использованного алфавита
Решение:
Дано:
Ответ: 4
Задача 14.
Сообщение, записанное буквами из 64-символьного алфавита, содержит 20 символов. Какой объем информации оно несет?
Решение:
Дано:
Ответ: 120бит
Задача 15.
Сколько символов содержит сообщение, записанное с помощью 16-символьного алфавита, если его объем составил 1/16 часть мегабайта?
Решение:
Дано:
Ответ: 131072
Задача 16.
Объем сообщения, содержащего 2048 символов,составил 1/512 часть мегабайта. Каков размер алфавита, с помощью которого записано сообщение?
Решение:
Дано:
Ответ: 256
Задачи для самостоятельного решения:
- Каждый символ алфавита записывается с помощью 4 цифр двоичного кода. Сколько символов в этом алфавите?
- Алфавит для записи сообщений состоит из 32 символов, каков информационный вес одного символа? Не забудьте указать единицу измерения.
- Информационный объем текста, набранного на компьюте¬ре с использованием кодировки Unicode (каждый символ кодируется 16 битами), — 4 Кб. Определить количество символов в тексте.
- Объем информационного сообщения составляет 8192 бита. Выразить его в килобайтах.
- Сколько бит информации содержит сообщение объемом 4 Мб? Ответ дать в степенях 2.
- Сообщение, записанное буквами из 256-символьного ал¬фавита, содержит 256 символов. Какой объем информации оно несет в килобайтах?
- Сколько существует различных звуковых сигналов, состоящих из последовательностей коротких и длинных звонков. Длина каждого сигнала — 6 звонков.
- Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 20 до 100%, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатом наблюдений.
- Скорость передачи данных через ADSL-соединение равна 512000 бит/с. Через данное соединение передают файл размером 1500 Кб. Определите время передачи файла в секундах.
- Определите скорость работы модема, если за 256 с он может передать растровое изображение размером 640х480 пикселей. На каждый пиксель приходится 3 байта. А если в палитре 16 миллионов цветов?