Что такое структурирование в информатике кратко

Обновлено: 04.07.2024

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

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

1) уметь осмысленно изучать материал любой дисциплины, выделяя в нем основное (базисное) и оставляя второстепенную информацию;

2) проводить анализ, сравнение, классификацию, выявить причинно-следственных связей и т. д.;

3) формировать точное изложение мыслей, ответы на вопросы, публичные выступления;

4) правильно приводить доказательства своих суждений;

5) оформлять вывод, создавать план действий, проявлять самостоятельность.

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

Технологию структурирования информации можно проводить в различных формах:

1) использование готового структурированного материала (графические схемы) из литературы и наглядных пособий;

2) подготовленный структурированный материал преподавателем (презентации, опорные конспекты);

3) формирование структурированной информации непосредственно на занятиях во время изложения нового материала;

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

Цели, задачи и принципы структуризации информации

Главная цель структурирования – упрощение понимания основных элементов, из которых состоит весь массив информации, а также логики взаимосвязанности этих элементов.

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

¾ в основе процесса создания базы данных лежат определенные принципы. Первый принцип заключается в необходимости исключать повторяющиеся (или лишние) данные, т. к. они занимают место и повышают вероятность возникновения ошибок и неполадок. Второй принцип касается важной роли правильных и полных данных. Если база данных содержит неправильные данные, все отчеты, основанные на сведениях из нее, будут также содержать неверные содержатся в таблицах;

¾ возможность поддержания и отслеживания точности и целостности данных;

¾ соответствие требованиям к обработке данных и созданию отчетов.

2) проводить анализ, сравнение, классификацию, выявить причинно-следственных связей и т. д.;

3) формировать точное изложение мыслей, ответы на вопросы, публичные выступления;

4) правильно приводить доказательства своих суждений;

5) оформлять вывод, создавать план действий, проявлять самостоятельность.

Технологию структурирования информации можно проводить в различных формах:

2) подготовленный структурированный материал преподавателем (презентации, опорные конспекты);

Цели, задачи и принципы структуризации информации

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

Еще в далеком 1976 швейцарский ученый Никлаус Вирт написал книгу Алгоритмы + структуры данных = программы.

40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.

В статье так же будут вопросы, которое вы можете услышать на интервью.

Что такое структура данных?

Какие бывают?

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

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

Основные структуры данных.

Массивы
Стеки
Очереди
Связанные списки
Графы
Деревья
Префиксные деревья
Хэш таблицы

Массивы

Массив — это самая простая и широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.

Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).

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

Бывают

Одномерные, как показано выше.
Многомерные, массивы внутри массивов.

Основные операции

Insert-вставляет элемент по заданному индексу
Get-возвращает элемент по заданному индексу
Delete-удаление элемента по заданному индексу
Size-получить общее количество элементов в массиве

Вопросы

Найти второй минимальный элемент массива
Первые неповторяющиеся целые числа в массиве
Объединить два отсортированных массива
Изменение порядка положительных и отрицательных значений в массиве

Стеки

Это не массивы. Это очередь. Придумал Алан Тюринг.

Изображение стека, в три элемента (1, 2 и 3), где 3 находится наверху и будет удален первым.

Основные операции

Push-вставляет элемент сверху
Pop-возвращает верхний элемент после удаления из стека
isEmpty-возвращает true, если стек пуст
Top-возвращает верхний элемент без удаления из стека

Вопросы

Реализовать очередь с помощью стека
Сортировка значений в стеке
Реализация двух стеков в массиве
Реверс строки с помощью стека

Очереди

Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.

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

Изображение очереди, в четыре элемента (1, 2, 3 и 4), где 1 находится наверху и будет удален первым

Основные операции

Enqueue—) — вставляет элемент в конец очереди
Dequeue () — удаляет элемент из начала очереди
isEmpty () — возвращает значение true, если очередь пуста
Top () — возвращает первый элемент очереди

Вопросы

Реализовать cтек с помощью очереди
Реверс первых N элементов очереди
Генерация двоичных чисел от 1 до N с помощью очереди

Связанный список

Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.

Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Бывают

Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.

Двунаправленный, две ссылки, связанные с каждым узлом, одним из опорных пунктов на следующий узел и один к предыдущему узлу.

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

Самое частое, линейный однонаправленный список. Пример – файловая система.

Основные операции

InsertAtEnd — Вставка заданного элемента в конец списка
InsertAtHead — Вставка элемента в начало списка
Delete — удаляет заданный элемент из списка
DeleteAtHead — удаляет первый элемент списка
Search — возвращает заданный элемент из списка
isEmpty — возвращает True, если связанный список пуст

Вопросы

Реверс связанного списка
Определение цикла в связанном списке
Возврат N элемента из конца в связанном списке
Удаление дубликатов из связанного списка

Графы

Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).

Бывают

Ориентированный, ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
Неориентированные, к каждому из ребер можно осуществлять переход в обоих направлениях.
Смешанные

Встречаются в таких формах как

Общие алгоритмы обхода графа

Поиск в ширину – обход по уровням
Поиск в глубину – обход по вершинам

Вопросы

Реализовать поиск по ширине и глубине
Проверить является ли граф деревом или нет
Посчитать количество ребер в графе
Найти кратчайший путь между двумя вершинами

Деревья

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

Древовидные структуры везде и всюду. Дерево скилов в играх знают все.

N дерево
Сбалансированное дерево
Дерево Бинарного Поиска

Три способа обхода дерева

В прямом порядке (сверху вниз) — префиксная форма.
В симметричном порядке (слева направо) — инфиксная форма.
В обратном порядке (снизу вверх) — постфиксная форма.

Вопросы

Найти высоту бинарного дерева
Найти N наименьший элемент в двоичном дереве поиска
Найти узлы на расстоянии N от корня
Найти предков N узла в двоичном дереве

Trie ( префиксное деревое )

Разновидность дерева для строк, быстрый поиск. Словари. Т9.

Вопросы

Подсчитать общее количество слов
Вывести все слова
Сортировка элементов массива с префиксного дерева
Создание словаря T9

Хэш таблицы

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

По сути это массив, в котором ключ представлен в виде хеш-функции.

Эффективность хеширования зависит от

Функции хеширования
Размера хэш-таблицы
Метода борьбы с коллизиями

Вопросы

Найти симметричные пары в массиве
Найти, если массив является подмножеством другого массива
Описать открытое хеширование

Список ресурсов

Вместо заключения

Матчасть так же интересна, как и сами языки. Возможно, кто-то увидит знакомые ему базовые структуры и заинтересуется.

Спасибо, что прочли. Надеюсь не зря потратили время =)

PS: Прошу извинить, как оказалось, перевод статьи уже был тут и очень недавно, я проглядел.
Если интересно, вот она, спасибо Hokum, буду внимательнее.

Структура данных (англ. data structure ) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

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

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

Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревья обычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адреса компьютеров.

Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов (STL) языка C++.

Сравнение структур данных в функциональном и императивном программировании

Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам [1] :

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

Первое:

Второе:

Как ехать в село Дудкино?

1. До Иванова на самолете.

1. Далее до Орехова на электричке.

1. До поселка Ольховка на пароме.

1. До села Дудкино на попутной машине.

Третье:

Рисунок 1. Связи между населенными пунктами

Четвертое:

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

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

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

Структуры информации можно разделить на классы:

множество-класс, в котором перечислен весь набор элементов и их характерные признаки (Например, множество, состоящее из Хризантем, Тюльпанов; Нарцисов определено характерным признаком – что это растения и цветы).
линейный класс или линейный список - множество, состоящее из конечного числа элементов и его элементы расположены в строго определенном порядке. В отличие от множества элементы в списке могут повторяться и должны быть отсортированы по определенному правилу, например по алфавиту.
таблицы- класс структуры позволяет установить связь между несколькими элементами. Например, в таблице 2 элементы каждой строки связаны между собой и отвечают за один объект. Таким образом хранится вся информация в базах данных. Строка таблицы называется записью, а столбец-полем (свойства записи).

Готовые работы на аналогичную тему

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

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

Рисунок 4. 1 иерархия

В информатике иерархию называют деревом.

Такое название закрепилось из-за того, что если перевернуть схему вверх ногами, она становится похожа на дерево (точнее, на куст, см. рисунок справа). Несколько деревьев образуют лес.

Дерево состоит из узлов и связей между ними (они называются дугами). Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка‐дуга) – это корень дерева. Конечные узлы, из которых не выходит ни одна дуга, называются листьями. Все остальные узлы, кроме корня и листьев – это промежуточные узлы.

Графы - класс структуры, где определен набор узлов (вершин) и связей между ними (рёбер). Приведем пример инфорации, которую обычно представляют в виде графа.

Читайте также: