2) Уравнение теплопроводности

Связь изменения температуры во времени и пространстве со свойствами среды описывается с помощью уравнения теплопроводности. Это уравнение вытекает из закона сохранения энергии: изменение во времени количества теплоты в элементарном объеме равно сумме притока-стока теплоты и изменения теплоты за счет ее превращения в другие виды энергии в том же объеме:

где Q – количество теплоты;  – вектор плотности теплового потока;

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

3. Рассчитать сетевую маску для IP адреса 192.168.0.37/28. Указать сколько компьютеров может входить в такую подсеть. Написать 2 зарезервированных адреса у которых в поле номер компьютера расположены все 0 или все 1.

Рассчитать сетевую маску для адреса 192.168.0.37/28

28 первых бит отдано для адреса сети (выделены более крупным шрифтом). Представляем предложенный адрес в битовом варианте по октетам, получаем

192

1	1	0	0	0	0	0	0
128	64	32	16	8	4	2	1

168

1	0	1	0	1	0	0	0
128	64	32	16	8	4	2	1

0

0	0	0	0	0	0	0	0
128	64	32	16	8	4	2	1

37

0	0	1	0	0	1	0	1
128	64	32	16	8	4	2	1

Если установить их в 1, тогда получится сетевая маска 255.255.255.240

Сколько компьютеров входит в данную сеть

Под адрес компьютеров в сети отдано 4 бита, получаем 2⁴ – 2 = 16 – 2 = 14 компьютеров

Написать 2 зарезервированных адреса, у которых в поле номер компьютера все нули или все 1.

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

Все биты номера компьютера в сети (4 последних бита) = 0

0	0	1	0	0	0	0	0
128	64	32	16	8	4	2	1

Ответ: Адрес 192.168.0.32

Все биты номеров компьютера в сети = 1

0	0	1	0	1	1	1	1
128	64	32	16	8	4	2	1

Ответ: 192.168.0.47

Билет 43.

1. Архитектура системы команд.

Системой команд вычислительной машины называют полный перечень команд, которые способна выполнять данная ВМ. В свою очередь, под архитектурой системы команд (АСК) принято определять те средства вычислительной машины, которые видны и доступны программисту. АСК можно рассматривать как линию согласования нужд разработчиков программного обеспечения с возможностями создателей аппаратуры вычислительной машины.

В истории развития вычислительной техники как в зеркале отражаются изменения, происходившие во взглядах разработчиков на перспективность той или иной архитектуры системы команд. Сложившуюся на настоящий момент ситуацию в области АСК иллюстрирует рис. 2.3.

Среди мотивов, чаще всего предопределяющих переход к новому типу АСК, остановимся на двух наиболее существенных. Первый — это состав операций, выполняемых вычислительной машиной, и их сложность. Второй — место хранения операндов, что влияет на количество и длину адресов, указываемых в адресной части команд обработки данных. Именно эти моменты взяты в качестве критериев излагаемых ниже вариантов классификации архитектур системы команд.

Рис. Хронология развития архитектур системы команд

Классификация по составу и сложности команд

Современная технология программирования ориентирована на языки высокого уровня (ЯВУ), главная цель которых — облегчить процесс программирования. Переход к ЯВУ, однако, породил серьезную проблему: сложные операторы, характерные для ЯВУ, существенно отличаются от простых машинных операций, реализуемых в большинстве вычислительных машин. Проблема получила название семантического разрыва, а ее следствием становится недостаточно эффективное выполнение программ на ВМ. Пытаясь преодолеть семантический разрыв, разработчики вычислительных машин в настоящее время выбирают один из трех подходов и, соответственно, один из трех типов АСК: архитектуру с полным набором команд: CISC (Complex Instruction Set Computer); архитектуру с сокращенным набором команд: RISC (Reduced Instruction Set Computer); архитектуру с командными словами сверхбольшой длины: VLIW (Very Long Instruction Word).

В вычислительных машинах типа CISC проблема семантического разрыва решается за счет расширения системы команд, дополнения ее сложными командами, семантически аналогичными операторам ЯВУ. Основоположником CISC-архитектуры считается компания IBM, которая начала применять данный подход с семейства машин IBM 360 и продолжает его в своих мощных современных универсальных ВМ, таких как IBM ES/9000. Аналогичный подход характерен и для компании Intel в ее микропроцессорах серии 8086 и Pentium.

Для CISC-архитектуры типичны: наличие в процессоре сравнительно небольшого числа регистров общего назначения; большое количество машинных команд, некоторые из них аппаратно реализуют сложные операторы ЯВУ; разнообразие способов адресации операндов;

множество форматов команд различной разрядности;

наличие команд, где обработка совмещается с обращением к памяти.

