Теория алгоритмов

М.: МЦНМО, 2009. — 256 с. В книге излагаются основные (начальные) разделы теории сложности алгоритмов. Различаются алгебраическая и битовая сложности, каждая из которых рассматривается в худшем случае и в среднем. Ряд основных понятий теории сложности, как-то: оценки снизу и сверху, нижняя граница сложности алгоритмов некоторого класса, оптимальный алгоритм и т. д., рассматривается не только в обычном функциональном, но и в асимптотическом смысле...

Абрамов С.М. Методы метавычислений и их применение. — Издание второе, дополненное и переработанное, Переславль-Залесский, Издательство «Университет города Переславля имени А.К.Айламазяна», 2006. —128 с., ил. Книга представляет собой описание вопросов теории метавычислений и их применения. Метавычисления — раздел теории и практики программирования, посвященный разработке методов анализа и преобразования программ за счет реализации конструктивных...

Категория: Математическая логика. Автор: Таль А. А. , Айзерман М. А. , Гусев Л. А. , Розоноер Л. И. , Смирнова И. М. Название: Логика, автоматы, алгоритмы. Количество страниц: 556. Год издания: 1963. Издательство: Наука. ОГЛАВЛЕНИЕ. Элементы математической логики. Вводные замечания. Основные понятия. Исчисление высказываний. Об исчислении предикатов (двузначных). Технические приложения исчисления высказываний. Однотактные релейно-контактные схемы...

Айтқожа А.А., Фазылова Л.С., Копбалина С.С. — Қарағанды: Е.А. Бөкетов атындағы Қарағанды мемлекеттік университеті, 2006. — 105 б. Экономикалық ғылым модельдер мен модельдеуді ертеден қолданып келеді. Экономикалық есептерді зерттеуде және шешуде математикалық аппаратты кеңінен қолдану экономикалық есептерді талдауға арналған математикалық әдістерді құруға қажеттілік туындатты. Осыған байланысты сызықтық программалау, динамикалық программалау, ойын...

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2010. – 16 слайдов. Содержание: Определения эйлерового пути, эйлерового цикла и эйлерова графа. Алгоритм нахождения эйлерова цикла. Алгоритм Прима. Приближенный алгоритм-1 для метрической «TSP». Алгоритм Кристофидеса для метрической «TSP».

Лектор Герман О.В. Остальные выходные данные отсутствуют. Содержание. Введение в теорию алгоритмов. Машины Тьюринга. Распознавание языков машинами Тьюринга. Рекурсивные множества и функции. Алгоритмически неразрешимые проблемы. Использование машин Тьюринга для обоснования универсальности языка программирования. Понятие вычислительной сложности. Распознавание языков. язык выполнимость. Метод резолюций Робинсона. Инфологическая сложность задач. Пос...

Воробьев С. - 2011. – 20 слайдов. Содержание: Введение. Решаемые проблемы. Задача кластеризации. Мера модулярности. Алгоритмы кластеризации. k-clique percolation. Алгоритм Керниган-Лин. Betweenness centrality. Алгоритм Гирван-Ньюмана. Особенность разбиения жадным алгоритмом. Спектральный метод Ньюмана (spectral partitioning). Алгоритм распространения меток.

301 кафедра МАИ, Белоногов В.Д., 2015, 13 с. Целью работы является изучение методов численного интегрирования, разработка алгоритмов, реализация их в форме программ на MATHCAD и оценка их сравнительной точности и трудоемкости на примере тестовых задач моделирования динамических систем. Программа численного интегрирования по Эйлеру. Программа интегрирования по Рунге-Кутту. Программа интегрирования методом Адамса. Программа интегрирования методом П...

М.: Издательский отдел ф-та ВМиК МГУ, 2002. — 82 с. — ISBN: 5894071372 Рассматриваются общие утверждения о сложности задач, методы построения быстрых алгоритмов и примеры их применения с оценками сложности, основные классы задач относительно их сложности, примеры универсальных задач в этих классах.

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

Учебн. пособие. - М.: Статистика, 1973. - 164 с. В учебном пособии излагаются основы теории алгоритмов и теории формальных грамматик, рассматриваются различные алгоритмические системы, методы оценки и преобразования алгоритмов, связь теории алгоритмов с теорией формальных грамматик, классификация грамматик, связь теории формальных грамматик с теорией автоматов. Пособие предназначено для студентов вузов, специализирующихся по механизированной обра...

Выходные данные не приведены. Автор не известен. — 35 с. Данный курсовой проект посвящен рассмотрению и изучению алгоритмов нечисленной обработки данных – линейный и двоичный поиск, а также упорядочение массива методом сортировки деревом. Алгоритмы реализованы на языке Turbo Pascal 7.0 Постановка задачи. Метод решения. Сортировка двоичным деревом. Организация массива в виде двоичного дерева. Простейший способ. Описание построения дерева. Описание...

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

Ульяновск: Ульяновский государственный технический университет, 2002. - 70 с. Учебное пособие разработано на кафедре прикладной математики и информатики в соответствии с учебными программами для студентов технических и математических специальностей. Содержание включает изложение методических приемов по практическому составлению визуальных алгоритмов, которые могут быть использованы для подготовки к выполнению практических заданий по курсу Информа...

Перевод с английского. — М.: Вильямс, 2003. — 384 с. — ISBN 5-8459-0122-7. В этой книге подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ. Показаны разнообразные реализации абстрактных типов данных, начиная от стандартных списков, стеков, очередей и заканчивая множествами и отображениями, которые используются для неформального описания и реализации алгоритмов. Две главы кни...

Учебник по дисциплине "Структуры и алгоритмы данных". Содержание: Построение и анализ алгоритмов Основные абстрактные типы данных Деревья Основные операторы множеств Специальные методы представления множеств Ориентированные графы Неориентированные графы Сортировка Методы анализа алгоритмов Методы разработки алгоритмов Структуры данных и алгоритмы для внешней памяти Управление памятью

Учебное пособие. - Улан-Удэ: Изд-во ВСГТУ, 2000 г. - 51 с. В учебном пособии рассмотрены основные понятия теории; формальные модели алгоритмов, дается классификация формальных грамматик, описаны используемые в практике программирования алгоритмы преобразования грамматик и синтеза автоматов. По каждому разделу приведен теоретический материал, даны методические рекомендации и примеры решения задач, а также задания для самостоятельной работы. Сод...

Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006. - 17 с. Методическое пособие по дисциплине «Математическая логика и теория алгоритмов». Приводится формализация понятия «алгоритм». Обсуждаются два способа формального описания алгоритма –с помощью нормальных алгоритмов Маркова и через машины Тьюринга. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и NP, алгоритмически неразрешимые проблемы.

Казань: КГУ, 1999. 25 с. В учебном пособии кратко рассмотрены следующие вопросы: эффективная нумерация алгоритмов; теорема о параметризации; универсальный алгоритм; перечислимые и разрешимые множества; алгоритмически неразрешимые проблемы, в т.ч. теорема Райса; элементы математической логики. В пособии не уделяется внимания определению понятия «алгоритм», оно считается синонимом понятия «компьютерная программа». В качестве языка для написания алг...

Казань: КГУ, 1999. 25 с. В учебном пособии кратко рассмотрены следующие вопросы: эффективная нумерация алгоритмов; теорема о параметризации; универсальный алгоритм; перечислимые и разрешимые множества; алгоритмически неразрешимые проблемы, в т.ч. теорема Райса; элементы математической логики. В пособии не уделяется внимания определению понятия «алгоритм», оно считается синонимом понятия «компьютерная программа». В качестве языка для написания алг...

М.: МЦНМО, 2013. - 576 с. - ISBN 978-5-4439-0212-8, eBook, Русский Классическая (шенноновская) теория информации измеряет количество информации, заключённой в случайных величинах. В середине 1960-х годов А. Н. Колмогоров (и другие авторы) предложили измерять количество информации в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект. Это определение послужило основой...

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2011. – 13 слайдов. В материале рассматриваются полиномиальные и матричные тождества. Содержание: Алгоритм Фрейвалда. Корректность алгоритма. Доказательство. Полиномиальные тождества. Лемма Шварца-Зиппеля и ее доказательство. Упражнение.

Издательство Мир, Москва 1997. - 183 с. Электронная книга одного из наиболее известных специалистов в современном программировании посвящена методам систематического конструирования алгоритмов и написана как вводный курс программирования. Поскольку такой курс должен быть составной частью общего математического образования, особое внимание уделяется системе обозначений, языку. В книге используется язык Паскаль, получивший в последние годы широкое...

Учебно-методическое пособие по курсу «Теория алгоритмов» для студентов специальности «Информатика» всех форм обучения. — Минск: БГУИР, 2007. — 54 с. Учебно-методическое пособие составлено в соответствии с рабочей программой курса «Теория алгоритмов». В него включены базовые определения и основные результаты классической теории алгоритмов, а также теории сложности вычислений. Описаны различные математические уточнения понятия «алгоритм», приведен...

