Постановки задач современной информатики

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

Пролог Задачи современной информатики   show.pdf

Постановки задач в современной информатике. Структура типичной постановки: исходные данные, свойства исходных данных, алгоритм (метод), результирующие данные. ¶ Понятие алгоритма. Понятие сложности алгоритма. Понятие алгоритмической разрешимости. ¶ Постановка задачи нахождения наибольшего общего делителя двух натуральных чисел. Алгоритм Евклида. Доказательство разрешимости задачи нахождения наибольшего общего делителя алгоритмом Евклида. ¶ Формальные, нормативные, эвристические и другие способы обоснования методов решения задач. Прямые и обратные задачи. Существование и единственность решения. Некорректные задачи. Обобщенные постановки задач. Задачи, допускающие проверку решения.

Литература
1. Кормен Т., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. - М.: ИД "Вильямс", 2005. [[Глава 1]]
2. Гиляревский Р. Основы информатики: Курс лекций. - М.: Экзамен, 2004.
3. Бабенко К.И. Основы численного анализа. - Москва-Ижевск: НИЦ, 2002. [[ Введение ]]
4. Гагарина Л.Г., Кокорева Е.В., Виснадул Б.Д. Технология разработки программного обеспечения. - М.: ИД "Форум"-ИНФРА-М, 2008.
5. Ульянов М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ. - М.: ФИЗМАТЛИТ, 2008.

Задачи численного анализа   show1.pdf   show2.pdf

Численный анализ как теория конструирования способов приближенного представления величин, получающихся при выполнении различных математических операций. ¶ Общая постановка задачи интерполяции. Многочлены Лагранжа и Ньютона. Оценки погрешности лагранжевой интерполяции. Задача интерполирования [четных и нечетных] периодических функций. ¶ Задачи численного дифференцирования и интегрирования. ¶ Задача приближения таблично заданной функции с помощью метода наименьших квадратов. Равномерное и среднеквадратическое приближения заданных функций. Задача сглаживания результатов наблюдений. ¶ Задача решения систем линейных алгебраических уравнений. Задача вычисления собственных значений и собственных векторов. ¶ Задача решения нелинейных уравнений. Задача отделения корней уравнений. ¶ Задача поиска экстремума функций одной и многих переменных.

Литература
1. Березин И.С., Жидков Н.Н. Методы вычислений. Т.1, 2 - М.: Наука, 1966.
2. Ильин В.П. Численный анализ. Часть 1. - Новосибирск: Изд-во ИВМиМГ, 2004.
3. Васильев Ф.П. Методы решения экстремальных задач. - М.: Наука, 1988.

Дополнительная литература
1. Тыртышников Е.Е. Методы численного анализа. - М.: Изд-во Моск. ун-та, 2006.
2. Бабенко К.И. Основы численного анализа. - Москва-Ижевск: НИЦ, 2002.

Задачи математического программирования   show.pdf

Математическое программирование как теория конструирования методов поиска условного экстремума функции многих переменных. Общая постановка задачи математического программирования. ¶ Постановка задача линейного программирования. Транспортная задача. Идея симплекс-метода. ¶ Постановка задачи нелинейного программирования. Дробно-линейное программирование. Квадратичное программирование. ¶ Постановка задачи дискретного программирования. Целочисленное линейное программирование. Булево программирование. Комбинаторные задачи. ¶ Постановка задачи динамического программирования. Постановка задачи параметрического программирования. Постановка задачи бесконечномерного программирования. Постановка задачи стохастического программирования. ¶ Задачи теории игр. Постановки задач матричных игр.

Литература
1. Балдин К.В., Рукосуев А.В., Брызгалов Н.А. Математическое программирование. - М.: Дашков и Ко, 2014.
2. Жолобов Д.А. Введение в математическое программирование. - М.: МИФИ, 2008.

Дополнительная литература
1. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении. - М.: "Дело", 2002.
2. Кулян В.Р., Юнькова Е.А., Жильцов А.Б. Математическое программирование (с элементами информационных технологий). - Киев, МАУП, 2003.

Задачи статистического анализа   show.pdf

Статистический анализ как теория конструирования и применения статистических методов выявления причинно-следственных связей. ¶ Задачи проверки статистических гипотез. Проверка гипотезы о виде распределения. Проверка гипотезы однородности. Проверка гипотезы независимости. Проверка гипотезы случайности. ¶ Задача корреляционного анализа. Простой корреляционный анализ. Множественная и частная корреляции. ¶ Задача регрессионного анализа. Простая линейная регрессия. Множественная линейная регрессия. Пошаговая регрессия. Нелинейная регрессия. ¶ Задача дисперсионного анализа. Однофакторный дисперсионный анализ. Двухфакторный дисперсионный анализ. Ковариационный анализ. ¶ Задача факторного анализа. Метод главных компонент. ¶ Задача дискриминантного анализа. Пошаговый дискриминантный анализ. Построение статистических решающих правил. ¶ Многомерный статистический анализ. ¶ Задачи статистического прогнозирования. Оптимальный предиктор. Линейный прогноз. Прогнозирование стационарных временных рядов.

