Проект:Словники/Информатика/Computing Curricula 2001

DS. Дискретные структуры

DS1. Функции, отношения и множества

Функции (сюръекции, инъекции, обратные функции, композиция)

Отношения (рефлексивность, симметричность, транзитивность, эквивалентность)

Множества (диаграммы Венна, дополнения, декартовы произведения, степенные множества)

Принцип Дирихле

Мощность и счетность

DS2. Основы логики

Логика высказываний Логические связки

Таблицы истинности

Нормальные формы (конъюнктивные и дизъюнктивные)

Общезначимость (тавтология)

Логика предикатов

Кванторы всеобщности и существования

Правила modus ponens и modus tollens

Ограничения логики предикатов

DS3. Методы доказательства

Понятия импликации, обращения, противопоставления, отрицания и противоречия

Структура формальных доказательств

Прямые доказательства

Доказательство через контрпример

Доказательство через противопоставление

Доказательство через противоречие Математическая индукция

Сильная индукция

Рекурсивные математические определения

Вполне упорядоченные множества

DS4. Основы вычислений

Основы вычислений

Правила суммы и произведения

Принцип включения-выключения

Арифметические и геометрические прогрессии

Числа Фибоначчи

Принцип Дирихле

Перестановки и сочетания

Основные определения

Тождество Паскаля

Биномиальная теорема

Решение рекуррентных соотношений

Общие примеры

Основная теорема рекуррентных соотношений

DS5. Графы и деревья

Деревья

Неориентированные графы

Ориентированные графы

Остовные деревья

Стратегии обхода графов

DS6. Дискретная вероятность

Конечное вероятностное пространство, вероятностная мера, события

Условная вероятность, независимость событий, теорема Байеса

Целочисленные случайные величины, математическое ожидание

CS301. Комбинаторика

CS302. Вероятность и статистика

CS303. Теория кодирования и информации

PF. Основы программирования

PF1. Основные конструкции программирования

Основы синтаксиса и семантики языков высокого уровня

Переменные, типы, выражения и присваивания

Основы ввода/вывода

Операторы проверки условия и цикла

Функции и передача параметров

Структурная декомпозиция

PF2. Алгоритмы и решение задач

Стратегии решения задач

Роль алгоритмов в процессе решения задач

Стратегии реализации алгоритмов

Стратегии отладки

Концепции и свойства алгоритмов

PF3. Фундаментальные структуры данных

Примитивные типы

Массивы

Записи

Строки и операции со строками

Представление данных в памяти

Статическое, автоматическое и динамическое выделение памяти

Управление памятью во время исполнения программы

Указатели и ссылки

Связные структуры

Методы реализации стеков, очередей и хэш-таблиц

Методы реализации графов и деревьев

Стратегии выбора подходящей структуры данных

PF4. Рекурсия

Понятие рекурсии

Рекурсивные математические функции

Простые рекурсивные процедуры

Стратегия "разделяй и властвуй"

Рекурсивный перебор с возвратами

Реализация рекурсии

PF5. Событийно-управляемое программирование

Методы обработки событий

Распространение событий

Обработка событий

AL. Алгоритмы и теория сложности

AL1. Основы анализа алгоритмов

Асимптотический анализ поведения алгоритмов в среднем и крайних случаях

Различия между поведением в лучшем, среднем и худшем случае

Нотация: О большое, o малое, омега, и тэта

Стандартные классы сложности

Эмпирические измерения производительности

Компромисс между временем и объемом памяти в алгоритмах

Использование рекуррентных отношений для анализа рекурсивных алгоритмов

AL2. Алгоритмические стратегии

Алгоритмы полного перебора

"Жадные" алгоритмы

Алгоритмы "разделяй и властвуй"

Перебор с возвратом

Метод ветвей и границ

Эвристики

Сопоставление с образцом и алгоритмы обработки текста

Алгоритмы численной аппроксимации

AL3. Фундаментальные вычислительные алгоритмы

Простые численные алгоритмы

Алгоритмы последовательного и бинарного поиска

Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками)

Алгоритмы сортировки за время O(N log N) (быстрая сортировка, пирамидальная сортировка, сортировка слиянием)

Хэш-таблицы, включая методы уменьшения количества коллизий

Бинарные деревья поиска

Представление графов (списки смежности, матрица смежности)

Обходы в глубину и ширину

Алгоритмы поиска кратчайшего пути (алгоритмы Дейкстры и Флойда)

Транзитивное замыкание (алгоритм Флойда)

Минимальное остовное дерево (алгоритмы Прима и Крускала)

Топологическая сортировка

AL4. Распределенные алгоритмы

Алгоритмы консенсуса и голосования

Распознавание завершения

Устойчивость к отказам

Стабилизация

AL5. Основы теории вычислимости

Конечные автоматы

Контекстно-свободные грамматики

Легко- и трудноразрешимые задачи

Невычислимые функции

Проблемы завершения

Следствия невычислимости

AL6. Классы сложности P и NP

Определения классов P и NP

NP-полнота (теорема Кука)]]

Стандартные NP-полные задачи

Методы сведения

AL7. Теория автоматов

Детерминированные конечные автоматы (DFA)

Недетерминированные конечные автоматы (NFA)

Эквивалентность DFA и NFA

Регулярные выражения

Лемма об условиях регулярности языка

Магазинные автоматы (PDA)

Связь между PDA и контекстно-свободными грамматиками

Свойства контекстно-свободных грамматик

Машины Тьюринга

Недетерминированные машины Тьюринга

Множества и языки Иерархия Хомского

Тезис Черча-Тьюринга

AL8. Углубленный анализ алгоритмов

Амортизационный анализ

Online- и offline-алгоритмы]]

Рандомизированные алгоритмы

Динамическое программирование

Комбинаторная оптимизация

AL9. Криптографические алгоритмы

Исторический обзор криптографии

Криптография с секретным ключом и проблема обмена ключами