Курс лекций для студентов специальности I-31 03 04 «Информатика» всех форм обучения. Минск: БГУИР, 2006, -103с. Содержание Основы теории алгоритмов Неформальное определение алгоритма и необходимость его уточнения Арифметические и интуитивно вычислимые функции Машины Тьюринга Вычислимость по Тьюрингу Машины Шёнфилда Частично вычислимые функции Кодирование алгоритмов Алгоритмически неразрешимые задачи Универсальные функции Некоторые теоремы теори...

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

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2011. – 9 слайдов. Содержание: Теорема об ускорении. Классы временной сложности. Теорема об иерархии. Классы пространственной сложности. «Карта памяти» лекции.

301 кафедра МАИ, Белоногов В.Д., 2015, 11 с. Вычисление матрицы передаточных функций по системе дифференциальных уравнений. Изучение алгоритмов вычислительных операций с матрицами и их реализация в Matcad.

301 кафедра МАИ, Белоногов В.Д., 2015, 8 с. Вычисление дискретной модели системы в форме системы разностных уравнений по системе дифференциальных уравнений в форме уравнений состояния. Реализация алгоритмов в Matcad. Оценка точности и трудоемкости.

Механико-математический факультет МГУ. 2005. 144с. Учебное пособие написано на основе специальных курсов "Теория баз данных и информационного поиска" и "Теория интеллектуальных систем", читаемых на кафедре математической теории интеллектуальных систем механико-математического факультета МГУ им. М.В.Ломоносова. В книге вводится новый вид представления баз данных, называемый информационно-графовой моделью данных, обобщающий известные ранее модели д...

3-е изд., испр. — М.: Дрофа, 2005. — 320 с. — (Классический университетский учебник). — ISBN 5-7107-8904-6. В учебном пособии впервые в отечественной литературе рассматривается связь вопросов арифметики с современными проблемами кибернетики. Книга представляет собой сборник задач по арифметике и теории сложности арифметических алгоритмов и позволяет получить систематические знания в этих областях математики. Для студентов университетов, педагогич...

В учебном пособии (2-е изд. — 2002 г. ) впервые в отечественной литературе рассматривается связь вопросов арифметики с современными проблемами кибернетики. Книга представляет собой сборник задач по арифметике и теории сложности арифметических алгоритмов и позволяет получить систематические знания в этих областях математики. Для студентов университетов, педагогических вузов и вузов с углубленным изучением математики.

Пер. с англ. Наука. М., 1974, 288с. Линейные последовательностные машины (ЛПМ) широко применяются в автоматике и вычислительной технике в качестве генераторов последовательностей, счетчиков, кодирующих и декодирующих устройств, устройств обнаружения и исправления ошибок, при моделировании нейронных сетей и т. д. Книга А. Гилла представляет собой первую в мировой литературе монографию, посвященную теории ЛПМ. В ней известные понятия и методы теори...

СПб.: Лань, 2012. — 406 с. Учебное пособие содержит полное изложение материала учебных дисциплин «Математическая логика и теория алгоритмов» и «Дискретные функции» Государственного образовательного стандарта высшего профессионального образования по специальностям «Компьютерная безопасность», «Информационная безопасность автоматизированных систем» и некоторым другим смежным специальностям. Пособие состоит из трех взаимосвязанных частей, составляющ...

Автор: Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Название: Алгебра. Языки. Программирование. Издательство: Издательство «Мир». Формат: djvu. Размер: 4.0 Mb. Эволюция общения человека с ЭВМ связана с созданием мощных средств их математического обеспечения. Используемые при этом развитые языки и системы программирования существенно повышают "Интеллект" ЭВМ, реализуемый как схемным, так и программным способом, и способствуют дальнейшему расширению сфе...

М.: ФИЗМАТЛИТ, 2006. 296 с. Книга является учебным пособием по теории рекурсии в аспекте ее применения в области проrраммирования. В ней рассматриваются основы теории рекурсии и ее использование в области разработки и анализа рекурсивных алrоритмов. Приводятся основные сведения о рекурсивных последовательностях и функциях, даны примеры рекурсивных алrоритмов, разработанных на основе рекуррентных соотношений, метода декомпозиции и метода динамичес...

1982 год, 120 страниц, 2-е издание Оригинальное и нестандартное изложение известных методов анализа алгоритмов, написанные крупным американским специалистом Д. Кнутом в соавторстве с Д. Грином. В книге представлены: комбинаторные тождества, рекуррентные соотношения, асимптотические представления. От читателя требуется знакомство с основами теории вероятностей, комбинаторного анализа и теории функций комплексного переменного. Для системных програ...

Пер. с нем. / Под ред. Б. Ф. Мельникова. - 3-е изд. - СПб.: БХВ-Петербург, 2010. - 336с (Учебная литература для вузов) Изложены основные понятия теоретической информатики: алфавиты, слова, языки, алгоритмические проблемы, конечные автоматы, машины Тьюринга. Рассматриваются теория вычислимости, теория сложности, алгоритмизация труднорешаемых задач, рандомизация, теория связи и криптографические методы. Книга известного ученого вышла на 4-х языках...

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

Издательство: Мир Год: 1982 Страниц: 416 300 dpi Монография американских ученых, посвященная вопросам сложности решения комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории чисел, теории автоматов, математической логике, теории множеств, теории графов и т. п. Книга отличается строгим и систематическим изложением теории, в приложении содержится более 300 труднорешаемых задач из различных разд...

12 стр. Содержание: Теория как особая форма научного познания. Дедукция. Типы дедуктивных теорий по О.С. Разумовскому. Дедуктивный метод Шерлока Холмса. Список используемой литературы.

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей. - М.: Институт системного программирования РАН, 2006. – 26 с. Графы являются естественным и наглядным средством представления сложных структур и процессов. Это позволяет широко использовать их в компьютерных системах при решении различных...

Учебное пособие. — Симферополь: Куб, 2016. — 232 с.: ил. — ISBN 978-5-9908044-1-8. Введение. Измерение информации. Энтропия и её свойства. Энтропия источника дискретной информации. Свойства энтропии источника дискретной информации. Совместная и условная энтропия. Информация и её свойства. Энтропия непрерывной информации. Передача дискретной информации, пропускная способность канала и теорема Шеннона. Скорость передачи и пропускная способ...

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

Учебное пособие. ЮУрГУ, кафедра ЭВМ, 2009. - 64 стр. В пособии рассматриваются общие особенности теории алгоритмов, а также конкретные алгоритмические системы, такие как «Рекурсивные функции», «Машины Поста и Тьюринга», «Нормальные алгоритмы Маркова» и т. п. В соответствии с предметом дисциплины «Математическая логика и теория алгоритмов». Для студентов специальности 230101 («Вычислительные машины, комплексы, системы и сети») и направления 01040...

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2010. – 15 слайдов. Содержание: Приближенный алгоритм с гарантированной точностью. Покрытие множества. Жадный алгоритм в задаче о покрытии. Покрытие на каждом шаге. Точность жадного алгоритма: верхняя оценка. Как обмануть жадный алгоритм? Нижняя оценка. k-покрытие множества. Вершинное покрытие. «Ленивый» алгоритм для ве...

В документе находятся теоретические и практические данные (с решениями) о машине Поста и Тьюринга. Машина Поста. Машина Тьюринга

60 слайдов. (Автор не указан). Содержание: LRU – «least recently used». CLOCK. LFU – «least frequently used». LRD – «least reference density». GCLOCK – «generalized CLOCK». Improved GCLOCK. CAR – «CLOCK with Adaptive Replacement». ARC – «Adaptive Replacement Cache». CART – «CAR with Temporal filtering». MQ – «Multiple Queue». LIRS – «Low Inter-reference Recency Set». Эксперименты и статистика.

Учебное пособие. — Минск: БГУ, 2013. — 159 с. В учебном пособии изложены современные методы построения и анализа алгоритмов с использованием эффективных способов хранения, представления и преобразования информации. Для магистрантов учреждений высшего образования, обучающихся по специальностям «Прикладная математика и информатика» и «Теоретические основы информатики». Дерево интервалов. Строковые алгоритмы и структуры данных. Графовые алгоритмы.

Выходные данные не приведены. Казиев В.М. — 9 с. Исполнитель. Человек (специалист). Структура мозга человека. Центральная нервная система. Человеческий мозг. Структура познания системы. Структура обработки информации человеком.

Новосибирск: Новосибирский гос. университет (НГУ), 1995. – 113 с. Излагаются основы теории формальных языков и грамматик. Рассматриваются классы регулярных и контекстно-свободных языков и их связь с конечными и магазинными автоматами. Обсуждаются фундаментальные вопросы сложности решения задач дискретной математики. Для студентов вузов, обучающихся по специальности "математика, "прикладная математика и ’’информатика. Содержание: Цепочки, языки и...

