В.В.Воеводин.
Вычислительная математика и структура алгоритмов.


В 2006 году в издательстве Московского университета выпущено учебное пособие:
В.В.Воеводин "Вычислительная математика и структура алгоритмов.".-М.: Изд-во МГУ, 2006.-112 с.
ISBN 5-211-05310-9



Скачать полный текст: PDF (916 Кбайт). Частичная или полная перепечатка данного издания возможна только с разрешения Вл.В.Воеводина.

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

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


Оглавление:

  • Введение (pdf)
  • Лекция 1. Большие задачи и большие компьютеры (pdf)
    • Компьютеры как эффективный инструмент численных исследований. Дискретизация объектов. Примеры больших задач - моделирование климатической системы и обтекание летательных аппаратов. Взаимосвязь компьютеров и задач. Необходимость создания больших вычислительных систем. Этапы численного эксперимента.
  • Лекция 2. Большие задачи и программирование (pdf)
    • Интересы специалистов и программирование. Предельно сложные задачи. Совершенствование техники и программирование. Преемственность программных наработок. Переносимость программного обеспечения. Отсутствие гарантий качества компиляции. Простые примеры. Необходимость изучения структуры алгоритмов.
  • Лекция 3. Компьютеры и параллельные формы алгоритмов (pdf)
    • Абстрактная модель последовательного компьютера. Влияние последовательных вычислений. Развитие параллелизма в компьютерах. Концепция неограниченного параллелизма. Граф алгоритма. Необходимость новых сведений о структуре алгоритмов. Параллельная форма алгоритма. Абстрактная модель параллельной системы.
  • Лекция 4. Характеристика вычислительных процессов (pdf)
    • Простое и конвейерное функциональное устройство. Загруженность. Производительность. Ускорение. Система устройств. Влияние связей между устройствами. Законы Амдала и следствия.
  • Лекция 5. Математически эквивалентные преобразования (pdf)
    • Математически эквивалентные преобразования. Алгебраические законы на практике не выполняются. Эквивалентные преобразования и устойчивость. Эквивалентные преобразования и число операций. Эквивалентные преобразования и параллелизм вычислений. Принцип сдваивания. Информационное ядро алгоритма. Снова граф алгоритма. Граф алгоритма и ошибки округления. Оценка параллелизма алгоритма снизу.
  • Лекция 6. Компьютеры и ошибки округления (pdf)
    • Позиционные системы счисления. Ошибки округления. Наилучшее округление. Преимущества сокращенных систем счисления. Фиксированная и плавающая запятая. Машинный нуль. Точность представления чисел. Обоснование вероятностных свойств ошибок округления. Особенность операций сложения и вычитания. Двоичная система счисления не является лучшей. Ошибки округления иногда помогают.
  • Лекция 7. Развертки и граф-машина (pdf)
    • Строгие и обобщенные развертки. Развертки и параллелизм в алгоритмах. Компьютерная интерпретация. Граф-машина. Теорема о гомоморфной свертке графа. Параллельная структура. Макро- и микропараллелизм. Расщепляющие развертки. Полумодуль обобщенных разверток. Направленные графы. Линейные развертки. Расщепление алгоритма на фрагменты. Рекуррентные соотношения. Регулярные графы.
  • Лекция 8. Новый математический аппарат (pdf)
    • Выбор формы описания алгоритмов. Линейный класс программ. Пространство итераций. Размещение вершин графа. Покрывающие функции. Теорема об информационном покрытии. Инвариантность линейных многогранников. Кусочно-линейные развертки. Теорема о кусочно-линейных развертках. Косвенная адресация и хаос в дугах. Унифицированное описание алгоритмов. Локальные алгоритмы и графы. Задача укладки графа.
  • Лекция 9. Типовые информационные структуры (pdf)
    • Перемножение матриц. Решение треугольных систем. Неожиданный эффект. Система с блочно-двухдиагональной матрицей. Макро- и микрореализации. Явная схема для уравнения теплопроводности. Макро- и микропараллелизм. Локальный алгоритм. Очень "простой" пример. Гипотеза о типовых структурах.
  • Лекция 10. Параллельные вычисления и математическое образование (pdf)
    • Что заставляет менять образование. Параллельные вычисления на стыке дисциплин. Последовательные вычисления маскируют проблемы развития. Необходимость учить решать задачи эффективно. Причина многих трудностей - незнание структуры алгоритмов. Возможные пути изменения ситуации.
  • Рекомендуемая литература (pdf)


© Лаборатория Параллельных информационных технологий НИВЦ МГУ