Лекция
Летом 2011 компания JetBrains объявила о разработке проекта Kotlin — статически типизированного ОО-языка программирования, компилируемого для платформы Java и...
Примитивно рекурсивные и частично рекурсивные функции
Примитивно рекурсивные функции: примеры. Примитивная рекурсивность вычислимых функций за примитивно...
Глобальная память, стек, куча. Динамическое выделение памяти.
Теорема о неподвижной точки (окончание). Машины Тьюринга
Главные универсальные функции. Вывод теоремы Успенского-Райса из теоремы Клини. Машины Тьюринга....
Алгоритмы сортировки.
Сортировка слиянием: с рекурсией и без.
Сортировка с помощью кучи.
Нижняя оценка Ω (n log n) для сортировки.
Быстрая сортировка: анализ...
Введение в ООП на Java (2).
Что такое транзакция. Зачем она нужна. Свойства ACID. Особенности распределенного состояния данных. CAP теорема. CAP "сказка". Понятие BASE.
Страница лекции на...
Основы комбинаторики:
Основные комбинаторные величины и простейшие комбинаторные формулы.
Числа сочетания (с повторениями и без повторений), числа размещения (...
Цвет
Формальные грамматики — это прикладная логика, предназначенная для задания синтаксиса языков, Применение грамматик тесно связано с алгоритмами для...
Поиск похожих объектов. MapReduce.
Утилита make. Указатели и ссылки.
Теорема Успенского-Райса, теорема о неподвижной точке
m-сведения, другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса....
Архитектура распределенной базы данных, компоненты системы, партиционирование и шардирование данных. Master-slave репликация, журнал операций. Memcached, Redis...
Рекуррентные соотношения.
Метод "разделяй и властвуй".
Умножение чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм.
Рекуррентные соотношения...
Логика:
Логика высказываний.
Таблицы истинности.
Пропозициональные формулы.
Кванторы. Предикаты.
Языки логики первого порядка.
Интерпретация языков.
Введение в ООП на Java (1).
Вводное занятие
Растровая графика
В 2010 году была показана практическая возможность использования таргетирования рекламных объявлений в социальных сетях с целью получения скрытой информации о...
Введение.
Программа, состоящая из нескольких файлов. Компиляция и линковка.
Бумажная телефонная книга. Организация информации в ней, хранение информации, операции над данными, CRUD, поиск, алгоритмы, скорость работы.
Страница лекции на...
Вычислимые функции, разрешимые и перечислимые множества
Введение.
Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ.
Время работы алгоритма, O-...
Теория множеств:
Основные понятия теории множеств.
Бинарные отношения и функции.
Рефлексивность, симметричность, транзитивность.
Взаимно-однозначные...
Мы обсудим еще несколько моделей, которые с разных сторон улучшают модель из первой лекции. Изучим различные свойства веб-графов в этих моделях и, возможно,...
В завершение курса мы поговорим о приложениях изученных нами моделей к задачам ранжирования в поиске.
Страница лекции на сайте Computer Science клуба
Мы расскажем о том, как зародилась наука о построении моделей веб-графов. Рассмотрим одну из таких моделей и обсудим, какими свойствами, близкими к свойствам...
Одной из задач в процессе разработки лекарств является задача поиска химических соединений, содержащих заданный фрагмент, в больших базах данных. Такие базы...
Задача о максимальном разрезе в ненаправленном графе. Рандомизированное 2-приближениеМаксимальный разрез как задача целочисленного квадратичного...
Субмодулярность ранговой функции. Субмодулярные функции на семействе множеств, примеры. Полиматроид и расширенный полиматроид. Жадный алгоритм для оптимизации...
Минимизация субмодулярной функции с помощью метода эллипсоидов. Пересечение матроидов, примеры. Трудность оптимизации по пересечению трех матроидов....
Краткое напоминание: целочисленные полиэдры и комбинаторные задачи, тотальная унимодулярность и тотальная двойственная целочисленность. Доказательство...
Задача о вершинно-взвешенном мультиразрезе, описание политопа. Двойственная линейная программа, T-пути и мультипотоки. Полуцелочисленность, 2-приближенный...
Системы допустимых множеств и их политопы, связь между комбинаторной и линейной задачами. Частично-упорядоченные множества, цепи и антицепи. TDI-системы....
Конусы и целые точки в них, базисы Гильберта. Существование конечного базиса Гильберта у любого рационального конуса. Всякий рациональный полиэдр задается TDI-...