Перевод с англ. А. А. Мучника под ред. С. Ю. Маслова Книга известного английского математика, охватывающая основные вопросы теории вычислимых функций и ее приложений: сложность вычислений и алгоритмов, теоремы Гёделя о неполноте и Чёрча о неразрешимости, семантику языков программирования. Изложение замкнутое, методически продуманное, имеется много упражнений. Для математиков, специалистов по ЭВМ, желающих ознакомиться с теоретическими основами...

Агаев Н. - М.: Факультет Вычислительной математики и кибернетики МГУ, 2011. – 31 слайд. Содержание: Понятие кластеризации Меры близости. Классификация алгоритмов. Неиерархические алгоритмы кластеризации. Иерархические алгоритмы кластеризации.

СПб.: Питер, 2016. — 800 c. — ISBN 9785496015455. Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных. Вы познакомитесь с базовыми аспектами построения алгоритмов, основными понятиями и определениями, структурами данных, затем перейдете к основным методам построения...

СПб.: Питер, 2016. — 800 c. — ISBN 9785496015455. Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных. Вы познакомитесь с базовыми аспектами построения алгоритмов, основными понятиями и определениями, структурами данных, затем перейдете к основным методам построения...

М.: МЦНМО, 2001 г., 78 с. "Цель данной работы состоит в том, чтобы ознакомить читателя с основами анализа алгоритмов, причём сделать это с помощью примеров, а не систематического изложения теории. Надеюсь, что такой подход позволит читателю быстро войти в курс дела, познакомиться с идеями, используемыми в этой области, а также понять взаимосвязь анализа алгоритмов с другими математическими дисциплинами. Задача об устойчивых супружеских парах наи...

М.: МЦНМО, 2011 г., 78 с. Содержание: От переводчиков русского издания От переводчика английского издания Предисловие к первому изданию (на французском языке) Введение, определения, примеры Существование устойчивого паросочетания: основной алгоритм Принцип отложенных решений: накопление купонов Теоретические основы: применение в задаче о кратчайшем пути Поиск в хеш-таблицах: поведение основного алгоритма в среднем Реализация основного алгори...

Новосибирск: изд. НГУ, 2005. - 89 с. Конспект лекций для студентов 1 курса. Содержание. Предварительные сведения. Конечные автоматы и формальные грамматики. Формализации понятия вычислимой функции. Теория вычислимости. Теория сложности алгоритмов. Список литературы.

Учебное пособие. — Новосибирск: мех.-математический факультет, Новосиб. гос. ун-т, 2009. — 107 с. В настоящем учебном пособии изложены математические основы теории алгоритмов. Пособие отражает содержание лекций основного курса «Теория алгоритмов», прочитанных автором для студентов 1-го курса механико-математического факультета НГУ и охватывает материал из нескольких областей математики, так или иначе связанных с понятием алгоритма: теория автомат...

Издательство Мир, 1974, -392 с. Библиотека «Кибернетического сборника» Затрагиваемые в сборнике проблемы математической логики тесно связаны с теорией вычислительных машин. В книге рассматриваются модели вычислительных устройств, их классификация, классификация языков, оценки сложности вычислений и оценки сложности программ. Развивается связанный со сложностью программ подход А. Н. Колмогорова к обоснованию теории вероятностей и теории информаци...

Оценить длину программы умножения матриц произвольного ранга. Оценить начальное количество ошибок в ОС, если число разрядов слова состояния системы равно 12. Оценить длину программы обращения матрицы произвольного ранга. Оценить длину программы сортировки массива (например, по методу «пузырька»). Оценить квалификационное время программирования для табулирования Pn(x).

М.: МЦНМО, 2001. - 960 с. Книга представляет собой перевод учебника по курсу построения и анализа эффективных алгоритмов, написанного в Массачусетсом технологическом институте; в ней разбираются важнейшие, классы быстрых алгоритмов и приёмы их построения. Изложение подробное и математически строгое. Книгу можно использовать в качестве учебника и справочника; она будет полезна как студентам, так и профессионалам в области computer science и прогр...

В книге подробно разобрано много конкретных алгоритмов; мы старались рассказать о них понятно, но не опуская деталей и не жертвуя строгостью изложения. Алгоритмы записаны с виде «псевдокода» и прокомментированы в тексте; мы старались сделать описание алгоритма понятным людям с минимальным программистским опытом. Книга содержит более 260 рисунков, поясняющих работу различных алгоритмов. Мы обращаем особое внимание на эффективность рассматриваемых...

М.: ООО И.Д. Вильямс, 2014. — 208 c. — ISBN: 9785845918680 Эта книга написана признанным авторитетом в области компьютерных алгоритмов - профессором информатики Томасом Корменом, чей труд "Алгоритмы: построение и анализ", написанный в соавторстве с такими выдающимися учеными, как Чарльз Лейзерсон, Рональд Ривест и Клиффорд Штайн, выдержав три издания, давно стал общепризнанным классическим учебником по алгоритмам. Поскольку книга "Алгоритмы: пос...

М.: Вильямс, 2014. - 208с. Эта книга написана признанным авторитетом в области компьютерных алгоритмов - профессором информатики Томасом Корменом, чей труд "Алгоритмы: построение и анализ", написанный в соавторстве с такими выдающимися учеными, как Чарльз Лейзерсон, Рональд Ривест и Клиффорд Штайн, выдержав три издания, давно стал общепризнанным классическим учебником по алгоритмам. Поскольку книга "Алгоритмы: построение и анализ" предназначена в...

1-е издание, 1990. — 893 с.: ил. Фундаментальный труд известных специалистов в области кибернетики достоин занять место на полке любого человека, чья деятельность так или иначе связана с информатикой и алгоритмами. Для профессионала эта книга может служить настольным справочником, для преподавателя — пособием для подготовки к лекциям и источником интересных нетривиальных задач, для студентов и аспирантов — отличным учебником. Каждый может найти...

3-е изд. — М.: Вильямс, 2013. — 1324 с. — ISBN 978-5-8459-1794-2. Книга "Алгоритмы. Построение и анализ" удачно объединяет в себе полноту охвата и строгость изложения материала. Много книг, посвященных алгоритмам, отличается строгостью изложения материала, но страдает определенной неполнотой; другие книги охватывают огромный объем материала, но недостаточно строго излагают его. В книге "Алгоритмы. Построение и анализ" описаны самые разнообразные...

Переводчик: И.В.Красикова. — 3-е изд. — М.: Вильямс. — 1324 с. — ISBN: 978-5-8459-1794-2. Книга "Алгоритмы. Построение и анализ" удачно объединяет в себе полноту охвата и строгость изложения материала. Много книг, посвященных алгоритмам, отличается строгостью изложения материала, но страдает определенной неполнотой; другие книги охватывают огромный объем материала, но недостаточно строго излагают его. В книге "Алгоритмы. Построение и анализ" опис...

Санкт-Петербург: Санкт-Петербургский Государственный институт Точной Механики и Оптики, 2003, 38 с. Данное пособие посвящено основам теории алгоритмов. Рассматриваются тезис Черча, регистровые машины, некоторые алгоритмические массовые проблемы, разрешимость и перечислимость множества тавталогий, формальные теории, язык Пролог. Пособие предназначено для студентов компьютерных и математических специальностей.

Учебное пособие для студентов 1 курса. - М.: МАКС Пресс, 2010. - 26 с. Учебное пособие представляет собой введение к основному курсу лекций для студентов факультета ВМК МГУ "Алгоритмы и алгоритмические языки". Обсуждается роль компьютера в решении проблемы накопления и сохранения знаний, детализируется представление о задаче обработки информации. Вводятся понятия процесса обработки и алгоритма. Подчеркивается эквивалентность задачи обработки слов...

М.: ИНТУИТ, 2016. — 216 с. — ISBN 978-5-9556-0069-7 Предлагаемый курс начинается с азов комбинаторики и охватывает все основные алгоритмы, их анализ и реализацию на языках программирования, а так же рассматриваются алгоритмы на графах с точки зрения комбинаторных методов их реализации и анализа. Курс описывает различные способы представлений конечных последовательностей и операций над ними; множества и мультимножества; производящие функции и реку...

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

М.: Факториал Пресс, 2006. - 128с. Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете МГУ им. М. В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности "Защита информации". Излагаются основные идеи и методы теории сложности вычислений. Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгорит...

Учебное пособие. M.: Факториал Пресс, 2006. — 128 с. — (Методы современной математики; Вып. 2) ISBN 5-88688-083-6 Тираж 1000 экз. Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете МГУ им. М.В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности «Защита информации». Излагаются основные идеи и методы теории сложности вы...