Литература
1. Королев В.Ю. Теория вероятностей и математическая статистика. - М.: Изд-во Проспект, 2006.
2. Кибзун А.И., Горяинова Е.Р., Наумов А.В. Теория вероятностей и математическая статистика. - М.: Физматлит, 2013.
3. Ивченко Г.И., Медведев Ю.И. Математическая статистика. - М: Книжный дом "ЛИБРОКОМ", 2014.

Дополнительная литература
1. Афифи А., Эйзен С. Статистический анализ. Подход с использованием ЭВМ. - М: Мир, 1982.
2. Гладун И.В. Статистика. - М.: КноРус, 2015.

Задачи распознавания образов   show.pdf

Распознавание образов как теория отнесения объектов-образов к некоторым классам, каждый из которых задан некоторым количеством правильно классифицированных объектов. ¶ Общая постановка задачи распознавания образов. Применение распознавания образов в системах машинного зрения, распознавания символов, диагностики, геологии, дактилоскопии и др. Основные понятия распознавания образов: признаки и решающие правила. ¶ Постановка задачи распознавания на основе байесовской теории. Байесовское решающее правило для нормального распределения. ¶ Постановка задачи распознавания образов на основе линейного решающего правила. Персептрон. ¶ Постановка задачи распознавания образов на основе нелинейного решающего правила. Многослойный персептрон. ¶ Постановка задачи распознавания образов с использованием нескольких решающих правил. ¶ Постановка задачи распознавания образов на основе сравнения с эталоном. ¶ Постановка задачи контекстно-зависимой классификации. ¶ Постановка задачи селекции признаков. Задача селекции признаков на основе проверки статистических гипотез. Методы генерации признаков. ¶ Постановка задачи обучения по прецедентам.

Литература
1. Местецкий Л.М. Математические методы распознавания образов. - М.: Изд-во Моск. ун-та, 2004.

Дополнительная литература
1. Минский М., Пейперт С. Персептроны. - М.: Мир, 1971.
2. Бонгард М.М. Проблема узнавания. - М.: Наука, 1967.
3. Вапник В.Н., Чевоненкис А.Я. Теория распознавания образов. - М.: Наука, 1974.
4. Закревский А.Д. Логика распознавания. - Мн.: Наука и техника, 1988.
5. Ту Дж., Гонсалес Р. Принципы распознавания образов. - М.: Мир, 1978.

Задачи анализа данных   show.pdf

Интеллектуальный анализ данных как наука выявления и описания связей признаков, измеренных в количественных и качественных шкалах. Шкалы измерений: формальное определение, классификация. ¶ Задачи корреляционного анализа: оценка связи количественных переменных, оценка связи качественных признаков. ¶ Задачи регрессионного анализа: оценивание коэффициентов регрессии методом наименьших квадратов, статистический анализ уравнения регрессии, проверка статистических гипотез относительно коэффициентов регрессии. Прикладные аспекты регрессионного анализа. ¶ Задача дисперсионного анализа: однофакторный, двухфакторный и многофакторный дисперсионный анализ. ¶ Постановка задачи планирования эксперимента: планирование эксперимента с количественными переменными, методы экспериментальной оптимизации. Планирование эксперимента с качественными переменными. ¶ Задача анализа изолированных временных рядов: структурные компоненты временного ряда, модели компонент детерминированной составляющей временного ряда, методы выделения тренда, анализ сезонной компоненты, линейные модели случайной составляющей временного ряда, проверка ряда на случайность, числовые характеристики случайной составляющей, оценивание числовых характеристик временного ряда, анализ стационарной случайной составляющей линейного вида. ¶ Задача анализа многомерных временных рядов: коинтегрируемость временных рядов, система одновременных уравнений. ¶ Задача кластерного анализа: раздельная кластеризация, иерархический кластерный анализ, нечеткая кластеризация. ¶ Задача анализа главных компонент. Статистические свойства главных компонент. ¶ Постановка задачи многомерного шкалирования: метрическое шкалирование, неметрическое шкалирование, нелинейные методы шкалирования.

Литература
1. Низаметдинов Ш.У. Анализ данных. - М.: МИФИ, 2006.
2. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа данных: OLAP и Data Mining - СПб.: БХВ-Петербург, 2004

