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

• 
  Задача построения линий для растровых устройств.
  
• 
  Использование симметрии.
  
• 
  Алгоритм построения прямоугольного отрезка (или дуги окружности), вывод рекуррентных соотношений.
  
• 
  Достоинства алгоритма по сравнению с традиционными методами.
  

1. 
   Понятие транзакции. Для чего нужны транзакции – целостность баз данных и изолированность пользователей.
   
2. 
   Понятие целостности баз данных. Виды целостности – ссылочная, по значению. Чем обеспечивается – триггеры, домены, ограничения: первичные, уникальные ключи, внешние ключи.
   
3. 
   Изолированность пользователей. Уровни изолированности транзакций.
   
4. 
   Сериализация транзакций. Понятие сериализации транзакций, сериального плана выполнения. Методы сериализации транзакций – на основе синхронизационных захватов и временных меток. Двухфазный протокол фиксации транзакций, объекты синхронизационного захвата.
   
5. 
   Гранулированные синхронизационные захваты.
   
6. 
   Предикатные синхронизационные захваты.
   
7. 
   Тупики, их обнаружение и разрушение.
   
8. 
   Метод временных меток
   

1. 
   Рекурсия:
   

• 
  определить рекурсию;
  
• 
  формула рекурсии 1-го порядка: Xi = Ai * X(i-1) + Di, i = 1,2,..n;
  
• 
  последовательная программа вычисления рекурсии.
  

2. 
   Циклическая редукция:
   

• 
  параллельные алгоритмы суммирования чисел методом циклической редукции;
  
• 
  алгоритмы параллельного суммирования чисел с сохранением частных сумм (рекурсия 1-го порядка при A (i-1) );
  

3. 
   Редукция по Хокни:
   

• 
  чистая редукция: уменьшение числа уравнений пополам;
  
• 
  редукция Хокни: не уменьшая числа уравнений , получить соотношение между каждым предыдущим и последующим уравнением (связать Xi с X(i-2) ), затем каждые четвертые и т.д.;
  
• 
  привести общую форму вычислений: Xi = …;
  
• 
  векторная программа алгоритма цикличнской редукции.
  

4. 
   Достоинства и недостатки алгоритма:
   

• 
  дать оценку степени параллельности алгоритма;
  
• 
  показать зависимость эффективности алгоритма от оборудования.
  

1. 
   Понятие программного средства [11, лекция 1] .
   
2. 
   Понятие и структура жизненного цикла программного средства
   

3. 
   Понятие качества программного средства. Критерии качества ПС
   

1. 
   Основные конструкции структурного программирования. Общее свойство этих конструкций. [11, лекция 8, раздел 8.2] .
   
2. 
   Назначение и сущность метода пошаговой детализации.
   

3. Понятие и назначение псевдокода. [11, лекция 8, раздел 8.2]

1. Сущность защиты от несанкционированного доступа. Понятие пароля.

[11, лекция 11, раздел 11.6 - Защита от несанкционированного доступа].

2. Защита от взлома защиты от несанкционированного доступа к хранящейся информации. Понятие электронной подписи.

[11, лекция 11, раздел 11.6 - Защита от несанкционированного доступа]

3. Защита от взлома защиты от несанкционированного доступа к передаче информации. Понятие электронной печати.

[11, лекция 11, раздел 11.6 - Защита от несанкционированного доступа]
12. Средства инкапсуляции данных. Абстрактные типы данных и их реализация в современных языках программирования.

План ответа на этот вопрос:

• 
  определение инкапсуляции;
  
• 
  необходимость поддержки инкапсуляции в современных языках программирования.
  
• 
  языковые средства инкапсуляции: управление видимостью (на примере языка Ада) . Принцип разделения определения, реализации и использования. Пакет, спецификация пакета, тело пакета;
  
• 
  языковые средства инкапсуляции: управление доступом (на примере Си++ и Ява). Классы, члены классов, спецификаторы доступа;
  
• 
  абстрактные типы данных (АТД) и их реализация: приватные и ограниченные приватные типы данных в Аде, реализация АТД с помощью классов языка Си++.
  

План ответа на этот вопрос:

• 
  инкапсуляция (см. предыдущий вопрос);
  
• 
  наследование – на примере языка Си++ и Ява – только единичное наследование;
  
• 
  статический полиморфизм (перекрытие операций) – на примере языков Ада и Си++;
  
• 
  динамический полиморфизм. Динамическое связывание методов – на примере виртуальных методов языка Си++ и нестатических методов языка Ява;
  