К типу CISC можно отнести практически все ВМ, выпускавшиеся до середины 1980-х годов, и значительную часть производящихся в настоящее время. Рассмотренный способ решения проблемы семантического разрыва вместе с тем ведет к усложнению аппаратуры ВМ, главным образом устройства управления, что, в свою очередь, негативно сказывается на производительности ВМ в целом. Это заставило более внимательно проанализировать программы, получаемые после компиляции с ЯВУ. Был предпринят комплекс исследований, в результате которых обнаружилось, что доля дополнительных команд, эквивалентных операторам ЯВУ, в общем объеме программ не превышает 10-20%, а для некоторых наиболее сложных команд даже 0,2%. В то же время объем аппаратных средств, требуемых для реализации дополнительных команд, возрастает весьма существенно. Так, емкость микропрограммной памяти при поддержании сложных команд может увеличиваться на 60%. Детальный анализ результатов упомянутых исследований привел к серьезному пересмотру традиционных решений, следствием чего стало появление RISC-архитектуры. Термин RISC впервые был использован Д. Паттерсоном и Д. Дитцелем в 1980 году. Идея заключается в ограничении списка команд ВМ наиболее часто используемыми простейшими командами, оперирующими данными, размещенными только в регистрах процессорах. Обращение к памяти допускается лишь с помощью специальных команд чтения и записи. Резко уменьшено количество форматов команд и способов указания адресов операндов. Сокращение числа форматов команд и их простота, использование ограниченного количества способов адресации, отделение операций обработки данных от операций обращения к памяти позволяет существенно упростить аппаратные средства ВМ и повысить их быстродействие. RISC-архитектура разрабатывалась таким образом, чтобы уменьшить TВИЧ за счет сокращения CPI и I/. Как следствие, реализация сложных команд за счет последовательности из простых, но быстрых RISC-команд оказывается не менее эффективной, чем аппаратный вариант сложных команд в CISC-архитектуре. Отметим, что в последних микропроцессорах фирмы Intel и AMD широко используются идеи, свойственные RISC-архитектуре, так что многие различия между CISC и RISC постепенно стираются.

Помимо CISC- и RISC-архитектур в общей классификации был упомянут еще один тип АСК — архитектура с командными словами сверхбольшой длины (VLIW). Концепция VLIW базируется на RISC-архитектуре, где несколько простых RISC-команд объединяются в одну сверхдлинную команду и выполняются параллельно. В плане АСК архитектура VLIW сравнительно мало отличается от RISC. Появился лишь дополнительный уровень параллелизма вычислений, в силу чего архитектуру VLIW логичнее адресовать не к вычислительным машинам, а к вычислительным системам. Таблица 2.1 позволяет оценить наиболее существенные различия в архитектурах типа CISC, RISC и VLIW.

Таблица 2.1. Сравнительная оценка CISC-, RISC- и VLIW-архитектур

Характеристика	CISC	RISC	VLIW
Длина команды	Варьируется	Единая	Единая
Расположение нолей и команде	Варьируется	Неизменное	Неизменное
Количество регистров	Несколько (часто специализированных)	Много регистров общего назначения	Много регистров общего назначения
Доступ к памяти	Может выполняться как часть команд различных типов	Выполняется только специальными командами	Выполняется только специальными командами

Классификация по месту хранения операндов

Количество команд и их сложность, безусловно, являются важнейшими факторами, однако не меньшую роль при выборе АСК играет ответ на вопрос о том, где могут храниться операнды и каким образом к ним осуществляется доступ. С этих позиций различают следующие виды архитектур системы команд: стековую; аккумуляторную; регистровую; с выделенным доступом к памяти.

Выбор той или иной архитектуры влияет на принципиальные моменты: сколько адресов будет содержать адресная часть команд, какова будет длина этих адресов, насколько просто будет происходить доступ к операндам и какой, в конечном итоге, будет общая длина команд.

Стековая архитектура Стеком называется память, по своей структурной организации отличная от основной памяти ВМ. Принципы построения стековой памяти детально рассматриваются позже, здесь же выделим только те аспекты, которые требуются для пояснения особенностей АСК на базе стека. Стек образует множество логически взаимосвязанных ячеек (рис. 2.4), взаимодействующих по принципу «последним вошел, первым вышел» (L1FO, Last In First Out).

Рис. 2.4. Принцип действия стековой памяти

Верхнюю ячейку называют вершиной стека. Для работы со стеком предусмотрены две операции: push (проталкивание данных в стек) и pop (вытаякивание данных из стека). Запись возможна только в верхнюю ячейку стека, при этом вся хранящаяся в стеке информация предварительно проталкивается на одну позицию вниз. Чтение допустимо также только из вершины стека. Извлеченная информация удаляется из стека, а оставшееся его содержимое продвигается вверх. В вычислительных машинах, где реализована АСК на базе стека (их обычно называют стековыми), операнды перед обработкой помещаются в две верхних ячейки стековой памяти.

Аккумуляторная архитектура Архитектура на базе аккумулятора исторически возникла одной из первых. В ней для хранения одного из операндов арифметической или логической операции в процессоре имеется выделенный регистр — аккумулятор. В этот же регистр заносится и результат операции. Поскольку адрес одного из операндов предопределен, в командах обработки достаточно явно указать местоположение только второго операнда. Изначально оба операнда хранятся в основной памяти, и до выполнения операции один из них нужно загрузить в аккумулятор. После выполнения команды обработки результат находится в аккумуляторе и, если он не является операндом для последующей команды, его требуется сохранить в ячейке памяти.

Регистровая архитектура В машинах данного типа процессор включает в себя массив регистров (регистровый файл), известных как регистры общего назначения (РОН). Эти регистры, в каком-то смысле, можно рассматривать как явно управляемый кэш для хранения недавно использовавшихся данных. Размер регистров обычно фиксирован и совпадает с размером машинного слова. К любому регистру можно обратиться, указав его номер. Количество РОН в архитектурах типа CISC обычно невелико (от 8 до 32), и для представления номера конкретного регистра необходимо не более пяти разрядов, благодаря чему в адресной части команд обработки допустимо одновременно указать номера двух, а зачастую и трех регистров (двух регистров операндов и регистра результата). RISC-архитектура предполагает использование существенно большего числа РОН (до нескольких сотен), однако типичная для таких ВМ длина команды (обычно 32 разряда) позволяет определить в команде до трех регистров. Регистровая архитектура допускает расположение операндов в одной из двух запоминающих сред: основной памяти или регистрах. С учетом возможного размещения операндов в рамках регистровых АСК выделяют три подвида команд обработки: регистр-регистр; регистр-память; память-память.

