- •Вопрос 2. Спецификация, представление, реализация абстрактных типов данных.
- •Вопрос 3. Многомашинные вс. Реализация на основе ес эвм. Кластерные вс.
- •Типы кластеров:
- •Вопрос 2. Линейные структуры данных: стек, очередь, дек
- •Вопрос 3. Сравнительный анализ и основные компоненты инструментальных среды разработки пользовательских интерфейсов. Классификация элементов пользовательского интерфейса
- •Вопрос 1. Конкретные реализации языков функционального программирования: язык программирования Лисп, основные объекты, примитивы, списки, правила составления программ.
- •Вопрос 2. Семантическая теория программ. Вычислимость и разрешимость
- •Вопрос 3. Формальные методы описания диалоговых систем. Законы Фитса и Хика.
- •Вопрос 1. Основные конструкции логической программы: факты, правила, запросы, логические переменные. Операционная и декларативная семантика логических программ.
- •1. 5. Декларативный и процедурный смысл программ
- •Вопрос 2. Интерфейсы. Способы согласования аппаратных структур. Организация асинхронных интерфейсов
- •Элементы процесса как поведенческой категории :
- •Дескриптивный асинхронный процесс (dp)
- •Асинхронный процесс (ap)
- •Инициаторы
- •Вопрос 3. Эргономика пользовательского интерфейса. Критерии эргономичности интерфейса. Человеческие ошибки. Методы предотвращения ошибок. Снижение чувствительности системы к ошибкам.
- •Типы ошибок
- •Методы предотвращения ошибок
- •Как избежать сообщений об ошибках
- •Вопрос 1. Интерпретация и корректность логических программ. Абстрактный интерпретатор, значение логической программы, вычислительная модель
- •Вопрос 2. Порядковые статистики (Гулаков сказал что его не будет)
- •Субъективная удовлетворенность
- •Типичные интерфейсные ошибки отечественного по
- •Программа перегружена элементами управления
- •Терминология не адекватна знаниям пользователя о системе
- •От пользователя постоянно требуется дополнительная информация
- •Вопрос 1. Программирование баз данных. Динамическая база данных. Добавление и удаление фактов в процессе работы программы.
- •Вопрос 2. Поиск и кодирование (сжатие) данных, кодовые деревья, оптимальные префиксные коды
- •Вопрос 1. Рекурсивное программирование на логическом языке. Рекурсивные структуры данных – списки. Объявление списков. Составные списки. Голова и хвост списка. Примеры работы со списками.
- •Вопрос 2. Бинарный поиск, хеширование
- •Вопрос 3. Тестирование и отладка программного обеспечения. Структурное и функциональное тестирование. Особенности тестирования объектно-ориентированного по. Автоматизация процесса тестирования.
- •Вопрос1. Вычислительная модель программы на логическом языке. Согласование целевых утверждений. Сопоставление и унификация. Детерминизм.
- •Вопрос 2. Понятие выполнения сети. Свойства сети (устойчивость, безопасность, консервативность).
- •Вопрос 3. Автоматизация проектирования программного обеспечения на базе case-технологий. Принципы построения и т.Д.
- •Вопрос 1. Множественные выражения Программирование второго порядка Недетерминированное программирование
- •Вопрос 2. Нелинейные структуры данных: иерархические списки, деревья и леса, бинарные деревья
- •Вопрос 1. Вне логические предикаты. Ввод-вывод. Доступ к программам и обработка программ. Металогические предикаты. Сравнение не основных термов.
- •Вопрос 2. Алгоритмы сортировки
- •Сортировка разделением (Quicksort)
- •Вопрос 1. Constraint–Пролог: операционная семантика обобщение механизма унификации, понятие constraint'а. Операционная модель Constraint-пролоГа.
- •Вопрос 2. Нелинейные структуры: обходы деревьев
- •Вопрос 3. Качество по. Критерии качества: сложность, корректность, надежность, трудоемкость. Методика оценки качества по. Метрические особенности объектно-ориентированных пс. Сертификация по
- •Вопрос 1. Cancelled мистером г.
- •Вопрос 2. Стандартные схемы программ. Методы формальной спецификации и верификации.
- •Вопрос 1. Использование деревьев в задачах поиска: бинарные деревья поиска, случайные, оптимальные, сбалансированные по высоте и рандомизированные деревья поиска
- •. Деревья цифрового поиска
- •Вопрос 2. Определение асинхронного процесса как описания модели вычислительного процесса. Глобальные свойства – асинхронность, недетерминированность, параллельность.
- •1. Задачи сортировки; внутренняя и внешняя сортировка
- •2. Подклассы асинхронного процесса. Эффективный асинхронный процесс
- •Длительность реакции системы
- •Субъективное восприятие скорости работы
- •Приемы для уменьшения субъективного восприятия
- •1. Оптимальная сортировка.
- •2. Конвейерный процесс. Автономный процесс. Асинхронный процесс как метамодель.
- •Непосредственное манипулирование
- •Потеря фокуса внимания (прерывание)
- •Ограничение принятия решений
- •1. Анализ сложности и эффективности алгоритмов поиска и сортировки.
- •2. Классификация сетей (ординарные, автоматные, маркированный граф).
- •Понятность системы
- •Ментальная модель
- •Метафора
- •Аффорданс
- •Стандарт
- •1. Файлы: организация и обработка, представление деревьями: b-деревья.
- •2. Сетевое представление параллельных процессов. Области применения сетей Петри
- •3. Основы теории формальных языков и грамматик. Основные понятия и определения. Операции над языками. Классификация формальных языков и грамматик по порождающей способности
- •1. Алгоритмы на графах: представления графов, схемы поиска в глубину и ширину, минимальное остовное дерево, кратчайшие пути.
- •2.1.Поиск в глубину
- •2.2 Поиск в ширину.
- •2. Протоколы взаимодействия объектов вычислительных структур. Понятие протокола.
- •3. Вывод контекстно-свободных (кс) – грамматик и правила построения дерева вывода. Синтаксический разбор. Способы задания схем грамматик. Форма Бэкуса-Наура.
- •1. Теория сложности алгоритмов: np-сложные и труднорешаемые задачи.
- •2. Недетерминированные конечные автоматы. Конечные преобразователи и переводы. Преобразование некоторых грамматик к автоматному виду.
- •3. Объектно-ориентированное проектирование. Принципы проектирования. Схемы, диаграммы, инструменты.
- •1. Детерминированные конечные автоматы. Эквивалентные состояния и автоматы.
- •2. Синтаксический анализ. Метод оперативного предшествования. Восходящие и нисходящие методы синтаксического анализа.
- •2. Жизненный цикл программного обеспечения. Структура жизненного цикла согласно международного стандарта.
- •1. Нисходящие распознаватели. Ll(k) – грамматики. Построение детерминированного нисходящего распознавателя.
- •2. Параллельная обработка как основа высокопроизводительных вычислений. Уровни организации параллелизма: уровень заданий, программ и команд. Системы (языки) параллельного программирования.
- •1. Восходящие распознаватели. Lr(k) грамматики. Построение грамматики.
- •2. Понятие архитектуры вычислительной системы (вс). Архитектура как набор компонент и как система уровневых интерфейсов. Основные аппаратные и программные элементы вс.
- •1.1. Архитектура как набор взаимодействующих компонент
- •1.2. Архитектура как интерфейс между уровнями физической системы
- •1. Магазинные преобразователи. Определение магазинного преобразователя. Перевод, определяемый преобразователем.
- •2. Архитектура системы команд. Микропроцессоры (мп) с полным (cisc) и сокращённых (risc) набором команд. Основные принципы risc- архитектуры. Организация risc мп Alpha 21x64 фирмы dec.
- •Особенности архитектуры Alpha компании dec
- •1. Описание перевода или трансляции. Синтаксически-управляемые (су) – схемы.
- •2. Основные идеи объектно-ориентированных языков программирования. Создание абстрактных типов данных. Инкапсуляция. Полиморфизм. Наследование.
- •3. Развитие архитектур современных мп. Конвейеризация и динамическое выполнение потока команд. Суперскалярность. Архитектура epic мп Intel itanium.
- •1. Транслирующие грамматики. Построение транслирующей грамматики по су-схеме. Атрибутные транслирующие грамматики.
- •3. Векторные и векторно-конвейерные вс. Структура векторного процессора. Матричные вс.
- •1. Трансляторы, интерпретаторы и компиляторы. Стадии работы компиляторы. Лексический анализ.
- •3. Системы массовой параллельной обработки (мрр). Супер эвм фирмы sgi - Cray t3e(t3d) -1200.
- •2. Классификация и типы вс. Многомашинные и многопроцессорные вс. Представление вс на основе распределения потоков команд и данных (классификация Флинна)
3. Системы массовой параллельной обработки (мрр). Супер эвм фирмы sgi - Cray t3e(t3d) -1200.
MPP архитектура (massive parallel processing) - массивно-параллельная архитектура. Главная особенность такой архитектуры состоит в том, что память физически разделена. В этом случае система строится из отдельных модулей, содержащих процессор, локальный банк операционной памяти (ОП), два коммуникационных процессора (рутера) или сетевой адаптер, иногда - жесткие диски и/или другие устройства ввода/вывода. Один рутер используется для передачи команд, другой - для передачи данных. По сути, такие модули представляют собой полнофункциональные компьютеры (см. рис.). Доступ к банку ОП из данного модуля имеют только процессоры (ЦП) из этого же модуля. Модули соединяются специальными коммуникационными каналами. Пользователь может определить логический номер процессора, к которому он подключен, и организовать обмен сообщениями с другими процессорами. Используются два варианта работы операционной системы (ОС) на машинах MPP архитектуры. В одном полноценная операционная система (ОС) работает только на управляющей машине (front-end), на каждом отдельном модуле работает сильно урезанный вариант ОС, обеспечивающий работу только расположенной в нем ветви параллельного приложения. Во втором варианте на каждом модуле работает полноценная UNIX-подобная ОС, устанавливаемая отдельно на каждом модуле.
Г
лавным
преимуществом систем с раздельной
памятью является хорошая масштабируемость:
в отличие от SMP-систем в машинах с
раздельной памятью каждый процессор
имеет доступ только к своей локальной
памяти, в связи с чем не возникает
необходимости в потактовой синхронизации
процессоров. Практически все рекорды
по производительности на сегодняшний
день устанавливаются на машинах именно
такой архитектуры, состоящих из
нескольких тысяч процессоров (ASCI Red,
ASCI Blue Pacific).
Недостатки:
• отсутствие общей памяти заметно снижает скорость межпроцессорного обмена, поскольку нет общей среды для хранения данных, предназначенных для обмена между процессорами. Требуется специальная техника программирования для реализации обмена сообщениями между процессорами. • каждый процессор может использовать только ограниченный объем локального банка памяти. •
Системы Cray T3E - это масштабируемые параллельные системы. Каждый процессорный элемент (ПЭ) Cray T3E имеет свою собственную DRAM-память объемом от 64 Мбайт до 2 Гбайт. В отличие от системы CRAY T3D, в которой исполняемая задача запрашивает фиксированное количество процессоров на все время выполнения, в CRAY T3E свободные процессоры могут использоваться другими задачами.
Каждый узел в системе содержит один процессорный элемент (ПЭ), включающий процессор, память и средство коммутации, которое осуществляет связь между ПЭ. Система конфигурируется до 2048 процессоров.
Системы Cray T3E выполняют операции ввода/вывода через многочисленные порты на один или более каналов GigaRing. Каналы ввода/вывода интегрированы в трехмерную межузловую сеть и пропорциональны размеру системы.
Быстродействие серии Cray T3E-1200 в два раза превышает производительность систем Cray T3E при уменьшенной вдвое стоимости за Мфлоп. Конфигурации в воздушно-жидкостном охлаждении имеют от 6 процессоров, а в жидкостном - от 32 процессоров. Система предназначена для наиболее важных научных и технических задач в аэрокосмической, автомобильной, финансовой, химико-фармацевтической, нефтяной и т.д. отраслях промышленности, а также в широких областях прикладных исследований, включая химию, гидродинамику, предсказание погоды и сейсмические процессы.
Билет 29
1. Ввод-вывод. Потоки ввода-вывода. Библиотека ввода-вывода (iostream). Группы классов библиотеки ввода-вывода. Краткая характеристика иерархии классов производимых от conbuf. Иерархия классов производимых от ios. Состояние потока. Ошибки потоков. Форматирование в С++. Форматирующие функции-члены. Форматирующие функции-элементы, изменяющие флаги форматирования. Управление потоком при помощи манипуляторов.
Библиотека потоков iostream представляет набор классов для управления вводом выводом (иерархию смотрите ниже). Эти классы имеют множество преимуществ, такие как надежность, расширяемость, простота и последовательность.
Библиотека iostream имеет 4 объекта-потока, которые ассоциированы со стандартным вводом выводом:
cin - стандартный ввод (клавиатура)
cout - стандартный вывод (на экран)
сегг - стандартное устройство ошибок с небуферизированным выводом
clog - то же, только с буферизированным выводом
В библиотеке используются 2 оператора:
« -- помещение в поток
»--извлечение из потока
Пример:
cout « ":-)"; //вывод на экран сложного слова
cin » YourName; //а теперь введите свое имя :)
Немножко пояснений по иерархии:
ios - базовый класс ввода/вывода определяет основные операторы состояния потока, форматирования обработки ошибок
istream - класс ввода из стандартного потока (клавиатуры)
ostream - класс вывода в стандартный поток (монитор)
iostream = istream+ostream.
fstream - работа с файловым потоком, организует стандартный ввод ifstream и стандартный вывод ofstream на жесткий диск.
streambuf, filebuf - буфера стандартного и файлового потока
Состояние потока. Ошибки потока. С каждым потоком связывается его состояние, определяемое с помощью комбинации:
enum io_state
{ goodbit=0, //нет ошибки
eofbit=1; //поток в конечной позиции
faitbit=2: //последняя операция ввода/вывода совершилась ненормально; ошибка форматирования или преобразования; использование потока можно продолжать
badbit=4: //ошибка ввода/вывода более серьезная; скорее всего дальше потоком пользоваться нельзя
hardfail=8 //неустранимая ошибка обычно связана с неисправным оборудованием
}
Состояние потока проверяется через функцию int rdstate(void), которая возвращает код ошибки, затем эта величина проверяется на то, какая ситуация имела место:
int eof() -состояние eof
int good() -состояние good
Int fail() -состояние fail or bad
int bad() -состояние bad
Функция clearfint(state=0) устанавливает состояние в state.
Форматирование. Существует три способа - функции, использование флагов и применение манипуляторов.
С каждым потоком связывается отдельный набор функций, доступ к которым осуществляется при содействии функций класса ios:
width() - макс. число символов
fill() - символ которым дополняется поле вывода (пробел по умолч.)
precision() - число дробных цифр вещественного числа
Флаги можно устанавливать или сбрасывать посредством функций setf и unsetf. Манипуляторы представляют собой функции, которые можно включать в цепочку последовательных операций помещения и извлечения из потока.
