Лекция
Аукцион первой цены, полное решение. Принцип эквивалентности дохода (теорема Маерсона). Оптимальный аукцион с точки зрения продавца, барьеры входа.
Разработка многопоточных приложений на Java
Общие сведения о параллелизме.
Управление потоками.
Синхронизация потоков.
Модель памяти.
Страница лекции на сайте ...
Вероятностно проверяемые доказательства и приближенные алгоритмы
Приближенные алгоритмы для MAX3SAT, вершинного покрытия. Класс PCP(r(n),q(n)), формулировка...
Экспоненциальная PCP-теорема
Отсутствие константного приближения для задачи о независимом множестве. Коды Уолша-Адамара, их локальное декодирование....
Подуровень управления доступом к среде. Ethernet. Коммутация на канальном уровне.
Страница лекции на сайте Computer Science Center
Рекуррентные соотношения
Рекуррентные соотношения и производящие функции. Числа Фибоначчи. Формула Бинэ и матричное представление чисел Фибоначчи. Линейные...
Морфологическая обработка изображений
Морфологические операции (дилатация, эрозия, размыкание, замыкание) и основанные на них алгоритмы.
Страница лекции на...
Кластерный анализ. Самоорганизующиеся сети Кохоннена.
Объекты, классы и пакеты в Java
Основы ООП.
Объявление класса.
Использование класса.
Наследование.
Пакеты.
Модификаторы доступа.
Вложенные классы.
Страница...
Теорема о неподвижной точке. Машины Тьюринга
Теорема о неподвижной точке. Программа, печатающая свой текст. Доказательство с помощью искусственного языка...
Группа перестановок.
Четность перестановки, разложение в произведение транспозиций, разбиение на циклы, четность цикла, классы сопряженных и циклический тип...
Операционная семантика большого и малого шага.
Архитектура распределенной базы данных, компоненты системы, партиционирование и шардирование данных. Master-slave репликация, журнал операций. Memcached, Redis...
Формализация: теория игр с неполной информацией. Напоминания из классической теории игр. Концепция равновесия Байеса-Нэша, примеры нахождения решения. Аукцион...
Теория вероятностей: использование неравенства Чебышёва и метода сравнения двух распределений (мартингалов) для оценок больших уклонений.
Вероятностные...
Коммуникационная сложность. Детерминированная коммуникационная сложность равенства максимальна.
Вероятностная коммуникационная сложность равенства:...
Последовательное и параллельное повторения для диалогов с одним и двумя доказывающими (формулировки вопросов).
В игре проверяющего с двумя доказывающими...
Тысячелетней давности миф про медленную Java все еще живет во многих сердцах. Рассказ Руслана — про то, как отдельные смельчаки, не верящие в мифы, ухитряются...
Разрешимые множества. Перечислимые множества как проекции разрешимых. Арифметическая иерархия. Выразимость с помощью формул первого порядка. Выразимые...
Выразимость перечислимых множеств (с помощью сведения к FRACTRAN). Множества из класса ∑2 как перечислимые с помощью оракула для проблемы остановки.
Теорема...
Уровень передачи данных или канальный уровень.
Страница лекции на сайте Computer Science Center
Подуровень управления доступом к среде. Введение в Ethernet.
Страница лекции на сайте Computer Science Center
Оценки и асимптотики для комбинаторных величин
Понятие об энтропии. Асимптотики для биномиальных коэффициентов и прочее. Оценки сумм биномиальных коэффициентов...
Массивы и строки в Java
Массивы:
объявление, создание, инициализация, индексация
одномерные и многомерные, представление в памяти
java.util.Arrays
Строки:
Компиляция и интерпретация
Смешанные вычисления. Проекции Футамуры-Ершова. Техника раскрутки (bootstrapping). Принципы организации компилятора. Просмотры,...
Функции. Функциональное программирование
Функции: как их определять? Передача параметров в функцию; Параметры по-умолчанию. Специальные аргументы -- *args и **...
Введение: что такое аукцион? Примеры аукционов, обсуждение более широкой области (дизайн экономических механизмов), обзор основных результатов. Эффективность и...
Объектно-ориентированное программирование. Классы
Классы и их синтаксис. Подробнее про области видимости и пространства имен. Объекты-классы. Объекты-...
Исчисление резолюций. Полнота и корректность.
Страница лекции на сайте Computer Science клуба
Цена игры двух лиц с нулевой суммой. Доказательство существования цены с помощью системы аффинных неравенств (теорема фон Неймана)
Нерешённые задачи: улучшение оценок в теореме Гача--Дея (о разрыве между априорной и монотонной сложностью) в терминах игры; дискретный вариант 13 проблемы...
Понятие алгоритма. Машины Тьюринга и программы с конечным числом счётчиков. Обсуждение их возможностей, эквивалентности моделей, универсальных функций и пр...
Сводимость. Доказательство неразрешимости с помощью сведения.
Страница лекции на сайте Computer Science клуба
Технологии физического уровня. Линии связи. Кабели связи. Модуляция. Физическое кодирование.
Страница лекции на сайте Computer Science Center
Элементарный асимптотический анализ
Асимптотики сумм и рекуррентных последовательностей. Преобразование Абеля и теорема Штольца. Оценки и асимптотики для...
Основы пространственной и частотной обработки изображений
Гистограммы, фильтрация, градиент, нахождение границ, выделение связных компонент, бинаризация....
Канальная и пакетная коммутация. Международные стандарты. Стандартизация в телекоммуникациях. Эталонные модели. OSI. TCP/IP.
Страница лекции на сайте Computer...
Примитивные типы в Java.
Примитивные и ссылочные типы.
Тип boolean.
Целочисленные типы.
Вещественные типы.
Явное и неявное преобразование типов.
Классы-обертки...
Вычислимые функции
Соотношения на биномиальные коэффициенты. Формула включений-исключений. Субфакториалы (задача о беспорядках). Формула обращения Мебиуса.
Основные комбинаторные величины и простейшие комбинаторные формулы. Числа сочетания (с повторениями и без повторений), числа размещения (с повторениями и без...
Управляющие конструкции. Списки. Кортежи
Кучи во внешней памяти. Вычисления на орграфах, time forward processing. Раскраски и независимые множества. Поиск в ширину. Связные компоненты.
Страница лекции...
Ускоренный поиск в ширину во внешней памяти. Рандомизированное разбиение графа.
Страница лекции на сайте Computer Science клуба
Кеши: стратегии замещения, ассоциативность. Cache oblivious алгоритмы. Транспонирование матриц. Деревья van Emde Boas. Бинарный поиск. Алгоритмы на потоках...
Модель вычислений во внешней памяти. Сканирование. Буферизация при чтении и записи. Оптимальая сортировка во внешней памяти. Задача ранжирования списка. Джойны...
Стеки, очереди и списки во внешней памяти. B-деревья. Буферизованные деревья.
Страница лекции на сайте Computer Science клуба
Введение в анализ изображений
Примеры практических задач, трудности анализа изображений, особенности зрительного восприятия человека, семантический разрыв,...
Теория множеств
Основные понятия теории множеств. Бинарные отношения и функции. Рефлексивность, симметричность, транзитивность. Взаимно-однозначные...
Введение в компьютерные сети. История и эволюция. Основные понятия.
Страница лекции на сайте Computer Science Center