В варианте «регистр-регистр» операнды могут находиться только в регистрах. В них же засылается и результат. Подтип «регистр-память» предполагает, что од и и из операндов размещается в регистре, а второй в основной памяти. Результат обычно замещает один из операндов. В командах типа «память-память» оба операнда хранятся в основной памяти. Результат заносится в память. Каждому из вариантов свойственны свои достоинства и недостатки (табл. 2.4).

В выражениях вида (т, п), приведенных в первом столбце таблицы, т означает количество операндов, хранящихся в основной памяти, а n — общее число операндов в команде арифметической или логической обработки.

Вариант «регистр-регистр» является основным в вычислительных машинах типа RISC. Команды типа «регистр-память» характерны для CISC-машин. Наконец, вариант «память-память» считается неэффективным, хотя и остается в наиболее сложных моделях машин класса CISC.

Вариант	Достоинства	Недостатки
Регистр-регистр (0,3)	Простота реализации, фиксированная длина команд, простая модель формирования объектного кода при компиляции программ, возможность выполнения всех команд за одинаковое количество тактов	Большая длина объектного кода, из-за фиксированной длины команд часть разрядов в коротких командах не используется
Регистр-память (1.2)	Данные могут быть доступны без загрузки в регистры процессора, простота кодирования команд, объектный код получается достаточно компактным	Потеря одного из операндов при записи результата, длинное поле адреса памяти в коде команды сокращает место под помер регистра, что ограничивает общее число РОН. СР1 зависит от места размещения операнда
Память-память (3,3)	Компактность объектного кода, малая потребность в регистрах для хранения промежуточных данных	Разнообразие форматов команд и времени их исполнения, низкое быстродействие из-за обращения к памяти

Архитектура с выделенным доступом к памяти В архитектуре с выделенным доступом к памяти обращение к основной памяти возможно только с помощью двух специальных команд: load и store. В английской транскрипции данную архитектуру называют Load/Store architecture. Команда load (загрузка) обеспечивает считывание значения из основной памяти и занесение его в регистр процессора (в команде обычно указывается адрес ячейки памяти и номер регистра). Пересылка информации в противоположном направлении производится командой store (сохранение). Операнды во всех командах обработки информации могут находиться только в регистрах процессора (чаще всего в регистрах общего назначения). Результат операции также заносится в регистр. В архитектуре отсутствуют команды обработки, допускающие прямое обращение к основной памяти. Допускается наличие в АСК ограниченного числа команд, где операнд является частью кода команды.

АСК с выделенным доступом к памяти характерна для всех вычислительных машин с RISC-архитектурой. Команды в таких ВМ, как правило, имеют длину 32 бита и трехадресный формат. В качестве примеров вычислительных машин с выделенным доступом к памяти можно отметить HP PA-RISC, IBM RS/6000, Sun SPARC, MIPS R4000, DEC Alpha и т. д. К достоинствам АСК следует отнести простоту декодирования и исполнения команды.

2. Уровни моделирования. Моделирование на макроуровне. Типичная общая модель и моделирование электрических систем.

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

Модель — материальный объект или образ (мысленный или условный: гипотеза, идея, абстракция, изображение, описание, схема, формула, чертеж, план, карта, блок-схема алгоритма, ноты и т.п.), которые упрощенно отображают самые существенные свойства объекта исследования.

Любая модель всегда проще реального объекта и отображает лишь часть его самых существенных черт, основных элементов и связей. По этой причине для одного объекта исследования существует множество различных моделей. Вид модели зависит от выбранной цели моделирования. Потребность в создании и использовании моделей связана с тем, что исследовать многие реальные явления и объекты сложно или дорого, а порой вовсе невозможно.

Уровни моделирования

(Метауровень моделирования — степень детализации описания крупномасштабных объектов исследования, характеризующаяся наименее подробным рассмотрением процессов, протекающих в самих объектах. Это позволяет в одном описании отразить взаимодействие многих элементов сложного объекта.

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

Моделирование на метауровне позволило наглядно подтвердить справедливость физических законов, сформулированных Исааком Ньютоном и Альбертом Эйнштейном. Исследователи из Дарэмского университета (Великобритания) с помощью компьютерной программы имитировали процесс саморазвития нашего мира, начиная с Большого взрыва. В качестве законов эволюции использовались современные научные представления теории относительности, гравитации и другие теории. В процессе моделирования первоначально однородная Вселенная начала развиваться и, в конце концов, пришла к тому виду, который мы наблюдаем сейчас.

Макроуровень моделирования — степень детализации описания объектов, характерной особенностью которой является рассмотрение физических процессов, протекающих в непрерывном времени и дискретном пространстве.

Например, макроуровень описания радиоэлектронной аппаратуры — схемотехнический уровень. На этом уровне рассматриваются радиоэлектронные схемы, состоящие из таких дискретных элементов, как транзисторы, диоды, резисторы, конденсаторы, триггеры, логические элементы и т. п.

Микроуровень моделирования — степень детализации описания объектов, характерной особенностью которой является рассмотрение физических процессов, протекающих в непрерывном пространстве (сплошных средах) и непрерывном времени.

Фазовыми переменными при моделировании на микроуровне являются поля напряжений и деформаций в деталях механических конструкций, электромагнитные поля в электропроводящих средах, поля температур нагретых деталей.

На этом уровне моделируется, например, работа излучающих телевизионных и радио антенн, устройств вихретоковой дефектоскопии, предназначенных для контроля качества промышленных металлических изделий, устройств электромагнитного ориентирования (силового воздействия на промышленные детали с помощью электромагнитного поля), изучаются защитные свойства электромагнитных экранов.)

