Гради Буч - Объектно-ориентированный анализ и проектирование с примерами приложений на С++ (1158635), страница 81
Текст из файла (страница 81)
Подумайте, например, каквы планируете маршрут поездки по городу, чтобы выполнить массу дел. В плохоосвещенном помещении вам удается распознавать границы предметов и избегатьстолкновений. Вы можете сосредоточиться на беседе с одним собеседником нашумной вечеринке, где много людей говорит одновременно. Ни одна из этих задач неимеет четкого алгоритмического решения. Планирование маршрута относится к классупр-полных задач. Передвижение в темноте подразумевает принятие решения наоснове неполной и нечеткой зрительной информации.
Выделение речи одногочеловека из множества разговоров требует умения улавливать полезную информациюв шуме и отфильтровать нужные сообщения из общей какофонии.Эти и подобные им проблемы привлекают внимание исследователей в областиискусственного интеллекта, которые стремятся улучшить наши представления о разумечеловека.
В частности, создаются интеллектуальные системы, которые подражаютнекоторым аспектам поведения человека. Ерман, Ларк и Хайес-Рот указывали, что"интеллектуальные системы отличаются от традиционных рядом признаков (не все изних обяэательны):• способностью достигать целей, меняющихся во времени;• способностью усваивать, использовать и преобразовывать знания;• способностью оперировать с разнообразными подсистемами, варьируя используемыеметоды;• интеллектуальным взаимодействием с пользователями и другими системами;• самостоятельным распределением ресурсов и концентрацией внимания" [1 ].Реализация в системе хотя бы одного из этих требований уже является непростойзадачей.
Еще сложнее сделать интеллектуальную систему для использования внекоторых специфических прикладных областях, например, в медицинской диагностикеи диспетчеризации авиарейсов: такие системы должны, как минимум, не причинятьвреда, а искусственный интеллект практически ничего не знает о здравом смысле.Успехи энтузиастов в этой области несколько преувеличены; но, тем не менее,искусственный интеллект дал немало хороших практических идей, в частностипредставление знаний, концепция информационной доски и экспертные системы [2]. Вданной главе рассматриваются подходы к созданию интеллектуальной системырасшифровки криптограмм на основе метода информационной доски, в достаточнойстепени моделирующего человеческий способ решения задачи.
Как мы увидим, методыобъектно-ориентированного проектирования очень хорошо работают в этой области.11.1. АнализОпределение границ предметной областиКак сказано во врезке, мы намерены заняться криптоанализом процессом преобразования зашифрованного текста в обычный. В общемслучае процесс дешифровки является чрезвычайно сложным и не поддаетсядаже самым мощным научным методам. Существует, например, стандартшифрования DES (Data Encryption Standard, алгоритм шифрования с закрытымключом, в котором используются многочисленные подстановки иперестановки), который, по-видимому, свободен от слабых мест и устойчив ковсем известным методам взлома.
Но наша задача значительно проще,поскольку мы ограничимся шифрами с одной подстановкой.В качестве первого шага анализа попробуйте решить (только честно,не заглядывая вперед!) следующую криптограмму записывая, каждый вашшаг:Q AZWS DSSC KAS DXZNN DASNNПодсказка: буква w соответствует букве v исходного текста. Переборвсех возможных вариантов совершенно лишен смысла. Предполагая, чтоалфавит содержит 26 прописных английских букв, получим 26! (около4.03х1026) возможных комбинаций. Следовательно, нужно искать другойметод решения, например, использовать знания о структуре слов ипредложений и делать правдоподобные допущения. Как только мы исчерпаемявные решения, мы сделаем наиболее вероятное предположение и будемпродвигаться дальше.
Если обнаружится, что предположение приводит кпротиворечию или заводит в тупик, мы вернемся назад и сделаем другуюпопытку.Вот наше решение, шаг за шагом:1. Используя подсказку, заменим w на v.Требования к системе криптоанализаКриптография "изучает методы сокрытия данных от посторонних" [З].Криптографические алгоритмы преобразовывают сообщения (исходный текст)в зашифрованный текст (криптограмму) и наоборот.Одним из наиболее общеупотребительных (еще со времен ДревнегоРима) криптографических алгоритмов является подстановка.
Каждая буква валфавите исходного текста заменяется другой буквой. Например, можноциклически сдвинуть все буквы алфавита: буква А заменяется на B, B на C, a Zна А. Тогда следующий исходный текст:CLOS is an object-oriented programming languageпревращается в криптограмму:DMPT jt bo pckfdu-psjfoufe qsphsbnnjoh mbohvbhfЧаще всего замена делается менее тривиальным образом.
Например, Азаменяется на G, B на J и т. д. Рассмотрим следующую криптограмму:PDG TBCER CQ ТСК AL S NGELCH QZBBR SBAJGПодсказка: буква C в этой криптограмме соответствует букве Oисходного текста.Существенно упрощает задачу предположение о том, что дляшифрования текста использован алгоритм подстановки, поскольку в общемслучае процесс дешифровки не будет столь тривиальным.
В процессерасшифровки приходится использовать метод проб и ошибок, когда мыделаем предположение о замене и рассматриваем его следствия. Удобно,например, начать расшифровку с предположения о том, что одно- идвухбуквенные слова в криптограмме соответствуют наиболееупотребительным словам английского языка (I, a, or, it, in, of. on).Подставляя эти предполагаемые буквы в другие слова, мы можем догадаться овероятном значении других букв. Например, если трехбуквенное словоначинается с литеры O, то это могут быть слова one,our, off.Знание фонетики и грамматики также может способствоватьдешифровке. Например, следование подряд двух одинаковых литер с оченьмалой вероятностью может означать qq.
Наличие в окончании слова буквы gпозволяет сделать предположение о наличии суффикса ing. На еще болеевысоком уровне абстракции логично предположить, что словосочетание itia более вероятно, чем if is. Необходимо учитывать и структурупредложения: существительные и глаголы. Если выясняется, что впредложении есть глагол, но нет существительного, которое с ним связано, тонужно отвергнуть сделанные ранее предположения н начать поиск заново.Иногда приходится возвращаться назад, если сделанноепредположение вступает в противоречие с другими предположениями.Например, мы допустили, что некоторое двухбуквенное слово соответствуетсочетанию or, что в дальнейшем привело к противоречию.
В этом случае мыдолжны вернуться назад и попытаться использовать другой вариантрасшифровки этого слова, например, on.Требования к нашей системе: по данной криптограмме, впредположении, что использована простая подстановка, найти этуподстановку и (главное) восстановить исходный текст.Q AZVS DSSC KAS DXZNN DASNN2. Первое слово из одной буквы, вероятна, А или I; предположим, чтоэто А:A AZVS DSEC KAS DXZNN DASNN3. В третьем слове должны быть гласные звуки и вероятно, что этодвойные буквы.
Это не могут быть UU или II, а также АА (буква А ужеиспользована). Попробуем вариант ЕЕ.A AZVE DEEC КАЕ DXZNN DAENN4. Четвертое слово состоит из трех букв и оканчивается на Е, это оченьпохоже на слово THE.A HZVE DEEC THE DXZNN DHENN5. Во втором слове нужна гласная, и здесь подходят только I, O, U(буква А уже использована). Только вариант с буквой I дает осмысленноеслово.A HIVE DEEC THE DXINN DHENN6. Можно найти несколько слов с двойной буквой E из четырех букв(DEER, BEER, SEEN). Грамматика требует, чтобы третье слово было глаголом,поэтому остановимся на SEEN.A HIVE SEEN THE SXINN SHENN7.
Смысл в полученном предложении отсутствует, поскольку улей(HIVE) не может видеть (SEEN), значит, где-то по дороге мы сделали ошибку.Похоже, что выбор гласной буквы во втором слове был неверен, и приходитсявернуться назад, отменив самое первое предположение - первым словомдолжно быть I. Повторяя все остальные наши рассуждения практически безизменений мы получаем:I HAVE SEEN THE SXANN SHENN8.
Посмотрим на два последних слова. Двойная буква S в конце не даетосмысленного значения и к тому же уже использована ранее, а вот LL даетосмысленное слово.I HAVE SEEN THE SXALL SHELL9. Из грамматических соображений очевидно, что оставшееся слово прилагательное. Анализируя шаблон S?ALL, находим SMALL.I HAVE SEEN THE SMALL SHELLТаким образом, решение найдено. Анализируя процесс решения, мыможем сделать три наблюдения:•Для решения применялись разнообразные знания: о грамматике, осоставе слов, о чередовании согласных и гласных.•Сделанные предположения регистрировались, потом мы применяли кним имеющиеся у нас знания и смотрели, что из этого получается.•Мы подходили к делу наугад, приспосабливаясь к обстановке.
Иногдаделались выводы от общего к частному (словом из трех букв,оканчивающимся на Е будет, вероятно, THE), а иногда от частногок общему (?ЕЕ? может соответствовать DEER, BEER, SEEN, ноглаголом из них является только SEEN).Изложенный подход известен как метод информационной доски. Онвпервые был предложен Ньюэллом в 1962 году, а позднее был использованРедди и Ерманом в проектах Hearsay и Hearsay II по распознаванию речи [4].Эффективность метода подтвердилась, и он был использован в другихобластях, включая интерпретацию сигналов, трехмерное моделированиемолекулярных структур, распознавание образов и планирование [5].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
