Теория вычислительных систем

Основы теории вычислительных систем

4.2. Содержание разделов дисциплины

(указывается название каждого раздела, количество часов, отводимое на изучение, и его содержание)

Раздел 1. Предмет, задачи и методы теории вычислительных систем

(лекции -2 часа).

Основные понятия и определения. Предмет теории вычислительных систем. Классификация вычислительных систем. Основные задачи теории вычислительных систем. Общая характеристика методов теории вычислительных систем.

Раздел 2. Концепция открытых систем — (лекции — 4 часа)

Проблема «открытых информационных систем».Взаимодействие открытых систем и переносимость программ — основа технологии открытых систем. Единое информационное пространство и его компоненты: информационные ресурсы, организационные структуры, средства информационного взаимодействия.

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

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

Терминология открытых систем. Определение «Открытая система» в соответствии с IEEEPOS1X1003.0.Эталонная модель функциональнойсреды открытых систем. Интерфейсы для обеспечения взаимодействия между прикладным программным обеспечением и прикладной платформой, между прикладной платформой и внешней средой. Виды услуг для функционального обслуживания. Функциональная вычислительная среда открытых систем (OSE) для поддержки переносимых, масштабируемых и взаимодействующих прикладных программ через стандартные услуги, интерфейсы, форматы и протоколы. Интерфейс прикладной программы (API) между прикладным программным обеспечением и прикладной платформой и интерфейс с внешней средой (EEI), обеспечивающий передачу информации между прикладной платформой ивнешней средой. Профили OSE и АРР; Области услуг профиля АРР.

Раздел 3. Основы методологии проектирования информационно -вычислительных систем — (лекции — 4 часа).

Тенденции развития современных информационных технологий. Особенности. современных крупных проектов ИВС:

Основы методологии проектирования информационно -вычислительных систем. Жизненный цикл программного обеспечения ИВС. Нормативные документы, регламентирующим жизненный цикл программного обеспечения: международный стандарт ISO/IEC.

Структура жизненного цикла, определяющая процессы, действия и задачи, которые должны быть выполнены во время создания ПО. Модели жизненного цикла: каскадная и спиральная.

Методологии, технологии и инструментальные средства проектирования ИВС. Общие требования к технологии проектирования, разработки и сопровождения ИВС. Стандарты проектирования, оформления проектной документации и интерфейсов пользователя.

Раздел 4. Программы, вычислительные процессы и их модели (лекции — 2 часа)

Логическая организация и порядок выполнения программ. Сложность задач и потребность в ресурсах памяти. Трудоемкость алгоритмов и марковские модели вычислительных процессов.

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

Такая машина допускает слово, если существует последовательность переходов, переводящая машину в допускающее состояние. В связи с этим есть несколько вариантов представления работы НМТ:

  1. Можно считать, что машина «очень удачлива», то есть если есть способ попасть в допускающее состояние, то машина всегда делает верный выбор пути.
  2. Если есть несколько вариантов пути, то машина делится на копии, каждая из которых следует по одному из возможных переходов. Слово считается допущенным, если его допускает хотя бы одна из копий.

Для записи недетерминированных программ используется специальный оператор.

Определение:
Оператор [math]\leftarrow?[/math] — недетерминированный выбор (недетерминированное присваивание).

теория вычислительных систем

Запись [math]x\leftarrow?A[/math] означает, что переменной [math]x[/math] недетерминированно присваивается некоторое значение из множества [math]A[/math].

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

Определение:
Недетерминированная программа — программа, в которой допускается использование недетерминированного выбора.
Определение:
Язык недетерминированной программы — множество слов, для которых существует такая последовательность недетерминированных выборов, что программа допустит это слово.

Классы NTIME и NSPACE[править]

Определение:
[math]\mathrm{NTIME}(f(n))[/math] — множество языков, для которых существует недетерминированная распознающая программа, время работы которой на входе длины [math]n[/math] есть [math]O(f(n))[/math].
[math]\mathrm{NSPACE}(f(n))[/math] — множество языков, для которых существует такая недетерминированная распознающая программа, что на любом входе длины [math]n[/math] ей требуется [math]O(f(n))[/math] памяти.