Академия, 2009. - 208 c. В учебном пособии изложены основы качественной и количественной теории алгоритмов; рассмотрены основные модели вычислений (машины Тьюринга, машины с неограниченными регистрами, рекурсивные функции) и связанные с ними подходы к формализации понятия алгоритма; даны начала алгоритмической теории множеств; представлены наиболее известные результаты об алгоритмической неразрешимости, а также элементы теории сложности вычислени...

Московский физико-технический институт. 2007 г. 135 стр. Элементы теории сложности Несложно о сложности. Примеры алгоритмов Формально об алгоритмах Сложность алгоритмов Вероятностные вычисления Вероятностно проверяемые доказательства Схемы и схемная сложность Коммуникационная сложность Диаграмма классов сложности Приближенные алгоритмы с гарантированными оценками точности Приближенные алгоритмы с фиксированными оценками точности Приближенные алго...

Эта книга написана по материалам двух спецкурсов, читавшихся авторами в течение нескольких лет для студентов 4-го и 6-го курсов Московского физико-технического института. Она знакомит читателей как с классическими результатами в разработке эффективных алгоритмов для решения вычислительно-трудных задач, полученными еще в 1960-1970-х годах, так и с новыми результатами, полученными в последние годы. Именно в рассмотрении современных подходов к решен...

М., 2011. – 363 с. Книга написана по материалам спецкурсов, читавшихся авторами в течение нескольких лет для студентов Московского физико-технического института. Она знакомит читателей как с классическими результатами в разработке эффективных алгоритмов для решения вычислительно-трудных задач, полученными еще в 1960-1970-х годах, так и с новыми результатами, полученными в последние годы. Именно в рассмотрении современных подходов к решению вычисл...

М.: Институт Системного Программирования РАН, 2004. – 12 с. При тестировании систем, поведение которых определяется не только последним обращением к ним, а и предшествующей историей работы, т.е. зависит от внутреннего состояния системы, необходимо строить тесты в виде последовательностей обращений, чтобы покрыть возникающие разнообразные ситуации. Если о системе известно немного, например, только список обращений, которые можно делать, построить...

Содержание Введение: Актуальность темы Понятие алгоритма Признаки алгоритмов Структуры данных и их представление в памяти ЭВМ Эффективность алгоритмов и методы её достижения Форма алгоритмов Эффективность алгоритмов Машина Тьюринга Краткое содержание курсовой работы Разработка эффективных алгоритмов: Типы алгоритмов Линейный алгоритм Задание 1 Алгоритмы разветвляющейся структуры Задание 2 Циклические вычислительные процессы Задание 3 Словесн...

Архив содержит файлы решенных задач на МТ следующих вариантов: Вариант 1 На информационной ленте машины Тьюринга содержится массив символов +. Необходимо разработать функциональную схему машины Тьюринга, которая каждый второй символ + заменит на -. Каретка в начальном состоянии находится где-то над указанным массивом. Вариант 2 Дано число п в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число n на...

Современное программирование излагается как искусство заставить компьютер решить задачу, возникшую перед человеком. Даны единые основания математики и программирования, краткие сведения из области графов, теории вероятностей и информации (в ее математическом толковании). Приведены основные понятия и конструкции современных языков программирования. Рассмотрен ряд вопросов теории программирования с упором на математическую семантику языковых констр...

Краткий конспект по лекциям, набранный в формате doc 12стр. Темы: Системы проектирования и отладки. Системы проектирования ALTERA. Программируемые логические интегральные схемы (ПЛИС). Программируемые логические схемы. ПЛИС блочной структуры. ПЛИС с матричной архитектурой. ПЛИС фирмы Altera. Программируемые ПЛИС. Настройка. (Конфигурация ПЛИС). Загрузка конфигурации из памяти конфигурации. Схема синхронизации. Тактовая сетка.

Автор не известен. 136 с. Лекции в виде презентации. Содержание. - Алгоритмы в математике. Основные черты алгоритмов. Числовые функциии алгоритмы их вычисления. Примитивно рекурсивные функции. - Частично рекурсивные функции.Тезис Черча. - Машины Тьюринга и машины с неограниченными регистрами. Вычислимость частично рекурсивных функций на МНР. - Нумерации и универсальные функции. - Нормальные алгорифмы. - Алгоритмические проблемы в логике и матем...

Введение в теорию алгоритмов Сложность алгоритмов Сортировка и поиск Сортировка всплытия Флойда Логарифмический поиск Сортировка с вычисляемыми адресами Генетические алгоритмы Моделирование генетических операций Вычислительные эксперименты с генетическими операциямиrn

М.: Мехмат МГУ, Зюзьков В.М., 2006. — 44 с. Содержание: Алгоритмы и вычислимые функции. Элементарная арифметика и неполнота. Сложность вычислений. NP-полнота.

Содержание. Часть1. Исторический экскурс. Математическое моделирование. Классификация задач по Евклиду. Классификация задач по Декарту. Классификация задач по Пойа. Классификация задач по Клини. Классификация задач в работах по искусственному интеллекту. Модель. Классификация абстрактных моделей. Этапы и цели компьютерного математического моделирования. Множества. Операции над множествами и их свойства. Теоретико-множественное описание АДТ. Древо...

Содержание. Часть2. Определение алгоритма. Вычислимость. Разрешимость. Типы алгоритмов. История создания. Алгоритмические машины. Примеры исчислений в IT. Структура алгоритма (составляющие алгоритма). Машина Поста. Пример программы (алгоритма). Программа, добавляющая к числу метку справа. Программа, добавляющая к числу метку слева. Машина Тьюринга (МТ). Математическое описание МТ. Пример: сложение двух чисел. Нормальные алгоритмы Маркова. Авто...

Елабуга: Елабужский государственный педагогический университет. – 87 с. Содержание: Теория рекурсивных функций. Примитивно рекурсивные функции. Базис элементарных функций. Операции подстановки и примитивной рекурсии. Основные свойства. Примитивно рекурсивные функции относительно совокупности функций. Основные свойства. Производные операции над функциями. Операции конечного суммирования и конечного произведения. Предикат, логическая функция....

Учебно-методическое пособие для студентов очного и заочного обучения технических специальностей. – Н. Новгород : Изд-во ФГОУ ВПО «ВГАВТ», 2010. – 81 с. Излагаются основные принципы и типовые приемы алгоритмизации при решении инженерных задач. Приводятся примеры алгоритмов решения типовых задач: табулирование функций, поиск элементов с заданными признаками и сортировка данных. Пособие направлено на формирование начальных навыков алгоритмизации и п...