Криптография с открытым ключом

Цифровые подписи

Протоколы безопасности

Приложения (доказательства с нулевым разглашением, аутентификация и т.д.)

AL10. Геометрические алгоритмы

Отрезки прямой: свойства, пересечения

Алгоритмы построения выпуклой оболочки

AL11. Параллельные алгоритмы

Модель PRAM

Монопольные и параллельные операции ввода-вывода

Переходы по указателям

Теорема Брента и эффективность работы

CS310. Анализ алгоритмов

CS311. Теория языков и автоматов

CS312. Криптография

CS313. Геометрические алгоритмы

CS314. Параллельные алгоритмы

AR. Архитектура и организация ЭВМ

AR1. Цифровая логика и цифровые системы

Обзор и история архитектуры компьютеров

Логические элементы компьютера (логические вентили, триггеры, счетчики, регистры, программируемая логическая матрица)

Логические выражения, минимизация, дизъюнкция конъюнкций

Нотация регистровых передач

Физические вопросы (вентильные задержки, нагрузочные модули по входу и выходу)

AR2. Представление данных в памяти компьютера

Биты, байты и слова

Представление числовых данных и системы счисления

Системы с фиксированной и плавающей точкой

Представление со знаковым битом и в дополнительном коде

Представление нечисловых данных (коды символов, графические данные)

Представление массивов и записей

AR3. Организация машины на уровне ассемблера

Принципы фон Неймана

Управляющее устройство: выборка инструкций, декодирование и выполнение

Набор инструкций и виды инструкций (манипуляция данными, управление, ввод-вывод)

Программирование на уровне ассемблера и машинном уровне

Форматы инструкций

Режимы адресации

Механизм вызовов и возвратов из процедур

Ввод-вывод и прерывания

AR4. Устройство памяти компьютера

Системы и технологии хранения данных

Кодирование данных, сжатие данных и целостность

Иерархия памяти

Организация основной памяти и операции с ней

Задержка, время цикла, пропускная способность и чередование

Кэш-память (отображение адресов, размер блока, стратегия замены и сохранения)

Виртуальная память (таблица страниц, буфер быстрого преобразования адреса)

Обработка ошибок и надежность

AR5. Взаимодействие и коммуникации

Основы ввода-вывода: "рукопожатие", буферизация, программируемый ввод-вывод, ввод-вывод с прерываниями

Структуры прерываний: вектор прерываний, прерывания с приоритетами, подтверждение прерывания

Внешняя память, физическая организация и устройства

Шины: протоколы шины, голосование, прямой доступ к памяти

Введение в сетевые технологии

Поддержка мультимедиа

Архитектуры RAID

AR6. Функциональная организация

Реализация простых информационных каналов

Устройство управления: "жесткая" реализация и микропрограммная реализация Конвейерная обработка команд

Введение в параллелизм на уровне инструкций (ILP)

AR7. Многопроцессорные и альтернативные архитектуры

Введение в SIMD, MIMD, VLIW, EPIC Систолическая архитектура

Сети с внутрисхемной коммутацией (гиперкуб, сеть с "перетасовкой", ячеистая архитектура, перекрестное соединение)

Системы с общей памятью

Когерентность кэшей

Модели памяти и модели целостности

AR8. Улучшение производительности

Суперскалярные архитектуры

Предсказание переходов

Предварительная выборка

Спекулятивное выполнение

Многопоточность

Масштабируемость

AR9. Архитектура сетевых и распределенных систем

Введение в локальные (LAN) и глобальные (WAN) cети

Многоуровневая модель сетевых протоколов, ISO/OSI, IEEE 802

Влияние архитектурных вопросов на распределенные алгоритмы

Сетевые вычисления

Распределенные мультимедиа-системы

CS320. Углубленные вопросы архитектуры компьютеров

CS321. Параллельные архитектуры

CS322. Однокристальные системы

CS323. Разработка VLSI

CS324. Кодизайн

OS. Операционные системы

OS1. Обзор операционных систем

Роль и задачи операционных систем

История развития операционных систем

Функционирование типичной операционной системы

Механизмы поддержки модели "клиент-сервер", мобильных устройств

Вопросы проектирования (эффективность, надежность, гибкость, переносимость, безопасность, совместимость)

Влияние безопасности, сетевых технологий, мультимедиа, графических оконных интерфейсов

OS2. Основы операционных систем

Методы декомпозиции системы (монолитная, многоуровневая, модульная, микроядерная модели)

Абстракции, процессы и ресурсы

Понятие программного интерфейса приложения (API)

Потребности приложений и эволюция программного и аппаратного обеспечения

Организация устройств

Прерывания: методы и реализации

Понятие состояния системы и пользователя, переход в режим ядра

OS3. Параллелизм

Состояния и диаграммы состояний

Структуры (таблица готовности, блоки управления процессом )

Диспетчеризация и переключение контекстов

Роль прерываний

Параллельное исполнение: преимущества и недостатки

Проблемы "взаимного исключения" и некоторые решения

Тупики: причины, условия, способы предотвращения

Модели и механизмы (семафоры, мониторы, условные переменные, рандеву)

Проблема "читатель/писатель" и синхронизация

Вопросы, связанные с многопроцессорностью (спин-блокировка, реентерабельность)

OS4. Планирование и диспетчеризация

Вытесняющее и невытесняющее планирование

Планировщики и политики

Процессы и потоки

Предельные сроки выполнения операции и другие вопросы реального времени

OS5. Управление памятью (5)

Обзор физической памяти и аппаратного обеспечения, предназначенного для управления памятью

Оверлеи, подкачка и разделы

Страничная и сегментная организации памяти

Стратегии вытеснения страниц

Рабочее множество и пробуксовка

Кэширование

OS6. Управление устройствами

Характеристики последовательных и параллельных устройств

Абстрагирование от различий между устройствами

Стратегии буферизации

Прямой доступ к памяти

