Обработка информации и алгоритмы реферат

Обновлено: 02.07.2024

Основные структуры и алгоритмы по обработке информации ( реферат , курсовая , диплом , контрольная )

Контрольная работа

На тему: Основные структуры и алгоритмы по обработке информации

1. Основные понятия

Для точного описания абстрактных структур данных и алгоритмов программ используются системы формальных обозначений, называемые языками программирования, в которых смысл всякого предложения определяется точно и однозначно. Среди средств, представляемых почти всеми языками программирования, имеется возможность ссылаться на элемент данных, пользуясь присвоенным ему именем, или, иначе, идентификатором . Одни именованные величины являются константами, которые сохраняют постоянное значение в той части программы, где они определены, другие — переменными, которым с помощью оператора в программе может быть присвоено любое новое значение. Но до тех пор, пока программа не начала выполняться, значение переменных не определено. Компилятор, транслирующий текст программы в двоичный код, связывает каждый идентификатор с определенным адресом памяти.

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

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

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

2. Хранение информации и алгоритмы их обработки

В ЦВМ можно выделить три основных вида запоминающих устройств: сверхоперативная, оперативная и внешняя память.

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

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

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

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

3. Классификация структур данных и алгоритмов

Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы.

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

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

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

Интегрированными называются такие структуры данных, составными частями которых являются другие структуры — простые или в свою очередь интегрированные (25, "https://referat.bookap.info").

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

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

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

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

2. множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

3. множество допустимых операций, которые применимы к объекту описываемого типа.

4. Операции над структурами данных

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

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

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

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

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

программирование данные информация алгоритм

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

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

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

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

Ключевым понятием в СУБД является понятие модели данных, в основном тождественное понятию логической структуры данных. Отметим, что физическая структура данных в СУБД не рассматривается вообще. Но сами СУБД являются программными пакетами, выполняющими отображение физической структуры в логическую.

Для реализации этих пакетов используются те или иные системы программирования, разработчики СУБД, следовательно, имеют дело со структурами данных в терминах систем программирования. Для пользователя же внутренняя структура СУБД и физическая структура данных совершенно прозрачна; он имеет дело только с моделью данных и с другими понятиями логического уровня.

В данный момент вы не можете посмотреть или раздать видеоурок ученикам

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

Получите невероятные возможности

Конспект урока "Обработка информации и алгоритмы"

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

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

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

К цифровым носителям информации относятся магнитные носители информации, оптические диски, флеш-носители.

Передача информации – это физический процесс, при котором происходит перемещение информации в пространстве. Этот процесс происходит при наличии приёмника и источника.

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

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

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

Давайте рассмотрим схему, при помощи которой разберёмся, как происходит сам процесс обработки информации.

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

Давайте разберёмся на примерах, как это происходит.

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

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

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

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

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

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

Здесь у нас также присутствует один из видов обработки информации: изменение формы представления информации.

Таким образом, исходными данными будут являться каталог книг в библиотеке или же Всемирная сеть, а также критерий поиска – тема реферата. А результатом будет готовый реферат.

В этом примере описан такой вид обработки информации, как поиск.

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

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

В IX веке в Багдаде жил Абу Аль-Хорезми – один из крупнейших средневековых персидских учёных IX века, математик, астроном, географ и историк.

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

Арабский оригинал этой книги был утерян, но остался латинский перевод XII века, по которому Западная Европа и познакомилась с десятичной системой счисления и правилами выполнения арифметических действий.

Аль-Хорезми стремился к тому, чтобы сформулированные им правила были понятными. Достичь этого в IX веке, когда ещё не была разработана математическая символика (знаки операций, скобки, буквенные обозначения и так далее), было сложно. Однако ему удалось выработать чёткий стиль строгого словесного предписания, который не давал читателю возможность уклониться от предписанного или пропустить какие-нибудь действия.

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

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

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

Но не все люди, которые решают те или иные примеры, знают, что они выполняют алгоритм.