• 
  абстрактные классы и интерфейсы.
  

• 
  Определение регулярного множества.
  
• 
  Определение регулярного выражения (РВ).
  
• 
  Определение недетерминированного конечного автомата (НКА).
  
• 
  Определение детерминированного конечного автомата (ДКА).
  
• 
  Алгоритм может быть представлен либо как последовательность двух алгоритмов: НКА - ДКА, либо непосредственно построение ДКА по дереву РВ.
  

[в вопросе пропущено слово СИСТЕМЫ]

• 
  Правосторонний вывод.
  
• 
  Восстановление правостороннего вывода.
  
• 
  Схема работы магазинного анализатора, таблицы действий и переходов, конфигурации.
  
• 
  Основа сентенциальной формы.
  
• 
  LR(1) ситуация.
  
• 
  Построение замыкания и переходы.
  
• 
  Построение автомата (таблиц) анализатора по канонической системе множеств.
  
• 
  Конфликты в таблицах.
  

• 
  Задача оптимального распределения регистров.
  
• 
  Условия применения алгоритма.
  
• 
  Обоснование алгоритма (минимальность числа используемых регистров при принятых ограничениях).
  
• 
  Разметка дерева.
  
• 
  Распределение регистров.
  
• 
  Генерация кода.
  

1. 
   Способы классификации архитектур вычислительных систем.
   
2. 
   Параллелизм работы основных устройств ЭВМ.
   
3. 
   Конвейерность выполнения вычислений и обработки команд в ЭВМ.
   
4. 
   Многопроцессорные вычислительные комплексы.
   
5. 
   Многомашинные вычислительные комплексы.
   

1. Организация памяти типа cache.

2. Организация оперативной памяти. Односегментное отображение, сегментация, страничная и сегментно-страничная организация памяти.

3. Способы организации доступа к внешней памяти (селекторные каналы, использование шинной архитектуры связи).

1. 
   Распределенная система [17, лекции 1-2].
   
2. 
   Распределенная операционная система [17, лекции 1-2].
   
3. 
   Синхронизация [17, лекции 3-4].
   
4. 
   Взаимное исключение критических интервалов – суть проблемы и требования к решению [17, лекции 3-4].
   
5. 
   Семафоры [17, лекции 3-4].
   
6. 
   Алгоритмы взаимного исключения - знать идеи 5-ти алгоритмов [17, лекции 5-6, раздел 4.3]
   

1. 
   Достоинства DSM [17, Лекции 9-11, раздел 6.1].
   
2. 
   Методы реализации [17, Лекции 9-11, раздел 6.2, раздел 6.5 – только принципы].
   
3. 
   Модели консистентности [17, Лекции 9-11, раздел 6.3 - определение и возможные алгоритмы реализации].
   

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

Факт – формула в некоторой логике.

Система знаний – совокупность формул.

База знаний – система знаний в компьютерном представлении.

Основные операции:

логический вывод (доказательство теорем)

иметь (Саша, книга) «Саша имеет книгу»

иметь (Саша, книги)  иметь (Саша, книга) «Если Саша имеет книги, то он имеет книгу»

(x) [человек (x)  иметь (x, книга)] «Каждый человек имеет книгу»

(x) [свободен (x)  (y) (на (y,x))] «Если кубик x свободен, то нет такого кубика y,

который находится на кубике x»

• 
  формальный аппарат вывода (новых фактов/знаний из известных фактов/знаний),
  
• 
  возможность контроля целостности,
  
• 
  простая и ясная нотация.
  

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

Знания, необходимые для решения задач и организации взаимодействия с пользователем, – объекты/события и связи между ними.

Статические семантические сети - сети с объектами.

Динамические семантические сети (сценарии) - сети с событиями.

Система знаний – совокупность сетей (или одна общая сеть).

База знаний – система знаний в компьютерном представлении.

откуда? – место . . .

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

вершина - атомарный объект (событие),

подграф - структурно сложный объект (событие),

дуга - отношение или действие.

Примеры отношений:

род-вид («компьютер» – «персональный_компьютер»)

целое-часть («компьютер» – «память»)

понятие-пример («компьютер» – «конкретный компьютер . . . »)

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

• 
  знания хорошо структурированы, структура понятна человеку.
  

• 
  при большом объеме сети очень долго выполняются все операции,
  
• 
  при большом объеме сети она трудно обозрима.
  

Знания, необходимые для решения задач и организации взаимодействия с пользователем, – фреймы.

Фрейм-понятие – отношение/действие + связанные этим отношением/участвующие в этом действии объекты.

