Метка «теория алгоритмов»

Здравствуйте, читатели. В последнее время было много разговоров о квайнах, и даже некоторый теоретический спин-офф.
Повторю за автором только что упомянутого топика: если вы знакомы с CS, то далее читать нет смысла — все это
вы и так хорошо знаете. А статья будет ответом на вопрос — всегда ли можно написать квайн? Точнее, на любом ли языке?
Физики скажут, что на всех: раз можно написать и на компилируемом C, и на брейнфаке, а кто-то и на SQL пишет — опыт говорит, что ответ на вопрос да. Математика тоже говорит, что да.

Теорема 2

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

Введение

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

Всегда следует искать оптимум в соответствии с поставленной задачей, в частности, при разработке алгоритмов решения класса задач.
Важно также оценивать, как будет вести себя алгоритм при начальных значениях разного объёма и количества, какие ресурсы ему потребуются и сколько времени уйдёт на вывод конечного результата.
Этим занимается раздел теории алгоритмов – теория асимптотического анализа алгоритмов.

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

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js