Реферат: Методические указания по информатике - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Методические указания по информатике

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 38 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Методические указания для выполн ения индивидуальных заданий для сту дентов направления 552800 “Информатика и вычислительная техника” Введение Тенденция усиления фактора самостоятельной работы студентов привела к разработке данн ых методических указаний по выполнению индиви дуальных заданий по инфор матике . Они п ризваны , с одной стороны , подробно ознакомить обучающихся с некоторыми практическими задач ами информатики , а с другой – закрепить навыки прикладного программирования и состав ления блок-схем. Настоящие методические указания состоят и з трех само стоятельных частей , в котор ых излагаются три практические задачи совреме нной информатики – адресация элементов данны х линейного списка , автокоррекция естественно языковых текстов , сжатие данных. Первая задача нашла свое применение в таких программных проду ктах , как сист емы управления базами данных , операционные си стемы (организация поисковых операций в систе мных данных ), компиляторы (работа с таблицами идентификаторов ) и многих других . Алгоритмы адресации имеют универсальный характер и испо льзуются практич е ски во всех зада чах , в которых ведется организация и поиск информации в одномерных массивах , независимо от места ее нахождения – основная п амять или внешняя. Вторая задача носит более частный хар актер , а изложенные методы используются при проверке орфограф ии в текстовых и табличных процессорах , издательских системах , а также как средство верификации результатов работы сканера – после распознавания текс та для устранения возможных ошибок выполняетс я его орфографический анализ. Проблема сжатия данных решается в современных архиваторах . Они , как правило , и спользуют комбинацию методов , изложенных в тр етьей части. Задачи программируются на языке программи рования , который изучается в курсе “Алгоритми ческие языки и программирование” , и , тем с амым , закрепляют навыки , полученные в это й дисциплине . Кроме этого , требование подготов ки блок-схем средствами WinWord позволяет углубить знания , связанные , с одной стороны , с логич еским проектированием алгоритма , а с другой – с правилами начертания блок-схем. Запрограммированны е и отлаженные зада чи должным образом оформляются , что также способствует умению студента правильно и акку ратно закреплять результат работы на бумажном носителе информации. ЧАСТЬ 1. МЕТОДЫ АДРЕСАЦИИ ВВЕДЕНИЕ Одной из проблем при создании информа ционных систем является работа со структуриро ванными данными , которые чаще всего являются линейными списками – упорядоченным множеств ом элементов , порядковые номера которых опред еляют местоположение элемента в спи ске . Элементы списка имеют структуру – они состоят из конечного множества полей , каждо е из которых имеет определенный смысл , нап ример , фамилии , адреса и т.д . Для таких списков важна задача адресации элементов спис ков – определение адреса элемента списка п о одному из его полей или по совокупному набору полей . Такие поля называются ключевыми (или ключами ) (в просте йшем случае ключом , например , может быть н омер зачетной книжки студента ). Иногда бывает необходимо объединить неско лько полей , чтобы образовать ун икальный ключ , называемый в этом случае сцепленным ключом : например , ключ , идентифицирующий студент а в институте , является комбинацией номера группы , фамилии , имени и отчества студента (есть случаи , когда в одной группе уча тся студенты с одинаковыми фамил и ями и именами ). Кроме простого и сцепленного , ключ мож ет быть первичным – определять максимум один элемент в списке или вторичным – определять множество (в общем случае не одноэлементное ) элементов в списке . Например , фамилия студента в учебной группе , как правило , является первичным ключом , а пол студента – вторичный ключ , поскольку одному значению этого ключа (мужской или женский ) соответствует , в общем случае , груп па студентов. Основную проблему при адресации элементов списков можно сформулировать следую щим образом : как по первичному ключу определи ть местоположение элемента с данным ключом (задача поиска )? Существует несколько различных способов адресации . Они рассматриваются дале е. 1. Теоретическая часть 1.1. Послед овательное сканирование списка Наиболее простым способом локализации эле мента списка является сканирование списка с проверкой ключа каждого элемента . Этот сп особ , однако , требует слишком много времени для большинства применений . Он может быть эффективен только при пакетной обработке последовательного файла , находящегося , например , на магнитной ленте , когда каждая запись все равно должна быть прочитана. 1. 2. Блочный поиск Если элементы упорядочены по ключ у , то при ск анировании списка не т ребуется чтение каждого элемента . Компьютер м ог бы , например , просматривать каждый n-ный элемент в последовательности возрастания ключей . При нахождении элемента с ключом , больши м , чем ключ , используемый при поиске , просм атриваются п о следние n-1 элементов , кото рые были пропущены . Этот способ называется блочным поиском : элементы группируются в бл оки , и каждый блок проверяется по одному разу до тех пор , пока ни будет на йден нужный блок . Вычисление оптимального для блочного поиска размер а блока выполняется следующим образом : в списке , содер жащем N элементов , число просмотренных элементов минимально при длине блока , равной N . При этом в среднем анализирует ся N элемен тов. 1.3. Двоичный поиск При двоичном поиске рассматривается элеме нт , находящийся в середине области , в кото рой выполняется поиск , и его ключ сравнива ется с поисковым ключом . Затем поисковая о бласть делится пополам , и процесс повторяется . При этом , если N велико , то в сре днем будет просмотрено примерно log 2 N-1 элементов . Это число меньше , чем число просмотров для случая бл очного поиска. 1.4. Индексно-последовательная организация В общем случае сканирование (последовате льный поиск ) в списках для нахождения в них элемента является процессом , требую щим много времени , если он выполняется над всем списком . Однако его можно использова ть для точной локализации элемента в небо льшой области , если эта область найдена не которым д р угим способом. Если список упорядочен по ключам , то обычно при адресации используется таблица , называемая индексом . При обращении к таблиц е задается ключ искомого элемента , а резул ьтатом процедуры поиска в таблице является относительный или абсолютный адре с эле мента. Индекс можно определить как таблицу , с которой связана процедура , воспринимающая на входе информацию о некоторых значениях а трибутов и выдающая на выходе информацию , способствующую быстрой локализации элемента или элементов , которые имеют задан ные зна чения атрибутов . Индекс использует в качестве входной информации ключ и дает на вы ходе информацию , относящуюся к физическому ад ресу данного элемента. Если для адресации используется индекс , ЭВМ в основном производит поиск в инде ксе , а не в списке . П ри этом су щественно экономится время , но требуется памя ть для хранения индекса . Это похоже на использование картотеки в библиотеке . Пользоват ель отыскивает название требуемой книги в картотеке и находит номер книги по кат алогу , который является как бы отн о сительным адресом положения книги на полках. Если элементы списка упорядочены по к лючу , индекс обычно содержит не ссылки на каждый элемент , а ссылки на блоки эле ментов , внутри которых можно выполнить поиск или сканирование. Хранение ссылок на блоки элемент о в , а не на отдельные элементы в значит ельной степени уменьшает размер индекса . Прич ем даже в этом случае индекс часто ок азывается слишком большим для поиска и по этому используется индекс индекса . В больших списках может быть больше двух уровней индекса. Д ля ускорения поиска сегменты ниж него уровня индекса могут находиться среди данных , на которые они указывают . Например , в файле на диске обычно имеется на каждом цилиндре индекс дорожек , содержащий ссылки на записи , хранящиеся на этом цилин дре. Индексно-пос ледовательные файлы представл яют собой наиболее распространенную форму адр есации файлов. 1.5. Индексно-произвольная организация Произвольный (непоследовательный ) список можно индексировать точно так же , как и последовательный спис ок . Однако при этом требуется значительно бо льший по размерам индекс , так как он д олжен содержать по одному элементу для ка ждого элемента списка , а не для блока элемента . Более того , в нем должны содержа ться полные абсолютные (или относительные ) адр еса , в то время как в индексе последовательного списка адреса могут содерж аться в усеченном виде , так как старшие знаки последовательных адресов будут совпадать. По сравнению с произвольным доступом индексно-последовательный список более экономичен как с точки зр ения размера индекса , так и с точки зрения времени , необход имого для поиска в нем . Произвольные списк и в основном используются для обеспечения возможности адресации элементов списка с н есколькими ключами . Если список упорядочен по одному ключу , то он не у п орядочен по другому ключу . Для каждого тип а ключей может существовать свой индекс : д ля упорядоченных ключей индексы будут более длинными , так как должны будут содержать по одному данному для каждого элемента . Ключ , который чаще всего используется при адре с ации списка , обычно служит для его упорядочения , поскольку наиболее быстрый доступ возможен в том случае , когд а применяется короткий последовательный индекс. Аналогия с картотекой библиотеки скорее соответствует индексно-последовательному доступу , чем прои звольному . В картотеке использу ются два ключа - название книги и фамилия автора , и , как правило , ни тот , ни другой ключ не применяются при упорядочивании книг на полках , следовательно , оба индекс а должны содержать по элементу для каждой книги . Книги упоря д очиваются по номеру в каталоге . После того как пол ьзователь нашел номер интересующей его книги в каталоге , он отыскивает книгу на ря дах полок . В каждом ряду обычно указаны начальный и конечный номера книг в нем . Пользователь сравнивает номер , который он п о лучил из каталога (индекса ), с номерами , указанными в рядах . Найдя нужны й ряд , он ищет полку , на которой стоит книга . Аналогично ЭВМ выполняет поиск в файлах , начиная , например , с главного инде кса , далее просматривая индекс цилиндров , а затем индекс дорож е к. В картотеке библиотеки не указывается физическое местоположение книги на полках . Вместо этого в ней содержится номер в каталоге , который может рассматриваться как символический адрес . Символический адрес указыв ается потому , что книги переставляются , и , если бы использовался физический адрес , это потребовало бы частой корректировки ка ртотеки библиотеки . По той же причине в индексно-произвольных списках часто используются символические , а не абсолютные адреса . При добавлении новых или удалении старых эле м е нтов изменяется местоположение оста льных элементов . Если имеется несколько ключе й , то индекс вторичного ключа может содерж ать в качестве выхода первичный ключ запи си . При определении же местоположения элемент а по его первичному ключу можно использов ать ка к ой-нибудь другой способ адр есации . По этому методу поиск осуществляется медленнее , чем поиск , при котором физичес кий адрес элемента определяется по индексу . В списках , в которых положение элементов часто изменяется , символическая адресация может оказаться предпочтительнее. Другой причиной для непоследовательного р азмещения элементов могут служить частые изме нения списка . Интенсивное включение новых и удаление старых элементов в последовательно упорядоченном списке связано с большими тр удностями и значительн ым расходом машинно го времени . Если бы книги хранились на полках библиотеки в алфавитном порядке , то обеспечение такого порядка занимало бы и злишне много времени , так как каждый раз при добавлении новой книги требовалось б ы передвигать много книг. 1.6. Адресация с помощью ключа , экви валентного адресу Известно много методов преобразования клю ча непосредственно в адрес в файле . В тех случаях , когда такое преобразование возмо жно , оно обеспечивает самую быструю адресацию ; при этом нет необходимости организовыв ать поиск внутри файла или выполнять опер ации с индексами. Наиболее простое решение задачи адресации - указывать во входном сообщении относительны й машинный адрес запрашиваемой записи . В н екоторых ранних банковских системах номера счетов видоизменялись так , чтобы новый номер или его часть являлись бы адресо м элемента для данного счета в списке . Таким образом , адрес был равен ключу ил и определялся по нему простым способом. Во многих приложениях такой прямой по дход невозможен . Номера изделий на завод е не могут изменяться только ради удобств а использования ЭВМ , поскольку для работников фирмы они имеют в запросе определенный смысл. Иногда во входном сообщении используется внутренний машинный код ; при этом не требуется , чтобы он был равен номеру клиента или номеру изделия . Например , адрес записи счета в файле может печататься в банковской расчетной книжке клиента сбер кассы и указываться далее в запросе с терминала. Такие схемы называются прямой адресацией , хотя обычно этот термин используе тся в более широком смысле для обозначения любого алгоритма , преобразующего ключ непосредс твенно в машинный адрес. 1.7. Алгоритм преобразования ключа в адрес Способ преобразования ключа в адрес д ает почти ту же скорость поиска , чт о и способ , в котором используется ключ , эквивалентный адресу . В некоторых прил ожениях адрес может быть вычислен на осно ве идентификаторов объекта , таких как адрес улицы и номер дома или номер рейса и его дата . Для таких приложений рассматри ваемый метод а д ресации является н аиболее простым и быстрым . Чаще всего данн ый способ применяется в диалоговых системах , где критичным является время поиска в списке , и называется хешированием , перемешивани ем или рандомизацией. К недостаткам данного способа относится мало е заполнение списка : в списке остаются свободные участки , поскольку ключи преобразуются не в непрерывное множество а дресов. При этом методе вся область памяти для размещения списка делится на участки – бакеты размером несколько десятков элем ентов списка . С ам алгоритм хеширования по первичному ключу определяет , в отличие от других методов , не адрес одного элем ента списка , а адрес бакета , содержащего ц елую группу элементов . При размещении элемент а в списке каждый новый элемент добавляет ся в конец уже имеющих с я в бакете элементов ; при поиске - после определ ения адреса бакета поиск нужного элемента выполняется методом последовательного сканирования . Алгоритм хеширования выполняется в три этапа : 1) первый этап выполняется только для нечисловых значений ключей и з аключает ся в замене их числовыми значениями . Для этого составляется таблица соответствия симв олов алфавита , в котором записываются значени я ключей , с цифрами от 1 до 9. Затем кажды й символ нечислового значения ключа заменяетс я своим цифровым эквивалентом. Наприме р , если нечисловые значения ключей определены на русском алфавите , такая таблица будет иметь вид : а -1 и -9 р -8 ш -7 б -2 й -1 с -9 щ -8 в -3 к -2 т -1 э -9 г -4 л -3 у -2 ю -1 д -5 м -4 ф -3 я -2 е -6 н -5 х -4 ь -3 ж -7 о -6 ц -5 ъ -4 з -8 п -7 ч -6 ы -5 Очевидно , разным симво лам присваивает ся один цифровой код , что ведет к поте ре информации. Тогда , например , для ключа со значение м КОМПЬЮТЕР цифровой эквивалент имеет вид 264731168. 2) формируется относительный адрес элемента списка . Для этого числовое значение адрес а приводится к порядку , равному порядку адресов памяти , где размещен список . Напр имер , список размещен на диске в кластерах с номерами от 10 до 999, т.е . в адресах с порядком , равным 3. Тогда для ключа , получе нного на предыдущем этапе , надо выполнить такое преобразов а ние , чтобы из дев ятизначного числа превратить его в трехзначно е . Подобные преобразования выполняются разными способами . Рассмотрим некоторые из них : возведение в квадрат . Числовое значение ключа возводится в квадрат и в получен ном числе по центру выбираетс я нужное количество цифр . Для нашего случая 264731168 2 = 70082591310644200, центральными ц ифрами являются 131. Таким образом , относительный адрес для ключа КОМПЬЮТЕР равен 131, метод складывания (не путать со сложен ием ). Числовое значение ключа делится на три части : средняя часть (размещается по центру ) имеет количество цифр , равное п орядку адресов памяти , где размещен список ; оставшиеся правая и левая части “заворачив аются” к средней и совпавшие цифры склады ваются до образования цифр . Например , для ключа 2 64731168 этот способ дает следующ ий результат : После складывания : 731- средняя часть 462 - левая часть , “завернутая” по месту стыка со средней частью 861 - правая “завернутая” часть . После сложения совпавших цифр (сложение идет до достижения значения цифр ы ): (7+4+8)(3+6+6)(1+2+1) = (19)(15)(4) = (1+9)(1+5)(4) = (10)(6)(4) = (1+0)(6)(4) = 164 Таким образом , относительный адрес для ключа КОМПЬЮТЕР , полученный вторым способом , равен 164, - метод деления . Числовое значение ключа делится на количество адресов п амяти , в которой размещается список . Остаток от деления – относительный адрес . Например , для ключа 264731168 и для числа адресов 989 (999 – 10) остаток от деления равен 593. Это и есть относительный адрес для ключа КОМПЬЮТЕР, 3) вычисление абсолютного адре са . Исх одная информация – диапазон изменения относи тельных адресов (очевидно , от 0 до 999) и адреса размещения элементов списка в памяти (нап омним , что список занимает кластеры с адре сами от 10 до 999). Тогда абсолютный адрес для элементов списка получает с я по формуле : <начальный адрес размещения списка > + <отн осительный адрес элемента > * const, где const – константа , получаемая по форм уле : число доступных адресов / максимальный отн осительный адрес , причем число доступных адре сов – разность между максималь ным и минимальным адресами размещения списка в памяти. Для нашего случая const = 989 / 999 = 0,989 Тогда , например , для относительного адреса 199 абсолютный адрес (читай – номер кластер а ) равен 10 + 199*0,989 = 10+197 = 207. ЧАСТЬ 2. АВТОКОРРЕКЦИЯ ТЕКСТА ВВЕДЕНИЕ Программы автоматического обнаружения и и справления ошибок в текстах на естественных языках (назовем их автокорректорами - АК , х отя терминология ещё не сложилась ) получ ают все большее распространение . Они и спользуются , в частности , в пакетах WINWORD и EXCEL д ля проверки орфографии текстовой информации. Говоря точнее , АК производят автоматическ и лишь обнаружение ошибок , а собственно ко ррекция ведется обычно при участии че ловека. В высокофлективных языках , к которым о тносятся , в частности , все славянские , от о дной основы могут образовываться до нескольки х сот различных словоформ . В этих условиях в АК неизбежны средства морфологического анализа той или иной сложности , а непо средственное испо льзование западных АК и перенос методов и х работы на неа нглоязычные тексты едва ли даст удовлетворите льные результаты , если исключить метод "грубой силы " - неограниченное наращивание объема опер ативной памяти (ОП ) и быстродействия ЭВМ. 1. Теоретическая часть 1.1. Методы обнаружения ошибок Известны , по крайней мере , три метода автоматизированного обнаружения орфограф ических ошибок в текстах - статистический , поли граммный и словарный. При ст атистическом методе из текс та одна за другой выделяются составляющие его словоформы , а их перечень по ходу проверки упорядочивается согласно частоте встр ечаемости . По завершении просмотра текста упо рядоченный перечень предъявляется человеку для контроля , н апример , через экран ди сплея . Орографические ошибки и описки в ск оль-нибудь грамотном тексте несистематичны и редки , так что искаженные ими слова оказыв аются где-то в конце перечня . Заметив их здесь , контролирующее лицо может автоматизирова нно найти их в т ексте и испр авить. При полиграммном методе все встречающиеся в тексте двух - или трехбуквенные сочетани я (биграммы и триграммы ) проверяются по та блице их допустимости в данном естественном языке . Если в словоформе не содержится недопустимых полиграмм , она с читается п равильной , а иначе - сомнительной , и тогда п редъявляется человеку для визуального контроля и , если нужно , исправления. При словарном методе все входящие в текст словоформы , после упорядочения или бе з него , в своем исходном текстовом виде или посл е морфологического анализа , сра вниваются с содержимым заранее составленного машинного словаря . Если словарь такую словофо рму допускает , она считается правильной , а иначе предъявляется контролеру . Он может оста вить слово как есть ; оставить его и вс тавить в словарь , так что далее в сеансе подобное слово будет опознаваться системой без замечаний ; заменить (исправить ) слово в данном месте ; потребовать подобных замен по всем дальнейшему тексту ; отредак тировать слово вместе с его окружением . Оп ерации над сомните л ьным участком текста , указанные или иные возможные , могут комбинироваться исходя из замысла проектировщи ка АК. Результаты неоднократных исследований показа ли , что только словарный метод экономит тр уд человека и ведет к минимуму ошибочных действий обоих род ов - пропуска текст овых ошибок , с одной стороны , и отнесения правильных слов к сомнительным , с другой . Поэтому словарный метод стал доминирующим , хотя полиграммный метод иногда и применяют как вспомогательный. 1.2. Автоматизация процесса испра вл ения Можно предложить три степени автоматизаци и процесса коррекции текста : 1) только обнаружение ошибок, 2) обнаружение их и выдвижение гипотез (альтернатив , кандидатов ) по исправлению ; 3) обнаружение ошибок , выдвижение гипотез и принятие од ной из них (если хотя бы одна выдвинута системой ) в качестве автоматически вноси мого исправления. Без первой степени АК немыслим. Вторая и третья степень возможны толь ко при словарном методе . Уже вторая сущест венно облегчает внесение исправлений , ибо в бол ьшинстве случаев исключает перенабор сомнительного слова . Особенно полезны найденные альтернативы , когда контролирующее текст лиц о нетвердо знает данный естественный язык или конкретную терминологическую область . Однак о выдвижение гипотез требует больших п ереборов с поиском по словарю . Поэтому современные АК часто имеют средство выдв ижения гипотез лишь в качестве факультативног о , запускаемого , если требуется , избирательно д ля данного сомнительного слова. Третья степень автоматизации заманчива и одновременно опасна . Заманчивость заключает ся в полной автоматизации процесса исправлени я . Опасность же в том , что ни один словарь , в том числе - заключенный в челове ческом мозгу , никогда не бывает исчерпывающе полным . Когда незнакомое слово встречает система , основа н ная на неполном сл оваре , она может "исправить " его на ближайш ее ей знакомое , порой резко исказив исходн ый смысл текста . Особо опасно править собс твенные имена лиц , фирм , изделий , Заманчиво уметь пропускать (обходить ) собственные имена и сугубо специа льные термины , априори полагая их правил ьными , но безошибочные способы обхода , особенн о - терминов, нам не известны. Чисто автоматическому исправлению мог бы способствовать автоматический синтаксический и семантический анализ проверяемого текста , но он ещё не ст ал принадлежностью о бычных АК . И даже при его наличии лишь человек сможет диагностировать быстро меняющ иеся совокупности собственных имен , терминов и аббревиатур , а также окказионализмы - случайн о появляющиеся словесные новации. В связи со сказанным полная авт оматизация исправлений может применяться лишь в любом из следующих ограничительных услов ий : I) Текст имеет вид перечня терминов и терминологических словосочетаний в стандартной их форме , так что в АК достаточно иметь словарь , замкнутый по объему и пр об лематике . При этом все термины между собой "непохожи " (например , в словаре нет одновременно АДСОРБЦИЯ и АБСОРБЦИЯ ). 2) Ошибки носят характер замены кодов исходных букв на коды литер , совпадающих или близких к исходным по начертанию . Например , заменяются ко ды ASCII русских букв А , В , С , Е , У на коды латинских букв А , В , С , Е , У ; латин ские буквы I и 0 - на цифры I и 0 и т.п . С юда же отнесем повторы одной и той же литеры , возникающие из-за продленного нажима клавиши дисплея или его неисправности . В подавляющем большинстве , если в словофо рме более 2 -3 букв , такие исправления абсолютно правильны. 1.3. Диалоговый и пакетный режимы Возможны , в общем случае , два режима работы АК : диалоговый , когда текст проверяет ся слово за словом и пользо вателю предоставляется возможность снять очередное за труднение по мере его возникновения , и пак етный , когда готовые большие тексты анализиру ются в отсутствии пользователя. Во втором случае ненайденные словоформы либо как-то отмечаются в исходном тексте , ли бо запоминаются отдельно в виде своих адресов (в качестве адреса может использоваться , например , номер строки и номер символа , с которого начинается слово , в строке ). Подобная проверка ведется до конца проверяемого файла без вмешательства человек а . Далее ф айл вызывается снова и предъявляется для контроля тех строк , где были замечены сомнительные слова. ЧАСТЬ 3. СЖАТИЕ ИНФОРМАЦИИ ВВЕДЕНИЕ В процессе ускоренной компьюте ри з ации общества объемы данных , хранимых на машинных носителях , быст ро растут . Ещё совсем недавно они измеряли сь килобайтами и мегабайтами , а теперь - ги габайтами и более крупными единицами . Естеств енно желание хранить эти данные пред е льно компактно . Причем интересны обратимые ме тоды , устраняющие избыточность информации при сжатии и восстанавливающие её при разжатии. Описанные в методически х указаниях методы обратимы. Объектами сжатия являются : - числовые данные, - упорядоченные текстовые данные (словари ), - специальные тексты на формализованных языках, - естественно-языковые тексты общего вида, - структурированные данные. В качестве к оличественной меры сжатия исполь з уется коэффициент сжатия - отноше ние длины первоначального к сжатому тексту , а также продолжительность требуемых преобра з ований. Теоретическая часть 1.1. Сжатие числовых данных На иболее распространены ме тоды : ра з ностное кодировани е , кодирование повторений и подавление незначащих нулей. Суть разностного кодирования заключается в хранении вместо абсолютных значений разност ей двух смежных чисел или отклонения чисел от их среднего значения . Например , для последовательности чисел 2 , 14, 18, 2 7, 34 первый способ даст последовательность 2, 12, 4, 9, 7. Второй способ поро ж дает последовательность : -17, -5, -1, 8, 15 (среднее значен ие для исходной последовательности - 19). Первый вариант эффективен для медленно меняющихся последовательностей , вт орой - когда максимальное отклонение от средне го з начительно меньше аб солютного значения среднего. Кодирование повторений заключается в заме не цепочки одинаковых символов кодом этого числа и числом повторений . Например , для последовательности 5555 6666 888888 применение этого с п особа даст последовательность 5(4) 6(4) 8(6). Подавление незначащих нулей о з начает отбрасывание незначащих нулей в старших ра з рядах целой части числа и в младших разрядах дробной части . Например , применение этог о способа сжатия к последовательности 0010 01,100 011 011 да ст последовательность : 10 1,1 11 11. 1.2 . Сжатие словарей Под словарями понимают списки неповторяющихся цепочек символов в алф авитном или ином строгом порядке . Такой сл оварь можно рассматривать как монотонную посл едовательность чисел и для его сжатия применять метод разностного к одирования (см . п .1.1). З десь он заключ ается в отбрасывании у каждого слова начальных букв , совпадающих с начальными символами предыдущего слова и з амене их на число отброшенных букв . Наприм ер , словарь : - вычислитель - вычислительный - вычислять - в р е зультате рассматриваемого способа кодир ования будет заменен словарем : - вычислитель - 11ный - 6ять. Такой метод , однако , неудобен тем , что при декодировании любого конкретного слова требуется последова тельно декодировать все предшест в ующие слов а . Поэтому порой используются отдельные переч ни н аиболее часто встреч ающихся частей слов (суффиксы , префиксы ), где каждой и з них ставится в соответст вие более короткий код , заменяющий её в словаре . Например , словарь : встречающийся заменяющий с помощью этого способа сжатия замени тся на совокупность словарей : Важнейшим здесь является алгоритм выбора достаточно длинных и часто вс тречающ ихся подцепочек . При его разработке использую тся эвристические алгоритмы , поскольку эффективно го алгоритма поиска оптимального решения не существует. Когда составляющие словаря обра з уют сильно обособленные групп ы слов , можно разделить весь словарь на подсловари, присвоив к аждому и з них свой ин декс , и кодировать слова независимо в кажд ом из них кодами минимальной длины , а слова из различных подслов арей различать этими индексами . Такой метод является модификацией описанного в п . 1.1 метода сжатия числовых данных через их среднее з начение . 1.3. Сжатие специальных тексто в К специал ьным относятся тексты на формальных языках , отличающихся о граниченным словарем , замкнутой грамматикой . Сюда прежде всего относятся тексты на языках программирования , машинные коды , различные фо рмулы и обозначения , а также ограниченн ы е подмножество фраз е стественного языка в таких четко формализован ных з адачах как организа ция реплик в интерактивных системах , выдача сообщений при компиляции и т.п. Для данного типа информации пригодны методы , описанны е в п. 1.5 . В то же вре мя специфика этих текстов по з воляет осуществить экономное хранение , основанное на выделении длинных часто по вторяющихся фрагмент ов. Например , текст Фортран-программы : Т YРЕ *, ’ ФОРТРАН ’ Т YРЕ *, ’ ПРОГРАММА ' может быть представлен с использованием кодового словаря : 1.4. Сжатие структурированных данных Структурированные данные содержат текстовую и иную информацию и хранятся в определенном формате , приемлемом для тех или иных прикла д ных задач , например , для документального или фактографического поиска информации . Пример стр уктурированных данных - библиографические описания. Ра з нородность данных структурированного типа обуславливает ра з личные типы информационной из быточ ности , поэтому необходимо использовать комбинацию методов , приспособленных к своим подгруппам данных . Так , для числовых полей целесообразно применять методы п . 1.1, для т екстовых - описанные в п . 1.5. По некоторым оце нкам комбинация этих методов дает сокр а щение объема данных в 1,5-4 раза , по другим оценкам - даже до 6 раз. В структурированных данных наряду с т ипами информационной избыточности , характерных дл я текстовых или нетекстовых данных , существуе т особый позиционный тип избыточности . Он связан с дубли рованием информации для идентификации структуры данных . Например , если записи файла имеют структуру : - Ф.И.О . студента - отношение к воинской обязанности - домашний адрес - специальность - оценки за сессию, причем поля имеют длину , соответственно , 40, 20, 50, 15, 10 байт , то при различных значениях тех или иных п олей для конкретных студентов часть области памяти , отводимой под отдельные поля , не будет использоваться . Тогда , если поле “О тношение к воинской обязанности” пусто , его можно исключить и з конкретной зап иси и вся запись будет иметь следующий вид : (Ф.И.О . студента ) 1 (домашний адрес ) 3 (специальность ) 4 (оценки за сессию ) 5 , где индексы означают принадлежность того или иного значения соответствующему полю. 1.5. Сжатие текстовой информа ции общего вида Принципиальная во з можность сжатия текстовой информации свя з ана с тем , что составляющие текста - буквы и словоформы - ра з личаются по част оте встречаемости в тексте , в то в ремя как их длины слабо связаны с час тотой. Все алгоритмы сжатия можно классифицирова ть по используемому методу кодирования и характеру использования статистики и грамматики текста. Методы кодирования можно ра з делить на четыре класса в з а висимости от того , какие группы символов к одируются (постоянной или переменной длины ), и какие коды исполь з уются (постоя нной или переменной длины ). По исполь з ованию статистики и грамматики алгоритмы сжатия можно разделить на семантически зависимые и семантически не з ависимые . Первые (лингвист ические ) методы опираютс я на грамматику естественного я з ыка для выделения в текстах элементов , подлежащих кодированию (как правило , это отдельные слова – словоформы ). Семантически независимые методы сжатия в свою очередь можно разделить на те , которые не исполь з уют , и те , которые используют априорные сведения о статистике текста . В соответствии с этим существуют два типа алгоритмов сжатия : одно - и двухфазные , ко торые будем называть соответственно адаптивными и статистическими. Семантически зависимые методы не использу ют для сжатия никаких априорных сведений о статистике текста . Кодирование прои з водится в процессе однократно го сканиро вания текста . Оно сводится к замене цепочек символов текста на встрое нные указатели , адресованные к той части т екста , где такие цепочки уже встречались . В этом случае говорят о внутренней адреса ции , а сами методы называются адаптивными. В алгоритмах второг о типа выполня ется ссылка на таблицу кодов , которая може т создаваться заново для каждого текста и ли использоваться одна на все гипотетические тексты . В этом случае говорят о внешн ей адресации и локальных или глобальных к одовых таблицах . 1.5.1 . Адаптивные алгорит мы Строят код постоянной длины для фрагментов переменной длины. Сжимают текст в процессе однократного его сканирования . Кодирование заключается в нахождении повторяющихся участков текста и замене каждого участка указателем, адресо ванным к той части текста , где такой у часток уже встречался . Для декодирования в этом случае кодовой таблицы не требуется . В качестве указателя может использоваться структура (m, n), где m – количество символов назад или вперед по тексту , перемести в шись на которые можно найти подобный фрагмент текста ; n – длина фрагмента в символах. Существует два типа встроенных указателей , указывающих на предшествующие или последующ ие участки . Алгоритмы , использующие указатели на з ад , м огут работа ть с непрерывным входным по током данных , генерируя непрерывный выход ной поток сжатой информации . На каждом шаг е алгоритма входной текст заполняет буфер фиксированной длины , внутри котор ого производится идентификация одинаковых подстрок максимально возможной длин ы . При нахождении двух таких подстрок втор ая з аменяется ука з ателем , адресованным в начало первой. Алгоритмы с указателя ми вперед мо гут работать лишь с текстами конечной дли ны , поскольку требуют обратного сканирования текста . Здесь также используется поиск совпад ающих подстрок в буфере переменной длины с уже закодированным текстом. Одной из характер н ых черт адаптивных алгоритмов является достат очная их универсальность , т.е . возможность рабо тать с любыми , не только текстовыми данным и , ненужность начальной информации о характер е данных и их статистике . Эта черта сн ижает эффективность сжатия и дост игаемое сжатие , как правило , меньше полученного д ругими методами . Но часто адаптивные алгоритм ы просты и все же приемлемы по эффект ивности. Коэффициент сжатия текстовых данных этим методом лежит в пределах 1,8 - 2,5. 1.5.2. Статистические алг оритмы. 1.5.2.1. Кодирование фрагментов ф иксированной длины Простейш е й формой словаря в этом случае является кодовая таблица символов алфавита , ставящая в соответствие каждому символу сво й код . Коды выбираются с таким расчетом , ч тобы общая длина з акодир ованного ими текста была минимальной . Такую же табли ц у можно сос тавить для всех или наиболее часто встреч ающихся комбинаций из дву х , трех и т.д . букв , т.е . фрагментов с фиксированным числом символов . Ниже приведены частоты бук в в русском языке : пробел -0,174 ы -0,016- о 0,080 з -0,016 е, ё 0,07 1 ъ -0,014 а 0,06 1 ь -0,014 и 0,061 б -0,014 т 0,0 5 2 г -0,013 м 0,052 ч -0,01 2 с 0,045 й -0,010 р 0,040 у -0,009 в 0,038 ж -0,007 л 0,035 ю -0,006 к 0,028 ш -0,006 н 0,026 ц -0,003 д 0,025 щ -0,003 п 0,023 э -0,003 у 0,021 ф -0,002 я 0,018 х -0,002 Сами коды рассчитываются на основании частот отдельных символов (в случае таблицы символов ) или их комбинаций (в этом сл учае общая частота рассчи тывается как произведение частот отдельных символов , входящи х в комбинацию ) с помощью методов Шеннона- Фано или Хаффмена (описание методов см . в приложении 1). И з быточность информаци и заключается ещё в корреляции между симв олам и (словами ). Метод Хаффмена сохраняет эту избыточность . Существуют модификации метода , позволяющие учесть взаимозависимости . Наиболее простая из них используется , когда все символы можно разделить на небольшое число групп с сильной корреляцией внутри груп п и слабой - между ними . Это и ногда имеет место для числовых и буквенны х символов текста. К другим недостаткам хаффменовс ких методов относится относительная сложность декодирования - необходимость анализа би товой структуры преф иксных кодов , замедля ющая процесс декодирования. Дальнейш и м развитием метода Хаффмена являются арифмети ч еские коды . Они происходят и з так называемых ко нкатенацион ных, или блочных , кодов . Суть их заключае тся в том , что выходной код генерируется для цепочки входных символ о в фиксированной длины без учета межсимвольных корреляций . В о снове мето да лежит представление вероятности каждой цеп очки К входных символов (А 1 , А 2 , ... А К ) в виде числа , получаемого как сумма К с лагаемых вида p(А 1 )p( А 2 ). .р (А I-1 )P(А I ) , I=1, 2, 3, …… K где р ( S ) - вероятность символа S , Р (S ) - куммулятивная вероятность символа S , равная сумме вероятностей всех символов A I , для которых р ( А I ) больше р ( S ). 1.5.2.2. Кодирование фрагментов п еременной длины Другой формой словаря может являть ся словарь фрагментов переменной длины . Словари фрагментов переменной длины строятся из словоформ , которые выделяются в тексте по естественным разделителям – про белам и знакам пунктуации . Затем рассчитывают ся частоты каждой словоформы как отношение числа е е повторений к общему количеству словоформ . Используя эти частоты , применяют метод Хаффмена или Шеннона- Фано для кодирования словоформ кодом переменн ой длины.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Учитель называл своих учеников "креативные тинейджеры". А они не понимали, что из термина нужно сделать аббревиатуру.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru