Название: Вычислительная математика и структура алгоритмов
Автор: Воеводин В. В.
Издательство: М.: Изд-во МГУ
Год: 2006
Страниц: 112
Формат: PDF
Размер: 0,84 Мб
ISBN: 5-211-05310-9
Качество: отличное
Язык: русский
Предмет: Математика, Информатика
Описание:В учебном пособии представлены лекции, прочитанные автором в различных учебных заведениях, институтах и на научных конференциях. Все они посвящены вопросам эффективного решения задач на вычислительных системах параллельной архитектуры. Особое внимание уделяется изучению информационной структуры алгоритмов и ее влиянию на разработку эффективно реализуемых программ. Обсуждаются особенности математического образования по отношению к требованиям параллельных вычислений.
Для студентов, аспирантов и научных работников, специализирующихся в области исследования структуры алгоритмов, решения больших задач и создания программного обеспечения для параллельных вычислительных систем.
Содержание
Лекция 1. БОЛЬШИЕ ЗАДАЧИ И БОЛЬШИЕ КОМПЬЮТЕРЫ: Компьютеры как эффективный инструмент численных исследований. Дискретизация объектов. Примеры больших задач - моделирование климатической системы и обтекание летательных аппаратов. Взаимосвязь компьютеров и задач. Необходимость создания больших вычислительных систем. Этапы численного эксперимента.
Лекция 2. БОЛЬШИЕ ЗАДАЧИ И ПРОГРАММИРОВАНИЕ: Интересы специалистов и программирование. Предельно сложные задачи. Совершенствование техники и программирование. Преемственность программных наработок. Переносимость программного обеспечения. Отсутствие гарантий качества компиляции. Простые примеры. Необходимость изучения структуры алгоритмов.
Лекция 3. КОМПЬЮТЕРЫ И ПАРАЛЛЕЛЬНЫЕ ФОРМЫ АЛГОРИТМОВ: Абстрактная модель последовательного компьютера. Влияние последовательных вычислений. Развитие параллелизма в компьютерах. Концепция неограниченного параллелизма. Граф алгоритма. Необходимость новых сведений о структуре алгоритмов. Параллельная форма алгоритма. Абстрактная модель параллельной системы.
Лекция 4. ХАРАКТЕРИСТИКА ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ: Простое и конвейерное функциональное устройство. Загруженность. Производительность. Ускорение. Система устройств. Влияние связей между устройствами. Законы Амдала и следствия.
Лекция 5. МАТЕМАТИЧЕСКИ ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ: Математически эквивалентные преобразования. Алгебраические законы на практике не выполняются. Эквивалентные преобразования и устойчивость. Эквивалентные преобразования и число операций. Эквивалентные преобразования и параллелизм вычислений. Принцип сдваивания. Информационное ядро алгоритма. Снова граф алгоритма. Граф алгоритма и ошибки округления. Оценка параллелизма алгоритма снизу.
Лекция 6. КОМПЬЮТЕРЫ И ОШИБКИ ОКРУГЛЕНИЯ: Позиционные системы счисления. Ошибки округления. Наилучшее округление. Преимущества сокращенных систем счисления. Фиксированная и плавающая запятая. Машинный нуль. Точность представления чисел. Обоснование вероятностных свойств ошибок округления. Особенность операций сложения и вычитания. Двоичная система счисления не является лучшей. Ошибки округления иногда помогают.
Лекция 7. РАЗВЕРТКИ И ГРАФ-МАШИНА: Строгие и обобщенные развертки. Развертки и параллелизм в алгоритмах. Компьютерная интерпретация. Граф-машина. Теорема о гомоморфной свертке графа. Параллельная структура. Макро- и микропараллелизм. Расщепляющие развертки. Полумодуль обобщенных разверток. Направленные графы. Линейные развертки. Расщепление алгоритма на фрагменты. Рекуррентные соотношения. Регулярные графы.
Лекция 8. НОВЫЙ МАТЕМАТИЧЕСКИЙ АППАРАТ: Выбор формы описания алгоритмов. Линейный класс программ. Пространство итераций. Размещение вершин графа. Покрывающие функции. Теорема об информационном покрытии. Инвариантность линейных многогранников. Кусочно-линейные развертки. Теорема о кусочно-линейных развертках. Косвенная адресация и хаос в дугах. Унифицированное описание алгоритмов. Локальные алгоритмы и графы. Задача укладки графа.
Лекция 9. ТИПОВЫЕ ИНФОРМАЦИОННЫЕ СТРУКТУРЫ: Перемножение матриц. Решение треугольных систем. Неожиданный эффект. Система с блочно-двухдиагональной матрицей. Макро- и микрореализации. Явная схема для уравнения теплопроводности. Макро- и микропараллелизм. Локальный алгоритм. Очень "простой" пример. Гипотеза о типовых структурах.
Лекция 10. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И МАТЕМАТИЧЕСКОЕ ОБРАЗОВАНИЕ: Что заставляет менять образование. Параллельные вычисления на стыке дисциплин. Последовательные вычисления маскируют проблемы развития. Необходимость учить решать задачи эффективно. Причина многих трудностей - незнание структуры алгоритмов. Возможные пути изменения ситуации.