Восстановление после сбоев

OS7. Безопасность и защита данных

Обзор безопасности системы

Механизмы и политики разграничения прав доступа

Методы и устройства обеспечения безопасности

Защита, доступ и аутентификация

Модели защиты Защита памяти

Шифрование данных

Управление восстановлением

OS8. Файловые системы

Файлы: данные, метаданные, операции, организация, буферизация, файлы с последовательным и произвольным доступом

Директории: содержимое и структура

Файловые системы: деление на разделы, монтирование и демонтирование, виртуальные файловые системы

Стандартные методы реализации

Файлы, проецируемые в память

Специализированные файловые системы

Именование, поиск, доступ, резервное копирование

OS9. Встроенные системы и системы реального времени

Планирование процессов и задач

Требования к управлению памятью и дисковыми устройствами в среде реального времени

Сбои, риски и восстановление

Специфические проблемы систем реального времени

OS10. Отказоустойчивость

Фундаментальные понятия: надежность и доступность системы

Пространственная и временная избыточность

Методы реализации отказоустойчивости

Примеры надежных систем

OS11. Оценка производительности системы

Почему требуется оценивать производительность системы

Какие параметры системы необходимо оценивать

Стратегии кэширования, подкачки, планирования, управления памятью, безопасности и другие

Модели оценки: детерминированная, аналитическая, имитационная и зависящая от реализации

Методы сбора данных для оценки (механизмы профилирования и трассировки)

OS12. Языки сценариев

Языки сценариев (scripting languages) и их роль

Основные системные команды

Написание сценариев, передача параметров

Выполнение сценария

Влияние языков сценариев на программирование

CS325. Операционные системы

CS326. Параллельные и распределенные системы

CS327. Надежные вычисления

CS328. Отказоустойчивость

CS329. Системы реального времени

NC. Распределенные вычисления

NC1. Введение в распределенные вычисления

Основы и история компьютерных сетей и Internet

Сетевые архитектуры

Специализации распределенных вычислений

Сети и протоколы

Сетевые мультимедиа-системы

Распределенные вычисления

Беспроводные и мобильные компьютеры

NC2. Сети и телекоммуникации

Сетевые стандарты и учреждения, занимающиеся стандартизацией

Семиуровневая модель сетевых протоколов ISO и ее отражение в TCP/IP Коммутация каналов и пакетная коммутация

Потоки и дейтаграммы

Понятия физического уровня сетевых протоколов (теоретические основы, средства передачи данных, стандарты)

Понятия канального уровня (кадрирование, контроль за ошибками, управление потоками, протоколы)

Объединение сетей и маршрутизация (алгоритмы маршрутизации, обеспечение межсетевого обмена, контроль перегрузки)

Службы транспортного уровня (установка соединения, проблемы производительности)

NC3. Сетевая безопасность

Основы криптографии

Алгоритмы с секретным ключом

Алгоритмы с открытым ключом

Протоколы аутентификации

Цифровые подписи

Примеры

NC4. Web как пример архитектуры "клиент-сервер"

Web-технологии:

Программное обеспечение Web-серверов

Программы CGI (Common gateway interface)

Сценарии, выполняющиеся на клиентской стороне

Понятие апплета

Характеристики web-серверов

Поддержка механизма прав доступа

Управление файлами

Возможности распространенных серверных архитектур

Роль клиентских компьютеров

Свойства отношений "клиент-сервер"

Web-протоколы

Программные средства поддержки разработки Web-сайтов и управления web

Разработка Web-серверов

Опубликование информации в Web

NC5. Разработка web-приложений

Протоколы уровня приложений

Основы web-инженерии

Web-сайты, основанные на базах данных

Удаленный вызов процедур (RPC)

"Легкие" распределенные объекты

Роль промежуточного ПО

Инструментальные средства поддержки

Проблемы безопасности в распределенных объектных средах

Web-приложения масштаба предприятия

NC6. Управление сетями

Обзор проблем сетевого управления

Использование паролей и механизмов контроля доступа

Доменные имена и служба имен

Проблемы поставщиков услуг Internet (ISPs)

Вопросы безопасности и брандмауэры

Вопросы качества обслуживания: производительность, восстановление после сбоев

NC7. Сжатие и распаковка данных

Аналоговое и цифровое представление данных

Упаковка и распаковка данных

Сжатие с потерей информации и без потерь

Сжатие данных: кодирование Хаффмана и алгоритм Лемпель-Зива

Сжатие и распаковка аудиоданных

Сжатие и распаковка изображений

Сжатие и распаковка видеоданных

Проблемы производительности: синхронизация, коэффициент сжатия, пригодность для использования в условиях реального времени

NC8. Технологии мультимедиа

Звук и аудио, изображения и графика, анимация и видео

Стандарты мультимедиа (аудио, музыка, графика, изображения, телефония, видео, телевидение)

Планирование загрузки и проблемы производительности

Устройства ввода и вывода (сканеры, цифровые камеры, сенсорные экраны и устройства, управляемые голосом)

MIDI-клавиатуры, синтезаторы

Стандарты хранения информации (магнитооптические накопители, CD-ROM, DVD)

Мультимедиа серверы и файловые системы

Инструментальные средства поддержки мультимедийных разработок

NC9. Беспроводные и мобильные компьютеры

История, эволюция и совместимость беспроводных стандартов

Специфические проблемы беспроводных и мобильных компьютеров

Беспроводные локальные сети и сети, основанные на спутниковой связи

Беспроводные линии связи

Протоколы Internet для мобильных устройств

Адаптация к условиям мобильных устройств

Расширения клиент-серверной модели для адаптации ее к мобильным устройствам

Мобильный доступ к данным: распространение данных с сервера и управление кэшем на клиенте

Установка программ на мобильные и беспроводные компьютеры

Роль промежуточного ПО и инструментальных средств поддержки

Проблемы производительности

Новые технологии

CS330. Углубленные вопросы компьютерных сетей

CS331. Распределенные вычисления

CS332. Программирование мобильных устройств

CS333. Кластерное программирование

CS334. Сжатие данных

CS335. Управление сетями

CS336. Сетевая безопасность

CS337. Корпоративные сети

PL. Языки программирования

PL1. Обзор языков программирования

История языков программирования

Краткий обзор парадигм программирования

Процедурные языки

Объектно-ориентированные языки

Функциональные языки

Декларативные, неалгоритмические языки

Языки сценариев

Влияние масштаба решаемых задач на методологию программирования масштаба разработок

PL2. Виртуальные машины

Понятие виртуальной машины

Иерархия виртуальных машин

Промежуточные языки

Проблемы безопасности, связанные с выполнением кода на сторонней машине

PL3. Введение в трансляцию (2)

Сравнение интерпретаторов и компиляторов

Стадии трансляции (лексический анализ, синтаксический анализ, генерация кода, оптимизация)

Машинно-зависимые и машинно-независимые аспекты трансляции

PL4. Переменные и типы данных (3)

Концепция типа данных как множества значений и операций над ними

Свойства объявлений (связывание, область видимости, блоки и время жизни)

Обзор проверки типов

Сборка мусора

PL5. Механизмы абстракции (3)

Процедуры, функции и итераторы как механизмы абстракции

Механизмы параметризации (ссылки и значения)

Активационные записи и управление памятью

Параметры типов и параметризованные типы

Модули в языках программирования

PL6. Объектно-ориентированное программирование

Объектно-ориентированное проектирование

Инкапсуляция и сокрытие информации

Разделение поведения и реализации

Классы и подклассы

Наследование (переопределение, динамическое связывание)

Полиморфизм (полиморфизм подтипов и наследование)

Иерархии классов

Классы коллекций и протоколы итерации

Внутреннее представление объектов и таблиц методов

PL7. Функциональное программирование

Обзор и мотивация функциональных языков

Рекурсия: списки, натуральные числа, деревья и другие рекурсивно определяемые структуры данных

Прагматика (отладка методом "разделяй и властвуй", живучесть структур данных)

Амортизационная эффективность для функциональных структур данных

Замыкания и использование функций в качестве данных (бесконечные множества, потоки)

PL8. Системы трансляции

Применение регулярных выражений в лексических анализаторах

Синтаксический анализ (конкретный и абстрактный синтез, абстрактные синтаксические деревья)

Применение контекстно-свободных грамматик в табличном синтаксическом анализе и методе рекурсивного спуска

Управление таблицей символов

Генерация кода путем обхода дерева

Архитектурно-зависимые оптимизации: выбор инструкций и распределение регистров

Методы оптимизации

Использование инструментальных средств для поддержки процесса трансляции и преимущества такого подхода

Библиотеки программ и раздельная компиляция

Создание синтаксически управляемых инструментальных средств

PL9. Системы типов

Тип данных как набор значений и операций над ними

Типы данных

Элементарные типы

Производные и сопроизводные типы

Алгебраические типы

Рекурсивные типы

Функциональные типы

Параметризованные типы

Модели проверки типов

Семантические модели типов, определяемых пользователем

Сокращенные типы

Абстрактные типы данных

Эквивалентность типов

Параметрический полиморфизм

Полиморфизм подтипов

Алгоритмы проверки типов

PL10. Семантика языков программирования

Неформальная семантика

Обзор формальной семантики

Денотационная семантика

Аксиоматическая семантика

Операционная семантика

PL11. Разработка языков программирования

Общие принципы проектирования языков

Задачи проектирования

Модели типизации

Модели структур данных

Модели структур управления

Механизмы абстракции

CS340. Создание компиляторов

CS341. Проектирование языков программирования

CS342. Семантики языков программирования

CS343. Парадигмы программирования

CS344. Функциональное программирование

CS345. Логическое программирование

CS346. Языки сценариев

HC. Взаимодействие человека и машины

HC1. Основы взаимодействия человека и машины

Мотивация: почему следует беспокоиться о людях?

Аспекты человеко-машинного взаимодействия (инструментальные средства, гипермедиа в web, коммуникации)

Ориентированные на человека разработка и оценка программного обеспечения

Человеческие модели производительности: восприятие, движение и узнавание

Человеческие модели производительности: культура, коммуникации и организации

Приспособление к человеческому разнообразию

Принципы хорошего дизайна и хороших проектировщиков; инженерные компромиссы

Введение в тестирование на пригодность к использованию (usability testing)

HC2. Построение простого графического интерфейса

Основы графических интерфейсов пользователя (GUI)

Инструментальные средства для разработки GUI

HC3. Оценка программного обеспечения, ориентированного на человека

Выявление задач оценивания

Оценка без пользователей: сквозные просмотры, KLM, руководящие документы и стандарты

Оценка с участием пользователей: тестирование на пригодность к использованию, интервью, обзор, эксперимент

HC4. Разработка программного обеспечения, ориентированного на человека

Подходы, характеристики и обзор процесса

Функциональность и пригодность к использованию: анализ задач, интервью, обзоры

Спецификация взаимодействия и представления Методы и средства прототипирования

"Бумажное" прототипирование

Наследование и динамическое связывание

Языки прототипирования и средства построения GUI

HC5. Проектирование графического интерфейса пользователя

Выбор стилей и методов взаимодействия с пользователем

Аспекты HCI для типовых экранных элементов

Аспекты HCI при проектировании экрана: размещение компонент, цвет, шрифты, обозначения

Обработка ошибок пользователя

Более сложные аспекты интерфейса: визуализация, представление, метафора

Способы взаимодействия: графика, звук и осязание

3D-интерфейс и виртуальная реальность

HC6. Программирование графического интерфейса пользователя

Системы управления взаимодействием с пользователем (UIMS), независимость диалога и уровни анализа, модель Сихайма

Классы экранных элементов

Управление событиями и взаимодействием с пользователем

Управление геометрией

Средства создания GUI и UI-среды программирования

Кросс-платформенное проектирование

HC7. Человеко-машинные аспекты мультимедиа-систем

Классификация и архитектуры информации: иерархии, гипермедиа

Извлечение информации и производительность действий человека

Поиск в Web

Использование языков запросов к базам данных

Графика

Звук

Проектирование HCI для информационных мультимедиа-систем

Распознавание речи и обработка естественного языка

Применение информации и мобильные компьютеры

HC8. Человеко-машинные аспекты сотрудничества и коммуникаций

[[Технологии совместного использования, предназначенные для выполнения специальных задач: подготовка документов, многопользовательские игры]]

Асинхронные средства коммуникаций внутри коллектива: электронная почта, электронные доски объявлений

Синхронные средства коммуникаций внутри коллектива: дискуссионные комнаты, конференции

Online-сообщества: MUDs/MOOs]]

Виртуальные персонажи и интеллектуальные агенты

CS350. Проектирование и оценка эргономичных структур

CS351. Графические пользовательские интерфейсы

CS352. Разработка мультимедийных систем

CS353. Разработка диалоговых систем

CS354. Использование компьютеров в коллективе

GV. Компьютерная графика и визуализация

GV1. Фундаментальные методы в графике

Иерархия графического программного обеспечения Использование графических API

Простые цветовые модели (RGB, HSB, CMYK)

Однородные координаты

Аффинные преобразования (масштабирование, вращение, перенос)

Преобразования представления

Отсечение (clipping)

GV2. Графические системы

Системы растровой и векторной графики

Устройства вывода видеоинформации

Физические и логические входные устройства

Проблемы, с которыми сталкиваются разработчики графических систем

GV3. Графические коммуникации

Психодинамика цвета и взаимодействия между цветами

Модификации цвета для людей с недостатками зрения

Культурное значение различных цветов

Использование эффективной псевдоцветовой палитры для изображений, рассчитанных на заданную аудиторию

Структурирование представлений для улучшения восприятия

Модификация изображений для эффективного представления в форме видеоинформации или тиражирования на бумаге

Использование легенды для представления информации о смысле цветов или других визуальных данных

Использование текста в изображениях для представления контекста и фоновой информации

Обратная связь с пользователем при графических операциях

GV4. Геометрическоемоделирование

Полигональное представление трехмерных объектов

Параметрические полигональные кривые и поверхности

Представление с помощью конструктивной блочной геометрии (CSG)

Неявное представление кривых и поверхностей

Методы пространственного подразделения

Процедурные модели

Деформируемые модели

Поверхности подразделения

Моделирование с разным уровнем детализации

Реконструкция

GV5. Основы

рендеринга

Алгоритмы генерации прямых (Брезенхэм)

Генерация шрифтов: контурные и растровые шрифты

Источники света и свойства материалов

Рассеянное, диффузное и зеркальное отражение

Модель отражения Фонга

Растеризация полигональной поверхности; плоская заливка, заливка по методам Гуро и Фонга

Текстурирование, рельефная текстура, текстура среды

Введение в трассировку лучей

Синтез изображений, методы семплирования и сглаживание

GV6. Углубленное изучение рендеринга

Уравнения переноса

Алгоритмы трассировки лучей

Трассировка фотонов

Учет эффекта освещения отраженным светом (radiosity) для вычисления общей освещенности, зависимость от формы

Эффективные подходы к расчету глобальной освещенности

Методы Монте-Карло для расчета глобальной освещенности

Рендеринг на основе изображения, панорамный вид

Рендеринг сложных явлений природы

Нефотореалистичный рендеринг

GV7. Более сложные методы

Квантование цвета

Сканирующее преобразование двумерного примитива

Разбиение кривых поверхностей

Методы удаления скрытых поверхностей

Z-буфер и кадровый буфер, цветовые каналы (альфа-канал)

Более сложные методы геометрическогомоделирования

GV8. Компьютерная анимация

Анимация по ключевым кадрам

Анимация камеры

Система сценариев

Анимация сочлененных структур: обратная кинематика

Захват движения (motion capture)

Процедурная анимация

Деформация

GV9. Визуализация

Визуализация векторных полей, тензоров и потоковых данных

Визуализация скалярных полей или полей высот

Простая визуализация объемных данных: трассировка лучей, функции преобразования, сегментация, аппаратное обеспечение

Визуализация информации: проекция и методы параллельных координат

GV10. Виртуальная реальность

Стереоскопический дисплей

Имитация обратной связи, осязательные устройства

Определение позиции смотрящего

Обнаружение столкновений Вычисление видимости

Критичный ко времени рендеринг, несколько уровней детализации (LOD)

Системы виртуальной реальности (VR), основанные на изображениях

Распределенные системы VR, совместная работа с помощью компьютерной сети

Интерактивное моделирование

Проблемы пользовательского интерфейса

Приложения в медицине, моделировании и обучении

GV11. Компьютерное зрение

Получение изображений

Цифровое изображение и его свойства

Предварительная обработка изображений

Сегментация (установление пороговых значений, сегментация на основе ребер и зон)

Представление формы и распознавание объектов

Анализ движения

Примеры (распознавание объектов, слежение за объектом)

CS355. Компьютерная графика

CS356. Компьютерная мультипликация

CS357. Визуализация

CS358. Виртуальная реальность

CS359. Генетические алгоритмы

IS. Интеллектуальные системы

IS1. Основные вопросы, связанные с интеллектуальными системами

История искусственного интеллекта

Философские вопросы

Тест Тьюринга

Мысленный эксперимент с "китайской комнатой"

Этические проблемы в искусственном интеллекте

Фундаментальные определения

Оптимальное рассуждение и человеческое рассуждение

Оптимальное поведение и человеческое поведение

Моделирование мира

Роль эвристики

IS2. Поиск решений

Пространство задач