Стаття связаная с построением самых быстрых алгоритмов для умножения двух произвольных матриц. Основное внимание приведено новым методам, развитым в последние годы для решения этой задачи. Результаты, относящиеся к главному направлению, приведены с доказательством. Также тут описан и обоснован самый асимптотически быстрый метод умножения матриц: алгоритм Копперсмита-Винограда. Лупанов О. Б., Касим-Заде О. М. - Кибернетический сборник (1988, выпу...

М.: «Наука», 1965. — 394 с. Скан, OCR слой. Еще в 30-х годах нашего столетия математическая логика и возникавшая тогда теория алгоритмов казались наиболее абстрактными и наиболее далекими от практических приложений математическими дисциплинами. В настоящее время положение коренным образом изменилось. Ныне общепризнано, что обе названные дисциплины образуют теоретический фундамент для создания и применений быстродействующих вычислительных и управл...

М.: Наука. Гл. ред. физ.-мат. лит., 1986.— 366 c. — 2-е изд. Скан, OCR слой. Посвящается одному из актуальных и бурно развивающихся разделов математической логики — теории алгоритмов, а также важнейшим ее связям с другими разделами математики. Является одним из лучших пособий для знакомства с основными направлениями, идеями и методами теории алгоритмов. 1-е изд.— в 1965 г. Для математиков различных специальностей: научных работников, аспирантов...

В оригинале - "Теория Алгорифмов". М. -Л.: Издательство Академии Наук СССР, 1954. - 377 с. Книга вводит читателя в область теории алгоритмов. В ней отыскали отблеска эти нюансы доктрины как многоцелевые, обычные методы, исчеслия Поста, комбинаторная неувязка Поста, неувязка определения применимости алгоритмов и всякое разное. Книга написана на высочайшем математическом уровне.

М.: МЦНМО, 2003. - 112 с. Книга написана на основе курсов лекций, которые автор читал на факультете Вычислительной математики и кибернетики МГУ. В книге собраны основное классы «элементарных» рекурсивных функций, изучаемые в теории алгоритмов. Приведены различные определения этих классов, установлены соотношения включения между ними. Получены разнообразные канонические представления элементарных функций, указаны эффективные операции, сохраняющие...

Учебное пособие. – Киров: Вятский государственный университет, 2011. – 40 с. Логические схемы алгоритмов. Матричные схемы алгоритмов. Граф-схемы алгоритмов. Формальные преобразования операторных схем алгоритмов. Объединение операторных схем алгоритмов.

М.: БИНОМ. Лаборатория знаний. 2008. — 202 с. Учебник по курсу «Теория алгоритмов» для педагогических вузов по специальности «Информатика», полностью соответствующий стандарту. Изложение имеет четкую логическую структуру и охватывает следующие темы: понятие алгоритма, машина Тьюринга, примитивно-рекурсивные функции, нормальные алгоритмы, вычислимость и разрешимость, сложность вычислений, NP-полные задачи. Каждая тема сопровождается тестовыми зада...

Теорія алгоритмів та представлення знань: Конспект лекцій для студентів освітньо-кваліфікаційного рівня «бакалавр» напряму підготовки 6.020303 «Філологія» / Укл.: Н.І. Мельникова, – Львів: Кафедра «Інформаційних систем та мереж» Інститут комп‘ютерних наук та інформаційних технологій Національного університету «Львівська політехніка», 2015.-91 с.

37 с. (Автор не указан). Содержание: Формулировки задач. Задача линейного раскроя. Задача о рюкзаке. Задача о камнях. Задача коммивояжера. NP-полнота. Переборные методы. Задача о рюкзаке. Задача о камнях. Задача коммивояжера. Метод ветвей и границ. Жадные алгоритмы. Задача о выборе заявок. Эвристические методы. Задача линейного раскроя. Задача о рюкзаке. Задача о камнях. Динамическое программирование. Задача линейного раскроя. Задача о рюкзаке. Л...

Учебное пособие. Новосибирск: НГУ, 2005. 114 с. Данная книга - изложение курса лекций по теории алгоритмов, читанного автором на математическом факультете Новосибирского госуниверситета в 2001-2003 годах. Задача учебника - дать хорошее интуитивное понимание математического понятия алгоритма и служить введением для дальнейшего изучения других руководств по теории алгоритмов, а также служить методологической основой для изучения других предметов,...

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

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2011. – 28 слайдов. Содержание: История алгоритмов. Теория сложности. Обозначения. Тривиальное и разумное вычисления. Дискретный логарифм. Наибольший общий делитель. Алгоритм Евклида. Задача коммивояжера. Переборный алгоритм для TSP. Кратчайшие пути в графе. Алгоритм Дейкстры. Трудоемкость алгоритма Дейкстры. Кратчайшие...

Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями): пер. с фран. М.: Мир, 1999. - 720 с. Книга известных французских математиков — это по существу энциклопедия алгоритмов алгебры и теории чисел от Евклида и до наших дней. В ней прослеживается общая идея — представить основные алгебраические структуры и концепции в виде объектов, поддающихся машинной обработке. Главными для авторов являются два вопроса: что значит вычислит...

Выходные данные не приведены. Автор не известен. — 8 с. Правило размещения результата. Построение НАМ. Построение алгоритмов из алгоритмов. Табличная запись программы. Выводы. Список литературы.

Возможности вычислительных машин, сложность вычислений, нижние оценки сложности, оптимизация алгоритмов

Борисенко О. - 2010. – 43 слайда. Для хранения и обработки больших объёмов данных требуется много памяти. Таким образом, разумно использовать внешнюю память для хранения информации. Для этого необходимы специальные структуры, которые были бы ориентированы на работу с использованием жесткого диска. В презентации производится подробный обзор используемых структур. Основные виды деревьев: В-дерево. B+. prefix B+. Berkley B+. String B-tree. B*. Сжаты...

Воронежский государственный технический университет, Воронеж, Литвиненко В.П., 2007. — 15 с. Введение. Разработка оптимального дихотомического алгоритма поиска при равновероятном распределении вероятностей и числе событий м=. Разработка оптимального алгоритма поиска для экспоненциального закона распределения вероятностей при м=. Разработка оптимального алгоритма поиска экспоненциального закона распределения при числе измерений от n=15 До n=Log2m....

Автор неизвестен. Конспект лекций по курсу "Матем. логика и теория алгоритмов". 2008 год. - 80 стр. Исчисления высказываний. Определение формального исчисления. Исчисление высказываний генценовского типа. Эквивалентность формул. Нормальные формы. Семантика исчисления секвенций. Исчисление высказываний гильбертовского типа. Алгоритмы проверки общезначимости и противоречивости в ИВ. Логика и исчисления предикатов. Алгебр. системы. Формулы сигнатуры...

Алгоритмы и структуры данных Опишите задачу решаемую алгоритмом Беллмана-Форда. Приведите пример использования данного алгоритма в обобщенном виде. Опишите задачу решаемую бинарным деревом поиска. Приведите пример использования данной структуры в обобщенном виде. Опишите задачу решаемую алгоритмом Дейкстры. Приведите пример использования данного алгоритма в обобщенном виде. Опишите задачу решаемую алгоритмом Форда-Фалкерсона. Приведите пример исп...

М.: Мир, 1984. - 510 с. В предлагаемой вниманию читателей книге удачно синтезированы вопросы, которые ранее в литературе освещались изолированно. Объединяющим все изложение лейтмотивом послужила задача линейного программирования, занимающая важное место в истории развития теории алгоритмов.

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2010. – 16 слайдов. Параллельный вероятностный алгоритм Луби – алгоритм нахождения максимального по включению независимого множества в графе. Для реализации данного алгоритма требуется полилогарифмическое время «в среднем».

Одесса: Одесский государственный политехнический университет (ОГПУ), 2004. – 36 с. Методические указания к курсовой работе по дисциплине Теория алгоритмов и вычислительных процессов для студентов специальности 7.080403. Данные методические указания предназначены для оказания помощи студентам при решении ключевых вопросов теории и практики проектирования алгоритмов: разработке эффективных алгоритмов и построению машин Тьюринга как модели вычислит...

Одесса: Одесский государственный политехнический университет (ОГПУ). – 66 с. Данные методические указания и задачи к практическим занятиям подготовлены в соответствии с программой курса «Теория алгоритмов и вычислительных процессов», изучаемого студентами специальностей 7.080403 «Программное обеспечение автоматизированных систем». Целью данных методических указаний и задач является закрепление лекционного материала и выработка у студентов навыко...

Издательство Иностранной литературы, Москва 1954 год. Перевод с немецкого: В. А. Успенского Под редакцией и с предисловием А. Н. Колмогорова Переход от n к n+1 как способ определения теоретико-числовых функций Рекурсивные функции и отношения Возвратная рекурсия Одновременная рекурсия Рекурсия, при которой производится подстановка некоторой функции на место параметра Рекурсия по многим переменным Дальнейшие упрощения Элементарные функции Пример т...

Уч-метод. пособие - М.: ВМК МГУ, 2006. – 47 с. Задачи на составление алгоритмов в виде машины Тьюринга и нормальных алгоритмов Маркова, а также задачи теоретического характера. Сведения по теории алгоритмов, типичные приёмы решения задач и большой набор задач для самостоятельного решения. Пособие рассчитано на студентов 1 курса факультета ВМК МГУ и преподавателей, ведущих семинарские занятия по программированию. Содержание: Машина Тьюринга. Кра...

М.: МГУ, 2006. – 47 с. Учебно-методическое пособие Задачи на составление алгоритмов в виде машины Тьюринга и нормальных алгоритмов Маркова, а также задачи теоретического характера. Сведения по теории алгоритмов, типичные приёмы решения задач и большой набор задач для самостоятельного решения. Пособие рассчитано на студентов 1 курса факультета ВМК МГУ и преподавателей, ведущих семинарские занятия по программированию.

Учебно-методическое пособие, М.: МГУ, 2012. - 38 с. Рекурсия – мощный инструмент программирования, по выразительным возможностям близкий к циклам. Рекурсия широко применяется при решении игровых и переборных задач. Однако зачастую освоение рекурсии представляет существенную сложность для начинающих программистов. Данное пособие посвящено обсуждению понятия рекурсии, рассмотрению особенностей рекурсивных функций и процедур, а также приёмов их опис...

Никаких данных нет. Содержание Основные понятия теории алгоритмов Машина Тьюринга Частично-рекурсивные функции Машина с неограниченными регистрами МНР-вычислимость частично-рекурсивных функций Нумерация вычислимых функций Теорема о параметризации Универсальная вычислимая функция Разрешимые и перечислимые множества Теоремы о разрешимых и перечислимых множествах Нумерация перечислимых множеств Неразрешимые алгоритмические проблемы Теоре...

Новосибирск: НГУ, 2005. – 102 с. Соодержание: Нумерации. Вычислимые нумерации. Вычислимые нумерации конечных семейств и конечных частично упорядоченных множеств. m-сводимость и 1-сводимость. Иерархия Ершова. Табличные сводимости. Вычислимость с оракулом и сводимость по Тьюрингу. Универсальные функции и операция скачка. Арифметическая иерархия. Конструктивные ординалы.