Метауровень.

Позволяет рассматривать объекты очень высокой сложности. Этот уровень наиболее обобщенного, размытого описания.

Функционально объект рассматривается как последовательность состояний его в дискретные моменты времени.

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

Особенности: время и пространство дискретно. Для построения модели выходных параметров, определенных в терминах стохастического (вероятностного) подхода. Характеристики приближенные.

Математический аппарат этого уровня:

имитационное моделирование

модели массового обслуживания

методы математической логики

методы дискретной математики

Макроуровень.

На макроуровне моделирования в математических моделях одна из координат (обычно время) может быть непрерывной. А остальные координаты либо отсутствуют, либо дискретны.

Чаще всего объект рассматривается как набор дискретных элементов в непрерывном времени. Количество объектов относительно невелико (порядка 100-1000).

Математический аппарат этого уровня:

алгебраические соотношения и уравнения

Обыкновенные дифференциальные уравнения (ОДУ).

Макроуровень = алгебра + ОДУ

Макроуровень - основной уровень моделирования в САПР. Причины:

наиболее доступный и эффективный для численной реализации на ЭВМ

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

Модели этого уровня используются на всех этапах проектирования (от ТЗ до поверочных рассчетов). Удобны для оптимизации.

Микроуровень.

Обеспечивает наиболее детальное и подробное описание объекта. На этом уровне все координаты, включая время, непрерывны. Поскольку параметры непрерывно меняются в пространстве и времени, эти модели еще называются моделями с распределенными параметрами. Распределенными моделями.

Математический аппарат этого уровня:

основной М.А. - дифференциальные уравнения в частных производных

Моделирование на макроуровне Модели макроуровня получаются, когда происходит переход от распределенных параметров к сосредоточенным – выделяются крупные элементы объектов и их параметры сосредоточиваются в одной точке: масса балки оказывается сосредоточенной в центре тяжести, поле потенциалов характеризуется величиной одного напряжения, поток электронов моделируется электрическим током и т. п. Происходит дискретизация пространства, однако время – по-прежнему непрерывная величина. Математическими моделями на макроуровне являются обыкновенные дифференциальные или интегро-дифференциальные уравнения.

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

В табл. 1.2 приведены типы фазовых переменных для объектов разной физической природы.

Таблица 1.2

Фазовые переменные для различных физических систем

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

Электрическая Электрическое напряжение Электрический ток

Механическая Скорость Сила

Механическая вращательная Угловая скорость Вращательный момент

Тепловая Температура Тепловой поток

Гидравлическая и пневматическая Давление Расход

В большинстве технических объектов можно выделить три типа пассивных простейших элементов

/типа R – элемент рассеивания (диссипации) энергии (как правило, преобразования энергии в тепловую и ее рассеивания);

/типа C и типа L – элементы накопления потенциальной и кинетической энергии.

Кроме пассивных элементов, существуют два активных элемента – источник напряжения и источник тока.

Уравнения, описывающие свойства элементов объекта, называют компонентными. В них входят переменные типа потенциала и типа потока. Способ связи элементов отражается с помощью других уравнений, которые называют топологическими. В них входят переменные одного типа: либо потенциала, либо потока. Топологические уравнения могут выражать законы сохранения, условия непрерывности, равновесия, баланса и т. п.

Математические модели объектов есть совокупность компонентных и топологических уравнений.

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

1) Электрические системы

Основными фазовыми переменными электрических систем являются напряжения и токи в различных элементах систем. Компонентные уравнения элементов имеют вид

,112

где U – напряжение; I – ток; R – сопротивление; C – емкость; L – индуктивность.

При соединении резисторов, емкостей, индуктивностей между собой образуется схема, соединение элементов в которой отражается топологическими уравнениями. Ими являются законы Кирхгофа:

где уравнения токов записываются для узлов, а уравнения напряжений для контуров. В ЭЭС имеются достаточно сложные элементы, и при их моделировании применяют схемы замещения, состоящие из сопротивлений, емкостей и индуктивностей.

3. Построить программу на языке С++ для работы со структурой Дата. Программа должна обеспечивать простейшие функции для работы с данными структуры: увеличение/уменьшение на 1 день, ввод значений, вывод значений.

interface

Uses SysUtils;

type TUserDate = class

private

fNumber:Word;

fMonth:word;

fYear:Integer;

public

Function SetUserDate(ANumber:Word;AMonth:Word;AYear:Integer):Boolean;

Function GetUserDate:String;

Function ModifyDate(AModify:Integer):String;

end;

implementation

Function TUserDate.SetUserDate;

Begin

If AYear>0 Then

Begin

fYear:=AYear;

if (AMonth >0) and (AMonth<=12) Then

Begin

fMonth:=AMonth;

fNumber:=0;

if ((fMonth=1)or(fMonth=3)or(fMonth=5)or(fMonth=7)or(fMonth=8)or(fMonth=10)or(fMonth=12))and(ANumber>0)and(ANumber<=31) Then

fNumber:=ANumber;

if ((fMonth=4)or(fMonth=6)or(fMonth=9)or(fMonth=11))and(ANumber>0)and(ANumber<=30) Then

fNumber:=ANumber;

if (fMonth=2) Then

if (fYear mod 4 = 0) Then

if (ANumber>0) and (ANumber<=29) Then fNumber:=ANumber

else

if (ANumber>0) and(ANumber<=28) Then fNumber:=ANumber;

if fNumber<>0 Then Result:=True else Result:=False;

