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

Энтропия — мера неопределённости, мера хаоса. В естественных науках это мера беспорядка системы, состоящей из многих элементов; в теории информации — мера неопределённости какого-либо опыта, процесса или испытания, которые могут иметь разные исходы (а значит, мера количества информации); в математике — мера сложности объекта или процесса. Понятие энтропии было впервые введено в 1865 году Р. Клаузиусом в термодинамике, К. Шенноном в теории информации в 1949 г., в теории стохастичпеских процессов Колмогоровым, Гельфандом и Яглом в 1956 г., в функциональном анализе и теории динамических систем Колмогоровым в 1956–1958 гг. Между мирами полной детерминированности, изучаемой классическим анализом и миром хаоса, изучаемым теорией вероятностей, ныне перекидывается мост, который связан с понятием энтропии.

Зильберман Александр Рафаилович. Летняя школа «Современная математика», г. Дубна 28 июля 2007 г.

План лекций: Доказуемость и недоказуемость (почему некоторые утверждения нельзя ни доказать, ни опровергнуть?); Вычислимые функции (почему некоторые функции нельзя вычислить на компьютере?); Сложность алгоритмов; Формальные языки и исчисления.

Март 2016 года ознаменовался сенсацией в области информатики и искусственного разума: программа AlphaGo, разработанная компанией Google DeepMind, выиграла со счётом 4:1 матч в го у одного из сильнейших гоистов мира Ли Седоля. До этого игра го считалась недоступной для компьютера, ввиду того что большую роль в ней играют не только расчёт, но и такие сложно формализуемые понятия, как интуиция, чувство гармонии и т.п. Как же удалось научить машину «чувствовать гармонию», преодолеть ограничения классических методов машинного анализа игр? В докладе будут рассмотрены как классические методы (минимакс, альфа-бета-отсечение), которые показали свою эффективность в шахматах и шашках, так и методы, воплощённые в программе AlphaGo: поиск на дереве методом Монте-Карло, свёрточные нейронные сети для распознавания изображений, обучение с подкреплением.

Наряду с привнесением революционных идей в информатику, искусственный интеллект и биологию, Тьюринг внес существенный вклад и в такой традиционный раздел математики, как теория чисел. К сожалению, даже о сaмом существовании таких исследований Тьюринга за пределами круга теоретико-числовиков известно немногим. Все опубликованные Тьюрингом работы по теории чисел связаны с одним, но фундаментальным вопросом этой области математики — распределением простых чисел. В частности, Тьюринг предложил метод для проверки справедливости гипотезы Римана для начальных нулей дзета функции Римана. Этот метод остается основным и при всех современных вычислениях на суперкомпьютерах. Тьюринг также изобрел механическое устройство для вычисления нулей дзета функции, получил грант на его реализацию, но эта работа была прервана войной и никогда не закончена.

В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта. Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.

Теорема о четырёх красках утверждает, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. В виде проблемы она была сформулирована в 1852 году — и доказана в 1976-м лишь с помощью компьютера. Такое решение не всем понравилось, и некоторые до сих пор ждут доказательства, которое можно проверить без компьютера. Другие (как великий математик Владимир Воеводский) — наоборот, стали развивать автоматическую проверку правильности доказательств на компьютере… В курсе мы разберем доказательство теоремы о четырёх красках (это простая комбинаторика, доступная любому школьнику), а также обсудим сегодняшнее использование компьютера в математике (надо примерно знать, что такое компьютер).

Все слышали слово «синергетика», гораздо меньше народу знает, что это относится к закономерностям развития сложных неравновесных систем, и уж совсем немногие точно представляют себе, что это такое. Из первых рук нам об этом расскажет один из адептов синергетики в России, автор физической концепции «белок — машина», биолог и физик Дмитрий Чернавский.

Системы искусственного интеллекта, которые могут играть в абстрактные, стратегические и настольные игры, прошли огромный путь, однако как на самом деле устроены их «мозги»?

На чем основаны генетические алгоритмы? Как происходит создание различных уровней в компьютерной игре? Каковы перспективы применения эволюционных алгоритмов? На эти и другие вопросы отвечает доцент Университета Иннополис Джозеф Браун. Процедурная генерация контента в играх — это процесс автоматического создания различных ресурсов. Таким образом можно создавать повествование или сюжет игры или более простые объекты, такие как деревья. Или какие-нибудь элементы игрового процесса. Например, какие будут уровни. Этим я в основном и занимаюсь: как создать уровень, который отвечает некоторым ожиданиям игрока и некоторым ожиданиям в контексте повествования. Я использую много приемов из области, которая называется вычислительный интеллект. А вычислительный интеллект применяет биоинспирированные методы для решения сложных задач оптимизации.