Метод "грубой силы" (поиск в ширину, поиск в глубину, поиск в глубину с итеративным углублением)

Поиск по первому наилучшему совпадению (общий поиск, алгоритм Дейкстры, A*, допустимость A*)

Игры с двумя участниками (минимаксный метод, альфа-бета отсечение)

Поиск допустимого решения (перебор с возвратами и методы локального поиска)

IS3. Представление знаний и вывод

Обзор логики высказываний и предикатов

Метод резолюций и доказательство теорем

Немонотонный вывод

Вероятностные рассуждения

Теорема Байеса

IS4. Углубленное изучение поиска

Генетический алгоритм

Метод "отжига" (simulated annealing)

Локальный поиск

IS5. Углубленное изучение представления знаний и вывода

Структурное представление

Фреймы и объекты

Логика описания

Системы наследования Немонотонный вывод

Неклассическая логика

Рассуждение по умолчанию

Проверка доверительности

Логика предпочтений

Интеграция источников знаний

Агрегация конфликтующих убеждений

Рассуждение в задачах действия и изменений

Ситуационное исчисление

Исчисление событий

Проблема разветвления

Временное и пространственное мышление

Неопределенности

Вероятностное рассуждение

Сети Байеса

Нечеткие множества и теория вероятностей

Теория принятия решения

Представление знаний для диагностики и качественное представление

IS6. Агенты

Определение агентов

Примеры успешного использования и реальные системы, основанные на агентах

Архитектуры агентов

Простые реактивные агенты

Реактивные планировщики

Многоуровневые архитектуры

Примеры архитектур и приложений Теория агентов

Обязательства

Намерения

Агенты, основанные на теории принятия решений

Марковские процессы принятия решений (MDP)

Программные агенты, персональные помощники, доступ к информации

Совместно работающие агенты

Агенты, предназначенные для сбора информации

Правдоподобные агенты (синтетические характеры, моделирование эмоций у агентов)

Самообучающиеся агенты

Мультиагентные системы

Экономические соображения в пользу мультиагентных систем

Совместно работающие агенты

Команды агентов

Моделирование агентов

Многоагентное обучение

Введение в теорию роботов-агентов

Мобильные агенты

IS7. Обработка естественного языка

Детерминированные и стохастические грамматики

Алгоритмы анализа

Методы, основанные на совокупности текстов

Информационный поиск

Перевод c одного языка на другой

Распознавание речи

IS8. Обучение машины и нейронные сети

Определение и примеры обучения машины

Обучение под наблюдением

Использование деревьев решений в обучении

Обучаемые нейронные сети

Обучаемые доверительные сети

Алгоритм ближайшего соседа

Теория обучения

Проблема сверхпригодности

Усиленное обучение

IS9. Системы искусственного интеллекта с планируемым поведением

Определения и примеры систем с планируемым поведением

Планирование как поиск

Планирование с участием оператора

Пропозициональное планирование

Расширенные системы планирования (системы планирования, основанные на случаях использования, обучающиеся и вероятностные системы)

Статические системы планирования

Планирование и исполнение

Планирование и робототехника

IS10. Робототехника

Обзор

Реально использующиеся робототехнические системы

Планирование в сравнении с реактивным управлением

Неопределенность в управлении

Очувствление (sensing)

Модели мира

Пространство конфигураций

Планирование

Очувствление

Подготовка программ для роботов

Навигация и управление

CS360. Интеллектуальные системы

CS361. Автоматическое доказательство теорем

CS362. Системы с базами знаний

CS363. Обучение машины

CS364. Системы планирования

CS365. Обработка естественного языка

CS366. Агенты

CS367. Робототехника

CS368. Символьные вычисления

CS369. Генетические алгоритмы

IM. Управление информацией

IM1. Информационные модели и системы

История и причины появления информационных систем

Хранение и поиск информации (Information Storage & Retrieval)

Приложения теории управления информацией

Получение и представление информации

Анализ и индексирование

Поиск, извлечение данных, связывание, навигация

Конфиденциальность, целостность, безопасность и сохранность информации

Масштабируемость, производительность и эффективность

IM2. Системы баз данных

История и причины появления систем баз данных

Компоненты системы баз данных

Функции систем управления базами данных (СУБД)

Архитектура базы данных и независимость данных

Использование языка запросов к системе баз данных

IM3. Моделирование данных

Моделирование данных

Концептуальные модели (включая модель "объект-отношение" и язык UML)

Объектно-ориентированная модель

Реляционная модель данных

IM4. Реляционные базы данных

Отображение концептуальной схемы в реляционную схему

Целостность сущностей-объектов и ссылочная целостность

Реляционная алгебра и реляционное исчисление

IM5. Языки запросов к базам данных

Обзор языков, применяемых в базах данных

Язык SQL (определение данных, написание запросов, команда обновления, ограничения, целостность)

Оптимизация запросов

Запросы по образцу и среды четвертого поколения

Встраивание непроцедурных запросов в процедурный язык

Введение в объектно-ориентированный язык запросов (Object Query Language)

IM6. Проектирование реляционных баз данных

Проектирование базы данных

Функциональная зависимость

Нормальные формы (1НФ, 2НФ, 3НФ, НФБК)

Многозначная зависимость (4НФ)

Зависимости соединения и пятая нормальная форма (5НФ)

Теория представлений

IM7. Обработка транзакций

Транзакции

Сбой и восстановление

Управление параллелизмом

IM8. Распределенные базы данных

Распределенные хранилища данных

Обработка распределенных запросов

Модель распределенных транзакций

Управление параллелизмом

Гомогенные и гетерогенные решения

Клиент-сервер

IM9. Проектирование физической структуры базы данных

Хранилище и файловая структура

Индексированные файлы

Хешированные файлы

Файлы сигнатур

B-деревья

Файлы с плотными индексами

Файлы с записями переменной длины

Эффективность и настройка базы данных

IM10. Извлечение информации