end else Result:=False; end else Result:=False; End; Function TUserDate.GetUserDate; Var str,Itog:String; Begin Itog:=''; str:=IntToStr(fNumber); If length(str)=1 Then Itog:=Itog+'0'; Itog:=Itog+str+'.'; str:=IntToStr(fMonth); if length(str)=1 Then Itog:=Itog+'0'; Itog:=Itog+str+'.'; Itog:=Itog+IntToStr(fYear); Result:=Itog End; //Данная функция очень утрирована Function TUserDate.ModifyDate; Begin fNumber:=fNumber+ AModify; Result:=GetUserDate; End; end.

Тело программы program Zad_17; {$APPTYPE CONSOLE} uses SysUtils, STR_Date in 'STR_Date.pas'; var UsDate:TUserDate; Y:Integer; N,M:Word; F:Boolean; begin repeat Write('Vvedite YEAR = '); Readln(Y); Write('Vvedite MONTH = '); Readln(M); Write('Vvedite Number = '); Readln(N); UsDate:=TUserDate.Create; F:=UsDate.SetUserDate(N,M,Y); if F=False Then Writeln('ERROR Date'); Until F; Writeln('Vvedena Date =>> ',UsDate.GetUserDate); Write('Vvedite znachenie izmenenij = '); Readln(Y); Writeln('New date =>> ',UsDate.ModifyDate(Y)); Readln; { TODO -oUser -cConsole Main : Insert code here } end.

Билет 44.

1. Структуры данных типа очередь. Логическая структура очереди. Машинное представление очереди FIFO и реализация операций. Очереди с приоритетами.

Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.

Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.

Машинное представление очереди FIFO и реализация операций

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

Очевидно, что со временем указатель на конец при очередном включении элемента достигнет верхней границы той области памяти, которая выделена для очереди. Однако, если операции включения чередовались с операциями исключения элементов, то в начальной части отведенной под очередь памяти имеется свободное место. Для того, чтобы места, занимаемые исключенными элементами, могли быть повторно использованы, очередь замыкается в кольцо: указатели (на начало и на конец), достигнув конца выделенной области памяти, переключаются на ее начало. Такая организация очереди в памяти называется кольцевой очередью. Возможны, конечно, и другие варианты организации: например, всякий раз, когда указатель конца достигнет верхней границы памяти, сдвигать все непустые элементы очереди к началу области памяти, но как этот, так и другие варианты требуют перемещения в памяти элементов очереди и менее эффективны, чем кольцевая очередь.

В исходном состоянии указатели на начало и на конец указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди. Если в процессе работы с кольцевой очередью число операций включения превышает число операций исключения, то может возникнуть ситуация, в которой указатель конца "догонит" указатель начала. Это ситуация заполненной очереди, но если в этой ситуации указатели сравняются, эта ситуация будет неотличима от ситуации пустой очереди. Для различения этих двух ситуаций к кольцевой очереди предъявляется требование, чтобы между указателем конца и указателем начала оставался "зазор" из свободных элементов. Когда этот "зазор" сокращается до одного элемента, очередь считается заполненной и дальнейшие попытки записи в нее блокируются. Очистка очереди сводится к записи одного и того же (не обязательно начального) значения в оба указателя. Определение размера состоит в вычислении разности указателей с учетом кольцевой природы очереди.

{==== Программный пример 4.3 ====}

unit Queue; { Очередь FIFO - кольцевая }

Interface

const SIZE=...; { предельный размер очереди }

type data = ...; { эл-ты могут иметь любой тип }

Procesure QInit;

Procedure Qclr;

Function QWrite(a: data) : boolean;

Function QRead(var a: data) : boolean;

Function Qsize : integer;

Implementation { Очередь на кольце }

var QueueA : array[1..SIZE] of data; { данные очереди }

top, bottom : integer; { начало и конец }

Procedure QInit; {** инициализация - начало=конец=1 }

begin top:=1; bottom:=1; end;

Procedure Qclr; {**очистка - начало=конец }

begin top:=bottom; end;

Function QWrite(a : data) : boolean; {** запись в конец }

begin

if bottom mod SIZE+1=top then { очередь полна } QWrite:=false

else begin

{ запись, модификация указ.конца с переходом по кольцу }

Queue[bottom]:=a; bottom:=bottom mod SIZE+1; QWrite:=true;

end; end; { QWrite }

Function QRead(var a: data) : boolean; {** выборка из начала }

begin

if top=bottom then QRead:=false else

{ запись, модификация указ.начала с переходом по кольцу }

begin a:=Queue[top]; top:=top mod SIZE + 1; QRead:=true;

end; end; { QRead }

Function QSize : integer; {** определение размера }

begin

if top <= bottom then QSize:=bottom-top

else QSize:=bottom+SIZE-top;

end; { QSize }

END.

Очереди с приоритетами

В реальных задачах иногда возникает необходимость в формировании очередей, отличных от FIFO или LIFO. Порядок выборки элементов из таких очередей определяется приоритетами элементов. Приоритет в общем случае может быть представлен числовым значением, которое вычисляется либо на основании значений каких-либо полей элемента, либо на основании внешних факторов. Так, и FIFO, и LIFO-очереди могут трактоваться как приоритетные очереди, в которых приоритет элемента зависит от времени его включения в очередь. При выборке элемента всякий раз выбирается элемент с наибольшим приоритетом.

Очереди с приоритетами могут быть реализованы на линейных списковых структурах - в смежном или связном представлении. Возможны очереди с приоритетным включением - в которых последовательность элементов очереди все время поддерживается упорядоченной, т.е. каждый новый элемент включается на то место в последовательности, которое определяется его приоритетом, а при исключении всегда выбирается элемент из начала. Возможны и очереди с приоритетным исключением - новый элемент включается всегда в конец очереди, а при исключении в очереди ищется (этот поиск может быть только линейным) элемент с максимальным приоритетом и после выборки удаляется из последовательности. И в том, и в другом варианте требуется поиск, а если очередь размещается в статической памяти - еще и перемещение элементов.

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