См. также[править]

  • Квантовые вычисления

    Александр Разборов

    Пожалуй ни одно другое достижение современной теории сложности вычислений не вызывает такого живого интереса и не менее яростных споров как модель квантовых вычислений. Предметом дискуссии, однако, в основном является возможность физической реализации квантового компьютера, чего мы, к счастью, касаться не будем. Вместо этого мы попробуем разобраться в чисто математических аспектах этой модели и, в частности, постараемся пройти столько из нижеследующего, сколько позволит время: Классические и квантовые схемы; Алгоритм Шора быстрого разложения чисел на множители: основные идеи; Квантовые оракулы и задача о скрытой подгруппе; Алгоритм квантового поиска Гровера.
  • Алгебраическая сложность

    Александр Разборов

    Как грамотно вычислить значение полинома от многих переменных? Можно, конечно, посчитать по отдельности каждый входящий в него моном и результаты сложить, но нельзя ли придумать способ сэкономить на числе используемых операций хотя бы для некоторых наиболее важных и часто встречающихся полиномов?

    Функции и графы

    Изучением таких вопросов как раз и занимается теория алгебраической сложности вычислений. Оказывается, что для некоторых классов полиномов ответ отрицателен, для других он положителен, а в подавляющем большинстве случаев ответ неизвестен. Соответствующие вопросы, открытые в течении нескольких десятилетий, по праву числятся среди наиболее важных, интересных и трудных проблем современной теории сложности.

  • Эволюционные алгоритмы

    Мультфильм рассказывает об использовании идеи биологической эволюции в задачах искусственного интеллекта, истории эволюционных алгоритмов и принципах их работы. Все это подробно изучается на магистерской программе Университета Иннополис «Робототехника». Историю об эволюционных алгоритмах нам помог рассказать доцент, руководитель Лаборатории искусственного интеллекта в разработке игр Университета Иннополис Джозеф Браун.

  • Эволюционные алгоритмы

    Джозеф Браун

    На чем основаны генетические алгоритмы? Как происходит создание различных уровней в компьютерной игре? Каковы перспективы применения эволюционных алгоритмов? На эти и другие вопросы отвечает доцент Университета Иннополис Джозеф Браун. Процедурная генерация контента в играх — это процесс автоматического создания различных ресурсов. Таким образом можно создавать повествование или сюжет игры или более простые объекты, такие как деревья. Или какие-нибудь элементы игрового процесса. Например, какие будут уровни. Этим я в основном и занимаюсь: как создать уровень, который отвечает некоторым ожиданиям игрока и некоторым ожиданиям в контексте повествования. Я использую много приемов из области, которая называется вычислительный интеллект. А вычислительный интеллект применяет биоинспирированные методы для решения сложных задач оптимизации.

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

    Александр Шень

    Какова история создания машины Тьюринга? Как она повлияла на развитие идей, лежащих в основе ряда современных технологий? Какие проблемы существуют в теории вычислительной сложности? И как математика рассматривает понятие случайность? Об идее универсальной машины, проблеме перебора и случайности рассказывает кандидат физико-математических наук Александр Шень.

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

    Валерий Опойцев

    Исходные понятия. Полиномиальные и экспоненциальные алгоритмы. Задачи распознавания и оптимизации. Определение классов P и NP. Совпадает ли P с NP или не совпадает — вопрос на миллион долларов. Машина Тьюринга как универсальный вычислительный прибор. Опорные комбинаторные задачи: коммивояжера, клика, изоморфизм графов, паросочетание, рюкзак, целочисленное линейное программирование (ЦЛП), транспортная задача. В двух словах о непрерывной задаче линейного программирования. Теорема Кука.
  • Колмогоровская сложность

    Алексей Сосинский

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

  • Вычисляемые знания и будущее чистой математики

    Стивен Вольфрам

    В вычислительной математике обычно ставится конкретная вычислительная задача, которая затем решается с целью получить результат — в точности как типичный сеанс работы в Mathematica. В чистой математике, напротив, берутся некоторые математические объекты, результаты или структуры, формируются некоторые гипотезы относительно них и потом приводятся доказательства верности выдвинутых гипотез. Большое число чистых математиков продолжает делать всё точно также, как это делалось веками — от руки и на бумаге. Как же эффективно привнести технологии в такой рабочий процесс?
  • Доказательство теоремы о тройках заняло 200 терабайт

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

  • Невычислимость, неразрешимость, недоказуемость (Тюринг → Колмогоров → Чейтин → Гёдель)

    Алексей Сосинский

    Курс занятий посвящен тому, что в математике сделать нельзя. Но речь пойдет не о запрещенных действиях (типа деления на ноль или квадратуры круга), а об отсутствии общих методов для решения некоторых широких классов задач.

    Начиная от определения вычислимой функции (через машину Тюринга), мы узнаем про существование универсальной вычислимой функции, и как следствие – о существовании не вычислимых функций. Отсюда мы поймем, какие задачи никакой компьютер (даже сколь угодно мощный) решить не может в принципе. Затем мы определим «Колмогоровскую сложность» и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте – одного из самых значительных научных открытий ХХ-го века.

  • Добавить комментарий

    Закрыть меню