Фрейм-пример – конкретный экземпляр отношения/действия + конкретные объекты (связанные этим отношением/участвующие в этом действии).

Система знаний – совокупность фреймов-понятий и фреймов-примеров.

База знаний – система знаний в компьютерном представлении.

Фрейм: ИМЯ - отношение/действие

СЛОТЫ - объекты или другие фреймы

С каждым слотом может быть связана такая информация:

УСЛОВИЕ НА ЗАПОЛНЕНИЕ (тип, «по умолчанию», связь с другими слотами)

АССОЦИИРОВАННЫЕ ПРОЦЕДУРЫ (действия, выполняемые, например, при заполнении этого слота)

Основные операции:

поиск фрейма/слота, замена значения слота, взятие копии фрейма-понятия

Фрейм-понятие «Перемещать»

ПЕРЕМЕЩАТЬ (кто?, что?, откуда?, куда?, когда?, . . .)

Условия: кто? – человек, робот, . . .

откуда? – место

. . .

ПЕРЕМЕЩАТЬ (Саша, Саша, Главное_Здание_МГУ, Факультет_ВМК, вчера в 15-30, . . .)

Фрейм-понятие «Персональный_компьютер»

ПЕРСОНАЛЬНЫЙ_КОМПЬЮТЕР (процессор?, тактовая_частота?, память?, монитор?, . . .)

ПЕРСОНАЛЬНЫЙ_КОМПЬЮТЕР (Pentium-III, 600 МГц, 128Мб, SONY, . . .)

• 
  знания хорошо структурированы, структура понятна человеку.
  

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

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

Продукция – правило вида: p:  (где: p – предусловие,  - антецедент,  - консеквент).

Система знаний – система продукционных правил + стратегия выбора правил.

База знаний – система знаний в компьютерном представлении.

Основные операции:

вывод (применение правила, определение правила-преемника и т.д.)

True: T > 200C & P > 5 кПа  открыть клапан № 3

True: Х - башня  Х имеет_часть У1 & У1 есть КРЫША & . . .

Достоинства:

• 
  простая и ясная нотация.
  

• 
  при большом количестве правил вывод идет очень долго,
  
• 
  при большом количестве правил их совокупность трудно обозрима.
  

• 
  Пространство состояний, поиск решения в пространстве состояний (примеры задач - 2-3 шт.).
  
• 
  Классификация алгоритмов поиска:
  

слепые vs. эвристические.

• 
  Словесное описание одного из алгоритмов (например, алгоритма поиска вширь).
  
• 
  Характер изменений в алгоритме при реализации поиска вглубь, эвристического поиска.
  
• 
  Фрагмент дерева поиска (например, для задачи "8").
  
• 
  Особенности игровых задач.
  
• 
  Использование при их решении аппарата И/ИЛИ-деревьев.
  
• 
  Фрагмент дерева решения (например, для игры "крестики-нолики" на поле 3 х 3).
  
• 
  Минимаксная процедура.
  
• 
  Эвристические приемы сокращения поиска (α-β процедура).
  

1. 
   сложные и динамически меняющиеся структуры данных;
   
2. 
   символьные (в основном) данные;
   
3. 
   модели, отражающие состояние проблемной среды;
   
4. 
   переборные алгоритмы;
   
5. 
   алгоритмы поиска по образцу;
   
6. 
   гибкие структуры управления.
   

- средства для работы со списками (лисповская часть) - (1), (2);

- плэнерская база данных - (3);

- встроенный режим возвратов - (4), (6);

- аппарат работы с образцами - (5);

- аппарат теорем - (5), (6).

- функции;

- сопоставители (для работы с образцами);

- теоремы (процедуры, вызываемые по образцу).

• 
  ориентированы на решение практических задач в трудноформализуемых предметных областях,
  
• 
  результаты работы сравнимы с результатами человека-эксперта,
  
• 
  «прозрачность» решения,
  
• 
  открытая совокупность знаний.
  

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

SPE - определение концентрации гамма-глобулина в крови.

PLANT/cd - определения потерь урожая от черной совки.

TATR - планирование авиаударов по аэродромам противника.

MYCIN - диагностика бактериальных инфекций.

ONCOCIN - планирования химиотерапевтического лечения.

TQMSTUNE - настройка масс-спектрометра.

XCON (R1) - выбор оптимальной конфигурации аппаратных средств (VAX).

VM - наблюдение за состоянием больного в палате интенсивной терапии.

