Табличные и иерархические структуры данных. Дихотомия данных.

Основные понятия и определения информатики. Схема передачи данных

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

Информация – сведения о лицах, предметах, фактах, событиях, явлениях и процессах независимо от формы их представления.

Схема передачи информации (может быть разной).

Источник информации → Кодер информации → Канал связи →

Декодер информации → Приёмник информации.

(физическая среда) >> (среда передачи)

Информация бывает: аналоговая (непрерывная), дискретная (прерывная), цифровая информация.

Информационные технологии, информационные ресурсы

Объектом информатики являются Автоматизированные Информационные системы (сокр. АИС), основанные на ЭВМ и телекоммуникациях.

Информационные технологии – основанные на ЭВМ способы обработки семантических информационных данных и знания, которые реализуются посредством АИС.

Классификация АИС:

Деление по зависимости от организации информационных процессов.

- Управляющие АИС

- Информационные АИС

Территориальный признак.

- АИС города, области, района

- Геоинформационные АИС

Деление по сфере применения

- Административные, учебные, медицинские итд.

По методу управления:

- АИС на предприятии

- АИС хозяйственной деятельности

Информационные ресурсы – это знания, ставшие информацией, т.е. это идеи человечества и указания по их реализации в любой форме, позволяющей воспроизводство.

Количество и качество информации. Формы адекватности информации.

Качество информации — степень её соответствия потребностям потребителей. Свойства информации являются относительными, так как зависят от потребностей потребителя информации.

Количество информации можно рассматривать как меру уменьшения неопределенности знания при получении информационных сообщений.

Адекватность информации – уровень соответствия образа, создаваемого с помощью полученной информации реальному объекту.

Различают три формы адекватности информации:

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

Информация и энтропия, единицы измерения информации

Информацио́нная энтропи́я — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

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

За единицей количества информации принимается такое количество информации, которое содержится в информационном сообщении, уменьшающем неопределенность знания в два раза. Такая единица названа битом.

Производные единицы измерения количества информации. Минимальной единицей измерения количества информации является бит, а следующей по величине единицей - байт, причем:

1 байт = 8 битов = 2³ битов.

В информатике система образования кратных единиц измерения несколько отличается от принятых в большинстве наук. Традиционные метрические системы единиц, например Международная система единиц СИ, в качестве множителей кратных единиц используют коэффициент 10ⁿ, где n = 3, 6, 9 и т. д., что соответствует десятичным приставкам "Кило" (10³), "Мега" (10⁶), "Гига" (10⁹) и т. д.

В компьютере информация кодируется с помощью двоичной знаковой системы, и поэтому в кратных единицах измерения количества информации используется коэффициент 2ⁿ

Так, кратные байту единицы измерения количества информации вводятся следующим образом:

1 килобайт (Кбайт) = 2¹⁰ байт = 1024 байт;

1 мегабайт (Мбайт) = 2¹⁰ Кбайт = 1024 Кбайт;

1 гигабайт (Гбайт) = 2¹⁰ Мбайт = 1024 Мбайт.

Свойства информации

1. Адекватность - степень соответствия информации, полученной потребителем, тому, что автор вложил в её содержание.

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

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

Методы повышающие достоверность информации

· Фильтрация

· Статистический анализ данных

3. Полнота информации - достаточность для принятия решения. Она зависит как от полноты данных, так и от наличия необходимых методов.

4. Избыточность информации. Это свойство, полезность которого мы ощущаем очень часто. Нередко избыточность информации человек чисто психологически воспринимает как её качество, потому что она позволяет ему меньше напрягать своё внимание и меньше утомляться. Обычный текст, напечатанный на русском языке, имеет избыточность порядка 20-25. Визуальная информация, которую мы получаем органами зрения, имеет очень большую избыточность - более 90. Ещё большую избыточность имеет видеоинформация (до 98-99).

Методы снижения избыточности

· Фильтрация

· Группировка

· Селекция

5. Объективность и субъективность - чем больше информационных процессов применяется к информации тем больше её субъективность.

6. Доступность информации - это мера возможности получить ту или иную информацию. Обеспечивается выполнением соответствующих процедур, получением информации и ее преобразования.

7. Актуальность - это степень соответствия информации текущему моменту времени.

Данные. Операции с данными

Данные – диалектическая составная часть информации. Данные напрямую связаны с носителем. Любой носитель можно характеризовать параметром разрешающей способности и динамическим диапазоном.

Операции с данными:

1. Сбор данных (накопление данных с целью обеспечения достаточной полноты информации с целью принятия решения).

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

3. Фильтрация данных (отсеивание лишних данных, в которых нет необходимости для принятия решения).

4. Сортировка данных

5. Группировка данных

6. Архивация данных (организация хранения данных в удобной и легкодоступной форме).

7. Защита данных (комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных).

8. Транспортировка данных (прием и передача данных между удаленными участками процесса).

9. Преобразование данных (перевод данных из одной формы в другую).
7. Основные структуры данных. Линейные структуры.

1. Линейная - простейшая структура данных, отличающаяся тем , что адрес каждого элемента данных однозначно определяет его номер. Разделителем может быть любой символ, не встречающийся в самих данных. Для розыска элемента с номером n, необходимо просмотреть всю линейную структуру сначала и пересчитать разделители. Когда будет рассчитано n-1 разделителей, начнется нужный элемент. Он закончится как только будет встречен следующий разделитель.