Полезность извлечения информации

Ассоциативные и последовательные шаблоны

Кластеризация данных

Анализ потребительской корзины

Очистка данных

Визуализация данных

IM11. Хранение и поиск информации

Символы, строки, кодирование, текст

Документы, электронная публикация, разметка и языки разметки

Деревья, предметные указатели, PAT-деревья, файлы сигнатур, индексирование

Морфологический анализ, анализ разветвлений, фразы, "черные списки"

Плотности распределения термов, неопределенность, нечеткость, взвешивание

Векторное пространство, вероятностная, логическая и расширенная модели

Информационные потребности, релевантность, оценка, эффективность

Тезаурус, онтология, классификация и категоризация, метаданные

Библиографическая информация, библиометрика, цитаты

Маршрутизация и фильтрация

Поиск и стратегия поиска, поведение алгоритма поиска информации, моделирование пользователя, обратная связь

Резюмирование и визуализация информации

Интеграция цитирования, ключевых слов, схемы классификации и другие термины

Протоколы и системы (включая Z39.50, системы OPAC, поисковые WWW-машины, исследовательские системы)

IM12. Гипертекст и гипермедиа

Модели гипертекста (исторические первые модели, web, Dexter, Amsterdam, HyTime)

Сервисы связи, машины, и (распределенные) архитектуры гипертекста

Узлы, композиты и якоря (anchors)

Измерения, единицы измерения, размещения, интервалы

Просмотр, навигация, виды, масштабирование

Автоматическая генерация ссылок

Представление, преобразование, синхронизация

Разработка, чтение и аннотирование

Протоколы и системы (включая web, HTTP)

IM13. Мультимедийная информация и системы мультимедиа

Устройства, драйверы устройств, сигналы и протоколы управления, системы DSP

Приложения, редакторы мультимедиа-информации, авторские системы и авторская разработка

Потоки/структуры, захват/представление/преобразование, пространства/области, сжатие/кодирование

Анализ на основе содержимого, индексирование и поиск аудио-, видео-информации и изображений

Представление, рендеринг, синхронизация, мультимодальная интеграция/интерфейсы

Доставка данных в режиме реального времени, качество обслуживания, аудио/видео конференции, видео по запросу

IM14. Цифровые библиотеки

Оцифровка, хранение и обмен

Цифровые объекты, композиты и пакеты

Метаданные, каталогизация, подача документов автором

Именование, репозитории, архивы

Пространства (концептуальные, географические, 2/3D, VR)

Архитектуры (агенты, шины, обертки/посредники), взаимодействие

Сервисы (поиск, связывание, просмотр и так далее)

Управление правами на интеллектуальную собственность, конфиденциальность, защита ("водяные знаки")

Архивация и сохранение, целостность

CS370. Базы данных

CS371. Устройство баз данных

CS372. Обработка транзакций

CS373. Распределенные и объектные базы данных

CS374. Информационная проходка

CS375. Организация информационных хранилищ

CS376. Мультимедийные информационные системы

CS377. Электронные библиотеки

SP. Социальные и профессиональные вопросы

SP1. История информатики

Предыстория - мир до 1946 года

История аппаратного и программного обеспечения компьютеров, компьютерных сетей

Пионеры информатики

SP2. Социальный контекст информатики

Введение в социальные последствия информатики

Социальные последствия компьютерных сетей

Рост, управление и доступ к Internet

Вопросы пола

Международные вопросы

SP3. Методы и средства анализа

Выдвижение и оценка этических аргументов

Выявление и оценка альтернатив с этической точки зрения

Понимание социального контекста проектирования

Выявление предположений и ценностей

SP4. Профессиональная и этическая ответственность

Общественные ценности и законы, по которым мы живем

Природа профессионализма

Различные формы профессиональной идентификации, их достоинства и недостатки

Роль профессионализма в общественной политике

Необходимость осознания последствий

Расхождение этических взглядов и сигнализация разногласий

Кодексы этики, поведения и практики (IEEE, ACM, SE, AITP и др.)

Борьба с притеснением и дискриминацией

Политика "допустимого использования" компьютеров на рабочем месте

SP5. Недостатки компьютерных систем и риски, связанные с их применением

Исторические примеры рисков, связанных с программным обеспечением (например, случай с Therac-25)

Следствия сложности программного обеспечения

Оценка рисков и управление ими

SP6. Интеллектуальная собственность

Основы интеллектуальной собственности

Авторские права, патенты и коммерческие тайны

Нарушение авторских прав на программное обеспечение

Патенты на программное обеспечение

Международные вопросы, касающиеся интеллектуальной собственности

SP7. Конфиденциальность и гражданские свободы

Этические и правовые основы обеспечения конфиденциальности (privacy protection)

Последствия использования больших баз данных с точки зрения конфиденциальности

Технологические стратегии обеспечения конфиденциальности

Свобода выражения в киберпространстве

Межнациональные и межкультурные последствия

SP8. Компьютерные преступления

История и примеры компьютерных преступлений

"Взлом" ("хакерство") и его эффекты

Вирусы, черви и троянские кони

Стратегии предотвращения преступлений

SP9. Экономические вопросы, связанные с применением компьютеров

Монополии и их экономические последствия

Нехватка квалифицированной рабочей силы и качество компьютерных продуктов

Ценовые стратегии в области компьютеров

Различия в доступе к вычислительным ресурсам и возможные последствия этих различий

SP10. Философские концепции

Философские течения, в частности, утилитаризм и деонтология (теория проблем долга и моральных требований)

Проблемы этического релятивизма

Научная этика в исторической перспективе

Различия в научных и философских подходах

CS380. Профессиональное программирование

CS381. Социальный контекст программирования

CS382. Компьютеры и мораль

CS383. Экономические вопросы программирования

CS384. Правовые вопросы, связанные с компьютерами

CS385. Интеллектуальная собственность

CS386. Право на частную жизнь и гражданские свободы