Каждое утро люди пьют чай или кофе.

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

· налить воду в чайник;

· насыпать кофе в кружку;

· налить воду в кружку.

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

Рассмотрим ещё один пример.

(7 + 16) · (23 – 5) : 5 – 203

Все мы знаем, что для решения этого примера необходимо:

· выполнить операции в скобках слева направо;

Порядок действий решения примера и есть алгоритм.

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

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

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

Когда, как и кем была создана такая машина мы с вами узнаем чуть позже.

А сейчас давайте подведём итоги урока.

· Обработка информации – это преобразование информации из одного вида в другой, которое осуществляется по строгим формальным правилам.

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

· Алгоритм – это строгий порядок правил, которые определяют последовательность шагов обработки информации.

2) изменение формы представления информации;

"Алгоритм" от имени выдающегося математика средневекового Востока Мухаммеда аль-Хорезми, который ещё в IX веке описал правила выполнение вычислений с многозначными десятичными числами.

В 30-х годах XX века возникает новая наука - теория алгоритмов. Английский учёный Алан Тьюринг, который создал "машину Тьюринга". По его замыслу та машина является универсальным исполнителем обработки любых символьных последовательностей в любом алфавите. Практически одновременно с Тьюрингом другую модель алгоритмической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и несколко проще в своём "устройстве".

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

1) Ученик (исполнитель) на уроке биологии составляет вторую цепь ДНК. Исходные данные - первая цепь ДНК. По правилу комплементарности ученик выполняет необходимые действия. Результат - вторая цепь ДНК. Вид обработки: получение новой информации, новых сведений.

2) Ученик (исполнитель) на уроке геометрии решает задачу и записывает все данные с помощью математических знаков, обозначений и латинских букв. Исходные данные - словесное описание задания. Обозначения из учебника помогают правильно "перевести" информацию. Результат - задача, записанная с помощью знаков (не словесно). Вид обработки: изменение формы представления информации.

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

4) Ученик (исполнитель) на уроке истории должен найти ответ на поставленный вопрос в параграфе учебника. Исходные данные - данные из поставленного вопроса. Слова в вопросе "подсказывают", какую информацию нужно найти. Результат - ответ на вопрос. Вид обработки: поиск информации.

1.7. Обработка информации. Алгоритмы. Объекты

Рис. 1.21. Абстрактная машина

а перечень действий отличаться от инструкций, входящих в запись алгоритма на языке пользователя. Поэтому функциями интерпретатора являются обеспечение интерфейса с пользователем, прием алгоритма и исходных данных и их перевод с языка пользователя на язык команд исполнителя, а также перевод результата исполнения алгоритма исполнителем на язык пользователя (рис. 1.21). Таким образом, исполнитель, входящий в состав AM, является, в свою очередь, вложенной в нее абстрактной машиной AM₁, а интерпретатор AM — пользователем АМ₁. Вложенность абстрактных машин можно продолжать до тех пор, пока язык пользователя абстрактной машины AM_i (i=1, 2, 3. ) не совпадет с языком ее исполнителя (рис. 1.22).
Поясним введенные понятия на примере. При работе человека-пользователя на компьютере (АМ) можно выделить несколько языков для записи алгоритмов. Первый — это машинный язык, или язык команд компьютера. Алфавит этого языка — двоичный. Предложения этого языка (инструкции) содержат код команды, которую должен выполнить процессор компьютера, и данные, которые используются в этой команде. Подчеркнем, что все команды машинного языка могут быть исполнены процессором (АМ₂), но непривычны для человека. Производительность

Рис. 1.22. Вложенные абстрактные машины

