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

преобразования выполняются разными способами. Рассмотрим некоторые из них:

- возведение в квадрат. Числовое значение ключа возводится в квадрат

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

Для нашего случая 2647311682 = 70082591310644200, центральными

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

КОМПЬЮТЕР равен 131,

- метод складывания (не путать со сложением). Числовое значение ключа

делится на три части: средняя часть (размещается по центру) имеет

количество цифр, равное порядку адресов памяти, где размещен

список; оставшиеся правая и левая части «заворачиваются» к средней

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

ключа 264731168 этот способ дает следующий результат:

264 731 168

левая средняя правая

часть часть часть

После складывания:

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. Это и есть относительный адрес для ключа

КОМПЬЮТЕР,

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

которые смещаются друг навстречу другу так, чтобы общее число разрядов

стало равно порядку адресов памяти. Совпавшие разряды складываются.

Например, для ключа 264731168 и для тех же адресов:

02647[1] 31168

левая правая

часть часть

направление движения

правой и левой частей числа

02647 после сдвига

31168

3 3 7 (10)(15) = 337(1+0)(1+5)=33716

Поскольку полученное число имеет порядок, больший трех, процедура

сдвига повторяется:

033 716

левая часть правая часть

033 после сдвига

716

749 – конечный результат – относительный адрес для ключа

КОМПЬЮТЕР.

Очевидно, и этот этап дает потерю информации.

3) вычисление абсолютного адреса. Исходная информация – диапазон

изменения относительных адресов (очевидно, от 0 до 999) и адреса размещения

элементов списка в памяти (напомним, что список занимает кластеры с

адресами от 10 до 999). Тогда абсолютный адрес для элементов списка

получается по формуле:

+ *

const,

где const – константа, получаемая по формуле:

число доступных адресов / максимальный относительный адрес, причем

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

адресами размещения списка в памяти.

Для нашего случая const = 989 / 999 = 0,989

Тогда, например, для относительного адреса 199 абсолютный адрес (читай

– номер кластера) равен 10 + 199*0,989 = 10+197 = 207.

2. Задания

