Динамическое программирование — Информатика. Шпоры | iFREEstore

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

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

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

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

Можно выделить два класса задач, к которым методы динамического программирования применяются наиболее удачно.

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

Второй класс задач – задачи оптимального распределения ресурсов между различными направлениями во времени.

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

Рассмотрим основные теоретические аспекты решения задач методом динамического программирования. Будем считать, что состояние рассматриваемой системы  на k-ом шаге  определяется совокупностью чисел

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

 

последовательности подзадач Ti выберем последовательность задач F(i), которые сводятся к вычислению i-го члена ряда. Тогда T1 и T2 нам известны

Задача Черепашка.

Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора “Черепашки”. Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен “максимальный” путь для всех клеток, кроме правой нижней (функция F(XY)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение:

Function F(x,y:integer):longint;

begin

if B[x, y] = –1 then

if F(x-1, y) > F(x, y - 1)

then B[x, y] := F(x - 1, y) + A[x, y]

else B[x, y] := F(x, y - 1) + A[x, y];

F := B[x, y]

end;

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

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

for i:=1 to N do

for j:=1 to N do

if B[i - 1, j] > B[i, j - 1]

then B[i, j] := B[i - 1, j] + A[i, j]

else B[i, j] := B[i, j - 1] + A[i, j];

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

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

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

По размеру, охваченной территории: Персональная сеть (PAN, Personal Area Network).Локальная сеть (LAN, Local Area Network)

HomePNA. Объединение нескольких зданий CAN, Campus Area Network). Городская сеть (MAN, Metropolitan Area Network).

Национальная сеть. Глобальная вычислительная сеть (WAN, Wide Area Network).

По типу функционального взаимодействия: Клиент-сервер. Смешанная сеть. Точка-точка. Одноранговая сеть. Многоранговые сети.

По типу сетевой топологии: Шина. Звезда. Кольцо. Решётка. Смешанная топология. Полносвязная топология

По функциональному назначению: Сети хранения данных. Серверные фермы. Сети управления процессом. Сети SOHO.

По скорости передачи информации компьютерные сети делятся на низко-, средне- и высокоскоростные..

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

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

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

Рассмотрим технологию разработки программ с использованием популярной системы программирования Турбо-Паскаль 7 (оставив знакомство с самим языком до следующей главы).

В подобных интегрированных системах программирования сделана попытка предоставить разработчику программ максимум сервисных возможностей. Помимо основных функций система Турбо-Паскаль 7 позволяет настроить компилятор на работу в трех режимах: обычном режиме MS DOS (Real), защищенном режиме (Protected) и в режиме операционной среды Windows (Windows).

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

File - работа с файлами (сохранение, загрузка, связь с ОС);

Edit - работа с текстовым редактором (после загрузки системы по умолчанию текстовый редактор находится в активном состоянии);

Search - поиск и замена фрагментов текста;

Run -запуск программы на выполнение;

Compile - компиляция программы и установка параметров компиляции;

Debug - установка параметров отладки программы;

Tools - инструментальные программные средства (ненавязчивый сервис);

Options-установка опций интегрированной среды;

Window - работа с окнами;

Help - система помощи и подсказок.

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

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

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

Тэг <div align="center">, означающий разделение документа на части, содержит, кроме имени div, атрибут align со значением "center", означающий выравнивание по центру.

В тэгах могут использоваться только символы латинского алфавита, а в значениях атрибутов - любые символы. Если в качестве значений атрибута используются, например, символы кириллицы, то они должны быть заключены в кавычки, например name="Раздел 1".

Язык HTML не различает большие и малые буквы, так что тэги <HEAD><head> и <Head> эквивалентны. Далее мы будем использовать написание тэгов в нижнем регистре.

Большинство тэгов спарены: за открывающим тэгом следует соответствующий ему закрывающий тэг, а между ними содержится текст или другие тэги.

В таких случаях два тэга и часть документа, заключенная между ними, образует блок, называемый элементом HTML. Некоторые тэги, например <hr>, являются одиночными, и для них закрывающий тэг не применяется. Такие тэги сами по себе являются элементами HTML.

Большинство тэгов могут иметь один или несколько атрибутов - параметров, дающих дополнительную информацию о том, как браузер должен обрабатывать текущий тэг. Однако атрибутов может и не быть вовсе. Атрибут тэга состоит из имени, например, align, знака равенства = и значения, которое задается строкой символов, например,"center":align="center". Значения атрибутов обычно заключаются в кавычки. Однако если эти значения используют только символы латинского алфавита, цифры и дефисы, то кавычки можно опустить, например: align=center.

Каждый HTML-документ имеет определенную структуру, которая выглядит следующим образом:

<html>

<head>

</head>

<body>

</body>

</html>

Структура HTML-документа содержит следующие обязательные элементы:

• тэги <html> и </html>, которые отмечают начало и конец документа;

•       заголовок, ограниченный тэгами <head> и </head>;

•       тело, ограниченное тэгами <body>...</body>.

В заголовке, ограниченном тэгами <head> и </head>, с помощью тэгов <title>...</title> определяется название документа, которое должно описывать его содержимое и обычно содержит не более 5-6 слов. Это название отображается браузерами в строке заголовка рабочего окна программы, а роботы, составляющие индексы для поисковых систем, идентифицируют документ, используя его название.

Кроме элемента <title>...</title>, заголовок может содержать элементы <meta>...</meta>. Открывающий тэг <meta> включает пары имя=значение, описывающие свойства документа, например, авторство, список ключевых слов и т.д. Эти данные используются также поисковыми серверами при индексации документов.

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