его труда при записи алгоритмов на этом языке будет невысокой. Второй язык — это более удобный для человека язык записи алгоритмов в графическом (язык блок-схем) или текстовом виде. Однако инструкции на этом языке непосредственно компьютером выполнены быть не могут. Проблема решается созданием и использованием третьего языка — языка программирования, предназначенного для разработки и записи на нем алгоритмов человеком, — и специальных программ (трансляторов) для перевода алгоритмов с этого языка на машинный. Таким образом, программу-транслятор можно рассматривать как интерпретатор промежуточной абстрактной машины (AM₁).
Взаимодействие пользователя с абстрактной машиной в диалоговом режиме можно представить как конъюнкцию (соединение) событий, инициируемых его действиями, с элементами интерфейса АМ (рис. 1.23).
Каждое такое событие связывается с состоянием (например, состояние 1 нарис. 1.23), в котором находится пользователь входе диалога, и выбираемой им командой (на рис. 1.23 это команда 1) на исполнение абстрактной машиной некоторого алгоритма, оперирующего с исходными данными (ИД 1), введенными пользователем или хранящимися в АМ. Поскольку диалоговый режим подразумевает возможность выбора пользователем определенной команды (события) из множества возможных в данном состоянии, интерпретация АМ происшедшего начинается с проверки, какое именно событие произошло, т. е. какой алгоритм необходимо исполнить. Для каждого конкретного состояния любое возможное в нем событие интерпретируется абстрактной машиной как выполнение одного из возможных для данного состояния условий

Рис. 1.23. Взаимодействие пользователя с абстрактной машиной в диалоговом режиме

(на рис. 1.23 это условие 1), сигнализирующего о том, что произошло именно это событие и необходимо исполнить соответствующий ему алгоритм (алгоритм 1 на рис. 1.23). Результат исполнения алгоритма (результат 1 на рис. 1.23) предъявляется пользователю, при этом изменяется состояние, в котором он находится (состояние 2 на рис. 1.23). Далее происходит новое событие (на рис. 1.23 это выбор пользователем команды 4), которое вновь интерпретируется АМ с исполнением уже другого алгоритма (алгоритма 4 на рис. 1.23). После чего пользователь оказывается в новом состоянии (состояние 3 на рис. 1.23) и т. д.
Для обобщенного описания возможностей, имеющихся у пользователя при диалоге с АМ, используются диаграммы перехода состояний (рис. 1.24). На диаграмме располагается конечное число прямоугольников, соответствующих всем возможным состояниям процесса диалога, одно из которых (на рис. 1.24 это состояние 1) является начальным. Все возможные в данном состоянии команды (условия), по которым осуществляется исполнение того или иного алгоритма, обозначаются на диаграмме стрелками, выходящими из соответствующего прямоугольника и ведущими в прямоугольник, обозначающий состояние, в которое осуществляется переход после исполнения алгоритма. Около стрелки размещают две надписи. Верхняя указывает условие, при выполнении которого должен быть исполнен алгоритм, обозначенный в нижней надписи.
Диаграммы перехода состояний, таким образом, описывают все возможные варианты совместной обработки информации человеком (пользователем), выбирающим то или иное Условие, и компьютером, выполняющим тот или иной Алгоритм. Эти диаграммы можно строить в виде иерархически упорядоченного множества диаграмм различного уровня подробности. Любую стрелку диаграммы верхнего уровня, соединяющую какие-то два состояния, можно более подробно описать с помощью диаграммы нижнего уровня, в которой эти состояния являются начальным и конечным. При таком иерархическом описании Алгоритм на диаграмме верхнего уровня исполняется не исключительно АМ, а попеременно АМ и пользователем в режиме диалога. Алгоритм диаграмм переходов состояний нижнего уровня, исполняемый только АМ, будем называть алгоритмической процедурой или просто процедурой этой АМ.
Пользователь, работая на ПК с каким-либо приложением (программой), снабженным современным графическим интерфейсом,

Рис. 1.24. Пример диаграммы перехода состояний

Рис. 1.27. Ветвление

При первой проверке условия цикла, когда n = 1, оно выполняется: выражение К101 истинно. К нулевому значению суммы s прибавляется единица, и она тоже становится равной единице. Затем модифицируется переменная цикла п, она увеличивается на единицу и становится равной двум. Условие n

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