2. Принципы построения современных ЭВМ.

Принципы построения современных ЭВМ --- - принцип программного управления - принцип децентрализации управления и построения - принцип модульности - принцип иерархичности построения - принцип однородности памяти.

Основным принципом построения всех современных ЭВМ является программное управление. В основе его лежит представление алгоритма решения любой задачи в виде программы вычислений. «Алгоритм – конечный набор предписаний, определяющий решение задачи посредством конечного количества операций». «Программа для ЭВМ –упорядоченная последовательность команд, подлежащая обработке»

Принцип децентрализации и параллельной работы распространен как на периферийные устройства, так и на сами ЭВМ (процессоры). Появились вычислительные системы (ВС), содержащие несколько вычислителей (ЭВМ или процессоры), работающие согласованно и параллельно. Внутри самой ЭВМ произошло еще более резкое разделение функций между средствами обработки. Появились отдельные специализированные процессоры, например сопроцессоры, выполняющие обработку чисел с плавающей точкой, матричные процессоры и др

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

Модульная конструкция ЭВМ делает ее открытой системой, способной к адаптации и совершенствованию.

Децентрализация управления предполагает иерархическую организацию структуры ЭВМ. Устройство управления главного, или центрального, процессора определяет лишь последовательность работ подчиненных модулей и их инициализацию, после чего они продолжают работу по собственным программам управления. Результаты выполнения требуемых операций представляются ими «вверх по иерархии» для правильной координации всех работ.

Основные принципы построения ЭВМ были сформулированы американским учёным Джоном фон Нейманом в 40-х годах 20 века:

1. Любую ЭВМ образуют три основные компоненты: процессор, память и устройства ввода-вывода (УВВ).

2. Информация, с которой работает ЭВМ делится на два типа: набор команд по обработке (программы). данные подлежащие обработке.

3. И команды, и данные вводятся в память (ОЗУ) – принцип хранимой программы.

4. Руководит обработкой процессор, устройство управления (УУ) которого выбирает команды из ОЗУ и организует их выполнение, а арифметико-логическое устройство (АЛУ) проводит арифметические и логические операции над данными.

5. С процессором и ОЗУ связаны устройства ввода-вывода (УВВ).

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

Шина - это кабель, состоящий из множества проводников. По одной группе проводников - шине данных передаётся обрабатываемая информация, по другой - шине адреса - адреса памяти или внешних устройств, к которым обращается процессор. Третья часть магистрали - шина управления, по ней передаются управляющие сигналы (например, сигнал готовности устройства к работе, сигнал к началу работы устройства и др).

Системная шина характеризуется тактовой частотой и разрядностью. Количество одновременно передаваемых по шине бит называется разрядностью шины. Тактовая частота характеризует число элементарных операций по передаче данных в 1 секунду. Разрядность шины измеряется в битах, тактовая частота – в мегагерцах.

Всякая информация, передаваемая от процессора к другим устройствам по шине данных, сопровождается адресом, передаваемым по адресной шине. Это может быть адрес ячейки памяти или адрес периферийного устройства. Необходимо, чтобы разрядность шины позволила передать адрес ячейки памяти. Таким образом, словами разрядность шины ограничивает объем оперативной памяти ЭВМ, он не может быть больше чем , где n – разрядность шины. Важно, чтобы производительности всех подсоединённых к шине устройств были согласованы. Неразумно иметь быстрый процессор и медленную память или быстрый процессор и память, но медленный винчестер.

Ниже представлена схема устройства компьютера, построенного по магистральному принципу:

В современных ЭВМ реализован принцип открытой архитектуры, позволяющий пользователю самому комплектовать нужную ему конфигурацию компьютера и производить при необходимости её модернизацию. Конфигурацией компьютера называют фактический набор компонентов ЭВМ, которые составляют компьютер. Принцип открытой архитектуры позволяет менять состав устройств ЭВМ. К информационной магистрали могут подключаться дополнительные периферийные устройства, одни модели устройств могут заменяться на другие.

Аппаратное подключение периферийного устройства к магистрали на физическом уровне осуществляется через специальный блок - контроллер (другие названия - адаптер, плата, карта). Для установки контроллеров на материнской плате имеются специальные разъёмы - слоты.

Программное управление работой периферийного устройства производится через программу - драйвер, которая является компонентой операционной системы. Так как существует огромное количество разнообразных устройств, которые могут быть установлены в компьютер, то обычно к каждому устройству поставляется драйвер, взаимодействующий непосредственно с этим устройством.

Связь компьютера с внешними устройствами осуществляется через порты – специальные разъёмы на задней панели компьютера. Различают последовательные и параллельные порты. Последовательные (COM – порты) служат для подключения манипуляторов, модема и передают небольшие объёмы информации на большие расстояния. Параллельные (LPT - порты) служат для подключения принтеров, сканеров и передают большие объёмы информации на небольшие расстояния. В последнее время широкое распространение получили последовательные универсальные порты (USB), к которым можно подключать различные устройства.

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

3. Найти в массиве максимальный элемент и его индекс. Вывести на печать.

Int num = 0;

Word arr[n];

Int max = arr[0];

For (int i = 0; i<n; i++)

{

if (arr[i]>max)

{

max = arr[i];

num = i;

}

}

printf(max, ‘/n’);

printf( num, ‘/n’);

Билет 45.

1. Характеристика канального и сетевого уровней стека протоколов TCP/IP.

