═══════════════════ COMPUTING CURRICULA 1991
═════════ рекомендуемая учебная программа по дисциплине
══════════ "Вычислительная техника и программирование"
════════════════════════════════════════════════════
═ ═════════ – Перечень тем, обязательных для изучения══════════════
═
═══
════════ AL. АЛГОРИТМЫ И СТУКТУРЫ ДАННЫХ (47 лекционных часов)
═══
══════ AL1. Основные структуры данных (13 лекц. часов)
═══ Определение, представление и использование основных структур═ данных (списков, массивов, таблиц, стеков, очередей, деревьев, графов).
═══ Темы лекций:
═════ - определение основных структур данных, основные операции
═════ - примеры использования
═════ - векторное и списковое представление, проблемы, сравнение
═══ Практические═ занятия:═ Использование структур в типичных программистских ситуациях (перебор с возвратами, синтаксический анализ, дискретное моделирование и т.п.). Сравнение различных структур и представлений. Реализация выбранных структур.
═══
══════ AL2. Абстрактные типы данных (2 лекц. часа)
═══ Концепция АТД, отделение деталей реализации от применения.
═══ Темы лекций:
════ - назначение АТД
════ - реализация АТД в языках программирования (с примерами)
═══ Практические занятия:═ Разработка программы с помощью АТД,═ подготовленных преподавателем, а затем своя реализация этих АТД.
═══
══════ AL3. Рекурсивные алгоритмы (3 лекц. часа)
═══ Понятие и применение рекурсивных алгоритмов при решении задач
═══ Темы лекций:
════ - введение в рекурсивные алгоритмы
════ - связь с математической индукцией
════ - сравнение рекурсивных и итеративных алгоритмов
═══ Практические занятия: Трассировка рекурсивной программы с наблюдением за изменением значений переменных и параметров. Реализация рекурсивного алгоритма.
═══
══════ AL4. Анализ сложности алгоритмов (4 лекц. часа)
═══ Понятие═ вычислительной сложности (по времени и памяти) и его применение для анализа алгоритмов.
══ ═Темы лекций:
════ - асимптотические верхние и средние оценки═ для итеративных и рекурсивных алгоритмов
════ - сравнение алгоритмов по времени и памяти
═══ Практические═ занятия:═ Практическое═ подтверждение═ теоретических оценок сложности с учетом хороших, типичных и худших случаев.
═══
══════ AL5. Классы сложности (4 лекц. часа)
═══ Обзор классов сложности (P и NP), верхние, средние и нижние оценки
═══ Темы лекций:
════ - P и NP классы сложности; разрешимые и неразрешимые задачи, приближенное решение неразрешимых задач
════ - получение нижних оценок (например, для сортировки)
════ - NP-полнота
═══ Практические занятия: Сравнение по времени алгоритмов из различных классов═ сложности, чтобы увидеть различие между малыми и большими задачами, между средними и худшими случаями.
══════════════════
══════ AL6. Сортировка и поиск (6 лекц. часов)
═══ Знакомство═ и сравнение (по времени и памяти) различных алгоритмов сортировки и поиска.
═══ Темы лекций:
════ - O(n^2) алгоритмы сортировки═ (например,═ выбором═ и═ вставкой); оценки сложности, лучшие и худшие случаи
════ - O(n*log n) алгоритмы сортировки═ (например, быстрая сортировка, метод слияния); оценки сложности
════ - другие методы сортировки (метод Шелла и т.д.)
════ - сравнение алгоритмов сортировки
════ - последовательный и бинарный поиск,═ поиск═ в═ двоичном═ дереве; оценки сложности, лучшие и худшие случаи
════ - хэширование, устранение коллизий
═══ Практические занятия: Реализовать алгоритмы сортировки и поиска═ и экспериментально подтвердить теоретические оценки.
═══
══════ AL7. Вычислимость и неразрешимость (6 лекц. часов)
═══ Модели═ вычислимых═ функции,═ неразрешимые проблемы. Универсальная функция. Тезис Черча.
═══ Темы лекций:
════ - модели вычислимых функций═ (выбрать из рекурсивных функций, машины Тьюринга, лямбда исчисления м т.п.); тезис Черча
════ - универсальные машины (например, Тьюринга)
════ - разрешимые и перечислимые проблемы
════ - неразрешимые проблемы (например, проблема останова)
═══ Практические занятия: Используя имитатор (например, машины Тьюринга), написать и выполнить алгоритмы решения конкретных задач.
═══
══════ AL8. Методы решения задач (6 лекц. часов)
═══ Различные═ методы═ построения алгоритмов (например, поиска на графах, матричных операций и т.п.).
═══ Темы лекций:
════ - алгоритмы═ полного═ перебора;═ определение,═ примеры,═ полнота,
══════ сложность
════ - алгоритмы"разделяй и властвуй"
════ - алгоритмы перебора с возвратами
═══ Практические═ занятия: Разработка и реализация решения задач с помощью подходящих алгоритмов, выбор адекватного метода решения.
═══
══════ AL9. Параллельные и распределенные вычисления (3 лекц. часа)
═══ Основы программирования на вычислителях с параллельной и распределенной архитектурой; иллюстрация того, как параллелизм значительно ускоряет═ вычисления═ по═ сравнению═ с последовательными алгоритмами (на примере реализации операций +, MAX, AND и т.п.).
═══ Темы лекций:
════ - модели вычислителей с параллельной архитектурой - простые параллельные алгоритмы
═══ Практические занятия: Реализовать и сравнить алгоритмы решения одной и той же задачи на последовательных и параллельных ЭВМ
════
════
═══
════════ AАРХИТЕКТУРА ЭВМ (59 лекционных часов)
═══
══════ AR1. Цифровая логика (12 лекц. часов)
═══ Физические основы ЭВМ. Системотехника.
═══ Темы лекций:
════ - основные логические элементы ЭВМ, логика переключений,═ минимизация и реализация переключательных функций
════ - задержки и помехи
════ - технологии
════ - устройства (дешифраторы, мультиплексоры, сумматоры и т.п.)
════ - виды памяти (ROM, PROM, EPROM, RAM и т.д.)
════ - анализ и синтез синхронных и асинхронных циклов
═══ Практические занятия: Проектирование простых логических схем; реализация машинных операций (например, сложения) на основе заданных═ логических элементов.
═══
══════ AR2. Цифровые системы═ (6 лекц. часов)
═══ Передача информации между устройствами ЭВМ, шины связи,═ различные способы описания устройств.
═══ Темы лекций:
════ - нотация для передач данных между регистрами
════ - алгоритмическое описание машины, диаграммы управления, передача
══════ сигналов
════ - структуры шин
════ - итерация, стек, "разделяй и властвуй"
════ - декомпозиция,═ выбор, экономичность
════ - диаграммы блоков, временные диаграммы, язык описания передач
═══ Практические═ занятия:═ Примеры передачи данных на алгоритмическом уровне описания машины с показом временных диаграмм
═══
══════ AR3. Машинное представление данных (3 лекц. часа)
═══ Основные способы представления чисел и символов в ЭВМ
═══ Темы лекций:
════ - представление чисел (с фиксированной и плавающей точкой, двоично-десятичное)
════ - представление нечисловых данных; системы кодировки
═══
══════ AR4. Система команд. Язык ассемблера (15 лекц. часов)
═══ Различные системы команд и способы адресации.═ Прерывания.═ Микропрограммирование. Язык ассемблера.
═══ Темы лекций:
════ - базовая структура машин фон Неймана, такт работы процессора
════ - система команд
════ - машинный язык и язык ассемблера
════ - способы адресации═ (прямая, косвенная, регистровая, индексная и др.)
════ - процессор, его регистры
════ - ввод-вывод, прерывания
════ - аппаратная и микропрограммая реализация машинных операций
═══ Практические занятия: Разработка программ на языке ассемблера, отладка программ, использование отладчика. Сравнение на имитаторах═ различных систем команд.
═══
══════ AR5. Организация памяти в ЭВМ (13 лекц. часов)
═══ Физические основы хранения данных. Структура и иерархия запоминающих устройств. Кэш-память. Виртуальная память. Прямой доступ к памяти.
═══ Темы лекций:
════ - технология запоминающих устройств
════ - кодирование, сжатие и целостность данных
════ - иерархия запоминающих устройств
════ - основные методы организации памяти, шины связи, цикл выборки
════ - кэш-память, чтение-запись
════ - виртуальная память
════ - системы управления шинами, прямой доступ к памяти
════ - сбои, устойчивость
═══
══════ AR6. Ввод-вывод. Прерывания (5 лекц. часов)
═══ Осуществление ввода-вывода. Обработка прерываний.
═══ Темы лекций:
════ - методы управления вводом-выводом, прерывания
════ - обработка прерываний, синхронизация, подтверждение связи
════ - внешняя память, физическая организация, драйверы
═══ Практические занятия: Эксперименты с имитатором для═ демонстрации процессов синхронизации и подтверждения связей.
═══
══════ AR7. Альтернативные архитектуры ЭВМ (5 лекц. часов)
═══ Машины со стековой,═ векторной,═ многопроцессорной,═ гиперкубовой,
RISK и CISC архитектурой. Машины с параллельной архитектурой.
═══ Темы лекций:
════ - сравнение машин с различной архитектурой
════ - RISC и CISC
════ - параллельные архитектуры (VLIM, SISD, MISD, SIMD, MIMD)
════ - многопроцессорные системы с общей памятью
═══
════
═══
════════ AI. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ (9 лекционных часов)
════════
══════ AI1. История и приложения ИИ (3 лекц. часа)
═══ История,═ цели, социальные и философские аспекты ИИ. Возможности и ограничения ИИ. Применение ИИ в различных областях.
═══ Темы лекций:
════ - история, область и ограничения ИИ; тест Тьюринга; игры
════ - социальные, этические, правовые и философские аспекты
════ - экспертные системы и оболочки
════ - общение с ЭВМ на естественном языке
════ - понимание речи, обработка изображений
════ - роботы и планирование действий
═══ Практические═ занятия:═ Общение═ с экспертной системой. Построение небольшой═ экспертной═ системы с помощью оболочки и на языках ИИ (Лисп или Пролог).
═══
══════ AI2. Решение задач в пространстве состояний (6 лекц. часов)
═══ Основые классы алгоритмов в ИИ. Представление задачи в виде пространства состояний и методы поиска в нем, эвристический поиск.
═══ Темы лекций:
════ - задачи и пространства состояний; представление знаний
════ - алгоритмы перебора (вглубь, вширь); прямой и обратный поиск
════ - эвристический поиск, анализ целей и средств, минимаксный метод
═══ Практические занятия: Реализация различный поисковых методов с использованием подходящих языков программирования. Наблюдение за поведением различных алгоритмов эвристического поиска, оценка═ их═ эффективности.
════
═══
════════ DB. БАЗЫ ДАННЫХ И ИНФОРМАЦИОННЫЙ ПОИСК (9 лекционных часов)
═══
══════ DB1. Обзор, модели и применение баз данных (4 лекц. часов)
═══ Цели, функции, модели, состав и применение СУБД.
═══ Темы лекций:
════ - история и причины появления СУБД
════ - состав СУБД; данные, словари,═ система═ управления,═ прикладные
══════ программы, пользователи, администратор
════ - концептуальные модели данных
════ - функции типичной СУБД; методы доступа, защита
════ - последние достижения и применения (гипертекст, оптические диски и др.)
════ - социальные аспекты СУБД, безопасность данных
═══ Практические═ занятия:═ Используя═ СУБД,═ построить небольшую базу данных и оценить возможности системы. Разработать (в═ составе═ группы) концептуальную модель некоторой задачи.
═══════════════════════
══════ DB2. Реляционная модель данных (5 лекц. часов)
═══ Реляционная модель данных, отображение на нее концептуальной модели. Концепция непроцедурного языка запросов.
═══ Темы лекций:
════ - реляционная модель, отображение на нее концептуальной модели
════ - представление отношений
════ - реляционная алгебра
════ - язык запросов, его основные возможности,═ включение в процедурный язык
═══ Практические занятия: Используя процедурный язык, реализовать операции алгебры отношений.
═══
════
═══
════════ HU. ЧЕЛОВЕКО-МАШИННОЕ ВЗАИМОДЕЙСТВИЕ (8 лекц. часов)
═══════════
═════ HU1. Интерфейс с пользователем (5 лекц. часов)
═══ Интерфейс с пользователем на аппаратном и программном уровнях. Командные интерпретаторы и оболочки. Оперативные подсказки.
═══ Темы лекций:
════ - средства общения: дисплеи, клавиатура, принтеры и др.
════ - интерфейс; системы меню, командные языки, мышь
════ - свойства общего интерфейсного пакета
═══ Практические занятия: Сравнение различный стратегий взаимодействия с═ пользователем═ (на основе двух или более систем). Исследование различных пакетов с целью сформулировать требования к хорошему интерфейсу с пользователем.
══════════════════════════════════════════
══════ HU2. Машинная графика (3 лекц. часа)
═══ Аппаратные и программные средства графики.
═══ Темы лекций:
════ - графические устройства и их свойства (векторные и растровые устройства, буфер изображения и т.д.)
════ - графические═ примитивы;═ примитивы═ двух- и трехмерной графики,
══════ текстовые примитивы
════ - графические пакеты, графические стандарты (GKS, PHIGS и др.)
═══ Практические занятия: Выполнение упражнений по графике, предложенных самими студентами.
═══
═══
═══
════════ NU. ЧИСЛЕННЫЕ И СИМВОЛЬНЫЕ ВЫЧИСЛЕНИЯ (7 лекц. часов)
═══
══════ NU1. Представление чисел, ошибки вычислений═ (3 лекц. часа)
═══ Основы обнаружения и контроля за ошибками при вычислениях. Переносимость математического обеспечения.
═══ Темы лекций:
════ - точность представления чисел
════ - ошибки вычислений, проблемы переноса программ
════ - хорошо- и плохо-обусловленные задачи
═══════════════════════
══════ NU2. Методы приближенных вычислений═ (4 лекц. часа)
═══ Знакомство со стандартными методами приближенных вычислений═ и═ их применением в различных задачах (например, для интегрирования и дифференцирования).
═══ Темы лекций:
════ - методы приближенного решения задач (метод Ньютона и др.)
════ - классификация ошибок; вычислительные, методологические и другие
══════ ограничения
════ - обзор применений методов в различных областях
═══ Практические═ занятия: Разработка программы решения системы линейных уравнений методом Гаусса (исключения переменных) и═ применение═ ее для решения при хорошо- и плохо-обусловленных данных.
═══
═══
══════════
════════ OS. ОПЕРАЦИОННЫЕ СИСТЕМЫ═ (31 лекционный час)
═══
══════ OS1. История и философия ОС═ (3 лекц. часа)
═══ Эволюция ЭВМ и ОС. Экономические проблемы использования ЭВМ. Обзор известных ОС (Multics, OS/VM, Unix, Atlas, Hydra).
═══ Темы лекций:
════ - эволюция аппаратуры ЭВМ
════ - экономические затраты и ограничения
════ - основные типы архитектуры ОС (монолитная, уровневая, объектно-ориентированная)
════ - исторически значимые ОС
══════════════
══════ OS2. Задачи и процессы (2 лекц. часа)
═══ Мультипрограммный═ режим,═ его═ достоинства.═ Управление задачами,разделение времени. Концепция процесса.
═══ Темы лекций:
════ - задачи, процессы
════ - структуры: список готовности, блоки управления процессами и др.
════ - диспетчеризация, переключение контекстов
════ - роль прерываний
═══ Практические занятия: Разработка и реализация (на═ языке═ высокого уровня или на имитаторе) простого переключателя контектсов.
══════════════════════════════════════════════════ ═══════════
════════════════════════════
══════ OS3. Координация и синхронизация процессов═ (4 лекц. часов)
═══ Совместное выполнение, проблемы. Тупики. Механизмы синхронизации.
═══ Темы лекций:
════ - параллельные процессы
════ - разделение доступа, временные соотношения
════ - тупики: причины, условия, предотвращение
════ - модели и механизмы синхронизации
═══ Практические занятия: Используя имитатор или реальную систему, исследовать последовательность событий при совместном доступа═ при═ различных временных характеристиках процессов. Разработать механизмы синхронизации═ доступа═ м═ доказать невозможность конфликтов. Исследовать проблему тупиков и показать, как их можно избежать.
═══
═══
══════ OS4. Планирование и диспетчеризация═ (3 лекц. часа)
═══ Стратегии планирования с откачкой и═ без═ нее,═ анализ═ стратегий.
Уровни планирования.
═══ Темы лекций:
════ - планирование с откачкой и без нее
════ - планировщики и алгоритмы распределения ресурсов
═══ Практические занятия: Выполнить различные смеси задач на имитаторе или реальной системе при различных методах планирования и═ затем═ проанализировать результаты с целью оценки различных методов.
═══
══════ OS5. Организация физической и виртуальной памяти (4 лекц. часа)
═══ Различные методы организации физической памяти. Организация виртуальной памяти, алгоритиы листания страниц. Рабочее множество.
═══ Темы лекций:
════ - физическая память и регистры
════ - оверлеи, свопинг, разделы памяти
════ - страницы и сегменты
════ - алгоритмы размещения и удаления страниц
════ - рабочее множество, перегрузка
═══ Практические занятия:═ Анализ с помощью имитатора времени доступа, задержек═ и числа обменов при различных алгоритмах листания на различных смесях задач, исследование зависимости от размера страниц,═ выбора удаляемых страниц и других характеристик.
═══
══════ OS6. Управление устройствами (2 лекц. часов)
═══ Закрепленные процессы. Буферизация. Время ожидания.
═══ Темы лекций:
════ - списки свободных устройств, распределение
════ - спецпроцессоры, прерывания
════ - восстановление после сбоев
═══
══════ OS7. Файловые системы═ (4 лекц. часа)
═══ Директории. Последовательное и списковое размещшение файлов.═ Способы доступа.
═══ Темы лекций:
════ - способы размещения файлов (непрерывный, цепочкой)
════ - директории, их структура и содержимое
════ - именование, поиск, доступ, резервное копирование
════ - концепция файлов, основные способы организации файлов, основные
══════ операции над файлами, блокирование и буферизация
════ - последовательные файлы
════ - непоследовательные файлы (хэш-файлы, файлы-деревья, B-деревья)
═══ Практические занятия: Эксперименты (возможно, на имитаторе) с различными файловыми системами: оценка числа обращений к файлу═ в зависимости═ от размера файла, количества свободного пространства на диске и др. характеристик.
═══
══════ OS8. Секретность и защита (3 лекц. часа)
═══ Секретность═ на═ физическом═ и═ логическом уровнях. Защита памяти. Восстановление, целостность.
═══ Темы лекций:
════ - обзор средств безопасности (с примерами)
════ - защита, доступ, аутентификация (пароли, ключи и т.п.)
════ - защита памяти
════ - сбои, восстановление, целостность данных
════
══════ OS9. Сети ЭВМ═ (3 лекц. часа)
═══ Протоколы. Потоки. Межсетевые связи.
═══ Темы лекций:
════ - пакеты протоколов
════ - потоки и дейтаграммы
════ - межсетевое взаимодействие и маршрутизация
════ - серверы, сервис
═══
══════ OS10. Распределенные и реального времени системы (3 лекц. часа)
═══ Распределенная обработка. Синхронизация и тупики. Сбои═ и═ восстановление. Специфика систем реального времени.
═══ Темы лекций:
════ - синхронизация при распределенной обработке
════ - отказы, восстановление
════ - специфические проблемы систем реального времени
═══
═══
═══
════════ PL. ЯЗЫКИ ПРОГРАММИРОВАНИЯ (46 лекционных часов)
═══
════════════════
══════ PL1. История и обзор языков программирования (2 лекц. часа)
═══ Краткая═ история═ основных тенденций. Парадигмы программирования и их отражение в языках.
═══ Темы лекций:
════ - первые языки (Алгол, Фортран, Кобол)
════ - эволюция процедурных языков (на примере линии═ Алгол, ПЛ/1, Паскаль, Эвклид, Модула-2, Ада)
════ - непроцедурные языки: функциональные═ (Лисп),═ логические═ (Пролог), объектно-ориентированные (Смоллток), параллельные (Оккам)
═══
══════ PL2. Виртуальные машины (2 лекц. часа)
═══ Реальные и виртуальные (ВМ) машины. Понимание ЯП═ в═ терминах═ его ВМ. Трансляция как реализация на ВМ с═ последовательным═ переводом═ на реальную машину. Время связывания как важное понятие семантики языков.
═══ Темы лекций:
════ - виртуальные машины для языков программирования
════ - иерархия ВМ, предоставленных пользователю через программы, трансляторы, ОС и т.д.
════ - последствия различного времени связывания для трансляции
═══
══════ PL3. Представление типов данных (2 лекц. часа)
═══ Простые и составные типы. Определение новых типов.
═══ Темы лекций:
════ - представление простых типов данных
════ - описание и представление составных типов (на примере языка Паскаль), динамическое размещение данных
═══ Практические занятия: Решение задачи, требующей использования составных или динамических структур данных.
═══
══════ PL4. Последовательные вычисления (4 лекц. часа)
═══ Выражения, операторы, процедуры.
═══ Темы лекций:
════ - выражения, старшинство операций, побочные эффекты
════ - операторы, простые и сложные
════ - подпрограммы и сопрограммы как абстракция выражений и═ операторов
════ - обработка исключений
═══
══════ PL5. Управление данными, контроль типов (4 лекц. часа)
═══ Разделение═ и═ ограничение═ доступа к данным. Контроль типов.
═══ Темы лекций:
════ - методы═ разделения═ и═ органичения═ доступа═ к═ данным═ (блоки, COMMON, АТД, совмещенные операции)
════ - статическая и динамическая области действия, видимость
════ - способы передачи параметров
════ - механизмы контроля типов
═══ Практические═ занятия:═ Выполнение═ простых═ программ на языках со статической и динамической областями действий имен, чтобы увидеть различие.═ Разработка═ программ на языке с динамической типизацией, чтобы увидеть ее гибкость по сравнению со статической типизацией.
═════
══════ PL6. Управление памятью на этапе счета═ (4 лекц. часа)
═══ Размещение, уничтожение, повторное использование данных.
═══ Темы лекций:
════ - статическое размещение
════ - стековое размещение, связь с рекурсией
════ - размещение в куче
══════ PL7. Конечные автоматы и регулярные выражения (6 лекц. часов)
═══ Конечные автоматы как модель вычисления регулярных выражений. Применение к лексическому анализу.
═══ Темы лекций:
══ ══- детерминированные═ и недетерминированные конечные автоматы,═ их
══════ эквивалентность
════ - регулярные выражения, их эквивалентность конечным автоматам
════ - применения регулярных выражений
═══ Практические занятия: Используя имитатор, построить конечный автомат для заданного языка.
═══
══════ PL8. КС-грамматики и магазинные автоматы (4 лекц. часа)
═══ Контекстно-свободные грамматики как средство формального═ описания синтаксиса языков программирования. Использование магазинных автоматов для синтаксичесого анализа языков.
═══ Темы лекций:
════ - КС-грамматики
════ - недетерминированные═ магазинные═ автоматы,═ их═ эквивалентность
══════ КС-грамматикам
════ - таблично-управляемый анализ, рекурсивный спуск
═══ Практические═ занятия: Разработать таблично-управляемый анализатор для простого КС-языка.
════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════ ══════════════════════════════════════════════
══════ PL9. Трансляторы (3 лекц. часа)
═══ Обзор процесса трансляции. Компиляторы и интерпретаторы.
═══ Темы лекций:
════ - сравнение компиляторов и интерпретаоров
════ - лексический и синтаксический анализ, таблицы имен
════ - генерация кода
════ - методы оптимизации
═══ Практические занятия: Разработка простого═ анализатора═ (использующего,═ например, рекурсивный спуск) арифметических выражений (результат - дерево выражения)
═══
══════ PL10. Семантика языков программирования (2 лекц. часа)
═══ Модели описания семантики.
═══ Темы лекций:
════ - неформальные модели семантики
════ - формальные модели (аксиоматическая,═ денотационная,═ операционная)
════
══════ PL11. Парадигмы программирования═ (10 лекц. часов)
═══ Непроцедурные парадигмы и языки.
═══ Темы лекций:
════ - обзор функциональной, логической и объектно-ориентированной парадигм и соответствующих языков (Лисп, Пролог, Смоллток)
════ - разработка программ в этих парадигмах, правила═ их═ выполнения, примеры программ
════ - достоинства и недостатки альтернативных парадигм (по сравнениею с процедурной); применение их в ИИ, БД и др. областях
═══ Практические занятия:═ Разработать на доступных непроцедурных языках простые программы.
════
══════ PL12. Распределенные и параллельные средства (3 лекц. часа)
═══ Средства описания асинхронных и параллельных═ вычислений═ в языках программирования.
═══ Темы лекций:
════ - средства параллельных вычислений (задачи, мониторы, сопрограммы и т.д.) в процедурных языках
═══ ═- проблемы (планирование, соперничество и т.д.)
════ - перспективы реализации непроцедурных языков на ЭВМ с параллельной и распределенной аритектурой
═══ Практические занятия:═ Разработка программ на языках, поддерживающих параллелизм (Ада, Оккам и др.).
═══
═══
════════
════════ PR. ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ (12 лекц. часов)
═══════ (факультативный курс, читаемый до или вставляемый в SE1)
═══
══════ PR. Введение в языки программирования (12 лекц. часов)
═══ Основные характеристики современных языков. Их применение для═ решения простых задач.
═══ Темы лекций:
════ - простые типы данных, их описание
════ - выражения, оператор присваивания
════ - условные операторы, операторы циклов, рекурсия
════ - процедуры, функции, параметры
════ - массивы, записи
════ - структура программы
═══ Практические занятия:═ Разработать 3-4 программы для решения простейших задач. Приобретение опыта работы с транслятором, в тестировании и отладке программ.
═══
═══
═══
════════ SE. ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ (44 лекционных часов)
═══
══════ SE1. Основы решения задач на ЭВМ═ (16 лекц. часов)
═══ Основные методы проектирования и разработки программ.
═══ Темы лекций:
════ - процедурная абстракция, параметры
════ - структуры управления, селекторы, итерация, рекурсия
════ - выбор типов данных при решении задач
════ - этапы разработки программы (от спецификации к реализации, пошаговая детализация, графические представления)
═══ Практические занятия: Наблюдение за═ поведением═ простой программы (ее═ переменными)═ при решении задачи. Разработка и реализация простой программы. Проектирование программы на псевдоязыке, описание ее подзадач в виде процедур с точной спецификацией их,═ реализация═ программы.
Реализация═ поискового═ алгоритма с помощью циклов и рекурсии, трассировка работы программ и сравнение их характеристик.═ Проектирование═ и реализация программы сортировки (например, методом пузырька) и демонстрация ее соответствия спецификации.
═══
═════ SE2. Процесс разработки программного обеспечения (8 лекц. часов)
═══ Модели═ и проблемы создания высококачественных программных систем. Использование программных инструментов при проектировании и реализации больших систем. Роль стандартов.
═══ Темы лекций:
════ - модель жизненного цикла программы
════ - требования к программной системе
════ - документация
════ - архитектура (структура, управление) программной системы
════ - надежность, безопасность, доверие
════ - сопровождение
════ - средства спецификации, проектирования и реализации
═══ Практические занятия: Разработать═ прототип═ системы═ по═ заданной спецификации; с помощью имеющих программных средств выполнить═ следующие шаги построения системы. Оценить имеющуюся документацию═ по═ программному═ продукту. При заданной спецификации и реализации системы изменить спецификацию и═ изменить═ соответствующим═ образом═ реализацию; составить документацию, необходимую для сопровождениия.
═══
══════ SE3. Спецификации═ (4 лекц. часа)
═══ Неформальные и формальные описания программных систем.
═══ Темы лекций:
════ - неформальные описания
════ - формальные спецификации; предусловия и постусловия, алгебраические спецификации для АТД
═══ Практические занятия: По заданному неформальному описанию разработать проект реализации и техническое задание. По неформальному═ описанию задачи построить эквивалентное формальное описание.
═══
══════ SE4. Проектирование и реализация (8 лекц. часов)
═══ Основные═ методы═ проектирования и реализации больших систем.
═══ Темы лекций:
════ - функциональное и процесс-ориентированное проектирование
════ - проектирование сверху вниз, возвраты
════ - методы реализации (сверху вниз, снизу вверх, команды)
════ - кодирование, модификация, отладка
═══ Практические═ занятия: Спроектировать систему по заданной спецификации; реализовать этот проект. По заданным спецификации задачи и спецификациям рабочих модулей спроектировать систему методом сверху вниз. Аналогично для метода снизу вверх. Закончить начатое кем-то проектирование системы методом сверху вниз.
═══
══════ SE5. Верификация и тестирование═ (4 лекц. часа)
═══ Методы проверки правильности программ.
═══ Темы лекций:
════ - использование пред- и постусловий, инварианты,═ примеры доказательства корректности программ
════ - читабельность программ
════ - методы тестирования (планирование тестов, выборочное тестирование, тестирование модулей, общее тестирование и т.д.)
═══ Практические занятия: По заданной спецификации программы выполнить ее верификацию и тестирование.
═══
═══
═══
════════ SP. СОЦИАЛЬНЫЕ, ЭТИЧЕСКИЕ И ПРОФЕССИОНАЛЬНЫЕ ВОПРОСЫ
════════════════════ (11 лекционных часов)
═══
═══ Замечание:═ практическими заданиями по SP могут быть написание рефератов по соотвествующим темам, дискуссии на семинарах═ по конкретным
проблемам.
═════════
══════ SP1. Исторические и социальные вопросы═ (3 лекц. часа)
═══ Роль ЭВМ и программирования в обществе, информатизация. Программирование═ и другие области знания, их взаимосвязь. Доступ программистов к секретной информации, профессиональная ответственность.
═══ Темы лекций:
════ - исторический и социальный контекст программирования
════ - предмет и области применения программирования
════ - взаимодействие с другими научными и техническими дисциплинами
════ - применение, злоупотребление и границы компьютерной технологии
═══
══════ SP2. Обязанности программистов═ (3 лекц. часа)
═══ Социальная и этическая ответственность за═ доступ═ к═ секретной═ и приватной информации, знание своих обязанностей, роль профессиональных обществ, участие в образовании.
═══ Темы лекций:
════ - профессиональные общества и их роль
════ - социальная ответственность (секретность, приватность)
════ - профессиональный рост
════ - этические проблемы
═══
══════ SP3. Риск и ответственность═ (2 лекц. часа)
═══ Виды риска и ущерба, которые могут сопровождать═ применение═ программ (аппаратные и программные ошибки, непредвиденный интерфейс, нарушение═ секретности ═и приватности, неэтичное использование программы и др.), и методы их устранения.
═══ Темы лекций:
════ - виды риска
════ - виды причиненного ушерба и ответсвенность; правовые аспекты
════
══════ SP4. Интеллектуальная собственность (2 лекц. часа)
═══ Основые виды интеллектуальной собственности, средства ее защиты═ и наказания за ее нарушение. Правовые сложности. Различие между патентами,═ авторским правом (копирайт), фирменными секретами, торговыми знаками и др. средствами защиты.
═══ Темы лекций:
════ - определение═ интеллектуальной═ собственности,═ специфика═ ее═ в
══════ программировании
════ - средства защиты
════ - нарушение права собственности и наказание