AAA
Обычный Черный



Кто не делится найденным, подобен свету в дупле секвойи (древняя индейская пословица)

версия для печатиВерсия для печати



Библиографическая запись: Вопросы. — Текст : электронный // Myfilology.ru – информационный филологический ресурс : [сайт]. – URL: https://myfilology.ru//165/teoriya-algoritmov/voprosy/ (дата обращения: 19.10.2021)

Вопросы

Вопросы

Содержание

    Понятия (определения) алгоритмов

    Алгоритмы и автоматы

    Машины Тьюринга

    Рекурсивные функции

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

    Модели автоматов (Мура, Мили)

    Диаграммы состояний

    Детерминированные и недетерминированные автоматы

    1. Динамическое программирование. Основные принципы, примеры алгоритмов: выравнивание текста по ширине, выравнивание
    последовательностей.

    2. Основные алгоритмы на графах. Представление графов в виде списков смежности и матрицы смежности. Обход графа в глубину и ширину. Связность в ориентированных и неориентированных графах. Двунаправленный поиск путей в графах. Поиск кратчайших путей во взвешенном графе, алгоритмы Беллмана – Форда, Флойда – Уоршелла. Поиск кратчайших путей в графе при помощи алгоритма Дейкстры. Минимальные остовные деревья: алгоритмы Прима и Крускала.

    3. Структуры данных. Система непересекающихся множеств. Хеш-таблицы. Самоорганизующиеся списки и конкурентный анализ онлайн-алгоритмов.

    4. Потоки в сетях. Определение потока, циркуляции. Задача о максимальном потоке. Алгоритм Форда – Фалкерсона. Максимальный поток и минимальный разрез. Максимальное паросочетание в двудольном графе. Совершенное паросочетание с минимальным весом во взвешенном двудольном графе.

    5. Конечные автоматы, регулярные выражения, контекстно-свободные грамматики. Конечные автоматы. Регулярные языки. Замкнутость регулярных языков по объединению. Минимизация конечного автомата. Регулярные выражения. Недетерминированные конечные автоматы. Замкнутость регулярных языков относительно регулярных операций. Построение конечного
    автомата по регулярному выражению. Эквивалентность регулярных выражений и конечных автоматов. Нерегулярные языки. Лемма о накачке. Контекстно-свободные грамматики. Автоматы с магазинной памятью. Эквивалентность контекстно-свободных грамматик и автоматов с магазинной памятью. Построение автомата по грамматике. Лемма о накачке для контекстно-свободных языков. 

    Основная литература


    1. Вирт Н. Алгоритмы и структуры данных. – М.: ДМК Пресс, 2012. – 272 с.
    2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: учеб. Пособие. - М.: Издательский дом «Вильямс», 2008. – 369 с.К
    3. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 2- е издание: Пер. с англ. — М.: Вильямс, 2007. 
    4. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МНЦМО, 2014.
     

    Дополнительная литература


    1. Сенилов М.А. Методические указания для самостоятельной работы студентов по дисциплине «Структуры и алгоритмы обработки данных в ЭВМ». – Ижевск: Изд-во ижгту, 2008.
    2. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных: учеб. Пособие. – М.: Финансы и статистика; ИРФРА-М, 2009. – 304 с.
    3. Кнут Д. Искусство программирования для ЭВМ. Том 1.: Основные алгоритмы. - М.: Издательский дом «Вильямс», 2008. – 690 с.
    4. Кнут Д. Искусство программирования для ЭВМ. Том 3.: Сортировка и поиск. - М.: Издательский дом «Вильямс», 2008. – 720 с.
    5. Бабенко М.А., Левин М.В. Введение в теорию алгоритмов и структур данных. – М.: ФМОП, МЦНМО, 2012. – 144 с.
    6. Круз Р.Л. Структуры данных и проектирование программ. – М.: БИНОМ. Лаборатория знаний, 2012. – 765 с.
    7. Окулов С.М. Абстрактные типы данных. – М.: БИНОМ. Лаборатория знаний, 2013. – 250 с.

    14.06.2021, 47 просмотров.


    Уважаемые посетители! С болью в сердце сообщаем вам, что этот сайт собирает метаданные пользователя (cookie, данные об IP-адресе и местоположении), что жизненно необходимо для функционирования сайта и поддержания его жизнедеятельности.

    Если вы ни под каким предлогом не хотите предоставлять эти данные для обработки, - пожалуйста, срочно покиньте сайт и мы никому не скажем что вы тут были. С неизменной заботой, администрация сайта.

    Dear visitors! It is a pain in our heart to inform you that this site collects user metadata (cookies, IP address and location data), which is vital for the operation of the site and the maintenance of its life.

    If you do not want to provide this data for processing under any pretext, please leave the site immediately and we will not tell anyone that you were here. With the same care, the site administration.