TCP/IP -  аббревиатура термина Transmission Control Protocol/Internet Protocol (Протокол управления передачей/Интернет Протокол) - это согласованный заранее стандарт, служащий для обмена данных между двумя узлами(компьютерами в сети), причём неважно, на какой платформе эти компьютеры и какая между ними сеть. TCP/IP служит как мост, соединяющий все узлы сети воедино, за это он и завоевал свою популярность. TCP/IP зародился в результате исследований, профинансированных ARPA (Advanced Research Project Agency) - специальным отделением правительства США в 1970-х годах. Он был задуман, как общий стандарт, который объединит все сети в единую виртуальную "сеть сетей"(internetwork). Таким образом был создан Интернет, в результате преобразования существующего конгломерата вычислительных сетей, носивших название ARPAnet, с помощью TCP/IP. Название "TCP/IP" связано с двумя протоколами: TCP и IP. Но TCP/IP - это не только эти два протокола. Это целое семейство протоколов, объединенное под одним началом - IP-протоколом. В это семейство входят протоколы, которые взаимодействуют с протоколом IP и с его помощью строят свои каналы данных. Это сам TCP, а также UDP, ICMP, telnet, SMTP, FTP и многие другие.

Структура стека TCP/IP

Уровень I	Прикладной уровень
Уровень II	Основной (транспортный) уровень
Уровень III	Уровень межсетевого взаимодействия
Уровень IV	Уровень сетевых интерфейсов

Канальный уровень - Уровень сетевых интерфейсов. Идеологическим отличием архитектуры стека TCP/IP от многоуровневой организации других стеков является интерпретация функций самого нижнего уровня - уровня сетевых интерфейсов. Протоколы этого уровня должны обеспечивать интеграцию в составную сеть других сетей, причем задача ставится так: сеть TCP/IP должна иметь средства включения в себя любой другой сети, какую бы внутреннюю технологию передачи данных эта сеть не использовала. Отсюда следует, что этот уровень нельзя определить раз и навсегда. Для каждой технологии, включаемой в составную сеть подсети, должны быть разработаны собственные интерфейсные средства. К таким интерфейсным средствам относится протокол инкапсуляции IP-пакетов межсетевого взаимодействия в кадры локальных технологий.

Уровень сетевых интерфейсов в протоколах TCP/IP не регламентируется, но он поддерживает все популярные стандарты физического и канального уровней: для локальных сетей - это Ethernet, Token Ring, FDDI, Fast Ethernet, Gigabit Ethernet, 100VG-AnyLAN, для глобальных сетей - протоколы соединений "точка-точка" SLIP и PPP, протоколы территориальных сетей с коммутацией пакетов X.25, frame relay. Разработана также специальная спецификация, определяющая использование технологии ATM в качестве транспорта канального уровня.

Сетевой уровень. Стержнем всей архитектуры является уровень межсетевого взаимодействия, или сетевой уровень, который реализует концепцию передачи пакетов в режиме без установления соединений, то есть дейтаграммным способом. Именно этот уровень обеспечивает возможность перемещения пакетов по сети, используя тот маршрут, который в данный момент является наиболее рациональным. Этот уровень также называют уровнем internet, указывая, тем самым, на основную его функцию - передачу данных через составную сеть.

Основным протоколом уровня (в терминологии модели OSI) в стеке TCP/IP является протокол IP. Этот протокол изначально проектировался как протокол передачи пакетов в составных сетях, состоящих из большого количества локальных сетей, объединенных как локальными, так глобальными связями. Поэтому протокол IP хорошо работает в сетях со множеством топологий, рационально используя наличие в них подсистем и экономно расходуя пропускную способность низкоскоростных линий связи. Так как протокол IP является дейтаграммным протоколом, он не гарантирует доставку пакетов до узла назначения, но старается это сделать.

К уровню межсетевого взаимодействия относятся все протоколы, связанные с состоянием и модификацией таблиц маршрутизации, такие как протоколы сбора маршрутной информации RIP и OSPF, а также протокол межсетевых управляющих сообщений ICMP. Последний протокол предназначен для обмена информацией об ошибках между маршрутизаторами сети и удаленным источником пакета. С помощью специальных пакетов ICMP сообщает о невозможности доставки пакета, о превышении времени жизни или продолжительности сборки пакета из фрагментов, об аномальных величинах параметров, об изменении маршрута пересылки и типа обслуживания, о состоянии системы и т. п.

2. Численное решение задачи Коши для обыкновенных дифференциальных уравнений. Метод Эйлера. Одношаговые и многошаговые методы.

Обыкновенным дифференциальным уравнением называются такие уравнения, которые содержат хотя бы одну или несколько производных от искомой функции. Y = y(x)

Т.е. связывают независимые переменные x с искомой функцией y и ее производными y’(x), y’’(x) и т.д.

Наивысший порядок производной в уравнении называют порядок уравнения. Эти уравнении записываются в следующем виде:

F(x, y, y’,y’’, …, y⁽ⁿ⁾) = 0, где x – независимая переменная, y – искомая функция

Если удается выразить старшую производную в явном виде, то уравнение принимает следующий вид: y⁽ⁿ⁾(x) = F(x, y, y’,y’’, …, y^(n-1)), такой вид называется уравнением, разрешенным относительно старшей производной. Решением уравнения обыкновенного дифференциального уравнения n-ого порядка содержитn производных постоянных c₁, c₂, …, c_n.

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

φ = φ(x, c₁, c₂, …, c_n ). Произвольные параметры геометрической интерпретации общего решения обыкновенных дифференциальных уравнений (ОДУ) 1-ого порядка представляют собой бесконечное семейство интегральных кривых с параметрами c₁, c₂, …, c_n.