SE. Программная инженерия

SE1. Проектирование ПО

Фундаментальные концепции и принципы проектирования

Шаблоны проектирования (design patterns)

Архитектура ПО

Структурное проектирование

Объектно-ориентированный анализ и проектирование

Проектирование на уровне компонентов

Проектирование с учетом повторного использования

SE2. Использование программных интерфейсов приложений

Программирование с использованием API Браузеры классов и подобные средства

Программирование с помощью примеров Отладка при использовании API

Введение в программирование на основе компонентов

SE3. Программные средства и окружения

Среды программирования

Анализ требований и средства моделирования проекта Инструментальные средства тестирования

Инструментальные средства управления конфигурацией Механизмы интеграции инструментальных средств

SE4. Процессы разработки ПО

Жизненный цикл ПО и модели процесса разработки Модели оценки процесса разработки

Метрики процесса разработки ПО

SE5. Спецификации и требования к ПО

Выявление требований

Методы моделирования и анализа требований

Функциональные и нефункциональные требования

Прототипирование

Основные концепции методов формальной спецификации

SE6. Проверка соответствия ПО

Планирование проверки соответствия (validation planning)

Основы тестирования, включая создание тестового плана и генерацию тестов

Тестирование методом "черного ящика" и "белого ящика"

Тестирование элементов, интеграционное, системное тестирование и проверка соответствия

Объектно-ориентированное тестирование

Проверки равных по рангу и инспекции (peer reviews, inspections)

SE7. Эволюция ПО

Сопровождение ПО

Свойства ПО, пригодного для сопровождения

Реинжиниринг

Унаследованные или устаревшие системы (legacy systems)

Повторное использование ПО

SE8. Управление программными проектами

Управление группой

Процессы, протекающие в коллективе

Организация группы и принятие решений

Роли и ответственности в группе разработчиков

Выявление и назначение ролей

Слежение за состоянием проекта

Решение проблем коллектива Планирование проекта

Методы оценки и измерения ПО

Анализ рисков

Обеспечение качества ПО

Управление конфигурацией программного продукта

Инструментальные средства управления проектом

SE9. Компонентно-ориентированная разработка

Основы

Определение и свойства компонентов

Компоненты и интерфейсы

Интерфейс как контракт

Выгоды, которые дает применение компонентов

Основные методы

Разработка и сборка компонентов

Соотношение с моделью "клиент-сервер" и шаблонами

Использование объектов и сервисы, предоставляемые объектами за время своего жизненного цикла

Использование объектных брокеров

Маршаллинг

Приложения (включая использование мобильных компонент)

Архитектура систем, основанных на компонентах

Компонентно-ориентированное проектирование

Обработка событий: обнаружение, извещение и ответ

Промежуточное программное обеспечение

Объектно-ориентированная парадигма в промежуточном программном обеспечении

Брокеры объектных запросов

Мониторы обработки транзакций

Системы управления бизнес-процессами

Современные инструментальные средства

SE10. Формальные методы

Концепции формальных методов

Языки формальных спецификаций

Исполнимые и неисполнимые спецификации

Пред- и постусловия

Формальная верификация

SE11. Надежность ПО

Модели надежности ПО

Устойчивость и восстановление после сбоев

Классификация дефектов

Вероятностные методы анализа

SE12. Разработка специализированных систем

Системы реального времени Системы "клиент-сервер"

Распределенные системы Параллельные системы

Системы, основанные на Web

Сильно интегрированные системы

CS390. Разработка ПО

CS391. Программная инженерия

CS392. Проектирование ПО

CS393. Проектирование ПО и формальные спецификации

CS394. Практическая программная инженерия

CS395. Улучшение процессов разработки ПО

CS396. Компонентное программирование

CS397. Программные окружения

CS398. Системы с повышенными требованиями к надежности

CN. Вычислительная математика и численные методы

CN1. Численный анализ

Арифметика с плавающей точкой

Ошибка, устойчивость, сходимость Ряды Тейлора

Итеративные методы поиска корней уравнения (метод Ньютона)

Подбор кривых; приближение функций

Численное дифференцирование и интегрирование (правило Симпсона)

Явные и неявные методы

Дифференциальные уравнения (метод Эйлера)

Линейная алгебра

Конечные разности

CN2. Исследование операций

Линейное программирование

Целочисленное программирование

Симплекс-метод

Вероятностное моделирование

Теория очередей

Сети Петри

Марковские цепи

Оптимизация

Анализ сетей и алгоритмы поиска путей

Предсказание и оценка

Анализ решений

Предсказание

Управление рисками

Эконометрика, микроэкономика

Анализ чувствительности

Динамическое программирование

Примеры приложений

Программные средства

CN3. Моделирование

Случайные числа

Генерация псевдослучайных чисел

Тестирование генераторов

Методы Монте-Карло

Введение в функции распределения

Моделирование

Дискретное моделирование

Аналоговое моделирование

Верификация и проверка соответствия моделей

Анализ входных данных

Анализ выходных данных Модели теории очередей

Примеры приложений

CN4. Высокопроизводительные вычисления

Введение в высокопроизводительные вычисления

История и важность вычислительных наук

Обзор прикладных областей

Обзор требуемых навыков

Высокопроизводительные вычисления

Архитектуры процессоров

Системы памяти для высокопроизводительных систем

Устройства ввода/вывода

Конвейерная обработка

Параллельные языки и архитектуры

Аналитическая визуализация

Представление результатов

Форматы данных

Инструментальные средства и пакеты визуализации данных

Примеры задач

Модели океана и атмосферы

Распространение сейсмической волны

Системы N-тел (алгоритм Барнс-Хата)

Химические реакции

Агрегатные переходы

Поток жидкости

CS304. Методы вычислений

CS305. Численный анализ

CS306. Исследование операций

CS307. Статистическое моделирование

CS308. Математическое программирование

CS309. Вычислительная биология