Новосибирск: НГУ, 2005. - 130 с. Курс по теории алгоритмов является составной частью дисциплины "Математическая логика", читаемого на 2-3 курсах механико-математического факультета НГУ. В настоящем курсе подробно рассматриваются конечные автоматы и языки, рекурсивные функции и понятие вычислимости, вопросы сложности вычислений.

Учебное пособие. – СПб: СПб НИУ ИТМО, 2012. – 51 с. Пособие содержит обзор моделей алгоритма: - алгоритмы распознавания регулярных языков конечными автоматами; - свойства читающих, записывающих конечных автоматов и автоматов с выходом; - преобразования блок-схем в конечные автоматы и регулярные выражения; - машины Тьюринга и Поста; - ассоциативные вычисления; - рекурсивные функции. Приводятся задания для преобразования регулярных выражений...

15 слайдов. Свойства алгоритма. Классификация алгоритмов по структуре. Классификация алгоритмов по форме представления. Таблица основных условных обозначений в блок-схемах.

24 слайда//Теория алгоритмов это. Возникновение теории алгоритмов. Модели вычисления. Машина Тьюринга. Машина Поста. Устройство машины Тьюринга.

Автор неизвестен. г. Екатеринбург, 2009. 73 слайда.Происхождение слова алгоритм. Варианты протекания алгоритмического процесса. Основные черты алгоритма. Алгоритмический процесс . Десятая проблема Гильберта. Направления формализации понятия алгоритм. Машина Тьюринга. Нормальные алгорифмы Маркова. Конструктивные объекты.

Понятие алгоритма. Свойства алгоритмов. Дискретность. Детерминированность. Конечность. Массовость. Результативность. Виды алгоритмов. Линейный алгоритм. Циклический алгоритм. Разветвляющийся алгоритм. Вспомогательный алгоритм. Способы описания алгоритмов. Словесный способ. Блок-схемы. Литература. Презентация была использована для защиты реферата Элементы теории алгоритмов. .