Первой действующей ЭВМ стал ENIAC (США, 1945 – 1946 гг.). Его название по первым буквам соответствующих английских слов означает “электронно-числовой интегратор и вычислитель”. Руководили ее созданием Джон Моучли и Преспер Эккерт, продолжившие начатую в конце 30-х годов работу Джорджа Атанасова. Машина содержала порядка 18 тысяч электронных ламп, множество электромеханических элементов. Ее энергопотребление равнялось 150 кВт, что вполне достаточно для обеспечения небольшого завода.

Практически одновременно велись работы над созданием ЭВМ в Великобритании. С ними связано прежде всего имя Аллана Тьюринга – математика, внесшего также большой вклад в теорию алгоритмов и теорию кодирования. В 1944 г. в Великобритании была запущена машина “Колосс”.

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

Огромный вклад в теорию и практику создания электронной вычислительной техники на начальном этапе ее развития внес один из крупнейших американских математиков Джон фон Нейман. В историю науки навсегда вошли “принципы фон Неймана”. Совокупность этих принципов породила классическую (фон-неймановскую) архитектуру ЭВМ. Один из важнейших принципов – принцип хранимой программы – требует, чтобы программа закладывалась в память машины так же, как в нее закладывается исходная информация. Первая ЭВМ с хранимой программой (EDSAC) была построена в Великобритании в 1949 г.

В нашей стране вплоть до 70-х годов создание ЭВМ велось почти полностью самостоятельно и независимо от внешнего мира (да и сам этот “мир” был почти полностью зависим от США). Дело в том, что электронная вычислительная техника с самого момента своего первоначального создания рассматривалась как сверхсекретный стратегический продукт, и СССР приходилось разрабатывать и производить ее самостоятельно. Постепенно режим секретности смягчался, но и в конце 80-х годов наша страна могла покупать за рубежом лишь устаревшие модели ЭВМ (а самые современные и мощные компьютеры ведущие производители – США и Япония – и сегодня разрабатывают и производят в режиме секретности).

Первая отечественная ЭВМ – МЭСМ (“малая электронно-счетная машина”) -была создана в 1951 г. под руководством Сергея Александровича Лебедева, крупнейшего советского конструктора вычислительной техники, впоследствии академика, лауреата государственных премий, руководившего созданием многих отечественных ЭВМ. Рекордной среди них и одной из лучших в мире для своею времени была БЭСМ-6 (“большая электронно-счетная машина, 6-я модель”), созданная в середине 60-х годов и долгое время бывшая базовой машиной в обороне, космических исследованиях, научно-технических исследованиях в СССР. Кроме машин серии БЭСМ выпускались и ЭВМ других серий – “Минск”, “Урал”, М-20, “Мир” и другие, созданные под руководством И.С.Брука и М.А.Карцева, Б.И.Рамеева, В.М.Глушкова, Ю.А.Базилевского и других отечественных конструкторов и теоретиков информатики.

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

← Предыдущая
Страница 1
Следующая →

Файл

остальные шпоры.docx

остальные шпоры.docx
Размер: 591 Кб

.

Пожаловаться на материал

В информатике совокупность взаимосвязанных данных называется информационной структурой. Компьютерные сети. Языки программирования. Язык разметки HTML. ЭВМ. Информационная система

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Эта тема принадлежит разделу:

Информатика. Шпоры

В информатике совокупность взаимосвязанных данных называется информационной структурой. Компьютерные сети. Языки программирования. Язык разметки HTML. ЭВМ. Информационная система

К данному материалу относятся разделы:

Табличные процессоры

Реляционные БД. Правила Кодда. Аномалии. Нормальные формы

Правил Кодда

Компьютерные сети

Базы данных. Классификация. Архитектура

Парадигмы программирования. Языки программирования. Системы программирования

Язык разметки HTML. Web-страницы. Создание

История развития ВТ

Поколения ЭВМ

Программное обеспечение ЭВМ

Информационная система (ИС)

SQL. Команды определения данных

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

Основные принципы функционирования ЭВМ. Основные структурные элементы современного компьютера. Функции и характеристики

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

SQL. Команды управления данными

Методы сортировки и поиска. Алгоритмы и программы

Симплекс-метод

Язык JAVA-Script

Исследование операций

Кодирование информации

Компьютерное моделирование в экологии

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

Компьютерное моделирование физических процессов

Массивы в ООП-языках. Примеры использования

Рекурсивно-логическое программирование. Пролог. Основные принципы работы с базами знаний

Работа со списками в Прологе

Основные концепции ООП

Похожие материалы:

Примерный список вопросов к зачету  по дисциплине «Базы данных»

Стратегический менеджмент

Предпринимательский менеджмент. Реализация организационных стратегий. Стратегическое управление. Функции предпринимательства. Стратегии. Наступательные стратегии. Модель дизайна школы. Миссия, фирмы, курс развития.

Осаждение из парогазовой смеси (ПГС)

Пример и Решение. Проводится осаждение реагента из парогазовой смеси, растворяемого в кислороде - газе-носителе. Определить число молекул. Изменение давления в процессе незначительно.

Жилищное право. Ответы на билеты

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

Охрана праці

ирішення питань з охорони праці в ході проектної розробки має на меті зменшити виробничі травми та професійні захворювання, які виникають в результаті дії небезпечних та шкідливих факторів