Мультфильм рассказывает об использовании идеи биологической эволюции в задачах искусственного интеллекта, истории эволюционных алгоритмов и принципах их работы. Все это подробно изучается на магистерской программе Университета Иннополис «Робототехника». Историю об эволюционных алгоритмах нам помог рассказать доцент, руководитель Лаборатории искусственного интеллекта в разработке игр Университета Иннополис Джозеф Браун.

Теория информации — математическая дисциплина, в которой одновременно применяются методы многих разделов математики: теории вероятностей, теории алгоритмов, комбинаторики. Она занимается, в числе прочих, вопросами — как лучше всего сжать файл? Сколько информации может содержать данное сообщение? Как возможно точно передать сообщение, несмотря на помехи в канале связи? Как защитить сообщение от несанкционированного доступа? Ключевые идеи о том как решать перечисленные задачи были изложены в статье К. Шеннона «Математическая теория информации», где впервые было введено понятие энтропии (количества информации) и намечены контуры будущей теории. Мы займёмся введением в теорию сжатия дискретных данных (в отличие от непрерывных; там — своя специфика). Рассмотрим несколько алгоритмов, которые применяются в универсальных архиваторах (zip, rar). А также сделаем первые шаги (определим понятия и докажем начальные теоремы) на пути, ведущем к теоретическому обоснованию эффективности этих алгоритмов.

Теория сложности вычислений — бурно развивающаяся область теоретической информатики (theoretical computer science) и охватывает как чисто теоретические вопросы, так и вопросы, непосредственно связанные с практикой. Среди наиболее важных приложений этой теории можно назвать способы построения и анализа эффективных алгоритмов, а также современные криптографические методы. Поэтому знакомство с основами теории сложности, безусловно, полезно любому, кто собирается серьезно заниматься практическим программированием или теоретическими исследованиями.

Теория кодирования – это отличный повод поговорить о красивых задачах из алгебры и комбинаторики, о линейной алгебре и алгебраической геометрии над конечными полями, конечных геометриях, простых группах и алгоритмах, связанных с передачей информации. Программа курса: Основные задачи теория кодирования. Коды, исправляющие ошибки. Расстояние Хемминга и неравенство треугольника. Предварительные сведения из алгебры. Строение конечных полей. Линейная алгебра над конечными полями. Линейные коды и их характеристики. Код Хемминга. Совершенные коды. Двойственный код и тождество Мак-Вильямса. Эквивалентность кодов. Методы вычисления минимального расстояния для подпространства. Циклические коды и главные идеалы. Алгеброгеометрические коды. Грассманианы и плюккеровы координаты. Грассмановы коды и минимальные расстояния. Точки на минимальной сфере. Алгоритмы декодирования. Синдромы и минимальные представители. Коды Голея. Конечные геометрии и группы Матье.

Курс занятий посвящен тому, что в математике сделать нельзя. Но речь пойдет не о запрещенных действиях (типа деления на ноль или квадратуры круга), а об отсутствии общих методов для решения некоторых широких классов задач. Начиная от определения вычислимой функции (через машину Тюринга), мы узнаем про существование универсальной вычислимой функции, и как следствие – о существовании не вычислимых функций. Отсюда мы поймем, какие задачи никакой компьютер (даже сколь угодно мощный) решить не может в принципе. Затем мы определим «Колмогоровскую сложность» и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте – одного из самых значительных научных открытий ХХ-го века.

В 1958 году в Докладах Академии Наук вышла заметка А. Н. Колмогорова об энтропии как новом инварианте преобразований, сохраняющих меру. Вместе с двумя более ранними заметками, в которых заложены основы того, что потом было названо КАМ-теорией, эти работы полностью изменили облик и место в математике теории динамических систем. Это открытие привело серьезному прогрессу в нескольких областях математики, однако, как ни странно, некоторые идеи, близко лежащие к колмогоровским, не были развиты и даже замечены. Энтропия является одним из целой серии инвариантов, которые возникают при рассмотрении динамики метрических пространств с мерой. Изучение динамики метрик полезно и в других вопросах комбинаторики и теории случайных процессов.

Исходные понятия. Полиномиальные и экспоненциальные алгоритмы. Задачи распознавания и оптимизации. Определение классов P и NP. Совпадает ли P с NP или не совпадает — вопрос на миллион долларов. Машина Тьюринга как универсальный вычислительный прибор. Опорные комбинаторные задачи: коммивояжера, клика, изоморфизм графов, паросочетание, рюкзак, целочисленное линейное программирование (ЦЛП), транспортная задача. В двух словах о непрерывной задаче линейного программирования. Теорема Кука.

Специалист по Computer Science Виктор Лемпицкий об обучении нейронных сетей, распознавании образов и принципах работы приложения Prisma.

Трансильванский университет Sapientia представил свой новый обучающий курс по алгоритмам сортировки. Стоит отметить талант создателей и высокую наглядность пособия.