Индивидуальные задания по информатике

Калининградский государственный технический университет

ИНФОРМАТИКА

Методические указания для выполнения индивидуальных заданий

для студентов направления 552800 «Информатика и вычислительная техника»

КАЛИНИНГРАД

2000

УДК 681.3.06

Автор – Топоркова О.М., к.т.н., доцент кафедры систем управления и вычисли-тельной техники Калининградского государственного технического университета

Методические разработки рассмотрены и одобрены кафедрой систем управления и вычислительной техники 20.9.99, протокол № 1.

Рецензент – кафедра систем управления и вычислительной техники Калининград-ского государственного технического университета

©Калининградский государственный технический университет, 2000

Введение

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

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

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

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

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

Задачи программируются на языке программирования, который изучается в курсе «Алгоритмические языки и программирование», и, тем самым, закрепляют навыки, полу-ченные в этой дисциплине. Кроме этого, требование подготовки блок-схем средствами WinWord позволяет углубить знания, связанные, с одной стороны, с логическим проекти-рованием алгоритма, а с другой – с правилами начертания блок-схем.

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

ЧАСТЬ 1. МЕТОДЫ АДРЕСАЦИИ

ВВЕДЕНИЕ

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

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

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

Основную проблему при адресации элементов списков можно сформулиро¬вать следующим образом: как по первичному ключу определить местоположение элемента с данным ключом (задача поиска)? Существует несколько различных спосо¬бов адресации. Они рассматриваются далее.

1. Теоретическая часть

1.1. Последовательное сканирование списка

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

1. 2. Блочный поиск

Если элементы упорядочены по ключу, то при сканировании списка не требуется чтение каждого элемента. Компьютер мог бы, напри¬мер, просматривать каждый n-ный элемент в последовательности возрастания ключей. При нахождении элемента с ключом, большим, чем ключ, используемый при поиске, просматриваются последние n-1 элемен-тов, которые были пропущены. Этот способ называется блочным поиском: элементы группируются в блоки, и каждый блок проверяется по одному разу до тех пор, пока ни будет найден нужный блок. Вычисление оптимального для блочного поиска раз¬мера бло-ка выполняется следующим образом: в списке, со¬держащем N элементов, число просмот-ренных элементов минимально при длине блока, равной N. При этом в среднем анализи-руется N элементов.

1.3. Двоичный поиск

При двоичном поиске рассматривается элемент, находящийся в середине области, в которой выполняется поиск, и его ключ срав¬нивается с поисковым ключом. Затем поиско-вая область делится пополам, и процесс повторяется. При этом, если N велико, то в сред-нем будет просмотрено примерно log2N-1 элементов. Это число меньше, чем число про-смотров для случая блочного поиска.

1.4. Индексно-последовательная организация

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

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

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

Если для адресации используется индекс, ЭВМ в ос¬новном производит поиск в индексе, а не в списке. При этом существенно экономится время, но требуется память для хранения индекса. Это похоже на использование картотеки в библиотеке. Пользова-тель отыскивает название требуемой книги в картотеке и находит номер книги по катало-гу, который является как бы отно¬сительным адресом положения книги на полках.

Если элементы списка упорядочены по ключу, индекс обычно со¬держит не ссылки на каждый элемент, а ссылки на блоки элементов, внутри которых можно выполнить по-иск или сканирование.

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

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

Индексно-последовательные файлы представляют собой наибо¬лее распространен-ную форму адресации файлов.

1.5. Индексно-произвольная организация

Произвольный (непоследовательный) список можно индексиро¬вать точно так же, как и последовательный список. Однако при этом требуется значительно больший по раз-мерам индекс, так как он должен содержать по одному элементу для каждого элемента списка, а не для блока элемента. Более того, в нем должны содер¬жаться полные абсо-лютные (или относительные) адреса, в то вре¬мя как в индексе последовательного спи-ска адреса