Игра «Жизнь» (Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Место действия этой игры — «вселенная» — это размеченная на клетки поверхность. В нашем случае она замкнутая. Каждая клетка на этой поверхности может находиться в двух состояниях: • быть живой; • быть мёртвой. Клетка имеет восемь соседей. Распределение живых клеток в начале игры называется первым поколением....

Учебное пособие. — Москва: МФТИ, 2016. — 138 с. Рассматриваются основы теории рекурсии, ее использование в области разработки рекурсивных алгоритмов и программирования. Приводятся основные сведения о рекурсивных функциях, даны разнообразные примеры рекурсивных алгоритмов. Описаны структуры данных, их компьютерное представление и алгоритмы обработки, знания которых лежат в основе современного программирования. Изложены различные алгоритмы для рабо...

Учебное пособие. — Москва: МФТИ, 2017. — 216 с. Пособие посвящено одному из наиболее интересных и практически ценных разделов информатики и дискретной математики – теории графов. Цель пособия – в весьма ограниченном объеме дать студентам достаточно широкий обзор различных задач теории графов. Рассмотрены базовые алгоритмы решения этих задач с такой степенью доскональности, которая позволила бы использовать полученные знания в практической работе....

18 ст. Вступ. Основні поняття. Властивості кліткових автоматів. Класифікація кліткових автоматів. Одновимірні кліткові автомати. Двовимірні кліткові автомати. Автомати з клітинами без пам'яті. Гра «Життя». Застосування кліткових автоматів. Висновок. Використана література.

Автор Лифшиц Ю.М. РАН СПб. Отделение Математического Института им. В.А. Стеклова, Лаборатория математической логики Содержание Введение Хронология теории алгоритмов Современное состояние теории алгоритмов Использование других наук в алгоритмах Наиболее значимые применения алгоритмов Идеи и техники в теории алгоритмов Формирование популярных направлений исследований Стили проведения научных исследований Заключение и выводы Список источников В эт...

Теоретическая часть - "Жадные алгоритмы". Элементы жадной стратегии. Свойство жадного выбора. Оптимальная подструктура. Алгоритм Хаффмена. Практическая часть - расчет вычислительной сложности алгоритма сортировки методом вставок. 10стр.

Содержание. Введение. Понятие алгоритма. Свойства алгоритмов. Дискретность. Детерминированность. Конечность. Массовость. Результативность. Виды алгоритмов. Линейный алгоритм. Циклический алгоритм. Разветвляющийся алгоритм. Вспомогательный алгоритм. Способы описания алгоритмов. Словесный способ. Блок-схемы. Заключение. Литература. Презентация для защиты реферата.

М.: Мир, 1972. — 624 с. Книга содержит изложение современного состояния теории рекурсивных функций и обзор основных приложений этой теории. В ней прослежено развитие теории рекурсивных функций, начиная с ее зарождения в тридцатых годах и кончая результатами исследований самых последних лет. Не предполагающая в основной своей части никаких предварительных знаний, кроме знакомства с теоретико-множественной терминологией, книга Роджерса написана хор...

Учебное пособие. — Ярославль: ЯрГУ, 2005. — 143 с. — ISBN 5-8397-0382-6. В учебном пособии излагаются основы алгоритмической грамотности (уточнение понятия алгоритма и алгоритмическая неразрешимость, анализ сложности алгоритмов, построение и анализ алгоритмов сортировки и поиска информации, выделение класса труднорешаемых задач). С целью усвоения материала и развития алгоритмических навыков в каждом разделе даются упражнения для самостоятельной р...

М.: Изд-во Моск. гос. ун-та гражд. авиации, 2003. - 237 с. Учебное пособие. Содержание: Множества и мощности. Упорядоченные множества. Логика высказываний. Языки первого порядка. Исчисление предикатов. Вычислимые и универсальные функции. Машины Тьюринга. В основном тексте содержится более 200 задач теоретической направленности.

Учебно-методическое пособие. – М.: Издательский отдел факультета ВМК МГУ, 2014. - 68 с. Методическое пособие посвящено сбалансированным деревьям поиска. В начале пособия рассматриваются деревья поиска общего вида. Далее рассматриваются три вида сбалансированных деревьев поиска: АВЛдеревья, красно-черные деревья и самоперестраивающиеся деревья. Теоретический материал сопровождается иллюстрациями и примерами реализации операций над деревьями на псе...

СПб.: БХВ-Петербург,2011. – 720 с. Второе издание популярного бестселлера "Алгоритмы. Руководство по разработке" раскрывает тайны проектирования алгоритмов, анализа их действенности и эффективности. Развивая успешную концепцию первого издания, книга является отличным практическим руководством по разработке эффективных алгоритмов, содержит практические упражнения и готовые решения 75-ти проблем алгоритмизации. Рассмотрены основы организации данных...

Л.: Наука. 1990. 238с. В сборнике представлены результаты исследований сотрудников лаборатории теории алгоритмов Ленинградского института информатики и автоматизации АН СССР, а также специалистов, сотрудничавших с этой лабораторией. Работы связаны в основном с разработкой и анализом алгоритмов для обработки знаний, анализа изменений и сигналов и для систем компьютерной алгебры. Оглавление. Баранов С. Н. Реализация системы символьных вычислений МИ...

У посібнику запропоновано модель вивчення основ алгоритмізації та програмування з використанням інтегрованого середовища, де на відміну від традиційного підходу головна увага приділяється задачі аналізу на всіх стадіях процесу проектування та реалізації алгоритмів. Описано новий підхід до вивчення поняття складності та вивчення властивостей алгоритмів і вибору оптимального алгоритма, що має величезне значення для порівняння різних алгоритмів і ви...

СПб.: Санкт-Петербургский государственный университет; Санкт-Петербургское отделение Математического института им. В.А.Стеклова (ПОМИ) РАН, Гирш Э.А., 2002 г. Спецкурс прочитан в Санкт-Петербургском государственном университете в 2002 г. Материал включает в себя конспекты 14 лекций по указанному спецкурсу. Задачи поиска. Классы P и NP. СведЕния. NP-полные задачи. Оптимальный алгоритм для NP-задачи… Иерархия по памяти. Сложность недетерминированны...

СПб.: Санкт-Петербургский государственный университет; Санкт-Петербургское отделение Математического института им. В.А.Стеклова (ПОМИ) РАН, Гирш Э.А., 2010 г. Курс лекций, прочитанный в Санкт-Петербургском государственном университете, посвящён оценкам длины доказательств в первую очередь для утверждений логики высказываний, хотя будут рассмотрены и другие языки. Существование системы, в которой есть доказательство полиномиальной длины для каждой...

Учебное пособие по алгоритмам в информатике. Перевод: Кириленко Вадим (главы 1-12), Волошко Роман Владимирович (главы13-19) Москва : Издательство «Э», 2016. - 544 с. - (Мировой компьютерный бестселлер). ISBN 978-5-699-81729-0 Тираж 2000 экз. Алгоритмы — это рецепты, которые делают возможным эффективное программирование. Их изучение позволяет усвоить общие подходы к решению задач и накапливать полезные методики для их решения. В этой книге предста...

Выходные данные не приведены. Автор не известен. — 13 с. Введение. Алгоритмизация. Понятие алгоритма и его свойства. Исполнитель алгоритмов. Заключение. Список использованной литературы.

Пер. с англ. — М.: Факториал, 1998. — 368 с.: ил. — ISBN 5-88688-039-9. Монография содержит систематическое изложение важнейших аспектов теории сложности вычислений. Ее автор — известный американский ученый, крупный специалист в области теории сложности и ее приложений. В книге на высоком научном уровне последовательно и во взаимосвязи рассмотрены основные модели вычислений: схемы, формулы, последовательностные машины (автоматы), машины Тьюринга...

Понятие алгоритма. Примеры. Способы задания. Общие свойства. Необходимость математического уточнения понятия алгоритма. Нормальный алгоритм Маркова. Машины Тьюринга. Сведение любого алгоритма к вычислению числовой функции. Геделевская нумерация объектов. Примитивно рекурсивные функ-ции. Универсальная функция. Существование вычислимых, но не примитивно рекурсивных функций. Частично рекурсивные функции. Тезис Чёрча. Рекурсивные и рекурсивно переч...

Для представленного графа найти остовное дерево с минимальным весом. Провести сравнительный анализ алгоритмов Крускала и Прима по количеству сравнений и присвоений, а также сравнить время выполнения алгоритмов.

Новосибирский государственный университет, С.Л. Березнюк. – 111 с. Содержание: Общий обзор теории алгоритмов. Алфавиты и языки. Конечные представления языков. Конечные автоматы. Регулярные и нерегулярные языки Минимизация числа состояний. Контекстно-свободные грамматики и языки. Нормальные алгорифмы Маркова. Машины Шенфилда. Частично вычислимые функции. Кодирование конечных последовательностей. Универсальные функции. Вычислимые и вычислимо-переч...

28 с. (Автор не указан). Содержание: Методы разработки алгоритмов. Жадные алгоритмы. Эвристические алгоритмы. Абстрактные типы данных. Введение. АТД дерево (TREE). АТД множество (SET). АТД словарь (DICTIONARY). АТД очередь с приоритетом (PRIORITYQUEUE). Задачи на графах. Определение компонент сильной связности ориентированного графа. Поиск точек сочленения в неориентированном графе. Поиск мостов в неориентированном графе. Кратчайшие пути. Алгорит...

Шпаргалка ДНУ Теория алгоритмов ФФЭКС 3 курс 55 вопросов. Вопросы: Понятие алгоритма. Алгоритм Евклида. Основные свойства алгоритмов. Метод математической индукции как метод доказательства справедливости алгоритмов. Метод доказательства справедливости произвольного алгоритма. Множество, подмножество, множество-степень. Операции над множествами. Отношения между множествами. Разбиение на систему множеств. Кортеж. Прямое произведение множеств. Степе...

Для контроля знаний предлагается программа ASSIST2, для которой приведены тесты по дисциплине "Теория алгоритмов". Содержатся вопросы по машинам Тьюринга и Поста. Дружеский интерфейс позволяет автоматически получить оценку по пятибальной системе.

Учебное пособие. Москва, МИФИ, 2008. 176 стр. - ISBN 978-5-7262-1078-0 Книга посвящена теории алгоритмов и содержит основные сведения о свойствах алгоритмов и способах их формального представления (машины Тьюринга, алгоритмы Маркова, рекурсивные функции). Изложены основы теории бесконечных множеств, рассмотрены вопросы нахождения эффективных процедур для перечисления объектов различной природы. Затронуты проблемы алгоритмической неразрешимости и...

Учебное пособие. Москва, МИФИ, 2008. 176 стр. - ISBN 978-5-7262-1078-0 Книга посвящена теории алгоритмов и содержит основные сведения о свойствах алгоритмов и способах их формального представления (машины Тьюринга, алгоритмы Маркова, рекурсивные функции). Изложены основы теории бесконечных множеств, рассмотрены вопросы нахождения эффективных процедур для перечисления объектов различной природы. Затронуты проблемы алгоритмической неразрешимости и...

М.: НИЯУ МИФИ, 2011. – 132 с. Даны базовые понятия теории алгоритмов, основные определения, свойства и теоремы. Теоретическая часть изложена кратко и носит справочный характер, цель – дать основу для решения практических задач и подготовки к сдаче экзамена. В каждом разделе приведены типовые задачи и вопросы с подробными решениям. Материал ориентирован на темы, изучаемые на третьем семестре НИЯУ МИФИ в рамках дисциплины «Дискретная математика (Те...

Учебное пособие. — Самара, 2002. — 44 с. Пособие содержит краткую теорию и варианты заданий по теории алгоритмов, включающих разделы, связанные с машинами Тьюринга, нормальными алгоритмами Маркова, а также теории рекурсивных функций. Рассматриваются также вопросы, связанные с теорией предикатов.

М. : Советское радио, 1974 . – 200 с. Книга является общедоступным введением в теорию алгоритмов и рассматривает круг вопросов, лежащих на грани между математической логикой и теорией автоматических вычислительных машин. Рассчитана на широкий круг читателей, интересующихся кибернетикой, вычислительной математикой и техникой.

Рассмотрены в популярной форме основные вопросы теории алгоритмов и связь этой теории с современной математикой. Государственное издательство технико-теоретической литературы. М. :1957, 99 стр.

Учебное пособие. М.: НАУКА, ФИЗМАТЛИТ, 2007. – 376 с. Разработка и анализ компьютерных алгоритмов — новая дисциплина, возникшая на стыке дискретной математики, программирования и классической теории алгоритмов, играющая важную роль в современных компьютерных технологиях. Для большинства практически значимых задач, решаемых сегодня с использованием компьютеров, существуют разнообразные алгоритмы их решения. Этот факт приводит к тому, что разработч...

Учебное пособие. — М.: МГАПИ, 2003. — 47 с., 80 с. Предлагаемое издание рекомендуется в качестве учебного пособия для подготовки студентов различных специальностей, изучающих математическую логику и теорию алгоритмов. Издание может быть использовано в качестве учебного пособия по разделу «Математическая логика» дисциплины «Математическая логика и теория алгоритмов». В первой части учебного пособия рассмотрены основы таких разделов математической...

2-е изд., исправленное. — М.: МЦНМО, 2009. — 48 с. — ISBN 978-5-94057-485-9. Файл: отскан. страницы (b/w 600 dpi) + OCR + букмарки. Брошюра написана по материалам лекции, прочитанной автором 23 июля 2005 года в летней школе «Современная математика» в Дубне. Она посвящена формализации такого интуитивно ясного термина, как «случайность». В брошюре рассматривается четыре разных подхода к этому понятию, основанных на характерных свойствах случайных п...

2-е изд., исправленное. — М.: МЦНМО, 2009. — 48 с. — ISBN 978-5-94057-485-9. Файл: отскан. страницы (b/w 600 dpi) + OCR + букмарки. Брошюра написана по материалам лекции, прочитанной автором 23 июля 2005 года в летней школе «Современная математика» в Дубне. Она посвящена формализации такого интуитивно ясного термина, как «случайность». В брошюре рассматривается четыре разных подхода к этому понятию, основанных на характерных свойствах случайных п...

М.: МЦНМО, 2010.— 556 с. Классическая (шенноновская) теория информации измеряет количество информации в случайных величинах. В середине 1960-х годов А. Н. Колмогоров (и другие авторы) предложили измерять количество информации в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект. Это определение послужило основой для алгоритмической теории информации, а также для алго...

М., Наука, 1987г. -288 с. Важнейшие достижения теории алгоритмов. Приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Влияние теории алгоритмов на алгоритмическую практику. Содержание: Основные математические приложения теории алгоритмов: 1. Исследование массовых проблем. 2. Приложения к основаниям математики. 3. Приложения к математической логике. 4. Вычислимый анализ. Нумерованные структуры. 5....

Предисловие. обозначения и терминология. введение. предварительные понятия теории алгоритмов: конструктивные объекты и их ансамбли, локальные свойства и локальные действия. Общее понятие алгоритма как самостоятельное (отдельное) понятие. Представительные вычислительные модели. Общее понятие исчисления как самостоятельное. (отдельное) понятие. Представительные порождающие модели. Выяснение связей между алгоритмами и исчислениями. Время и емкость к...

Учебно-методическое пособие. — Шахты : ГОУ ВПО «ЮРГУЭС», 2011. — 66 с. Учебно-методическое пособие охватывает традиционные разделы математической логики и теории алгоритмов. Значительное место в пособии занимает описание методов, наиболее часто применяемых на практике при решении задач математической логики и теории алгоритмов. В пособии рассмотрено достаточное количество практических задач, иллюстри- рующих теоретический материал. Рекомендовано...

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН, 2010. – 26 слайдов. Содержание: RAM — random access machine. RAM: набор команд. RAM: моделирование FOR через GOTO. RAM: меры сложности алгоритмов. Машина Тьюринга. Симулятор Машины Тьюринга. Машина Тьюринга: Удвоение строки. Машина Тьюринга: Унарное сложение. Машина Тьюринга: Распознавание четных строк. Машина Тьюринга: «Одинаковое количество 0 и 1?» Универсальная Машина Тью...

М.: Лаборатория знаний, 2016. - 250 с. «Золотой билет» – великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны «железного занавеса», и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию. Для студентов и специал...

Международный журнал прикладных и фундаментальных исследований. — 2016. — № 7-1. — С. 131-132. Рассматривается возможность применения к решению задачи КОММИВОЯЖЕР «скупого» метода, суть которого заключается в том, что, уже имея оптимальный путь, новая точка добавляется так, чтобы прирост пути был минимальным.

М.: Интуит, 2016. — 336 с. Курс содержит задачи по программированию различной трудности. Большинство задач приводятся с решениями. Цель курса - научить основным методам построения корректных и быстрых алгоритмов. Курс будет полезен учителям информатики, старшеклассникам, студентам младших курсов высших учебных заведений. Курс может быть использован на кружковых и факультативных занятиях в общеобразовательных учреждениях, в школах с углубленным из...

Ответы на вопросы: Машина Тьюринга. Конструирование МТ. Вычислимые по Тьюрингу функции: ПРФ, ЧРФ. Правильная вычислимость. Уточнение понятия алгоритма через машину с неограниченными регистрами. нормальные алгоритмы Маркова. Вычислимые функции и разрешимые множества: вычислимость, разрешимость, перечислимость, множество n-ок нат чисел, диагональная конструкция, главные универсальные функции, универсальная ОРФ, перечислимое неразрешимое множество.r...

Издательство Chapman&Hall/CRC Press, 2010, -990 pp. The design and analysis of algorithms and data structures form the foundation of computer science. As current algorithms and data structures are improved and new methods are introduced, it becomes increasingly important to present the latest research and applications to professionals in the field. This series aims to capture new developments and applications in the design and analysis of al...

Chapman and Hall/CRC, 2009. - 950 pages. Algorithms and Theory of Computation Handbook, Second Edition: Special Topics and Techniques provides an up-to-date compendium of fundamental computer science topics and techniques. It also illustrates how the topics and techniques come together to deliver efficient solutions to important practical problems. Along with updating and revising many of the existing chapters, this second edition contains mo...

Издательство InTech, 2008, -596 pp. Сборник статей The greedy algorithm is one of the simplest approaches to solve the optizmization problem in which we want to determine the global optimum of a given function by a sequence of steps where at each stage we can make a choice among a class of possible decisions. In the greedy method the choice of the optimal decision is made on the information at hand without worrying about the effect these decisio...

Computing Research Repository, 2008, -81 pp. We survey the average-case complexity of problems in NP. We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but somewhat artificial) NP problem is easy-on-average with respect to the uniform distribution, then all problems in NP are easy-on-average with respect...

Prentice Hall, 1988. - 302 pages. From the Preface of the book: Our book is neither a programming manual nor an account of the proper use of data structures. Still less is it a "cookbook" containing a long catalogue of programs ready to be used directly on a machine to solve certain specific problems, but giving at best a vague idea of the principles involved in their design. On the contrary, the aim of our book is to give the reader some basic...

College Publications, 2004. 256 pages. На англ. языке. ISBN-10: 9780954300647 ISBN-13: 978-0954300647 Хорошая коллекция алгоритмов сравнения и поиска строк: от классики (Кнут-Морис-Пратт) до кластерных алгоритмов. С подробными описаниями и вставками кода на C. String matching is a very important subject in the wider domain of text processing. It consists of finding one,or more generally, all the occurrences of a string (more generally called a...

This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor.Each chapter presents an algorithm, a design technique, an application area, or a related topic. Algorithms are...

Издательство Springer, 2006, -494 pp. Parameterized complexity theory provides a framework for a refined analysis of hard algorithmic problems. Classical complexity theory analyzes and classifies problems by the amount of a resource, usually time or space, that is required by algorithms solving them. It was a fundamental idea, going back to the work of Hartmanis and Stearns in the early 1960s, to measure the required amount of the resource as a...

Kluwer Academic Publishers, 1992. - 585 pages. Algorithms for Computer Algebra is the first comprehensive textbook to be published on the topic of computational symbolic mathematics. The book first develops the foundational material from modern algebra that is required for subsequent topics. It then presents a thorough development of modern computational algorithms for such problems as multivariate polynomial arithmetic and greatest common divis...

Издательство Cambridge University Press, 2008, -632 pp. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by...

Издательство Cambridge University Press, 2010, -216 pp. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by...

Birkhauser, 1981. - 107 pages. A quantitative study of the efficiency of computer methods requires an in-depth understanding of both mathematics and computer science. This monograph, derived from an advanced computer science course at Stanford University, builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms, emphasizing the more difficul...

Из серии Foundations and Trends in Theoretical Computer Science издательства NOWPress, 2009, -110 pp. Spectral methods refer to the use of eigenvalues, eigenvectors, singular values, and singular vectors. They are widely used in Engineering, Applied Mathematics, and Statistics. More recently, spectral methods have found numerous applications in Computer Science to discrete as well as continuous problems. This monograph describes modern applicati...

Издательство Springer, 2008, -1219 pp. Серия Springer Reference The Encyclopedia of Algorithms aims to provide the researchers, students, and practitioners of algorithmic research with a mechanism to efficiently and accurately find the names, definitions, key results, and further readings of important algorithmic problems. The work covers a wide range of algorithmic areas, and each algorithmic area is covered by a collection of entries. An encyc...

Издательство Springer, 2006, -405 pp. The course serves a dual purpose: to cover core material in the foundations of computing for graduate students in computer science preparing for their PhD qualifying exams, and to provide an introduction to some more advanced topics in the theory of computational complexity for those intending to pursue further study in the area. The course is thus a mixture of core and advanced material. Most of the course...

Communication Complexity, New York, Cambridge University Press 1997, ISBN 978-0-521-56067-2, pp. I-XIII, 1- 189. [j19]. Communication Complexity surveys this mathematical theory, concentrating on the question of how much communication is necessary for any particular process. The first part of the book is devoted to the simple two-party model introduced by Yao in 1979, which is still the most widely studied model. The second part treats newer mode...

Из серии Foundations and Trends in Theoretical Computer Science издательства NOWPress, 2009, -127 pp. We survey lower bounds in communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure such as rank, or the trace norm that serves as a lower bound to the unde...

Издательство Springer, 2010, -222 pp. Does P=NP?. In just five symbols Dick Karp –in 1972–captured one of the deepest and most important questions of all time. When he first wrote his famous paper, I think it’s fair to say he did not know the depth and importance of his question. Now over three decades later, we know P=NP is central to our understanding of computation, it is a very hard problem, and its resolution will have potentially tremendou...

Издательство Springer, 1998, -337 pp. Proof Verification and Approximation Algorithms - Hardly any area in theoretical computer science has been more lively and flourishing during the last few years. Different lines of research which had been developed independently of each other over the years culminated in a new and unexpected characterization of the well-known complexity class NP, based on probabilistically checking certain kinds of proofs. T...

Издательство McGrow-Hill, 1967, -504 pp. In addressing the American Mathematical Society in 1944, E. L. Post concluded, "Indeed, if general recursive function is the formal equivalent of effective calculability, its formulation may play a role in the history of combinatory mathematics second only to that of the formulation of the concept of natural number." This book may be viewed as a progress report on some of the ideas and hopes expressed in...

Книга профессора прикладной математики из Массачу?сетского технологи?ческого институ?та. Русского преревода, к сожалению, не существует (или я не нашел). Очень полезная книжка. В Маи по ней читаются лекции по Сппо. Michael Sipser Welcome! You are about to embark on the study of a fascinating and important subject. the theory of computation. It comprises the fundamental mathematical proper. ties of computer hardware, software, and certain applic...

Издательсто Elsiever/MIT Press, 1990, -1010 pp. Всеобъемлющий справочник о различных типах сложности алгоритмов и вычислений Machine Models and Simulations A Catalog of Complexity Classes Machine-Independent Complexity Theory Kolmogorov Complexity and its Applications Data Structures Computational Geometry Algorithmic Motion Planning in Robotics Average-Case Analysis of Algorithms and Data Structures Graph Algorithms Algorithms in Number Theory...

Издательство Springer, 2005, -306 pp. Complexity theory – is it a discipline for theoreticians who have no concern for the real world or a central topic of modern computer science? In this introductory text, complexity theory is presented as an active area of computer science with results that have implications for the development and use of algorithms. Our study will lead to insights into the structure of important optimization problems and wil...