Вычислительная разрешимость

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

Сначала мы попробуем выявить общие темы и принципы проектирования при разработке алгоритмов.

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Вычислительная разрешимость:

  1. О.А. Акулов Н.В. Медведев. Информатика и вычислительная техника, 2005
  2. Степанов А. Н.. Архитектура вычислительных систем и компьютерных сетей, 2007
  3. А.П. Пятибратов, Л.П. Гудыно, А.А. Кириченко. Вычислительные машины, сети и телекоммуникационные системы, 2009
  4. Осмотр средств вычислительной техники
  5. Раздел 16 - Уголовного Кодекса Украины Преступления в сфере использования электронно-вычислительных машин (компьютеров), систем и компьютерных сетей и сетей электросвязи
  6. Статья 361. Несанкционированное вмешательство в работу электронно-вычислительных машин (компьютеров), автоматизированных систем, компьютерных сетей или сетей электросвязи
  7. Статья 363-1. Препятствование работе электронно-вычислительных машин (компьютеров), автоматизированных систем, компьютерных сетей или сетей электросвязи путем массового распространение сообщений электросвязи
  8. Статья 362. Несанкционированные действия с информацией, обрабатывается в электронно-вычислительных машинах (компьютерах), автоматизированных системах, компьютерных сетях или сохраняется на носителях такой информации, совершенные лицом, имеет право доступа к ней
  9. Статья 361-2. Несанкционированные сбыт или распространение информации с ограниченным доступом, которая сохраняется в электронно-вычислительных машинах (компьютерах), автоматизированных системах, компьютерных сетях или на носителях такой информации
  10. Статья 363. Нарушение правил эксплуатации электронно-вычислительных машин (компьютеров), автоматизированных систем, компьютерных сетей или сетей электросвязи или порядка или правил защиты информации, которая в них обрабатывается
  11. Г.С.Иванова, Т.Н.Ничушкина, Е.К.Пугачев. Объектно- ориентированное программирование, 2001
  12. Под ред. С. В. Симоновича. Информатика. Базовый курс. 2-е издание, 2004
  13. В. Г. Олифер, Н. А. Олифер. 54 Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд, 2006