1. Создать на диске линейный список в соответствии с вариантом (состав

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

2. Разработать алгоритмы и программы поиска нужной информации в

линейном списке в соответствии с вариантом.

3. Выполнить автоматизированный сравнительный анализ методов

адресации, данных в варианте, на основе обобщенного критерия - произведения

числа обращений к машинному носителю на объем информационной базы (вместе с

индексами).

Варианты заданий

Таблица 1

|№ |Характеристика записей|Методы адресации |Ключ |

|варианта|файла |(пункты из п. 1) | |

|1 |2 |3 |4 |

|1. |Учетная карточка |1.1, 1.7 |Ф. И. О. студента |

| |студенческой группы | | |

|2. |То же |1.2, 1.6 |Порядковый номер в |

| | | |группе |

|3. |Экзаменационная |1.3, 1.4 |Ф. И. 0. студента |

| |ведомость | | |

|4. |То же |1.3, 1.5 |Номер зачетной книжки |

|5. |То же |1.1, 1.6 |Номер по порядку |

|6. |Ведомость выдачи |1.1, 1.5 |То же |

| |стипендии | | |

|7. |То же |1.1, 1.4 |Ф. И. 0. студента |

|8. |Прейскурант цен |1.2, 1.7 |Наименование товара |

|9. |То же |1.2, 1.6 |Индекс товара |

|10. |Расписание движения |1.2, 1.5 |Номер рейса |

| |самолетов | | |

|11. |Фрагмент телефонного |1.2, 1.4 |Ф. И. 0. абонента |

| |справочника | | |

|12. |То же |1.2, 1.6 |Номер телефона |

| | | |Продолжение таблицы 1 |

|1 |2 |3 |4 |

|13. |Из варианта 1 |1.2, 1.7 |Номер в группе |

|14. |Из варианта 1 |1.3, 1.4 |Номер в группе |

|15. |Из варианта 3 |1.1, 1.7 |Ф. И. 0. студента |

|16. |То же |1.2, 1.6 |Номер зачетной книжки |

|17. |Из варианта 6 |1.2, 1.7 |Номер по порядку |

|18. |То же |1.1, 1.6 |То же |

|19. |То же |1.3, 1.5 |То же |

|20. |Из варианта 8 |1.1, 1.5 |Индекс товара |

|21. |То же |1.3, 1.4 |То же |

|22. |Из варианта 10 |1.1, 1.7 |Номер рейса |

|23. |То же |1.3, 1.6 |То же |

|24. |Из варианта 11 |1.1, 1.5 |Номер телефона |

|25. |То же |1.3, 1.7 |То же |

ЧАСТЬ 2. АВТОКОРРЕКЦИЯ ТЕКСТА

ВВЕДЕНИЕ

Программы автоматического обнаружения и исправления ошибок в текстах

на естественных языках (назовем их автокорректорами - АК, хотя терминология

ещё не сложилась) получают все большее распространение. Они используются, в

частности, в пакетах WINWORD и EXCEL для проверки орфографии текстовой

информации.

Говоря точнее, АК производят автоматически лишь обнаружение ошибок, а

собственно коррекция ведется обычно при участии человека.

В высокофлективных языках, к которым относятся, в частности, все

славянские, от одной основы могут образовываться до нескольких сот

различных словоформ. В этих условиях в АК неизбежны средства

морфологического анализа той или иной сложности, а непосредственное

использование западных АК и перенос методов их работы на неанглоязычные

тексты едва ли даст удовлетворительные результаты, если исключить метод

"грубой силы" - неограниченное наращивание объема оперативной памяти (ОП) и

быстродействия ЭВМ.

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

1.1. Методы обнаружения ошибок

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

орфографических ошибок в текстах - статистический, полиграммный и

словарный.

При статистическом методе из текста одна за другой выделяются

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

согласно частоте встречаемости. По завершении просмотра текста

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

экран дисплея. Орографические ошибки и описки в сколь-нибудь грамотном

тексте несистематичны и редки, так что искаженные ими слова оказываются где-

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

автоматизированно найти их в тексте и исправить.

При полиграммном методе все встречающиеся в тексте двух- или

трехбуквенные сочетания (биграммы и триграммы) проверяются по таблице их

допустимости в данном естественном языке. Если в словоформе не содержится

недопустимых полиграмм, она считается правильной, а иначе - сомнительной, и

тогда предъявляется человеку для визуального контроля и, если нужно,

исправления.

При словарном методе все входящие в текст словоформы, после

упорядочения или без него, в своем исходном текстовом виде или после

морфологического анализа, сравниваются с содержимым заранее составленного

машинного словаря. Если словарь такую словоформу допускает, она считается

правильной, а иначе предъявляется контролеру. Он может оставить слово как

есть; оставить его и вставить в словарь, так что далее в сеансе подобное

слово будет опознаваться системой без замечаний; заменить (исправить) слово

в данном месте; потребовать подобных замен по всем дальнейшему тексту;

отредактировать слово вместе с его окружением. Операции над сомнительным

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

из замысла проектировщика АК.

Результаты неоднократных исследований показали, что только словарный

метод экономит труд человека и ведет к минимуму ошибочных действий обоих

родов - пропуска текстовых ошибок, с одной стороны, и отнесения правильных

слов к сомнительным, с другой. Поэтому словарный метод стал доминирующим,

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

1.2. Автоматизация процесса исправления

Можно предложить три степени автоматизации процесса коррекции текста:

1) только обнаружение ошибок,

2) обнаружение их и выдвижение гипотез (альтернатив, кандидатов) по

исправлению;

3) обнаружение ошибок, выдвижение гипотез и принятие одной из них

(если хотя бы одна выдвинута системой) в качестве автоматически вносимого

исправления.

Без первой степени АК немыслим.

Вторая и третья степень возможны только при словарном методе. Уже

вторая существенно облегчает внесение исправлений, ибо в большинстве

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

альтернативы, когда контролирующее текст лицо нетвердо знает данный

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

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

современные АК часто имеют средство выдвижения гипотез лишь в качестве

факультативного, запускаемого, если требуется, избирательно для данного

сомнительного слова.

Третья степень автоматизации заманчива и одновременно опасна.

Заманчивость заключается в полной автоматизации процесса исправления.

Опасность же в том, что ни один словарь, в том числе - заключенный в

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

слово встречает система, основанная на неполном словаре, она может

"исправить" его на ближайшее ей знакомое, порой резко исказив исходный

смысл текста. Особо опасно править собственные имена лиц, фирм, изделий,

Заманчиво уметь пропускать (обходить) собственные имена и сугубо

специальные термины, априори полагая их правильными, но безошибочные

способы обхода, особенно - терминов, нам не известны.

Чисто автоматическому исправлению мог бы способствовать автоматический

синтаксический и семантический анализ проверяемого текста, но он ещё не

стал принадлежностью обычных АК. И даже при его наличии лишь человек сможет

диагностировать быстро меняющиеся совокупности собственных имен, терминов и

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

новации.

В связи со сказанным полная автоматизация исправлений может

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

I) Текст имеет вид перечня терминов и терминологических словосочетаний

в стандартной их форме, так что в АК достаточно иметь словарь, замкнутый по

объему и проблематике. При этом все термины между собой "непохожи"

(например, в словаре нет одновременно АДСОРБЦИЯ и АБСОРБЦИЯ).

2) Ошибки носят характер замены кодов исходных букв на коды литер,

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

ASCII русских букв А, В, С, Е, У на коды латинских букв А, В, С, Е, У;

латинские буквы I и 0 - на цифры I и 0 и т.п. Сюда же отнесем повторы одной

и той же литеры, возникающие из-за продленного нажима клавиши дисплея или

его неисправности. В подавляющем большинстве, если в словоформе более 2 -3

букв, такие исправления абсолютно правильны.

1.3. Диалоговый и пакетный режимы

Возможны, в общем случае, два режима работы АК: диалоговый, когда

текст проверяется слово за словом и пользователю предоставляется

возможность снять очередное затруднение по мере его возникновения, и

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

пользователя.

Во втором случае ненайденные словоформы либо как-то отмечаются в

исходном тексте, либо запоминаются отдельно в виде своих адресов (в

качестве адреса может использоваться, например, номер строки и номер

символа, с которого начинается слово, в строке). Подобная проверка ведется

до конца проверяемого файла без вмешательства человека. Далее файл

вызывается снова и предъявляется для контроля тех строк, где были замечены

сомнительные слова.

2. Задания

1. Создать русскоязычный текстовый файл в ASCII-кодах размером с

машинописный лист.

2. Разработать алгоритмы и программы автокорректора русскоязычного

текста с характеристиками, указанными в вариантах. Автокорректор должен

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

ASCII-кодах в виде файла.

Варианты заданий

Таблица 2

|№ |Метод обнаружения|Метод исправления ошибок |Способ |

|вариа|ошибок | |реализации |

|нта | | | |

|1 |2 |3 |4 |

|1. |Статистический |Исправления только в тексте, без |Диалоговый |

| | |гипотез | |

|2. |То же |Исправления и в словаре, без гипотез |Пакетный |

|3. |То же |Исправления только в тексте, с |Диалоговый |

| | |выдвижением гипотез | |

|4. |То же |Исправления и в словаре, с выдвижением|Пакетный |

| | |гипотез | |

|5. |Полиграммный |Исправления только в тексте, без |Диалоговой |

| |(биграммы) |гипотез | |

|6. |То же |Исправления и в словаре, без гипотез |Пакетный |

|7. |То же |Исправления только в тексте, с |Диалоговый |

| | |выдвижением гипотез | |

|8. |То же |Исправления и в словаре, с выдвижением|Пакетный |

| | |гипотез | |

|9. |Словарный |Исправления только в тексте, без |Диалоговый |

| | |гипотез | |

|10. |То же |Исправления и в словаре, без гипотез |Пакетный |

| | |Продолжение таблицы 2 |

|1 |2 |3 |4 |

|11. |То же |Исправления только в тексте, с |Диалоговый |

| | |выдвижением гипотез | |

|12. |То же |Исправления и в словаре, с выдвижением|Пакетный |

| | |гипотез | |

ЧАСТЬ 3. СЖАТИЕ ИНФОРМАЦИИ

ВВЕДЕНИЕ

В процессе ускоренной компьютеризации общества объемы данных, хранимых

на машинных носителях, быстро растут. Ещё совсем недавно они измерялись

килобайтами и мегабайтами, а теперь - гигабайтами и более крупными

единицами. Естественно желание хранить эти данные предельно компактно.

Причем интересны обратимые методы, устраняющие избыточность информации при

сжатии и восстанавливающие её при разжатии. Описанные в методических

указаниях методы обратимы.

Объектами сжатия являются:

- числовые данные,

- упорядоченные текстовые данные (словари),

Страницы: 1, 2, 3