Задачи компьютерной визуализации   show.pdf

Компьютерная визуализация как наука о разработке алгоритмов преобразования данных в наглядное представление. Современное состояние компьютерной визуализации: электронные карты, медицинская визуализация, технический анализ. Эталонная модель визуализации. Виды визуализации. ¶ Задачи информационной визуализации: 1D-, 2D- 3D-визуализация. Деловая графика. Задача визуализации многомерных данных. Визуализация иерархических и сетевых структур. ¶ Задачи научной визуализации: срезы, изоповерхности, линии тока, глифы, пространственные структуры.

Литература
1. Касьянов В.Н., Касьянова Е.В. "Визуализация графов и графовых моделей" , Новосибирск: Сибирское Научное Издательство, 2010.
2. Голо В.Л., Синицын Д.О. Компьютерное моделирование и визуализация задач механики и геометрии. - M.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2009.

Дополнительная литература
1. Зиновьев А.Ю. Визуализация многомерных данных. - Изд-во КГТУ, 2000
2. Гришин В Г. Образный анализ экспериментальных данных. - М.: Наука,1982.

Задачи криптографической защиты информации

Криптография как наука о способах преобразования информации с целью ее защиты от незаконных пользователей. Криптография vs. криптоанализ. ¶ Основные цели криптографии: (1) обеспечение конфиденциальности данных, (2) обеспечение целостности данных, (3) обеспечение аутентификации, (4) обеспечение невозможности отказа от авторства. ¶ Базовые понятия криптографии: операции с "большими" простыми числами, хеш-функции, криптографические протоколы. ¶ Постановка задачи симметричного шифрования. Задача управления ключами. Стандарты симметричного шифровния: DES, 3DES, AES и др. ГОСТ 28147-89. ¶ Задача вычисления невоспроизводимой контрольной суммы. Стандартные алгоритмы расчета контрольных сумм: MD5, SHA-1, ГОСТ Р 34.11-94. ¶ Постановка задачи асимметричного шифрования. Секретный и открытый ключи. Алгоритмы расчета ключевой пары. Задача обмена открытыми ключами. Инфраструктура открытых ключей. Стандарты асимметричного шифрования: алгоритм Диффи-Хеллмана, RSA, EI Hamal, DSA, ГОСТ Р 34.10-94, 2001. ¶ Постановки задач вычисления и аутентификации электронной цифровой подписи. Федеральный Закон Российской Федерации "Об электронной цифровой подписи".

Литература
1. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб.: Изд-во "Лань", 2001.
2. Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. - СПб.: БХВ-Петербург, 2010.
3. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. - М.: КУДИЦ-ОБРАЗ, 2001.

Дополнительная литература
1. Рябко С.Д. Криптография: Основные понятия и алгоритмы. 2007. Презентация: Cryptography_introduction.pdf
2. Жданов О.Н., Золотарев В.В. Методы и средства криптографической защиты информации. - Красноярск: СибГАУ, 2007.

Задачи информационного поиска

Информационный поиск как теория конструирования методов обнаружения в большой коллекции неструктурированной информации, удовлетворяющей информационные потребности. Модель информационной системы. Классификационные информационно-поисковые системы. ¶ Постановка задачи булева информационного поиска. Задачи навигации пользователя по коллекции документов, Задача фильтрации данных. Задача кластеризации документов по их содержимому. Задача информационного поиска по произвольному запросу. Вероятностная модель информационного поиска. ¶ Постановка задачи построения индекса поисковой системы. Задача сжатия индекса. ¶ Постановка задачи оценки информационного поиска. Стандартные текстовые коллекции. Оценка результатов поиска. Оценка релевантности. Постановка задачи переформулировки запроса. ¶ Постановка задачи XML-поиска. Задача веб-поиска. ¶ Постановка задачи автоматического рубрицирования текстов. Задача кластеризации текстов. Задача классификации текстов [по тональности]. Постановка задачи автоматического аннотирования. Задачиаразрешения лексической однозначности. ¶ Задача автоматизированного построения тезаурусов и онтологий. Задача извлечения метаданных из текстов. Задача извлечения ключевых слов их текстов.

Литература
1. Маннинг К.Д., Рагхаван П., Шютце Х. Введение в информационный поиск. - М.: ИД "Вильямс", 2011.
2. Лукашевич Н.В. Тезаурусы в задачах информационного поиска. - М.: Изд-во Моск. ун-та, 2011.

Дополнительная литература
1. Шокин Ю.И., Федотов А.М., Барахнин В.Б. Проблемы поиска информации. - Новосибирск: Наука, 2010.
2. Ландэ Д.В. Основы интеграции информационных потоков. - Киев: Инжиниринг, 2006.