1.1. Список - структура данных, состоящая из элементов одного типа, связанных между собой.

1.2. Ассоциативный массив - абстрактный тип данных, позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу.

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

1.4. Стек - структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

1.5. Очередь - структура данных с дисциплиной доступа к элементам «первый пришёл - первый вышел» (FIFO, First In - First Out). Добавление элемента возможно лишь в конец очереди, выборка - только из начала очереди, при этом выбранный элемент из очереди удаляется.

1.6. Двусвязная очередь - структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO.

1.7. Буферное окно - динамический массив, который позволяет эффективно производить вставку и удаление элемента в некоторой области. Текст хранится в большом буфере в двух смежных сегментах с окном для вставки элементов между ними. Вставка добавляет новый текст в конец первого сегмента.

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

3. Иерархическая - адрес n-го элемента определяется путем доступа, ведущем от вершины структуры к данному элементу. Для упорядочения в таких структурах применяется метод предварительной индексации.

Табличные и иерархические структуры данных. Дихотомия данных.

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

Табличная структура – отличается от линейной тем, что адрес ячейки определяется не одним параметром, а несколькими. Чтобы найти элемент в табличной структуре, нужно просмотреть набор данных с начала и пересчитать внешние разделители (будет подсчитан один индекс), а затем считаем внутренние разделители.

Пример:

1 , 2 , 3 , 4 /

5 , 6 , 7, 8 /

9 , 0 , й , у/

Запятая – внутренний разделитель, слэш – внешний. Адрес элемента «6» (2,2) при отсчёте с 1.

Иерархическая структура – в ней адрес определяется путём доступа от вершины структуры к данному элементу. Каждому элементу данных присваивается свой уникальный индекс, который используется при поиске, сортировке и т.п. Достоинства этой структуры – это простота, лёгкость упорядочивания, лёгкость обновления. Недостаток – большая трудоёмкость при работе с ней.

Дихотомия данных.

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

В иерархической структуре, построенной методом дихотомии, путь доступа к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи.
9. Системы счисления и методы перевода чисел.

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

Различают позиционные и непозиционные системы.

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

Любая позиционная система счисления характеризуется основанием. Основание – количество различных знаков или символов, используемых для изображения чисел в данной системе.

Методы перевода чисел:

1. Последовательное деление числа на основание системы. Данный метод действенен при переводе из системы с большим основанием в систему с меньшим (10→9-2)

2. Суммирование произведений основания системы счисления в степени, соответствующей порядковому номеру цифры, и самой цифры соответственно. Метод перевода из системы с меньшим основанием в десятичную систему. (2-9→10).

3. Перевод триадами\группами по 4, а так же обратный перевод по тому же принципу. Действенно для перевода внутри 2ой, 8ой и 16ой системах.

10. Основные этапы компьютерного решения задач.

Решение задач в любой сфере деятельности – это всегда получение определенных результатов. А процесс получения результатов опирается на некоторый способ действий и предполагает использование определенных средств. Одним из новейших средств решения различных задач становятся современные компьютеры – универсальные устройства обработки и накопления данных.

Решение задачи на компьютере происходит в несколько этапов.

1. Анализ требований

2. Определение спецификаций

3. Проектирование

4. Написание программы

5. Тестирование

6. Сопровождение

1-й этап – анализ требований. На данном этапе строится описательная информационная модель объекта или процесса.

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

1. Что представляют из себя исходные данные?

2. Какими должны быть действия программы?

3. Какими должны быть выходные данные?

2-й этап – Определение спецификаций. На данном этапе формируются выводы, основанные на анализе требований и выполняется техническое задание, согласуемое с заказчиком и исполнителем.

3-му этап. Выбирается метод решения, составляется общий проект программы, выделяются основные части и определяются методы их взаимодействия.

4-й этап – перевод алгоритма в программу.

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

1. Обнаружение ошибок

2. Локализация ошибок

3. Исправление ошибок.

Для более эффективной отладки используется текст с заведомо известным результатом.

Виды ошибок: алгоритмические, ошибки программирования, синтаксические ошибки кодирования.

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

Алгоритм. Основные понятия. Свойства алгоритма.

Алгоритм – точный набор инструкций, описывающий последовательность действий некоторого исполнителя, для достижения результата в решении некоторой задачи за конкретное время

Виды алгоритмов

Линейный – все этапы решения задачи выполняются в естественном порядке следования записи этих этапов.

Ветвление

Выбор направления обработки информации зависит от исходных и промежуточных данных.

Циклический – многократно повторяемый участок вычислений. Циклическим называется алгоритм, который содержит 1 или несколько циклов.

Свойства алгоритма

1. Дискретность. Означает способность разбиения определяемого алгоритмом вычислительного процесса на конечное число отдельных действий (шагов), возможность выполнения которых исполнителем не вызывает сомнения

2. Понятность. Каждое из элементарных действий алгоритма, является законченным и понятным для исполнителя (применительно к ВТ; действия должны входить в систему команд исполнителя)

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

4. Массовость. Предполагает, что алгоритм должен быть применен к различным наборам исходных данных, т.е. подходит для решения подобных задач.

5. Результативность (завершаемость, конечность). Свойство указывает, что при конкретно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. Отрицательный результат тоже считается результатом.

Способы записи алгоритма.

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

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

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

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

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

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

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

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

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

Итерационным называется цикл, число повторений которого не задается, а определяется в ходе выполнения цикла. В этом случае одно повторение цикла называется итерацией.