По закону Мура плотность транзисторов на микросхеме удваивается каждые 24 месяца. Производительность CPU, GPU, TPU и NPU растёт уже несколько десятилетий, что привело нас вплотную к задачам эмуляции мозга и Сверхинтеллекта.
Рубрика «теория алгоритмов»
Сложные вычисления — в минимальном объёме памяти
2026-03-18 в 7:01, admin, рубрики: MicroQuickJS, ruvds_статьи, временная сложность, вычислительная сложность, закон Мура, ожирение софта, пространственная сложность, симуляция времени, теория алгоритмовПонятия способ, случай, действие и его свобода, причина, измерение, предположение и его верность, игра, поведение и ум
2026-03-10 в 7:04, admin, рубрики: математика, математическая статистика, ошибки, словарь, теория алгоритмов, теория вероятностей, теория игр, философия, философия программирования, философия разумаРадченко Андрей Леонидович, примеры https://goo.su/dF5r
Есть проблемы гораздо сложнее, чем NP-Complete
2023-06-06 в 8:01, admin, рубрики: crypto, np, np-complete, np-hard, NP-полная задача, p=np, PSPACE, timeweb_статьи, Алгоритмы, Блог компании Timeweb Cloud, задача тысячелетия, информационная безопасность, класс NP, классы сложности, криптография, математика, машина Тьюринга, теоретическая информатика, теория алгоритмов, теория вычислимости
Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.
В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать полностью »
Неожиданная полнота по Тьюрингу повсюду
2018-11-12 в 13:06, admin, рубрики: FRACTRAN, вычислительная сложность, делегация доверия, ИИ, информационная безопасность, искусственный интеллект, Компьютерное железо, Настольные компьютеры, полнота по Тьюрингу, Процессоры, странные машины, теория алгоритмов, тьюринг-полные системыКаталог программных конструкций, языков и API, которые неожиданно являются полными по Тьюрингу; последствия этого для безопасности и надёжности. Приложение: сколько компьютеров в вашем компьютере?
Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp. — Десятое правило Гринспена
Полнота по Тьюрингу (Turing-completeness, TC) — это свойство системы при некотором простом представлении ввода и вывода реализовать любую вычислимую функцию.
Тьюринг-полнота — фундаментальное понятие в информатике. Она помогает ответить на многие ключевые вопросы, например, почему невозможно создание идеальной антивирусной программы. Но в то же время она является поразительно распространённым явлением. Казалось бы, компьютерной системе трудно достичь такой универсальности, чтобы выполнять любую программу, но получается наоборот: трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему. Это может быть забавным, полезным (хотя обычно нет), вредным или чрезвычайно небезопасным и настоящим подарком для хакера (см. о «теоретико-языковой безопасности», которая изучает методы взлома «странных машин»1). Удивительные примеры такого поведения напоминают нам о том, что полнота по Тьюрингу таится повсюду, а защитить систему чрезвычайно сложно.
Читать полностью »
Мысль — материальна: Алан Тьюринг как «универсальный вычислитель»
2016-06-28 в 6:03, admin, рубрики: автоматы, Алгоритмы, искусственный интеллект, криптография, математика, машина Тьюринга, Программирование, теория алгоритмов
Источник: geektimes.ru
В первой половине XX века, когда были изобретены первые вычислительные машины. Однако наряду с физически осязаемыми машинами появлялись и машины-концепции. Одной из них была «машина Тьюринга» — абстрактное вычислительное устройство, придуманное в 1936 году Аланом Тьюрингом — учёным, которого считают одним из основоположников информатики.
Его кругозор распространялся от квантовой теории и принципа относительности до психологии и неврологии. А в качестве способа познания и передачи своих знаний Тьюринг использовал аппарат математики и логики. Он находил решения, казалось бы, нерешаемых задач, но был сильнее всего увлечен идеей «Универсальной машины», способной вычислить всё, что в принципе вычислимо.Читать полностью »
Теорема Клини о неподвижной точке: квайны
2013-08-13 в 23:13, admin, рубрики: Алгоритмы, квайн, Программирование, теория алгоритмов, метки: квайн, теория алгоритмов Здравствуйте, читатели. В последнее время было много разговоров о квайнах, и даже некоторый теоретический спин-офф.
Повторю за автором только что упомянутого топика: если вы знакомы с CS, то далее читать нет смысла — все это
вы и так хорошо знаете. А статья будет ответом на вопрос — всегда ли можно написать квайн? Точнее, на любом ли языке?
Физики скажут, что на всех: раз можно написать и на компилируемом C, и на брейнфаке, а кто-то и на SQL пишет — опыт говорит, что ответ на вопрос да. Математика тоже говорит, что да.
Теорема 2
На любом алгоритмически полном языке программирования можно написать программу, печатающую свой код.
Читать полностью »
Оценка сложности алгоритмов
2013-03-22 в 11:54, admin, рубрики: Алгоритмы, Песочница, теория алгоритмов, метки: Алгоритмы, теория алгоритмовВведение
Для любого программиста важно знать основы теории алгоритмов, так как именно эта наука изучает общие характеристики алгоритмов и формальные модели их представления. Ещё с уроков информатики нас учат составлять блок-схемы, что, в последствии, помогает при написании более сложных задач, чем в школе. Также не секрет, что практически всегда существует несколько способов решения той или иной задачи: одни предполагают затратить много времени, другие ресурсов, а третьи помогают лишь приближённо найти решение.
Всегда следует искать оптимум в соответствии с поставленной задачей, в частности, при разработке алгоритмов решения класса задач.
Важно также оценивать, как будет вести себя алгоритм при начальных значениях разного объёма и количества, какие ресурсы ему потребуются и сколько времени уйдёт на вывод конечного результата.
Этим занимается раздел теории алгоритмов – теория асимптотического анализа алгоритмов.
Предлагаю в этой статье описать основные критерии оценки и привести пример оценки простейшего алгоритма. На Хабрахабре уже есть статья про методы оценки алгоритмов, но она ориентирована, в основном, на учащихся лицеев. Данную публикацию можно считать углублением той статьи.