10 Алгоритмических задач. Однако для алгоритмов

Алгоритмы действительно существуют уже несколько столетий, поэтому вы могли бы подумать, что ученые могли бы найти и решить каждый алгоритм к настоящему времени. К сожалению, обратное верно. Решение определенного алгоритма часто представляет собой еще несколько вопросов, которые алгоритм не решает, и это не показалось очевидным до тех пор, пока кто-то не придумает решение.

Алгоритмы - это серия шагов, используемых для решения проблемы, и вы не должны путать их с другими объектами, такими как уравнения. Алгоритм никогда не является решением проблемы поиска. Никто не создал бы ряд шагов для решения проблемы, которая еще не существует (или может никогда не существовать).

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

Работа с текстовыми поисками

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

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

Дифференцирование слов

При работе с символами компьютер видит числа, а не буквы. Цифры на самом деле всего лишь серия 0s и 1s для компьютера и на самом деле не имеют никакого значения. Объединение символов в строки просто делает серию из 0s и 1s длиннее. Следовательно, сравнивая две строки, что-то, что человек может сделать с первого взгляда, может занять время в компьютере, и путаница, вероятно, существует между конъюгатами. Например, если вы не будете осторожны при построении алгоритма, компьютер может запутать записаться и прослушать. Что еще более важно, компьютеру потребуется время, чтобы различить разницу между ними. Проблема разделительных слов стремится найти наименьший (и самый быстрый) возможный алгоритм (детерминированный конечный автомат, DFN, в данном случае) для выполнения разделения слов.Цель состоит в том, чтобы принять одно слово и отвергнуть другое, учитывая два слова определенной длины.

Определение завершения приложения

Одна из проблем, предложенных Аланом Тьюрингом в 1936 году, заключается в том, может ли алгоритм, описывающий описание программы и ввода, определить, будет ли программа в конечном итоге останавливаться (проблема с остановкой). При работе с простым приложением во многих случаях легко определить, остановится ли программа или продолжит работу в бесконечном цикле. Однако, по мере увеличения сложности программы, определение результата запуска программы с любым заданным вводом становится сложнее. Машина Тьюринга не может сделать это определение; в результате получается баггированный код с бесконечными циклами. Никакое количество тестов, использующих текущую технологию, не может решить эту проблему.

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

Создание и использование односторонних функций

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

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

Умножение действительно больших чисел

Во многих местах существуют большие числа. Например, рассмотрите возможность выполнения расчетов с расстояниями до Марса или, возможно, с Плутоном. В настоящее время существуют методы для умножения на действительно большие числа, но они, как правило, медленны, потому что им требуется выполнить несколько операций. Проблема возникает, когда числа слишком велики, чтобы вписываться в регистры процессора. В этот момент умножение должно происходить более чем на один шаг, что значительно замедляет работу. Текущие решения включают в себя:

• Комплексный алгоритм умножения Гаусса
• Умножение Карацубы
• Toom-Cook
• Методы преобразования Фурье

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

Разделение ресурса в равной степени

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

Два решения уже существуют для проблемы зависания пирога без зависания с определенным количеством людей, но не существует общего решения. Когда задействованы два человека, первый разрезает торт, а второй выбирает первую часть. Таким образом, обе стороны уверены в равном разделении. Проблема становится сложнее с тремя людьми, но вы можете попробовать решение Selfridge-Conway для решения этой проблемы. Однако, после того, как вы доберетесь до четырех человек, решения не существует.

Сокращение времени вычисления расстояния редактирования

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

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

Устранение проблем быстро

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

Этот вопрос изначально обсуждался в 1950-х годах Джоном Нэшем в письмах в Агентство национальной безопасности (NSA) и снова в письмах между Курт Геделем и Джоном фон Нейманом. Помимо машинного обучения (и AI в целом), эта проблема связана с многими другими областями, включая математику, криптографию, исследование алгоритмов, теорию игр, обработку мультимедиа, философию и экономику.

Игра в паритетную игру

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

Понимание пространственных проблем

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

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

Математики, такие как Сэм Лойд, часто используют головоломки, чтобы продемонстрировать сложные математические проблемы, некоторые из которых сегодня не имеют решения. Посещать эти сайты весело, потому что вы не только получаете бесплатные развлечения, но и пищу для размышлений. Проблемы, которые возникают у этих головоломок, имеют практические приложения, но они представлены в интересной форме.