Лекция
Аукцион первой цены, полное решение. Принцип эквивалентности дохода (теорема Маерсона). Оптимальный аукцион с точки зрения продавца, барьеры входа.
Разработка многопоточных приложений на Java
Общие сведения о параллелизме.
Управление потоками.
Синхронизация потоков.
Модель памяти.
Страница лекции на сайте ...
Экспоненциальная PCP-теорема
Отсутствие константного приближения для задачи о независимом множестве. Коды Уолша-Адамара, их локальное декодирование....
Вероятностно проверяемые доказательства и приближенные алгоритмы
Приближенные алгоритмы для MAX3SAT, вершинного покрытия. Класс PCP(r(n),q(n)), формулировка...
Подуровень управления доступом к среде. 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 клуба
Понятие алгоритма. Машины Тьюринга и программы с конечным числом счётчиков. Обсуждение их возможностей, эквивалентности моделей, универсальных функций и пр...
Канальная и пакетная коммутация. Международные стандарты. Стандартизация в телекоммуникациях. Эталонные модели. OSI. TCP/IP.
Страница лекции на сайте Computer...
Технологии физического уровня. Линии связи. Кабели связи. Модуляция. Физическое кодирование.
Страница лекции на сайте Computer Science Center
Элементарный асимптотический анализ
Асимптотики сумм и рекуррентных последовательностей. Преобразование Абеля и теорема Штольца. Оценки и асимптотики для...
Основы пространственной и частотной обработки изображений
Гистограммы, фильтрация, градиент, нахождение границ, выделение связных компонент, бинаризация....
Примитивные типы в Java.
Примитивные и ссылочные типы.
Тип boolean.
Целочисленные типы.
Вещественные типы.
Явное и неявное преобразование типов.
Классы-обертки...
Вычислимые функции
Соотношения на биномиальные коэффициенты. Формула включений-исключений. Субфакториалы (задача о беспорядках). Формула обращения Мебиуса.
Управляющие конструкции. Списки. Кортежи
Основные комбинаторные величины и простейшие комбинаторные формулы. Числа сочетания (с повторениями и без повторений), числа размещения (с повторениями и без...
Кучи во внешней памяти. Вычисления на орграфах, time forward processing. Раскраски и независимые множества. Поиск в ширину. Связные компоненты.
Страница лекции...
Ускоренный поиск в ширину во внешней памяти. Рандомизированное разбиение графа.
Страница лекции на сайте Computer Science клуба
Кеши: стратегии замещения, ассоциативность. Cache oblivious алгоритмы. Транспонирование матриц. Деревья van Emde Boas. Бинарный поиск. Алгоритмы на потоках...
Стеки, очереди и списки во внешней памяти. B-деревья. Буферизованные деревья.
Страница лекции на сайте Computer Science клуба
Модель вычислений во внешней памяти. Сканирование. Буферизация при чтении и записи. Оптимальая сортировка во внешней памяти. Задача ранжирования списка. Джойны...
Введение в анализ изображений
Примеры практических задач, трудности анализа изображений, особенности зрительного восприятия человека, семантический разрыв,...
Теория множеств
Основные понятия теории множеств. Бинарные отношения и функции. Рефлексивность, симметричность, транзитивность. Взаимно-однозначные...
Введение в компьютерные сети. История и эволюция. Основные понятия.
Страница лекции на сайте Computer Science Center