Спецификации требований к программным продуктам

Базовые этапы разработки программных продуктов: (1) разработка спецификации, (2) проектирование и реализация, (3) аттестация, (4) эволюция. Каскадная, эволюционная и другие технологии разработки программных продуктов. ¶ Спецификация как постановка задачи на разработку программного продукта. Творческий характер процесса разработки спецификаций. ¶ Требования к программному продукту. Функциональные и нефункциональные требования. Пользовательские требования. Системные требования. ¶ Разработка требований к программному продукту. Анализ осуществимости. Формирование и анализ требований. Аттестация требований. Управление требованиями. ¶ Модели систем для разработки требований. Модели системного окружения. Поведенческие модели. Модели данных. Объективные модели. Инструментальные средства. ¶ Прототипирование программных продуктов. Технологии быстрого прототипирования. Прототипирование пользовательских интерфейсов. ¶ Формальные спецификации. Формальные спецификации в процессе разработки. Спецификации интерфейсов. Спецификация поведения программного продукта.

Литература
1. Соммервилл И. Инженерия программного обеспечения. - М.: ИД "Вильямс", 2002. [[Часть 2]]
2. Вигерс К.И. Разработка требований к программному обеспечению. - М.: Издательско-торговый дом "Русская Редакция", 2004.

Дополнительная литература
1. Брукс Ф. Мифический человеко-месяц или как создаются программные системы. - СПб.: Символ-Плюс, 2001.
2. Константайн Л., Локвуд Л. Разработка программного обеспечения. - СПб.: Питер, 2004.
3. Белладжио Д., Миллиган Т. Разработка программного обеспечения: управление изменениями. - М.: ДМК Пресс, 2009.

Вопросы к зачету

На зачете студент должен продемонстрировать знание постановок следующих задач:

Численный анализ
1. Обобщенная задача интерполирования
2. Задача интерполирования многочленами
3. Задача вычисления значений интерполяционного многочлена
4. Задача интерполирования тригонометрическими многочленами
5. Задача интерполирования четными тригонометрическими многочленами
6. Задача интерполирования нечетными тригонометрическими многочленами
7. Задача выбора оптимальных узлов интерполирования
8. Задача приближения таблично заданной функции методом наименьших квадратов
9. Задача численного дифференцирования
10. Задача численного дифференцирования в узлах
11. Задача построения квадратурных формул
12. Задача построения интерполяционных квадратурных формул
13. Задача решения систем линейных алгебраических уравнений
14. Задача вычисления корней уравнения f(x) = 0
15. Задача вычисления корней уравнения x = f(x)

Математическое программирование
16. Задача математического программирования
17. Задача линейного программирования
18. Транспортная задача
19. Задача целочисленного линейного программирования
20. Задача дробно-линейного программирования
21. Задача выпуклого программирования
22. Задача квадратичного программирования

Статистический анализ
23. Задача нахождения доверительного интервала для вероятности события
24. Задача нахождения доверительного интервала для математического ожидания
25. Задача нахождения доверительного интервала для среднеквадратического отклонения
26. Задача проверки гипотезы о равенстве дисперсий нормально распределенных генеральных совокупностей
27. Задача проверки гипотезы о равенстве математических ожиданий нормально распределенных генеральных совокупностей
28. Задача проверки гипотезы о равенстве вероятностей двух событий при больших объемах выборок
29. Задача проверки гипотезы о законе распределения генеральной совокупности
30. Задача проверки гипотезы о независимости случайных величин
31. Задача построения эмпирической простой линейной регрессии
32. Задача нахождения доверительного интервала для коэффициентов простой линейной регрессии

Рапознавание образов
33. Задача байесовской классификации
34. Задача построения линейного классификатора
35. Задача построения решающего дерева
36. Задача композиции классификаторов
37. Задача иерархической кластеризации
38. Задача кластеризация метом k-means

Анализ данных
39. Задача факторного анализа
40. Задача неметрического многомерного шкалирования
41. Задача метрического многомерного шкалирования
42. Задача поиска ассоциативных правил
43. Задача поиска негативных ассоциативных правил
44. Задача поиска обобщенных ассоциативных правил
45. Задача поиска численных ассоциативных правил
46. Задача поиска временнЫх ассоциативных правил

Компьютерная визуализация
47. Задачи 1D-визуализации
48. Задачи 2D-визуализации
49. Задачи 3D-визуализации
50. Задача визуализации многомерных данных
51. Задача визуализации иерархических структур
52. Задача визуализации графов
53. Задача научной визуализации