Частному решению соответствует 1 интегральная кривая из этого семейства.

 y=y(x, a) или (-∞; +∞) - геометрическая интерполяция

Через каждую току из области решения проходит 1 интегральная кривая. Это следует из теоремы Коши.

Теорема Коши

Если правая часть f(x, y) для уравнения y’=f(x,y) и ее частная производная

 определена и непрерывна в некоторой области G изменение переменных x, y, то для всякой внутренней точки из этой области (x0, y0) данное уравнение имеет единственное решение при x = x0 и y = y0. Для уравнений высшего порядка геометрическая интерполяция будет более сложной.

Различные постановки задачи Коши

ОДУ первого порядка, разрешённое относительно производной

Системаn ОДУ первого порядка, разрешённая относительно производных (нормальная система n-го порядка)

ОДУ n-го порядка, разрешённое относительно старшей производной

Теоремы о разрешимости задачи Коши для ОДУ

Пусть в области  рассматривается задача Коши:

где . Пусть правая часть является непрерывной функцией в . В этих предположениях имеет место теорема Пеано, устанавливающая локальную разрешимость задачи Коши: Пусть a>0 и b>0 таковы, что замкнутый прямоугольник

принадлежит области D, тогда на отрезке [x₀ − α,x₀ + α], где α = min{a,b / M}, , существует решение задачи Коши.

Указанный отрезок называется отрезком Пеано. Заметим, что, локальный характер теоремы Пеано не зависит от гладкости правой части. Например, для f(x,y) = y² + 1 и для x₀ = 0,y₀ = 0 решение y(x) = tan(x) существует лишь на интервале ( − π,π). Также отметим, что без дополнительных предположений относительно гладкости правой части, нельзя гарантировать единственность решения задачи Коши. Например, для  возможно более одного решения.

Чтобы сформулировать теорему о единственности решения задачи Коши, необходимо наложить дополнительные ограничения на правую часть. Будем говорить, что функция f(x,y) удоволетворяет условию Липшица на D относительно y, если существует постоянная L такая, что

для всех , i=1,2.

Пусть правая часть f(x,y) дополнительно удовлетворяет условию Липшица на D относительно y, тогда задача Коши не может иметь в D более одного решения.

Также отметим, что хотя эта теорема имеет глобальный характер, тем не менее она не устанавливает существование глобального решения.

Для существования глобального решения необходимо наложить условия на рост правой части по y: пусть функция f удовлетворяет условию

где A>0 - константа не зависящая ни от x, ни от y, тогда задача Коши имеет решение в D. В частности, из этой теоремы следует, что задача Коши для линейных уравнений (с непрерывными по x коэффициентами) имеет глобальное решение.

Вычислительные (численные) методы — методы решения математических задач в численном виде

Представление как исходных данных в задаче, так и её решения — в виде числа или набора чисел

В системе подготовки инженеров технических специальностей является важной составляющей.

Основами для вычислительных методов являются:

решение систем линейных уравнений

интерполирование

численное интегрирование

численное решение системы нелинейных уравнений

численное решение обыкновенных дифференциальных уравнений

Метод Эйлера — наиболее простой численный метод решения (систем) обыкновенных дифференциальных уравнений. Впервые описан Леонардом Эйлером в 1768 году в работе «Интегральное исчисление»^. Метод Эйлера является явным, одношаговым методом первого порядка точности, основанном на аппроксимации интегральной кривой кусочно линейной функцией, т. н. ломаной Эйлера.

Описание метода

Пусть дана задача Коши для уравнения первого порядка

где функция f определена на некоторой области . Решение разыскивается на интервале (x₀,b]. На этом интервале введем узлы

Приближенное решение в узлах x_i, которое обозначим через y_i определяется по формуле

Эти формулы обобщаются на случай систем обыкновенных дифференциальных уравнений.

Оценка погрешности

Метод Эйлера является методом первого порядка. Если функция f непрерывна в D и непрерывно дифференцируема по переменной y в D, то имеет место следующая оценка погрешности

где h — средний шаг, то есть существует C > 0 такая, что .

Заметим, что условия гладкости на правую часть, гарантирующие единственность решения задачи Коши, необходимы для обоснования сходимости метода Эйлера.

Значение метода Эйлера

Метод Эйлера являлся исторически первым методом численного решения задачи Коши. О. Коши использовал этот метод для доказательства существования решения задачи Коши. Ввиду невысокой точности и вычислительной неустойчивости для практического нахождения решений задачи Коши метод Эйлера применяется редко. Однако в виду своей простоты метод Эйлера находит свое применение в теоретических исследованиях дифференциальных уравнений, задач вариационного исчисления и ряда других математических проблем.

Модифицированный метод Эйлера с пересчетом

Вычисления по методу Эйлера с пересчетом делаются в два этапа.

Прогноз:

.

Коррекция:

.

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

3. Указать к какому классу относится каждый из перечисленных IP адресов:

192.168.0.15

127.0.0.1

112.0.0.15

167.58.13.21

Определить к какому классу относится каждый IP-адрес

Старший октет адреса представляем в двоичном коде: если старший бит = 0 (класс А), = 10 (класс B), = 11 (класс С)

192.168.0.15

1	1	0	0	0	0	0	0
128	64	32	16	8	4	2	1

Ответ: Класс С

127.0.0.1

0	1	1	1	1	1	1	1
128	64	32	16	8	4	2	1

Ответ: Класс А

112.0.0.15

0	1	1	1	0	0	0	0
128	64	32	16	8	4	2	1

Ответ: Класс А

167.58.13.21

1	0	1	0	0	1	1	1
128	64	32	16	8	4	2	1

Ответ: Класс В