скачать книгу бесплатно
o а) Каскадная модель
o б) Итерационная модель
o в) Спиральная модель
o г) Модель «под себя»
4. Какие процедуры включают этапы работы с экономической информацией?
o а) Только сбор и регистрация информации
o б) Только анализ и передача информации
o в) Сбор, регистрация, кодирование, обработка, хранение и анализ информации
o г) Только накопление и хранение данных
5. Что относится к синтаксису в семиотике?
o а) Значение информации
o б) Способ записи и сочетания знаков
o в) Практическое использование информации
o г) Оценка полезности информации
Правильные ответы:
1. Правильный ответ: в)
2. Правильный ответ: в)
3. Правильный ответ: в)
4. Правильный ответ: в)
5. Правильный ответ: б)
1.6. Структура данных и преобразование информации
Изучение информатики не только даёт возможность использовать информационно-коммуникационные технологии в практической деятельности, но и развивает логическое мышление, аналитические способности, креативность и воображение. Это также помогает формировать информационную культуру и критическое отношение к источникам информации.
Количество информации при передаче из одной системы в другую определяется не только с помощью сигналов и импульсов, но и с помощью единицы измерения информации. Существует несколько таких единиц, например, бит, байт, нат, хартли и др. Они позволяют количественно оценивать объем и поток информации, а также ее степень сжатия, избыточность и неопределенность.
Существует множество типов носителей данных, например, бумага, магнитная лента, оптический диск, флеш-память и др.
Классификация структуры данных по типам не ограничивается линейной, иерархической и табличной. Существуют и другие типы структур данных, например, сетевая, древовидная, графовая, хеш-таблица, стек, очередь, список и др. Каждый тип структуры данных имеет свои преимущества и недостатки, а также свои области применения. Выбор подходящей структуры данных зависит от задачи, которую нужно решить, и от свойств исходных данных.
Когда мы разбиваем книгу на отдельные листы и перемешиваем их, книга теряет свою целостность и становится бесполезной для чтения. В этом случае мы все еще имеем набор данных, но нет ясного способа получить из них информацию. Если же мы вырежем каждую букву из книги, то текст станет непонятным и нечитаемым. Даже если мы сможем расположить буквы в правильном порядке, понять смысл текста будет трудно.
Однако, если мы соберем все листы книги в правильной последовательности, мы получим линейную структуру данных. Такую книгу можно читать, но для поиска нужной информации придется прочитать все страницы по порядку, что не всегда удобно. Для быстрого поиска данных используется иерархическая структура. Книги, например, разбиваются на части, разделы, главы и параграфы. Элементы структуры более низкого уровня входят в элементы структуры более высокого уровня: разделы состоят из глав, главы и параграфы. Рассмотрим, какие виды структур управления существуют.
Линейные структуры, такие как списки данных или векторы данных, представляют собой простые списки, где каждый элемент однозначно определяется своим номером в массиве. Например, обычный журнал посещаемости занятий имеет структуру списка, где студенты зарегистрированы под уникальными номерами.
При создании любой структуры данных важно решить два основных вопроса: каким образом разделить элементы данных и как эффективно их найти. В журнале посещаемости, например, это решается следующим образом: каждый новый элемент списка заносится с новой строки, то есть разделителем является конец строки. Таким образом, если нам нужно найти определенный элемент, мы можем обратиться к его номеру строки.
Номер строки – это простой и эффективный способ организации данных в списке. Однако, разделителем может быть и специальный символ, который не встречается в самих данных. В рассмотренном нами классном журнале мы можем использовать символ «*» в качестве разделителя:
1. Аистов Александр Алексеевич *
2. Бобров Борис Борисович *
3. Воробьева Валентина Владиславовна *
…
27. Сорокин Сергей Семенович
В этом случае, для поиска элемента с номером «n», мы начинаем просмотр списка с начала и считаем количество встреченных разделителей. Когда мы отсчитываем «n-1» разделителей, мы находим нужный элемент.
Табличные структуры данных, такие как таблицы и матрицы, представляют собой способ организации информации, где каждый элемент данных имеет свой адрес в виде координат ячейки. Важно различать их от списочных структур, где каждый элемент определяется своим порядковым номером.
Рассмотрим пример таблицы умножения. В этой таблице, адрес каждой ячейки определяется номером строки и номером столбца. Например, для умножения числа из 3-й строки на число из 4-го столбца, мы найдем ячейку, расположенную на пересечении этих строк и столбцов.
При хранении таких данных, важно использовать разделители, которые отделяют строки и столбцы друг от друга. Это облегчает поиск элементов по их адресам. Например, при использовании символьной строки для представления таблицы, мы можем разделить элементы одной строки одним символом-разделителем, а строки друг от друга – другим символом.
Для поиска элемента в таблице с адресом (m, n), мы начинаем просмотр таблицы с самого начала и считаем внешние разделители. Когда мы отсчитываем «m-1» разделитель, мы переходим к соответствующей строке. Затем мы считаем внутренние разделители, чтобы найти нужный столбец. Если все элементы таблицы имеют одинаковую длину, мы можем рассматривать ее как матрицу. В этом случае нам не нужны разделители, так как длина каждого элемента известна. Для поиска элемента с адресом (t, p) в матрице, мы используем формулу a [N (m -1) + (n -1)], где «а» – длина элемента, «N» – количество столбцов, а «m» и «n» – номер строки и столбца соответственно. Таким образом, табличные структуры данных (матрицы) позволяют упорядочить информацию, где каждый элемент имеет свой уникальный адрес. Многомерные таблицы представляют собой таблицы с более чем двумя измерениями. Рассмотрим пример таблицы, используемой для учета учащихся. В такой таблице каждый учащийся идентифицируется пятью параметрами: номер факультета, номер курса на факультете, номер специальности на курсе, номер группы в потоке одной специальности и номер учащегося в группе. Размерность такой таблицы равна пяти, и для доступа к информации об учащемся необходимо знать все пять параметров, то есть их координаты в таблице.
Иерархические структуры данных представляют собой способ организации данных, где каждый элемент имеет свой адрес в виде пути, ведущего от вершины структуры к данному элементу. Примером иерархической структуры данных является система почтовых адресов или систематизации информации в классификациях. Например, для доступа к программе «Калькулятор» в операционной системе Windows 98 необходимо пройти следующий путь: Пуск> Программы> Стандартные> Калькулятор.
Дихотомия данных является методом регуляризации иерархических структур данных в информационных технологиях. Основным недостатком иерархических структур данных является увеличенный размер пути доступа, который может оказаться длиннее, чем сами данные, к которым он ведет.
Метод дихотомии позволяет сделать путь доступа к данным более компактным. В иерархической структуре, построенной с использованием метода дихотомии, доступ к каждому элементу представляется как путь через лабиринт с поворотами налево (0) или направо (1). Таким образом, путь доступа представляется в виде компактной двоичной записи. Например, для пути доступа к текстовому процессору Word 2000 с использованием метода дихотомии выражается следующим двоичным числом: 1010. Упорядочение структур данных играет важную роль в обеспечении эффективного доступа к информации и обновлении данных. Простые структуры данных, такие как списки и таблицы, легко упорядочиваются, основным методом часто является сортировка. Списочные и табличные структуры данных хоть и просты в использовании, но их обновление может быть сложным. Например, при переводе студента из одной группы в другую, изменения должны быть внесены в несколько мест одновременно, что может привести к нарушению структуры данных.
Добавление нового элемента в упорядоченную структуру списка может также привести к изменению адресных данных других элементов. В отличие от простых структур, иерархические структуры данных более сложны по форме, но их обновление проще. Их легко развивать путем создания новых уровней, и изменения в одной части структуры обычно не затрагивают другие. Однако упорядочение иерархических структур может быть сложным из-за относительной трудоемкости записи адреса элемента данных и необходимости использования методов индексации для обеспечения быстрого доступа и сортировки. Методы индексации, такие как дихотомия, позволяют значительно упростить поиск и сортировку данных в иерархических структурах, делая их более эффективными для использования в информационных системах. Выбор подходящей структуры данных зависит от различных факторов, таких как:
Объём данных: Если имеется большой объём данных, необходимо выбирать структуру данных, которая обеспечивает эффективный доступ и хранение. Например, для хранения большого количества данных с быстрым доступом к ним можно использовать хеш-таблицы или деревья.
Частота операций: Если операции добавления, удаления и поиска выполняются часто, нужно выбирать структуру данных, оптимизированную под эти операции. Например, для быстрого поиска элементов при частом изменении данных можно использовать хеш-таблицы или сбалансированные деревья.
Сложность алгоритмов: Некоторые структуры данных подходят для определённых типов алгоритмов. Например, для эффективной реализации алгоритмов поиска кратчайшего пути в графе следует использовать графовые структуры данных.
Ограничения памяти: В случае ограниченных ресурсов памяти важно выбирать структуры данных, которые эффективно используют доступную память. Например, для эффективного использования памяти при хранении большого объёма данных можно применять компактные структуры, такие как битовые массивы или сжатые структуры данных. Некоторые ресурсы, которые помогут в изучении структур данных и алгоритмов:
? «Структуры данных и алгоритмы на Python» (Data Structures and Algorithms in Python) от Michael T. Goodrich, Roberto Tamassia и Michael H. Goldwasser. Этот учебник предлагает подробное объяснение основных концепций и принципов структур данных и алгоритмов, используя язык программирования Python. Он включает множество примеров, упражнений и проектов для закрепления материала.
? «Введение в алгоритмы» (Introduction to Algorithms) от Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest и Clifford Stein. Это классическое учебное пособие, охватывающее широкий спектр тем по структурам данных и алгоритмам. Оно подходит для продвинутого уровня и требует хорошего знания математики и анализа алгоритмов.
? «Структуры данных и алгоритмы» (Data Structures and Algorithms) на платформе Coursera. Это серия онлайн-курсов, предлагающих интерактивное обучение по различным аспектам структур данных и алгоритмов. Курсы включают видеолекции, тесты, задачи и проекты, и доступны на разных языках, включая английский и русский.
Тестовые вопросы с вариантами ответов
1. Кто является основателем семантического подхода и отцом кибернетики?
o а) А. Харкевич
o б) Н. Винер
o в) Майкл Т. Гудрич
o г) Томас Х. Кормен
2. Какие единицы измерения информации используются для количественной оценки объёма и потока информации?
o а) Байт, нат, хартли
o б) Метр, килограмм, секунда
o в) Грамм, литр, метр
o г) Секунда, минута, час
3. Какая структура данных лучше всего подходит для двумерных данных?
o а) Линейная структура
o б) Табличная структура
o в) Иерархическая структура
o г) Сетевая структура
4. Какой метод позволяет сделать путь доступа к данным в иерархических структурах более компактным?
o а) Сортировка
o б) Дихотомия
o в) Хеширование
o г) Балансировка
5. Какое преимущество имеют иерархические структуры данных?
o а) Простота обновления данных
o б) Эффективное использование памяти
o в) Легкость упорядочения данных
o г) Простота реализации
Правильные ответы:
1. Правильный ответ: б)
2. Правильный ответ: а)
3. Правильный ответ: б)
4. Правильный ответ: б)
5. Правильный ответ: а)
1.7. Кодирование информации
Кодирование информации — это процесс представления информации в различных формах. Это может включать преобразование информации из одной формы в другую для улучшения её обработки, передачи, хранения и восприятия.
Часто кодирование применяется для перехода от исходного представления к представлению удобному для хранения, передачи и обработки. Обратный переход называется декодированием.
При кодировании могут достигаться различные цели и соответственно применяться различные методы.
Цели кодирования:
? экономность, т.е. уменьшение избыточности сообщения;
? повышение скорости передачи или обработки;
? надёжность, т.е. защита от случайных искажений;
? секретность, т.е. защита от нежелательного доступа к информации;
? удобство физической реализации;
? удобство восприятия.
Эти цели часто противоречат друг другу.
Экономные сообщения могут оказаться ненадёжными, т.к. они не содержат лишних символов, и искажение любого символа может изменить смысл сообщения.
Например, обычная запись числа цифрами гораздо экономичнее и удобнее для вычислений, чем запись символами. Однако искажение или удаление любой цифры изменит величину числа.
Поэтому в финансовых документах, где надёжность должна быть велика, цифровые сообщения в некоторых местах заменяются или дублируются словесными сообщениями. Дублирование повышает избыточность.
Теория кодирования подробно исследует проблемы разумного сочетания экономности и надёжности при передаче сообщения.
Экономное сообщение может существенно уменьшить объём передаваемой информации, уменьшить требования к пропускной способности канала связи, повысить оперативность передачи сообщения.
