Содержание
- 2. Что есть истина ? To them, I said, the truth would be literally noting but the
- 3. О КУРСЕ Д. Д. Предмет курса. Приложения. Предмет – все дискретное, то есть счетные множества, графы,
- 4. ПЛАН. Часть 1 Введение Дискретное и непрерывное Часть 2 ГРАФЫ Рост графов Мир как сеть Часть
- 5. ЧАСТЬ 1 Содержание части 1 Дискретные и непрерывные объекты в математике. Целые рациональные и вещественные (действительные)
- 6. Литература Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1969.
- 7. Литература Основная книга по нейронным сетям- Саймон Хайкин Нейронные сети: полный курс = Neural Networks: A
- 8. Математика не наука Математика - это некий формализованный способ описания, который применим или не применим к
- 9. Структура математической теории Аксиомы Правила вывода (логика) Теоремы (которые применимы или не применимы к реальным объектам)
- 10. Дискретность Дискре́тность (от лат. discretus — разделённый, прерывистый) — свойство, противопоставляемое непрерывности, прерывность. Дискретность — всеобщее
- 11. Дискретное множество Дискретное множество – это счетное множество (то есть множество, элементы которого можно занумеровать натуральными
- 12. Первая неочевидная теорема Множество рациональных чисел – счетное Но сначала напомним некоторые факты о развитии чисел
- 13. Рациональные числа это несократимые дроби m/n, где числитель и знаменатель целые. Обозначается Q . Эти числа
- 14. Иррациональные числа Долгое время в Древней Греции думали, что все числа – рациональны. Однако потом (около
- 15. Теорема Кантора Множество вещественных чисел R - несчетно. Доказательство этой теоремы очень простое, красивое и дальнейшее
- 16. Диагональный процесс и его следствия Теорема об остановке Тьюринга Теорема Геделя
- 17. Трудности Трудности связаны с обработкой больших массивов информации. Жизнь в многомерном пространстве совсем другая Возникает так
- 18. Формальное определение Графа Ориентированный граф определяется как пара (V, E), где V – конечное множество, E
- 19. Граф неформально На самом деле граф очень простая вещь, которая может быть изображена картинкой. Построим граф,
- 20. Картинка Предметом первых задач теории графов были конфигурации, состоящие из точек и линий, связывающих некоторые точки.
- 21. Первая задача о графах
- 22. Степени вершин Если в графе G имеется ребро e=(u,v), то говорят, что вершина v смежна с
- 23. Маршруты Пусть G - неориентированный граф Маршрут – это последовательность ребер e_1, e_2,…, e_n, такая, что
- 24. Цепи Маршрут называется цепью, если каждое ребро встречается в нем не более одного раза, и простой
- 25. Расстояние и диаметр Граф связен, если для каждых двух вершин u, v есть маршрут, который их
- 26. ПУТИ Рассмотрим ориентированный граф G. Путь длины к из вершины u в вершину v – это
- 27. Циклы и связность Циклом в графе называется путь, где начальная и конечная вершина совпадают и содержащий
- 28. Матрица смежности графа G Это квадратная матрица (двумерный массив) δ(I, j), l=1,…N, j=1…N, где N -
- 29. Матрица инцидентности Пусть имеется неориентированный граф G с вершинами v_1,…, v_m и ребрами e_1,… e_ n.
- 30. Матрица инцидентности для орграфов Пусть имеется ориентированный граф G с вершинами v_1,…, v_m и ребрами e_1,…
- 31. Типы графов Лес – ациклический неориентированный граф. Связный ациклический неориентированный граф называется деревом. (без выделенного корня)
- 32. Теория роста графов Теория Эрдеша -Реньи –графы растут случайно. Реальные графы, соответствующие социальным сетям и т
- 33. Рост реальных графов Оказывается, реальные графы имеют ряд общих свойств, и несмотря на их грандиозный размер,
- 34. Свойства реальных графов Свойство 2. Scale free structure Граф устроен, грубо говоря, как страна с городами
- 35. Безмасштабные Графы Свойство 2. Scale free structure Граф устроен, грубо говоря, как страна с городами на
- 36. Граф биохимических реакций
- 37. Булевские функции Б. Ф. от N переменных отображает вектор булевских переменных длины N в булевскую переменную
- 38. Способы задания б. ф. Таблица Логические формулы в том числе КНФ и ДНФ Многочлены Жегалкина (АНФ)
- 39. ДНФ Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет
- 40. КНФ Конъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет
- 41. АНФ Многочлен Жегалкина от булевских Переменных x, z, y, …– это многочлен С коэффициентами 0 или
- 42. Основные булевские функции двух переменных (N=2) Конъюнкция Дизъюнкция Сложение по модулю 2 Импликация Эквиваленция Штрих Шеффера
- 43. Таблицы для N=2 Конъюнкция (OR) 0001 Дизъюнкция (AND) 0111 Импликация → 1011 Штрих Шеффера | 1110
- 44. Сигмоидальная функция
- 45. Суперупрощенная модель ui (t+1) = σ (Σk Kik uk(t) - hi) Индексы i, k в [1,…
- 46. Примеры функций сигма σ = 1/(1+ exp(-a x)) σ = H(x) (скачок) Кусочно-линейная ( функция σ
- 47. Функция скачка (безграмотный график)
- 48. Кусочно-линейная функция и функция Ферми σ =1/ (1 + exp(- a x)), a > 0.
- 49. Задача классификации Предположим, мы хотим создать автоматическую систему, которая различает два типа объектов, А и B.
- 50. Задача классификации Мы можем рассматривать признак как вектор с k компонентами, или элемент (точку) k -мерного
- 51. Обучение (learning) В задачах классификации нейронные сети обучаются таким образом. Имеются некие обучающие примеры, где ответ
- 52. Математическая формализация схемы обучения моделей ИИ (на примере задачи классификации) Формируется набор признаков (x1 , x2
- 53. Общая схема обучения с учителем Дано - реальный выход устройства d(t) при входе X(t), где X(t)
- 54. Минимизация риска Введем эмпирический риск R = T -1 Σ t=1,T ( d(t) - F(X(t), w(t)))
- 55. Однослойный персептрон Однослойный персептрон получает входной сигнал, заданный вектором x и выдает число y = σ
- 56. Структурная форма
- 57. Моделирование логических функций персептроном Конъюнкция Дизъюнкция Отрицание Демократическое голосование
- 58. Решает ли персептрон все ?? БЫТЬ ИЛИ НЕ БЫТЬ ? Марвин Минский показал, что возможности персептрона
- 59. Персептрон как игра в квадратики и шарики (n=2)
- 60. Геометрическая интерпретация S=0 ↔ w1 x1 + w2 x2 + … wn xn =h Это -
- 61. Пример Минского Иногда квадратики и шарики неразделимы «Исключающее или» (XOR) нереализуемо однослойным персептроном. XOR(x,y)=x+y (mod 2)
- 62. Часть 3 Алгоритмы Алгоритм - формально описанная процедура, получающая исходные данные, называемые также входом алгоритма (input)
- 63. Пример Алгоритма Простейший пример алгоритма автор обнаружил в ирландском баре В городе Ренн (Франция), где он
- 64. Численные характеристики алгоритмов Время работы и требуемая память ( running time T and memory M)
- 65. Время работы Алгоритма Скорость алгоритма определяется зависимостью времени работы (Running time) от размера входа (input size).
- 66. Пример: Оценка времени работы алгоритма Гаусса. Пусть мы решаем систему N уравнений с N неизвестными. Матрица
- 67. Практическое применение Каковы практические следствия этой формулы (как ее практически применить)? Этот вопрос тем более актуален,
- 68. Простые, сложные и неразрешимые задачи. Простые, когда время решения растет как степень размера входа T(|X|) (running
- 69. Сложные (hard) Сложные, когда время решения растет, в общем случае, намного быстрее, чем степень размера входа.
- 70. Неразрешимые ( non decidable) Вообще алгоритмически неразрешимые, то есть нет алгоритма, который для любого входа выдает
- 71. Зацикливание программ Гениальный математик Ален Тьюринг доказал Важную Теорему В общем случае проблема остановки алгоритмически не
- 72. Примеры Пример простой задачи - решение системы линейных уравнений. Она решается в полиномиальное время методом Гаусса.
- 73. Поиск кратчайшего пути в графе Пример простой задачи. Введем так называемый взвешенный (weighted) граф (то есть
- 74. Алгоритм Флойда-Уоршалла Пусть вершины графа G=(V,E), |V|=n} пронумерованы от 1 до n и введено обозначение d_{ij}^k
- 75. Алгоритм ФУ Тогда рекуррентная формула для d_{ij}^{k}} имеет вид: d_{ij}^{0} — длина ребра (i,j); d_{ij}^{k}=\min(d_{ij}^{k-1}, d_{ik}^{k-1}+d_{kj}^{k-1}).}
- 76. Псевдокод ФУ for k = 1 to n for i = 1 to n for j
- 77. Задача коммивояжера - трудная Пример сложной задачи – задача коммивояжера. Предположим, некий человек собирается посетить (используя
- 78. Алгоритм обучения однослойного персептрона
- 79. Первые шаги Шаг 1. Инициализация синаптических весов и смещения: Значения синаптических весов wi(0) (0 Обозначение: wi(t)
- 80. Формула перенастройки (адаптации весов) Шаг 4. адаптация (настройка) значений весов: где r – параметр обучения (меньше
- 81. Пример программы на Матлабе Напишите программу по этому алгоритму for m=1:N out=out+ wout(m)*x(m); end; if(ssout >
- 82. Пример программы delta(k)=y(k)-yout(k); for i=1:N wout(i)=wout(i) + r*delta(k)*x(i); end;
- 83. Иллюстрация работы алгоритма
- 84. Эволюция синаптических весов w1 … wm
- 85. Эволюция весов
- 86. Откуда появился этот алгоритм Это алгоритм градиентного спуска, который ищет параметры, чтобы минимизировать ошибку. Алгоритм итеративный
- 87. Градиентный спуск Минимизация функции R(w) итеративно, движением по градиенту grad R(w) w(t+1)=w(t) + r grad R(w)
- 88. Кое что об алгоритмах Алгоритм получает вход X и выдает ответ Y Размер входа обозначаем |X|
- 89. Оценка скорости работы алгоритма Если время работы T не больше чем постоянная умножить на f(|X|) пишем
- 90. Решаемое и не решаемое Задача считается трудной для алгоритма, если максимальное время работы алгоритма T(|X|) растет
- 91. Трудное и легкое в среднем и некоторые замечания Задача линейного программирования для вещественных переменных теоретически трудная
- 92. Жадные алгоритмы Задача о деньгах. Получить нужную сумму с помощью наименьшего числа купюр Алгоритм – делаем
- 93. Градиентный спуск Минимизация функции F(X) итеративно, движением по градиенту grad F(X) Работает для выпуклых вниз функций
- 94. Динамическое программирование Метод предложен Р. Беллманом для задач оптимального управления. Основная идея- это работает, если задача
- 95. Принцип оптимальности подзадач Пример. Принцип Ферма. Допустим, мы должны найти оптимальную траекторию из А в B.
- 96. Архитектура многослойного персептрона
- 97. Абсолютное разделение ФУНДАМЕНТАЛЬНАЯ ТЕОРЕМА. Пусть имеется произвольное множество синих точек и непересекающееся с ним множество красных
- 98. Некоторые задачи для практики 1)Сколько существует булевских функций От двух переменных ? От трех ? 2)
- 99. Некоторые задачи для практики Найти многослойный персептрон минимальной архитектуры, моделирующий XOR Построить многослойный персептрон, моделирующий выборы
- 100. Нечеткая логика (fuzzy logic) задание Сила ++ Моисеенко + + Иванов Сергей + Траков + Большаков
- 102. Скачать презентацию