|
Реферат: Понимание речи (Программирование)
Понимание речи
Понимание речи обычно трактуют как преобразование акустического
представления речи в смысловое. При создании практических систем смысл
можно определить, как представление, из которого извлекаются действия,
совершенные системой. Понимание речи следует отличать от распознования
речи, где целью является сопоставить речевое высказывание с
соответствующими словами в словаре. До начала 70-ых большинство
исследований было направлено на распознование речи. 5 лет потребовалось на
создание системы ARPA, первоначальная исследовательская цель которой
заключалась в распознавании речи, а конечные результаты в понимании.
Казалось, что способность системы давать разумный ответ на речь была более
значимым критерием для развития речевых систем. К тому же считалось, что
речевой сигнал является недостаточным источником информации, и знание
контекста речевого высказывания важно только для успешного распонавания и
интерпретации. Системы по распознованию речи, основанные на динамическом
программировании и соответствии с образцами, развивали для речевых
высказываний, которые состояли почти полностью из изолированных слов,
выбираемых из небольшого вокабуляра. Однако такой подход, при котором
ищется наиболее точное соответствие между определенными произнесенными
словами и вокабуляром акустическох образцов слов, меньше всего подходил к
связанной речи, так как входной акустической сигнал в этом случае не может
быть эффективно смоделирован, как простое сочетание произнесенных частей
лексических единиц. В связанной речи изменчивость, выявляемая при
соответствии с образцами, передает полезную информацию и для распознования,
и для интерпретации. Однако, необходимо начинать с основных лингвистических
единиц, таких как фонемы, и сохранять информацию о ритме и длительности
речевого высказывания. Если следуют таким путем, то подход к обработке
речи, основанный скорее на знании, чем на соответствиях с образцами,
становится неизбежным, так как, чтобы извлекать преимущества из
распознавания конкретных лингвистических единиц в сигнале, необходимо
знать, как данная единица связана с остальной частью языка.
Системы понимания речи (СПР) имеют дело со связанными единицами речи,
такими как, фразы, предложения и даже параграфы, так как "понимание"
изолированных слов может означать только тривиальный процесс сопоставления
некоторого значения к каждому слову словаря системы. Понимание связанной
речи - очень сложная задача, и на проект СПР повлияли исследования в таких
разных областях, как акустическая обработка сигнала, нейро-физиология,
психолингвистика, психология. СПР была создана, чтобы понимать всего
нескольких дикторов одного диалекта, производя грамматически ограниченное
подмножество языка со словарем около тысячи слов. Сейчас хотя и имеются
много потенциальных прикладных программ для СПР их эффективность и
надежность все еще недостаточна, чтобы широко использоваться. Системы,
зависимые от диктора, распознающие изолированные слова с небольшим
словарем, использующие в качестве образцов-соответствий целые слова уже
нашли свое применение, типа обработки багажа на авиалиниях. Тем не менее
признано, что усовершенствование такого типа систем (большие словари,
независимость от диктора) требует подхода, основанного на более глубоких
знаниях.
Теоретические предпосылки
Посредником при преобразовании речи в ее значение должны служить
определенные компоненты, которые используют разнообразные источники знания
(ИЗ), т.к. речевой сигнал кодирует много различной информации, необходимой
для восстановления значения. Например, вариативность в произношении слов в
связанной речи больше не является помехой при подборе образца
соответствия, но это довольно важный источник информации, например,
относительно расположения границ слова или контекстуально важной
(выделенной ударением) информации в произнесении. Единственной возможной
организацией СПР и основных ИЗ является следующая: РЕЧЬ - ОБРАБОРТКА
АКУСТИЧЕСКОГО СИГНАЛА - ФОНЕТИЧЕСКИЙ АНАЛИЗ - ФОНОЛОГИЧЕСКИЙ АНАЛИЗ -
МОРФОЛОГИЧЕСКИЙ АНАЛИЗ - ЛЕКСИЧЕСКИЙ ДОСТУП К СЛОВАРЮ - СИНТАКСИЧЕСКИЙ
АНАЛИЗ - СЕМАНТИЧЕСКИЙ АНАЛИЗ - ЗНАЧЕНИЕ. При такой организации СПР
информация течет вверх по мере того, как каждый элемент создает
промежуточные представления, кодируя (частичные) гипотезы относительно
ввода на основе ему доступного знания.
Акустическая обработка отцифровывает сигнал с входной частотой, которая
сохраняет сигнал для понимания. Акустическая обработка также трансформирует
отцифрованный сигнал различными способами, чтобы представить его в той
форме, которая поддается фонетическому декодированию. Например,
спектральный анализ будет выполнен для каждого проанализированного фрейма,
и дополнительные параметры, такие как частота основного тона, подсчитаны.
Параметрический сигнал может затем быть помечен как дискретная
последовательность фонем. Например, если сигнал с низкой амплитудой
равномерно распространяется поперек спектра, то этот звук вероятно
фрикативный, типа [f] или [v]. Кроме того, для каждой фонемы характерны
такие особенности, как высота тона, длительность и амплитуда. Акустическо -
фонетическое преобразование является решающим для эффективной работы СПР,
но все еще одно из наиболее слабых сторон речевой обработки. И это являлось
главным недостатком СПР, разработанной на основе ARPA в 1970-ых.
Фонологический анализ выполняется на фонетическом представлении, которое
определяет лингвистически важные различия, имеющиеся в фонетическом
представлении произнесения, например, уровни и расположение ударения,
интонационный контур, структуры слога, последовательности фонем, лежащих в
основе произнесения. Фонологический анализ необходим для лексического
доступа, т.е. процесса, который сопоставляет фонетическую форму
произнесения с каноническими фонемными представлениями слов в словаре,
чтобы восстановить информацию, хранящуюся там относительно их
морфологических, синтаксических, и семантических свойств. Это отменяет
такие эффекты быстрой речи, как ассимиляция или сокращения. Например, слова
“did” и "you" могли бы иметь в словаре следующие последовательности фонем:
/dld/ и /ju:/. Однако, акустическо - фонетическое преобразование могло бы
восстанавливать фактические звуки или фонемы, типа [dIje]; связывать эту
фонетическую последовательность c каноническими фонемными представлениями
“did” и "you". Это необходимо, если нужно узнать, что палатализация
произошла на границе слова, заменив [dj] на [j], и что неударный гласный
"you" был редуцирован до нейтрального безударного. Аналогично,
фонологическое знание относительно допустимых последовательностей фонем в
слогах может использоваться, чтобы распознать слог, и следовательно,
границы слова. Например, в /houmhelp/ должна быть граница между /m/ и
вторым /h/, потому что никакой слог в английском не может содержать /mh/.
Как только фонологический анализ завершен, дальнейшая обработка ввода
будет подобна пониманию текста. Дальнейшие морфологический, синтаксический,
семантический и прагматический анализы способствуют распознаванию,
эксплуатируя избыточность речи, в информационно - теоретическом смысле. В
некоторых из проектов APRA задача синтаксического анализа заключалась в
том, чтобы исключить гипотезы слова на основе синтаксически недопустимых
последовательностей.
Прежде, чем слова, выделенные в речевом сигнале будут сопоставлены с
лексическими входам в словаре системы, необходимо провести морфологический
анализ, который приведет слова к их основной форме, например, устранит
окончание множественного числа /s/ или /z/, которые сильно бы расширили
число входов в словарь.
После морфологического анализа возникшее морфофонологическое представление
речевого ввода может быть найдено в словаре системы, чтобы получить
синтаксическую и семантическую информацию относительно гипотезы
последовательности слов. Синтаксический, семантический, и прагматический
анализ - в основном тот же самый для речевого и текстового понимания.
Однако, должно быть взаимодействие между этими и более низкими уровнями
анализа не только, потому что они будут дополнять правильное распознавание
произнесения, но также потому что некоторые аспекты фонологического
анализа, особенно касающиеся ударения и интонации, будут способствовать
интерпретации. Ударение, например, необходимо для определения
контекстуально новой информации и для нахождению зависимых слов для
местоимений.
Это краткое описание вклада различных ИЗ в понимание речи только
раскрывает основные процессы. ИЗ, использованные в понимании речи, являются
прежде всего лингвистическими. Однако, эффективность СПР зависит во много
как от эффективного использования этих ИЗ так и от разработки их
содержания.
Акустическо - фонетический Анализ
Несомненно наиболее важная область в обработке речи, нуждающаяся в
исследованиях, - это акустическо - фонетический анализ. Если акустическо -
фонетический анализ слабый, то ошибочные гипотезы выдадут в итоге
неправильный анализ. Сегментация и идентификация акустического сигнала в
последовательности лингвистических единиц чрезвычайно трудна. Сначала, речь
- это код, а не шифр; то есть, акустическое сигналы, ассоциирующиеся с
сегментами, непосредственно с ними не связанны; на эти сигналы сильно
влияют соседние сегменты. Например, спектрограммы /d/ в /di/ и /du/ очень
различны, т.к. на них влияют последующий гласный. Кроме того, не возможно
разделить акустической сигнал на /d/ и следующий гласный. Эти наблюдения
создали следующую теорию: конечное количество этих сегментов не всегда
можно достичь из-за непрерывного движения вокального трактата. Такой
синтезирующий анализ был бы, однако, очень в вычислительном отношении
дорогой, так как он требовал бы, чтобы СПР умел генерировать всех возможные
произнесения и сопоставлять их с акустическом вводом. Однако во-первых,
акустическое сигналы, в противоположность фонемам или алафонам, содержат
инвариантные сигналы. Во-вторых, акустическое сигналы часто сильно
редуцируются в безударном положении. Это часто вызывает много неправильных
гипотез в системах, где акустическо - фонетический компонент будет
принимать за гипотезу сегмент из фиксированного инвентаря. В-третьих,
акустическое сигналы варьируют от диктора диктору из-за физиологических
особенностей вокального тракта, различия в характеристиках речи и т.д..
Люди способны компенсировать эти различия быстро и плавно, но все еще мало
понятно, как сделать этот процесс автоматическим. Большинство коммерческих
систем распознавания речи требует длинного обучения, повторяя за
пользователем каждое слово в словаре системы несколько раз и -
следовательно очень зависимо диктора. В ARPA несколько из разработанных СПР
достигли определенной степени независимости от диктора, пытаясь ввести
параметр в акустическо - фонетический анализ для нового диктора на основе
обучающегося предложения, которое знала система, пользователю же
следовало его проговорить.
Во всех ARPA проектируют СПР, где акустическо - фонетический анализ
фактически не существовал и сегментный анализ не был точным. Конечное
представление каждой системы было главным образом определено эффективностью
более высоких уровней анализа при исправлении ошибок на фонетическом
уровне. Более современные системы используют более сложный акустическо -
фонетический анализ, интегрируя информацию из ряда преобразований
акустического сигнала и создавая несколько типов фонетических
представлений, но эффективность все еще ограничивается в среднем 70%
успешным распознаванием фонем из речевого высказывания, произнесенных
небольшим количеством дикторов.
Фонологический Анализ
Фонологический компонент необходим для любой, обрабатывающей речь,
системы, основанной на знаниях, потому что система требует знания
относительно фонологических процессов, активных в языке и в прикладных
программах, чтобы восстанавливать канонические произношение слов, которые
могут быть сопоставлены с соответствующими входами словаря, и получать
дальнейшие сигналы к синтаксической и семантической/прагматической
интерпретации речевого высказывания. Фонологические компоненты были
разработаны для СПР и других систем ARPA. Однако, они были в значительной
степени ограничены лексическими, сегментными процессами и обычно имели дело
с фонологически управляемыми изменениями, генерируя альтернативное
произношение для индивидуальных лексических единиц и сохраняя их в
дополнительном словаре. Этот подход не может иметь дело адекватно с
фонологическими процессами, которые соединяют границы слова, типа
палатализации. Самая большая область прикладной программы для
фонологического правила - интонационная фраза; следовательно, фонологию
нельзя рассматривать в терминах различного произношения для лексических
единиц. Фонологический анализ обеспечивает много важной информации для СПР;
например, различные виды фонологического правила блокированы различными
лингвистическими границами между сегментами. Полезно разложить на слоги и
слова речь, сегментация может также обеспечить сведения для синтаксического
анализа; палатализация соединяет границы слова, но блокирована на границах
главных синтаксических составляющих, так что ее отсутствие может
использоваться, чтобы решить неоднозначность относительно присутствия такой
границы в данном месте речевого сигнала. Фонологические правила также
изменяются среди диалектов. Следовательно, СПР, способные к пониманию
дикторов с различными диалектами, требовали бы знания относительно этих
различий и способности реконфигурировать себя для их речи. Палатализация,
например, происходит чаще в американских диалектах, чем в британских или
английских.
В конце семидесятых стали развиваться новые подходы к фонологии, такие как
автосегментная, метрическая зависимости, фонология зависимости, для
которых центральным является сверхсегментальный аспект. Некоторые из этих
достижений были включены в СПР.
Интерпретация, основанная на источнике знаний
ИЗ бесполезны в СПР, если знание, которое они кодируют, не может быть
представлено таким образом, который позволяет интерпретацию с помощью
машины. Например, специалисты по фонетики обычно используют Международный
Фонетический Алфавит для фонетической записи. Однако, так как выбор
представления воздействует на прикладную программу знания, системы
представления ИЗ в СПР часто являлись компромиссом между описательной
адекватностью и вычислительной эффективностью. Например, в ARPA проектируют
каждый СПР, используя идею синтаксического представления, чтобы не выражать
все грамматические возможности английского языка. Формальный язык и теория
автоматов предлагают эффективные алгоритмы для прикладной программы ИЗ,
выраженные в наборах правил с соответствующими формальными свойствами.
Например, минимально увеличенные контекстно - свободные записи для
адекватного описания английского синтаксиса и фонологии. Однако, успехи
этого вида не ведут автоматически в вычислительном отношении к ИЗ, так как
наборы правил, требуемые, чтобы выразить знание в этой форме могут быть
чрезвычайно большие. Кроме того, кажется маловероятно, что все ИЗ,
используемые в СПР могут быть выражены внутри таких ограниченных записей.
Тем не менее, более специализированные и мощные методы также были
разработаны, типа интерпретаторов для промышленных систем или увеличенные
сети переходов. Появляются некоторые экспертные оболочки системы,
являющееся многообещающими прикладными программами для акустическо -
фонетического преобразования. Чем лучше понимание специфической области,
тем больше возможность представления знания адекватно и эффективно. Кроме
того, вероятно, что различные схемы представления будут наиболее эффективны
для различных ИЗ; следовательно, структура СПР, которая навязывает,
одинаковую схему для всех ИЗ, типа HAERSAY-11 или HARPY, не идеальна.
На выбор представления воздействуют факторы, другие чем доступность
методики интерпретации для специфической схемы; например, несколько СПР не
пытаются отображать непосредственно между акустическом сигналом и
фонетическим алфавитом, но создавать промежуточные представления, отмечая
акустическо яркие особенности типа назальности, помогать процессу
распознавания фонем. На представления также воздействует порядок, в котором
расположены различные ИЗ, относящиеся к речевому сигналу и полной структуре
СПР. Недавно было предложено, чтобы начальный фонетический анализ отмечал
согласные, гласные, а также ударные и безударные слоги и что это простое
представление должно использоваться, чтобы получить набор слов-кандидатов
из соответственно организованного словаря. Детализированный фонетический
анализ затем применялся бы к безударному слогу(слогам), чтобы распознать
его между кандидатами.
Структура Системы
Большая часть литературы по СПР касается межкомпонентной связи во время
обработки. Эта проблема является основной, т.к. неоднозначности должны быть
решены быстро, чтобы избежать ненужного вычисления, и также потому, что
избыточность между ИЗ может использоваться, чтобы разложить на множители
неправильные гипотезы, вызванные или ошибками системы или подлинной
неоднозначностью в речевом сигнале. Например, акустическо - фонетический
компонент мог бы предложить аспирированный /p/ или /b/, за которым следует
гласные и /t/, результатом этого предположения могут стать такие слова-
кандидаты, как “put” и "but". Однако, вероятно, одно из них будет
отклонено на основе синтаксического анализа, так как глаголы и союзы не
играют одинаковую роль в предложении. Аналогично, подлинная синтаксическая
неоднозначность имеется в высказывании, типа " He gave her dog biscuits ",
где сочетание "her” может функционировать и как прилагательное и как
существительное. Но в этом случае неоднозначность может быть решена с
помощью ударения и интонации, которые будут сопровождать обе
интерпретации.
Предложенные структуры - иерархические, с последовательным потоком
информации через цепочку компонентов ИЗ, и неиерархические, без ограничения
на поток информации между компонентами.
Преимущество иерархического подхода в том, что имеется естественный
порядок для прикладной программы ИЗ, чтобы вводить речь; синтаксический
анализ может осуществляться только на основе лексической информации и т.д.
Кроме того, в целом управление системы просто. Однако, имеются много
случаев, когда непоследовательные взаимодействия между цепочкой компонентов
полезны; например, аспекты просодической, сверхсегментальной структуры
высказывания будут релевантны по отношению к фонологической,
синтаксической, семантической, и прагматической интерпретации.
Непоследовательное взаимодействие может быть достигнуто внутри
иерархической модели, передавая все возможные анализы, совместимые с
данным компонентом следующему, который затем выбирает подмножество
анализов. Но это только тогда сработает, если промежуточные представления,
переданные через СПР настолько обогащены, что можно было бы использовать
всю проанализированную информацию в следующих компонентах. Таким образом,
ввод синтаксического компонента в дополнение к синтаксической информации
относительно слов должен включить всю доступную информацию для
синтаксического анализа, типа просодической информации, и вся информация,
относящаяся семантическому/прагматическому анализу должна быть также
включена. Это усложняет схему представления, и дорого в вычислительном
отношении, т.к. создает много неправильных гипотез. Неправильных гипотез
можно избежать, т.к. информация, в которой отсутствует неоднозначность
временно доступна, она закодирована в той части речевого сигнала, который
уже проанализирован на более низких уровнях, но в иерархической модели этот
способ не применяется, пока ввод не достигает соответствующего компонента в
последовательной цепочке.
Неиерархические системы избегают неэффективности, позволяя компонентам
применять в наиболее эффективном порядке сложные межкомпонентные связи.
Каждый компонент нужно обеспечить средствами, чтобы запрашивать и получить
информацию из других компонентов или начинать определенную обработку в
другом компоненте. Это требует специальных каналов связи между
компонентами в системе. Разработка адекватной системы управления для такой
модели невозможна, т.к. должна предусматривать все возможные потоки
управления в стадии проекта. Практически, реальные неиерархические модели
для СПР были ограничены однородными представлениями из ИЗ и одиночной
глобальной структурой данных, как в (blackboard systems) рабочих системах.
Стратегии Обработки
Различные стратегии обработки использовались в разных структурах СПР, чтобы
сократить вычисление, требуемое для успешного анализа. И иерархические и
неиерархические системы могут работать со способами управления данными как
снизу-вверх, так и сверху-вниз при использовании знания, чтобы создать
гипотезы относительно ввода. Однако, самые современные СПР используют
способ снизу-вверх из-за довольно слабого предсказания речи на основе ИЗ.
Аналогично, СПР может исследовать пространство, определяя его глубину и
ширину. Большинство систем оперирует с шириной пространства из-за
сомнительного или ошибочного характера многих гипотез, но использует
подсчитывающие методы, чтобы сохранить размер активного исследуемого
пространства. Одна из таких методик, подсчитывающая неудачи, которая
включает измерение совокупности множества индивидуальных слов-кандидатов в
соотношении с теоретической верхней границей и обработку гипотезы,
гарантирует, что СПР найдет наиболее полную подсчитывающую гипотезу для
первого высказывания. Однако это не гарантирует, что наиболее
привлекательная гипотеза является правильной; эффективность компонентов,
которые способствуют порождению гипотез слова, все еще является
определяющим фактором в полном представлении системы. Этим оценкам должны
отвечать все компоненты, и они должны отражать различные добавления
каждого ИЗ. Однако, значение, которое должно быть присоединено к любому ИЗ,
должно измениться в соответствии с контекстом. Например, при распознавании
безударного и фонетически редуцированного предлога, синтаксический анализ
должен чаще обращаться к акустическому анализу, чем при распознавании
ударного слога. Кроме того, исследования должны быть оценены с помощью
времени. Хотя некоторые схемы оценки, которые использовались в готовых СПР,
улучшают эффективность, это связано или по теоретическим причинам, с
подсчитывающей методикой, например, подсчитывающей неудачи, или, потому что
они были разработаны на основе испытаний и ошибок и оценивались
исключительно по эффективности, связанной со временем выполнения, например
механизм фокуса внимания в рабочей системе HEARSAY-11.
Анализ речевого сигнала может проходить слева направо через линейный
сигнал или из середины островов большей акустической надежности в обоих
направлениях. Подход, использующий острова надежности, имеет преимущество
в принятии свободных от ошибок фонетических данных за начальную отметку за
счет более сложной структуры управления и организации системы, как в HWIM.
По-видимому слушатели обращают большее внимание на ударные слоги, которые
вообще более ясно произносятся, и следовательно более легко анализируются
фонетически. Кроме того, фонологическая структура английского словаря
вынуждена быть составленной таким способом, при котором каждое слово может
быть получено даже при грубом фонетическом анализе структуры слога вместе
с детальным анализом ударного слога. Следовательно, подход, использующий
острова надежности по существу правилен, хотя и был бы более эффективен,
если обработка началась в ударных слогах.
Текущие Тенденции
Начиная с проекта ARPA в 70-ых имел место период в исследовании речевого
понимания, скорее ориентированный на проблемы, чем на построение систем.
Многие из этих исследований сосредоточились на акустическо-фонетическом
преобразование в результате новых доказательств, показывающих
информационное богатство акустического сигнала. Сейчас же возобновлен
интерес к построению полных систем, включающий исследования, касающиеся
структуры системы. Однако, большинство развивающихся систем, основанных на
знаниях, ограничено скорее распознаванием непрерывной речи, чем пониманием.
Усовершенствования в акустическо-фонетическом анализе предполагают, чтобы
верхние уровни анализа не были определяющими для распознавания непрерывной
речи, вопреки преобладающему мнению во времена проекта ARPA. Но проблемы
понимания, такие как способы представление знаний, остаются нерешенным.
Системы
Главные СПР, разработанные в проекте ARPA, были HARPY, HWIM, HTEARSAY-11, и
SRI/SDC. HARPY оказался наиболее близким по критерию эффективности,
определенном для проекта. Однако, структура HARPY требовала составления
всего ИЗ в одну конечную сеть, так что язык, воспринимаемый системой был
более ограничен, чем в других системах. Система HEARSAY-11 была создана как
промышленная система. Несколько СПР были разработаны для Европейских
языков, таких как KEAL и MYRTILLE-11 для Французского языка и EVAR для
немецкого. Однако, эти системы не превзошли системы ARPA по эффективности
или проекту. Так же была создана автоматическая система бронирования места
на авиалинии, которая включает непрерывное понимание речи. Эта система,
разработанная в Лабораториях Bell, отвечает на телефон, чтобы установить
соответствующую бронь. Она использует метод сопоставления целового слова с
шаблоном, чтобы распознать слова из словаря, насчитывающего 127 слов.
Реферат на тему: Понятие алгоритма
Слово "Алгоритм" происходит от algorithmi - латинского написания имени аль-
Хорезми, под которым в средневековой Европе знали величайшего математика из
Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-
850 гг. В своей книге "Об индийском счете" он сформулировал правила записи
натуральных чисел с помощью арабских цифр и правила действий над ними
столбиком. В дальнейшем алгоритмом стали называть точное предписание,
определяющее последовательность действий, обеспечивающую получение
требуемого результата из исходных данных. Алгоритм может быть предназначен
для выполнения его человеком или автоматическим устройством. Создание
алгоритма, пусть даже самого простого, - процесс творческий. Он доступен
исключительно живым существам, а долгое время считалось, что только
человеку. Другое дело - реализация уже имеющегося алгоритма. Ее можно
поручить субъекту или объекту, который не обязан вникать в существо дела, а
возможно, и не способен его понять. Такой субъект или объект принято
называть формальным исполнителем. Примером формального исполнителя может
служить стиральная машина-автомат, которая неукоснительно исполняет
предписанные ей действия, даже если вы забыли положить в нее порошок.
Человек тоже может выступать в роли формального исполнителя, но в первую
очередь формальными исполнителями являются различные автоматические
устройства, и компьютер в том числе. Каждый алгоритм создается в расчете на
вполне конкретного исполнителя. Те действия, которые может совершать
исполнитель, называются его его допустимыми действиями. Совокупность
допустимых действий образует систему команд исполнителя. Алгоритм должен
содержать только те действия, которые допустимы для данного исполнителя.
Объекты, над которыми исполнитель может совершать действия, образуют так
называемую среду исполнителя. Для алгоритмов, встречающихся в математике,
средой того или иного исполнителя могут быть числа разной природы -
натуральные, действительные и т.п., буквы, буквенные выражения, уравнения,
тождества и т.п.
Данное выше определение алгоритма нельзя считать строгим - не вполне ясно,
что такое "точное предписание" или "последовательность действий,
обеспечивающая получение требуемого результата". Поэтому обычно формулируют
несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от
других инструкций.
Такими свойствами являются:
Дискретность (прерывность, раздельность) - алгоритм должен представлять
процесс решения задачи как последовательное выполнение простых (или ранее
определенных) шагов. Каждое действие, предусмотренное алгоритмом,
исполняется только после того, как закончилось исполнение предыдущего.
Определенность - каждое правило алгоритма должно быть четким, однозначным и
не оставлять места для произвола. Благодаря этому свойству выполнение
алгоритма носит механический характер и не требует никаких дополнительных
указаний или сведений о решаемой задаче.
Результативность (конечность) - алгоритм должен приводить к решению задачи
за конечное число шагов.
Массовость - алгоритм решения задачи разрабатывается в общем виде, то есть,
он должен быть применим для некоторого класса задач, различающихся только
исходными данными. При этом исходные данные могут выбираться из некоторой
области, которая называется областью применимости алгоритма.
На основании этих свойств иногда дается определение алгоритма, например:
“Алгоритм – это последовательность математических, логических или вместе
взятых операций, отличающихся детерменированностью, массовостью,
направленностью и приводящая к решению всех задач данного класса за
конечное число шагов.” Такая трактовка понятия “алгоритм” является неполной
и неточной. Во-первых, неверно связывать алгоритм с решением какой-либо
задачи. Алгоритм вообще может не решать никакой задачи. Во-вторых, понятие
“массовость” относится не к алгоритмам как к таковым, а к математическим
методам в целом. Решение поставленных практикой задач математическими
методами основано на абстрагировании – мы выделяем ряд существенных
признаков, характерных для некоторого круга явлений, и строим на основании
этих признаков математическую модель, отбрасывая несущественные признаки
каждого конкретного явления. В этом смысле любая математическая модель
обладает свойством массовости. Если в рамках построенной модели мы решаем
задачу и решение представляем в виде алгоритма, то решение будет “массовым”
благодаря природе математических методов, а не благодаря “массовости”
алгоритма.
Разъясняя понятие алгоритма, часто приводят примеры “бытовых алгоритмов”:
вскипятить воду, открыть дверь ключом, перейти улицу и т. д.. : рецепты
приготовления какого-либо лекарства или кулинарные рецепты являются
алгоритмами. Но для того, чтобы приготовить лекарство по рецепту,
необходимо знать фармакологию, а для приготовления блюда по кулинарному
рецепту нужно уметь варить. Между тем исполнение алгоритма – это бездумное,
автоматическое выполнение предписаний, которое в принципе не требует
никаких знаний. Если бы кулинарные рецепты представляли собой алгоритмы, то
у нас просто не было бы такой специальности – повар.
Правила выполнения арифметических операций или геометрических построений
представляют собой алгоритмы. При этом остается без ответа вопрос, чем же
отличается понятие алгоритма от таких понятий, как “метод”, “способ”,
“правило”. Можно даже встретить утверждение, что слова “алгоритм”,
“способ”, “правило” выражают одно и то же ( т.е. являются синонимами ),
хотя такое утверждение, очевидно, противоречит “свойствам алгоритма”.
Само выражение “свойства алгоритма” некорректно. Свойствами обладают
объективно существующие реальности. Можно говорить, например, о свойствах
какого-либо вещества. Алгоритм – искусственная конструкция, которую мы
сооружаем для достижения своих целей. Чтобы алгоритм выполнил свое
предназначение, его необходимо строить по определенным правилам. Поэтому
нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма,
или о требованиях, предъявляемых к алгоритму.
Первое правило – при построении алгоритма прежде всего необходимо задать
мно-жество объектов, с которыми будет работать алгоритм. Формализованное (
закодирован-ное ) представление этих объектов носит название данных.
Алгоритм приступает к работе с некоторым набором данных, которые называются
входными, и в результате своей рабо-ты выдает данные, которые называются
выходными. Таким образом, алгоритм пре-образует входные данные в выходные.
Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”.
Пока мы не имеем формализованных входных данных, мы не можем построить
алгоритм.
Второе правило – для работы алгоритма требуется память. В памяти
размещаются входные данные, с которыми алгоритм начинает работать,
промежуточные данные и выходные данные, которые являются результатом работы
алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек.
Поименованная ячейка памяти носит на-звание переменной. В теории алгоритмов
размеры памяти не ограничиваются, т. е. счита-ется, что мы можем
предоставить алгоритму любой необходимый для работы объем памяти.
В школьной “теории алгоритмов” эти два правила не рассматриваются. В то же
время практическая работа с алгоритмами ( программирование ) начинается
именно с реализации этих правил. В языках программирования распределение
памяти осуществляется декларативными операторами ( операторами описания
переменных ). В языке Бейсик не все переменные описываются, обычно
описываются только массивы. Но все равно при запуске программы транслятор
языка анализирует все идентификаторы в тексте программы и отводит память
под соответствующие переменные.
Третье правило – дискретность. Алгоритм строится из отдельных шагов
(действий, операций, команд). Множество шагов, из которых составлен
алгоритм, конечно.
Четвертое правило – детерменированность. После каждого шага необходимо
указывать, какой шаг выполняется следующим, либо давать команду остановки.
Пятое правило – сходимость ( результативность ). Алгоритм должен завершать
работу после конечного числа шагов. При этом необходимо указать, что
считать результатом работы алгоритма.
Итак, алгоритм – неопределяемое понятие теории алгоритмов. Алгоритм каждому
определенному набору входных данных ставит в соответствие некоторый набор
выходных данных, т. е. вычисляет ( реализует ) функцию. При рассмотрении
конкретных вопросов в теории алгоритмов всегда имеется в виду какая-то
конкретная модель алгоритма.
Любая работа на компьютере – это есть обработка информации. Работу
компьютера можно схематически изобразить следующим образом:
[pic]
“Информация” слева и “информация” справа – это разные информации. Компьютер
воспринимает информацию извне и в качестве результата своей работы выдает
новую информацию. Информация, с которой работает компьютер, носит название
“данные”.
Компьютер преобразует информацию по определенным правилам. Эти правила
(операции, команды ) заранее занесены в память компьютера. В совокупности
эти правила преобразования информации называются алгоритмом. Данные,
которые поступают в компьютер, называются входными данными. Результат
работы компьютера – выходные данные. Таким образом, алгоритм преобразует
входные данные в выходные:
[pic]
Теперь можно поставить вопрос: а может ли человек обрабатывать информацию ?
Конечно, может. В качестве примера можно привести обычный школьный урок:
учитель задает вопрос ( входные данные ), ученик отвечает ( выходные данные
). Самый простой пример: учитель дает задание – умножить 6 на 3 и результат
написать на доске. Здесь числа 6 и 3 – входные данные, операция умножения –
алгоритм, результат умножения – выходные данные:
[pic]
Вывод : решение математических задач – частный случай преобразования
информации. Компьютер ( по-английски означает вычислитель, на русском языке
– ЭВМ, электронная вычислительная машина ) был создан как раз для
выполнения математических расчетов.
Рассмотрим следующую задачу.
Длина класса 7 метров, ширина – 5 метров, высота – 3 метра. В классе 25
учеников. Сколько кв. м площади и сколько куб. м воздуха приходится на
одного ученика ?
Решение задачи:
1. Вычислить площадь класса :
7 х 5 = 35
2. Вычислить объем класса :
35 х 3 = 105
3. Вычислить, сколько квадратных метров площади приходится на одного
ученика :
35 : 25 = 1,4
4. Вычислить, сколько куб. метров воздуха приходится на одного ученика :
105 : 25 = 4,2
Ответ : на одного ученика приходится 1,4 кв. метров площади и 4,2 куб.
метров воздуха.
Если теперь убрать вычисления и оставить только “действия”, то получим
алгоритм – перечень операций, которые необходимо выполнить, чтобы решить
данную задачу.
Получается, что при решении любой математической задачи мы составляем
алгоритм решения. Но прежде мы сами и выполняли этот алгоритм, то есть
доводили решение до ответа. Теперь же мы будем только писать, что нужно
сделать, но вычисления проводит не будем. Вычислять будет компьютер. Наш
алгоритм будет представлять собой набор указаний ( команд ) компьютеру.
Когда мы вычисляем какую-либо величину, мы записываем результат на бумаге.
Компьютер записывает результат своей работы в память в виде переменной.
Поэтому каждая команда алгоритма должна включать указание, в какую
переменную записывается результат. Алгоритм решения нашей задачи будет
выглядеть так :
1. Вычислить площадь класса и записать в переменную S.
2. Вычислить объем класса и записать в переменную V.
3. Вычислить, сколько квадратных метров площади приходится на одного
ученика и записать в переменную S1.
4. Вычислить, сколько куб. метров воздуха приходится на одного ученика и
записать в переменную V1.
5. Вывести на экран значения переменных S1 и V1.
Теперь остается только перевести команды алгоритма с русского языка на
язык, понятный компьютеру, и получится программа. Программирование – это
есть перевод алгоритма с “человеческого” языка на “компьютерный” язык.
Трактовка работы алгоритма как преобразования входных данных в выходные
естественным образом подводит нас к рассмотрению понятия “постановка
задачи”. Для того, чтобы составить алгоритм решения задачи, необходимо из
условия выделить те величины, которые будут входными данными и четко
сформулировать, какие именно величины требуется найти. Другими словами,
условие задачи требуется сформулировать в виде “Дано ... Требуется” – это и
есть постановка задачи.
Алгоритм применительно к вычислительной машине – точное предписание,
т.е. набор операций и правил их чередования, при помощи которого, начиная с
некоторых исходных данных, можно решить любую задачу фиксированного типа.
Виды алгоритмов как логико-математических средств отражают указанные
компоненты человеческой деятельности и тенденции, а сами алгоритмы в
зависимости от цели, начальных условий задачи, путей ее решения,
определения действий исполнителя подразделяются следующим образом:
. Механические алгоритмы, или иначе детерминированные, жесткие (например
алгоритм работы машины, двигателя и т.п.);
. Гибкие алгоритмы, например стохастические, т.е. вероятностные и
эвристические.
Механический алгоритм задает определенные действия, обозначая их в
единственной и достоверной последовательности, обеспечивая тем самым
однозначный требуемый или искомый результат, если выполняются те условия
процесса, задачи, для которых разработан алгоритм.
Вероятностный (стохастический) алгоритм дает программу решения задачи
несколькими путями или способами, приводящими к вероятному достижению
результата.
Эвристический алгоритм (от греческого слова “эврика”) – это такой
алгоритм, в котором достижение конечного результата программы действий
однозначно не предопределено, так же как не обозначена вся
последовательность действий, не выявлены все действия исполнителя. К
эвристическим алгоритмам относят, например, инструкции и предписания. В
этих алгоритмах используются универсальные логические процедуры и способы
принятия решений, основанные на аналогиях, ассоцияциях и прошлом опыте
решения схожих задач.
Линейный алгоритм – набор команд (указаний), выполняемых последовательно во
времени друг за другом.
Разветвляющийся алгоритм – алгоритм, содержащий хотя бы одно условие, в
результате проверки которого ЭВМ обеспечивает переход на один из двух
возможных шагов.
Циклический алгоритм – алгоритм, предусматривающий многократное повторение
одного и того же действия (одних и тех же операций) над новыми исходными
данными. К циклическим алгоритмам сводится большинство методов вычислений,
перебора вариантов.
Цикл программы – последовательность команд (серия, тело цикла), которая
может выполняться многократно (для новых исходных данных) до удовлетворения
некоторого условия.
На рисунке продемонстрированы в условных обозначениях схемы основных
конструкций алгоритмов:
а). линейного алгоритма;
б,в,г). разветвляющихся алгоритмов (б-ответвление, в-раздвоение, г-
переключение);
д,е,ж). циклических алгоритмов (д,ж-проверка в начале цикла, е-проверка в
конце цикла).
Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее
разработанный и целиком используемый при алгоритмизации конкретной задачи.
В некоторых случаях при наличии одинаковых последовательностей указаний
(команд) для различных данных с целью сокращения записи также выделяют
вспомогательный алгоритм.
На всех этапах подготовки к алгоритмизации задачи широко используется
структурное представление алгоритма.
Структурная (блок-, граф-) схема алгоритма – графическое изображение
алгоритма в виде схемы связанных между собой с помощью стрелок (линий
перехода) блоков – графических символов, каждый из которых соответствует
одному шагу алгоритма. Внутри блока дается описание соответствующего
действия.
Графическое изображение алгоритма широко используется перед
программированием задачи вследствие его наглядности, т.к. зрительное
восприятие обычно облегчает процесс написания программы, ее корректировки
при возможных ошибках, осмысливание процесса обработки информации.
Можно встретить даже такое утверждение: “Внешне алгоритм представляет собой
схему – набор прямоугольников и других символов, внутри которых
записывается, что вычисляется, что вводится в машину и что выдается на
печать и другие средства отображения информации “. Здесь форма
представления алгоритма смешивается с самим алгоритмом.
Принцип программирования “сверху вниз” требует, чтобы блок-схема поэтапно
конкретизировалась и каждый блок “расписывался” до элементарных операций.
Но такой подход можно осуществить при решении несложных задач. При решении
сколько-нибудь серьезной задачи блок-схема “расползется” до такой степени,
что ее невозможно будет охватить одним взглядом.
Блок-схемы алгоритмов удобно использовать для объяснения работы уже
готового алгоритма, при этом в качестве блоков берутся действительно блоки
алгоритма, работа которых не требует пояснений. Блок-схема алгоритма должна
служить для упрощения изображения алгоритма, а не для усложнения.
При решении задач на компьютере необходимо не столько умение составлять
алгоритмы, сколько знание методов решения задач ( как и вообще в математике
) . Поэтому изучать нужно не программирование как таковое ( и не
алгоритмизацию ), а методы решения математических задач на компьютере.
Задачи следует классифицировать не по типам данных, как это обычно делается
(задачи на массивы, на символьные переменные и т. д. ), а по разделу
“Требуется”.
В информатике процесс решения задачи распределяется между двумя субъектами
: программистом и компьютером. Программист составляет алгоритм ( программу
), компьютер его исполняет. В традиционной математике такого разделения нет
, задачу решает один человек, который составляет алгоритм решения задачи и
сам выполняет его. Сущность алгоритмизации не в том, что решение задачи
представляется в виде набора элементарных операций, а в том, что процесс
решения задачи разбивается на два этапа : творческий ( программирование ) и
не творческий ( выполнение программы ). И выполняют эти этапы разные
субъекты – программист и исполнитель
В учебниках по информатике обычно пишут, что исполнителем алгоритма может
быть и человек. На самом деле алгоритмы для людей никто не составляет ( не
будем забывать, что не всякий набор дискретных операций является алгоритмом
). Человек в принципе не может действовать по алгоритму. Выполнение
алгоритма – это автоматическое, бездумное выполнение операций. Человек
всегда действует осмысленно. Для того, чтобы человек мог выполнять какой-то
набор операций, ему нужно объяснить, как это делается. Любую работу человек
сможет выполнять только тогда, когда он понимает, как она выполняется.
Вот в этом – “ объяснение и понимание” – и кроется различие между понятиями
“алгоритм” и “способ”, “метод”, “правило”. Правила выполнения
арифметических операций – это именно правила ( или способы ), а не
алгоритмы. Конечно, эти правила можно изложить в виде алгоритмов, но толку
от этого не будет. Для того, чтобы человек смог считать по правилам
арифметики, его нужно научить. А если есть процесс обучения, значит, мы
имеем дело не с алгоритмом, а с методом.
При составлении алгоритма программист никому ничего не объясняет, а
исполнитель не пытается ничего понять. Алгоритм размещается в памяти
компьютера, который извлекает команды по одной и исполняет их. Человек
действует по другому. Чтобы решить задачу, человеку требуется держать в
памяти метод решения задачи в целом, а воплощает этот метод каждый по-
своему.
Очень ярко эта особенность человеческой психологии – неалгоритмичность
мышления – проявилась в методичесом пособии А. Г. Гейна и В. Ф. Шолоховича.
В пособии излагаются решения задач из известного учебника. Решения задач
должны быть представлены в виде алгоритмов. Однако авторы пособия понимают,
что если просто написать алгоритм решения задачи, то разобраться в самом
решении будет трудно. Поэтому они сначала приводят “нечеткое изложение
алгоритма” ( т. е. объясняют решение задачи ), а затем пишут сам алгоритм.
Л И Т Е Р А Т У Р А
1. Нестеренко А. В. ЭВМ и профессия программиста.
М., Просвещение, 1990.
2. Брудно А. Л., Каплан Л. И. Московские олимпиады по программированию.
М., Наука, 1990.
3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для
инженера.
М., Энергоатомиздат, 1988.
4. Гейн А.Г. и др.. Основы информатики и вычислительной техники.
М., Просвещение, 1994.
5. Информатика. Еженедельное приложение к газете “Первое сентября”. 1998, №
1.
6. Радченко Н. П. Ответы на вопросы выпускных экзаменов. – Инфоматика и
образование, 1997, №4.
7. Касаткин В.Н. Информация, алгоритмы, ЭВМ. М., Просвещение, 1991.
8. Каныгин Ю. М., Зотов Б. И. Что такое информатика ?
М., Детская литература, 1989.
9. Гейн А. Г., Шолохович В.Ф. Преподавание курса “Основы информатики и
вычислительной техники” в средней школе. Руководство для учителя.
Екатеринбург, 1992.
10. Извозчиков В.А. Информатика в понятиях и терминах.
11. Газета «Информатика», №35, 1997г.
12. Л.З. Шауцуков Основы информатики в вопросах и ответах.
| |