GUIDON - обучение студентов-медиков (антибактериальная терапия).

Эталонная модель взаимосвязи открытых систем OSI ISO.

Уровни протоколов и их основные функции.

Понятие сервиса, интерфейса, протокола.

[24, раздел 1.4-1.8]
26. Эталонная модель TCP/IP (Internet) и ее сравнение с эталонной моделью OSI ISO. Основные функции протоколов IP и TCP. Основные прикладные протоколы архитектуры TCP/IP.

Ответ изложен в литературе:

[24, разделы 1.7, 1.10, 5.5, 7.1, 7.2, 7.3, 7.4]

[24, разделы 1.9, 2.1 – 2.5]

[24, разделы 4.4, 5.2 – 5.4]

• 
  Назначение UML;
  
• 
  История создания и перспективы развития UML;
  
• 
  Состав диаграмм UML и их назначение:
  

• 
  диаграммы вариантов использования (use case diagrams);
  
• 
  диаграммы классов (class diagrams);
  
• 
  диаграммы последовательности (sequence diagrams);
  
• 
  кооперативные диаграммы (collaboration diagrams);
  
• 
  диаграммы состояний (statechart diagrams);
  
• 
  диаграммы деятельности (activity diagrams);
  
• 
  диаграммы компонентов (component diagrams);
  
• 
  диаграммы размещения (deployment diagrams).
  

а также http://sp.cmc.msu.ru/courses/prak5/umlpracticum.pdf.

1. 
   Цели создания DFS [17, Лекции 7-8, раздел 5].
   
2. 
   Прозрачность именования [17, Лекции 7-8, раздел 5.1.2].
   
3. 
   Семантика разделения файлов [17, Лекции 7-8, раздел 5.1.3].
   
4. 
   Серверы с состоянием и без состояния. Их достоинства и недостатки.
   

5. 
   Организация кэширования [17, Лекции 7-8, раздел 5.2.3].
   

2. Яблонский С.В. Введение в дискретную математику. - М.: Наука, 1986.

3. Алексеев В.Б., Ложкин С.А. Элементы теории графов и схем. Методическая разработка.

4. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем.

5. Братко И. Программирование на языке Пролог для искусственного интеллекта. М.МИР.1990

6. Дейт К. Введение в системы баз данных. - М.: Наука, 1980.

7. Хокни Р., Джессхоуп К. Параллельные ЭВМ. - М.: Радио и связь , 1986.

8. Кауфман В.Ш. Языки программирования. Концепции и принципы. - М.: Радио и связь, 1993.

9. Джехани Н. Язык Ада. - М.: Мир, 1988.

10. Вирт Н. Программирование на языке Модула-2. - М.: Мир, 1988.

11. Жоголев Е.А. Лекции по технологии программирования. - М.: Издат. отдел ф-та ВМК МГУ, 2001.

12. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и трансляции, т.1, т.2.

13. Королев Л.Н. Структура ЭВМ и их математическое обеспечение. - М.: наука, 1978.

14. Малые ЭВМ высокой производительности. Архитектура и программирование. - М.: Радио и связь, 1990.

15. Коуги П. Архитектура конвейерных ЭВМ. - М.: Радио и связь, 1985.

16. Смирнов А.Д. Архитектура вычислительных систем. - М.: Наука, 1990.

17. Крюков В.А. Распределенные операционные системы. http://sp.cmc.msu.ru в разделе информация

18. Нильсон Н. Принципы искуственного интеллекта. - М.: Радио и связь, 1985.

19. Интеллектуализация ЭВМ. - М.: Высшая школа, 1989.

20. Пильщиков В.Н. Язык плэнер. - М.: Наука, 1983.

21. Ларионов А.М. Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети – Л., Энергоиздат, 1987.

22. Нильсон Н. Знакомьтесь World Wide Web. Киев, BHV, 1996.

23. Смелянский Р.Л., Брежнев А.Ф. Протокол TCP/IP. Технологии электронных коммуникаций - М.1991, Т.3.стр.61-125.

24. 
    Смелянский Р.Л. Конспекты лекций «Компьютерные сети», http://lvk.cs.msu.su/index.php/docs/255
    

26. Фаулер М., Скотт К. UML в кратком изложении. Применение стандартного языка объектного моделирования.: Пер. с англ. – М.: Мир, 1999.

1. 
   Шикин Е.В., Боресков А.В. "Компьютерная графика: полигональные модели" М., 2000. Стр.156-164
   
2. 
   http://graphics.cs.msu.su/courses/cg_el99/notes/lect01.doc