Алгоритм (значения)

Алгори́тм — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.

Сжа́тие да́нных — алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы — упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных.

P (латиница), Р (кириллица) — многозначный термин. Может означать:

• P — шестнадцатая буква латинского алфавита.
• Р — буква кириллицы.

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

Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах, а под размером выхода — длина описания решения задачи.

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

LZ77 и LZ78 — алгоритмы сжатия без потерь, опубликованные в статьях израильских математиков Авраама Лемпеля и Яакова Зива в 1977 и 1978 годах. Эти алгоритмы — наиболее известные варианты в семействе LZ*, которое включает в себя также LZW, LZSS, LZMA и другие алгоритмы.

Группа экспертов в области фотографии в дополнение к известным форматам сжатия изображений JPEG и JPEG 2000, ориентированным прежде всего на сжатие с потерями, предложила также стандарт на сжатие без потерь — JPEG-LS.

nofollow — значение атрибута rel тега <a> языка гипертекстовой разметки веб-страниц HTML (rel="nofollow"). Значение предназначено для поисковых систем: оно указывает их роботам, что гиперссылку не нужно сканировать. Таким же образом на практике помечаются рекламные ссылки, а для поисковых систем Google и Яндекс ссылки с данным атрибутом не передают PR и ТиЦ соответственно.

Хронология событий, связанных с теорией информации, сжатием данных, кодами коррекции ошибок и смежных дисциплин:

• 1872  — Людвиг Больцман представляет свою H-теорему, а вместе с этим формулу Σp_i log p_i для энтропии одной частицы газа.
• 1878  — Джозайя Уиллард Гиббс, определяет энтропию Гиббса: вероятности в формуле энтропии теперь взяты как вероятности состояния целой системы.
• 1924  — Гарри Найквист рассуждает о квантификации «Интеллекта» и скорости, на которой это может быть передано системой коммуникации.
• 1927  — Джон фон Нейман определяет фон Неймановскую энтропию, расширяя Гиббсовскую энтропию в квантовой механике.
• 1928  — Ральф Хартли представляет формулу Хартли как логарифм числа возможных сообщений, с информацией, передаваемой, когда приёмник может отличить одну последовательность символов от любой другой.
• 1929  — Лео Силард анализирует демона Максвелла, показывают, как двигатель Szilard может иногда преобразовывать информацию в извлечение полезной работы.
• 1940  — Алан Тьюринг представляет deciban как единицу измерения информации в немецкой машине Энигма с настройками, зашифрованными процессом Banburismus.
• 1944  — теория информации Клода Шеннона в основном завершена.
• 1947  — Ричард Хемминг изобретает Код Хемминга для обнаружения ошибок и их исправления, но не публикует их до 1950 года.
• 1948  — Клод Шеннон публикует Математическую теорию связи
• 1949  — Клод Шеннон публикует Передачу Информации в виде шумов, в которой описаны Теорема отсчётов и Теорема Шеннона — Хартли.
• 1949  — Рассекречена Теория связи в секретных системах Клода Шеннона.
• 1949  — Роберт Фано опубликовал отчет, в котором независимо от Клода Шеннона описан Алгоритм Шеннона — Фано.
• 1949  — опубликовано Неравенство Крафта — Макмиллана.
• 1949  — Марсель Голей вводит коды Голея для исправления ошибок методом упреждения.
• 1950  — Ричард Хемминг публикует коды Хемминга для исправления ошибок методом упреждения.
• 1951  — Соломон Кульбак и Ричард Лейблер вводят понятие расстояния Кульбака-Лейблера.
• 1951  — Дэвид Хаффман изобретает кодирование Хаффмана, метод нахождения оптимальных префиксных кодов для сжатия данных без потерь.
• 1953  — опубликован Sardinas–Patterson algorithm.
• 1954  — Ирвинг Рид и Дэвид E. Мюллер вводит коды Рида-Мюллера.
• 1955  — Питер Элиас вводит свёрточные коды.
• 1957  — Юджин Прандж первый обсуждает циклический избыточный код.
• 1959  — Алексис Хоквингем, и самостоятельно в следующем году Радж Чандра Боуз и Двайджендра Камар Рей-Чоудхури, представляют коды Боуза-Чоудхури-Хоквингема (БЧХ-коды).
• 1960  — Ирвинг Рид и Густав Соломон вводят коды Рида-Соломона.
• 1962  — Роберт Галлагер предлагает код с малой плотностью проверок на чётность; их не использовали в течение 30 лет из-за технических ограничений.
• 1966  — опубликована статья Дэвида Форнея Concatenated error correction code.
• 1967  — Эндрю Витерби открывает алгоритм Витерби, делающий возможным декодирование свёрточных кодов.
• 1968  — Элвин Берлекэмп изобретает алгоритм Берлекэмпа — Мэсси; его применение к расшифровке БЧХ-кодов и кода Рида-Соломона, указанный Джеймсом Мэсси в последующем году.
• 1968  — Крис Уоллис и Дэвид М. Бутон издают первый из многих докладов о Сообщениях минимальной длины (СМД) — их статистический и индуктивный вывод.
• 1972  — опубликована статья о Justesen code.
• 1973  — Дэвид Слепиан и Джек Волф открывают и доказывают Код Слепиана-Вольфа, кодирующего пределы распределённого источника кодирования.
• 1976  — Готфрид Унгербоэк публикует первую статью о Треллис-модуляции.
• 1976  — Йорма Риссанен разрабатывает и позднее патентует арифметическое кодирование для IBM.
• 1977  — Абрахам Лемпель и Яаков Зив разрабатывают алгоритм сжатия Лемпеля-Зива (LZ77)
• 1982  — Готфрид Унгербоэк публикует более подробное описание Треллис-модуляции, что приводит к увеличению скорости аналогового модема старой обычной телефонной службы от 9.6 кбит/сек до 36 кбит/сек.
• 1989  — Фил Кац создаёт .zip формат, включая формат сжатия DEFLATE ; позже это становится наиболее широко используемым алгоритмом сжатия без потерь.
• 1993  — Клод Берроу, Алэйн Главиукс и Punya Thitimajshima вводят понятие Турбо-кодов.
• 1994  — Майкл Барроуз и Дэвид Уилер публикуют теорию преобразования Барроуза-Уилера, которая далее найдет своё применение в bzip2.
• 1995  — Benjamin Schumacher предложил термин Кубит.
• 1998  — предложен Fountain code.
• 2001  — описан алгоритм Statistical Lempel–Ziv.
• 2008  — Erdal Arıkan предложил Полярные коды.

A8 — алгоритм формирования ключа шифрования, который впоследствии используется для обеспечения конфиденциальности передаваемой по радиоканалу информации в стандарте мобильной сотовой связи GSM. A8 является одним из алгоритмов обеспечения секретности разговора в GSM вместе с A5 и A3. Его задача — генерация сеансового ключа Kc для потокового шифрования информации в канале связи между сотовым телефоном и базовой станцией после аутентификации. По причине безопасности формирование Kc происходит в Sim-карте.

АГС — фильтр поисковой системы «Яндекс», призванный минимизировать фактор постороннего влияния на результат поисковой выдачи. С помощью данного алгоритма «Яндекс» заносит сайты в черный список. Со временем фильтр усовершенствовался, получая названия АГС-17, АГС-30, АГС-40, и АГС-2015.

LZSS — алгоритм сжатия данных без потерь, производный от метода LZ77. Создан в 1982 году Джеймс Сторером и Томасом Шиманским. LZSS был описан в статье «Data compression via textual substitution», опубликованной в журнале АСМ.