Количественная оценка информации. Формула Хартли, формула Шеннона.




Заслуга Хартли в том, что он впервые предложил логарифмическую меру количества информации. I=log (N)=log (mn) = n log (m) Формула Шеннона для неравновероятных символов: В случае равновероятных символов она переходит в формулу Хартл. Единицы измерения количества информации. Понятие кодового дерева и его связь с количеством информации.

21. Теория принятия решений
Фридман А.Я.

 

  • 2 основных этапа многокритериальной оптимизации.

 

Постановка задачи критериального анализа, стратегические и тактические задачи планирования. Функции предпочтений, критерии, Парето-оптимальность. 1 этап оптимизации: определение множества эффективных векторных оценок (безусловная оптимизация). 2 этап оптимизации (условная оптимизация): частные критерии и использование дополнительной информации для принятия решения (нормализация критериев и методы построения обобщенного критерия).
  • Аксиома Парето и эффективные варианты. Определение множества Парето в дискретном и непрерывном случаях

 

Формулировка аксиомы Парето. Отличие эффективных вариантов от неэффективных. Способы определения множества Парето в дискретном (метод прямоугольника) и непрерывном (метод отбора конусом) случаях (на примерах).

 

  • Количественная оценка эффективности решений: функция полезности

 

Показатели исхода операции (ПИО) и их связь с показателями эффективности для трех категорий операций (детерминированных, стохастических, с неопределенностью). Полезность исходов операции, ранжирование исходов. Функция полезности: определение и свойства, виды и примеры.

 


22. Технология программирования
Тоичкин Н.А.

 

  • Рекурсивные алгоритмы. Примеры рекурсивных алгоритмов
1. Определение рекурсии. · Рекурсия. · Рекуррентное соотношение. · Рекурсивный алгоритм. · Глубина рекурсии. · Конечность и окончание рекурсивного алгоритма. 2. Схемы прямой (простой) и косвенной (сложной) рекурсии. 3. Реализация механизма рекурсивного вызова процедуры. 4. Рекурсивные данные. 5. Примеры рекурсивных алгоритмов. 6. Рекурсия и итерация.
  • Анализ временной сложности (трудоемкости) алгоритмов

 

  1. Цель анализа временной сложности (трудоемкости) алгоритмов.
  2. Факторы, влияющие на сложность алгоритмов.
· что подсчитывать и что учитывать при анализе сложности. · наилучший, наихудший и средний случай работы алгоритма. · асимптотическая сложность.
  1. Примеры анализа сложности алгоритмов
· внутренняя сортировка массивов (сортировка вставками, сортировка обменом). · бинарный поиск (поиск в отсортированном массиве); · поиск подстроки в строке (примитивный алгоритм, алгоритм КМП).

 


23. Численные методы/Вычислительная математика
Малыгина С.Н.

 

  • Постановка задач аппроксимации функций одной переменной: Интерполирование алгебраическими многочленами.
В основе большинства численных методов математического анализа лежит подмена одной функции (известной, неизвестной или частично известной) другой функцией , близкой к и обладающей «хорошими» свойствами, позволяющими легко производить над нею те или иные аналитические или вычислительные операции. Такая подмена называется аппроксимацией или просто приближением функции функцией . Такую подмену можно сделать разными способами. Интерполирование Постановка задачи, пример возникновения задачи интерполирования   Интерполирование алгебраическими многочленами Пусть на отрезке заданы точки (будем называть их узлами интерполирования), в которых известны значения функции . Задача интерполирования алгебраическими многочленами состоит в том, чтобы построить многочлен степени , (1) значения которого в заданных точках совпадают со значениями функции в этих точках. Для любой непрерывной функции сформулированная задача имеет единственное решение. Действительно, для отыскания коэффициентов получаем систему линейных уравнений (2) Если среди нет совпадающих, то определитель системы (1.2) отличен от нуля, и следовательно система имеет единственное решение. Определение Многочлен , удовлетворяющий условию (3) называется интерполяционным многочленом для функции , построенным по узлам . Решение системы (1.2) можно записать различным образом. Наиболее употребительна запись интерполяционного многочлена в форме Лагранжа и в форме Ньютона. Интерполяционный многочлен Лагранжа имеет вид (4) Интерполяционная формула Ньютона позволяет выразить интерполяционный многочлен через значения в одном из узлов и через разделенные разности функции , построенные по узлам . Интерполяционным многочленом Ньютона называется многочлен , (5) где - разделенные разности. Интерполяционную формулу Ньютона удобнее применять в том случае, когда интерполируется одна и та же функция , но число узлов интерполирования увеличивается. Если узлы интерполяции фиксированы и интерполируется не одна, а несколько функций, то удобнее пользоваться формулой Лагранжа.
  • Методы решения систем линейных алгебраических уравнений
План ответа: · Постановка задачи · Прямые методы (определение, примеры) · Итерационные методы (определение, понятие одношаговых и двухшаговых методов, условия окончания итераций, каноническая форма записи итерационных методов, понятие стационарных, нестационарных, явных и неявных методов, понятие матрицы перехода от n -ой итерации к (n +1)-ой, достаточное условие сходимости стационарных методов, необходимое и достаточное условие сходимости стационарных методов) Рассмотрим задачу численного решения системы вида (1) В матричном виде она записывается Ax = b,(1а) где - вектор свободных членов; - вектор неизвестных с вещественными координатами; - вещественная квадратная матрица коэффициентов системы размерности . Будем предполагать, что определитель матрицы A отличен от нуля. Тогда для каждого вектора b система (1) имеет единственное решение. Для решения таких систем можно использовать как прямые, так и итерационные методы. Прямые методы позволяют за конечное число действий получить точное решение системы уравнений, если входная информация задана точно и вычисления ведутся без округления (напр., методы Гаусса, Крамера и т.п.).   Итерационный метод позволяет найти приближенное решение системы путем построения последовательности приближений (итераций), начиная с некоторого начального приближения. Само приближенное решение является результатом вычислений, полученным после конечного числа итераций. Перейдем к общему описанию метода итераций для решения СЛАУ. Будем рассматривать систему (1) Для ее решения выбирается некоторое начальное приближение , и последовательно находятся приближенные решения (итерации) уравнения (5.1). Значение итерации выражается через известные предыдущие итерации . В дальнейшем верхний индекс будет указывать номер итерации, т.е. , где - n -ая итерация i –той компоненты вектора x. Определение 1 Если при вычислении используется только одна предыдущая итерация , то итерационный метод называют одношаговым (или двухслойным) методом; если же выражается через две итерации и , то метод называют двухшаговым (или трехслойным).   Окончание итераций определяется либо заданием максимального числа итераций , либо условием , (2) где e > 0 – заданное число. Определение 2. Канонической формой одношагового итерационного метода решения системы вида (5.1) называется его запись в виде (3) Здесь - матрица, задающая тот или иной итерационный метод, - итерационный параметр, - вектор, полученный на n – ой итерации. Предполагается, что задано начальное приближение и существует . Определение 3. Итерационный метод (3) называется явным, если , неявным, если , где E – единичная матрица. Определение 4. Итерационный метод (3) называется стационарным, если и , т.е. не зависят от номера итерации, и нестационарным – в противоположном случае. Определение 5. Матрица называется матрицей перехода от n -ой итерации к (n +1)-ой. Теорема 1. (Необходимое и достаточное условие сходимости) Итерационный метод сходится при любом начальном приближении, тогда и только тогда, когда все собственные значения матрицы перехода S по модулю меньше единицы. Теорема 2. (Достаточное условие сходимости) Итерационный метод сходится при любом начальном приближении, если норма матрицы перехода S меньше единицы.    

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-11-19 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: