Принцип работы динамической памяти

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

Не следует также забывать о том, что время хранения заряда конденсатора ограниченно из-за «паразитных утечек». Поэтому, чтобы не потерять имеющиеся данные, необходимо периодически восстанавливать записанную информацию, которая выполняется в циклах регенерации (refresh cycle). Для считывания содержимого ячеек (которое сопровождается перезаписью информации) используется один из каналов контроллера прямого доступа (DMA) — в первых моделях РС.

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

Вопросы для активизации и создания проблемной ситуации.

1. Дайте определение запоминающих устройств

2. Для чего предназначены запоминающие устройства?

3. Основные характеристики запоминающих устройств?

4. Какая память называется системной?

5. Какая память называется виртуальной?

6. Для чего служит оперативная память.

7. Для чего служит постоянная память.

8. В чем заключается принцип работы динамической памяти

9. Дайте понятие адреса

10. Дайте понятие абсолютного адреса

11. В чем заключается принципиальное различие между ПЗУ и ППЗУ?

Раздел 4. Алгоритмическое решение задач, анализ алгоритмической

Сложности.

Лекция №9. Стратегии решения задач. Алгоритм и поиск решений. (1 час)

Цель лекции: Рассмотреть стратегии решения задач; понятие алгоритма; поиск

решений; свойства алгоритма; стратегию реализации алгоритма;

виды алгоритмов; способы записи алгоритмов; графический способ

записи алгоритмов; виды блок- схем.

Вопросы лекции:

1. Стратегии решения задач.

2. Алгоритм и поиск решений.

3. Свойства алгоритма.

4. Концепции алгоритма.

5. Стратегии реализации алгоритма.

6. Виды алгоритмов. Способы записи алгоритмов

7. Графический способ записи алгоритмов. Виды блок- схем.

Содержание лекции:

Стратегии решения задач.

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

Пример. Задача Звонок другу по телефону подразделяется на следующие этапы (шаги):

1) поднять телефонную трубку;

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

определить тип гудков: вызов или занято. Если вызов, перейти на п. 4, если занято, перейти на п. 6;

дождаться 5 вызывающих гудков;

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

6) положить телефонную трубку; конец решения задачи с отрицательным результатом (абонент занят).

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

Приведенная последовательность шагов является алгоритмом, решения задачи Звонок другу по телефону. Исполнитель этого алгоритма — человек. Объекты алгоритма — телефон и телефонные сигналы.

Алгоритм и поиск решений.

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

во-первых, требуется выделить систему и построить ее информационную модель — ею определяется набор данных и их взаимосвязи;

во-вторых, должен быть установлен порядок обработки данных.

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

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

определение правил обработки информации с учетом того, что она представлена в дискретной форме;

установление, каким требованиям должно удовлетворять устройство, производящее обработку;

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

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

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

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

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

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

Свойства алгоритма.

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

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

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

Замечание. Свойство детерминированности объединяет в себе одновременное выполнение свойств точностии понятности.Поясним эти свойства.

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

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

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

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

Конечность— завершение работы алгоритма за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.

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

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

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

Отметим, что для каждого исполнителя набор допустимых действий всегда ограничен — не может существовать исполнителя, для которого любое действие является допустимым. Перефразированное рассуждение И.Канта обосновывает сформулированное утверждение следующим образом: «Если бы такой исполнитель существовал, то среди его допустимых действий было бы создание такого камня, который он не может поднять. Но это противоречит допустимости действия Поднять любой камень». Ограничение над допустимыми действиями означает, что для любого исполнителя имеются задачи, которые нельзя решить с его помощью.

Концепции алгоритма.

Понятие алгоритма, в какой-то мере определяемое перечислением свойств 1-5, также нельзя считать строгим, поскольку в формулировках свойств использованы термины «величина», «способ», «простой», «локальный» и другие, точный смысл которых не установлен. В дальнейшем данное определение будем называть нестрогим (иногда его называют интуитивным) понятием алгоритма.

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

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

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

Таким образом, возникла необходимость в точном определении понятия «любой алгоритм, т.е. максимально общем определении, под которое подходили бы все мыслимые виды алгоритмов. В 20-е гг. XX в. построение определения алгоритма стало одной из центральных математических проблем. Определение это, с одной стороны, должно было соответствовать сущности интуитивного понятия алгоритма, а с другой стороны, быть формально строгим. Попытки формулировки такого понятия привели к появлению в 30-х гг. XX века теории алгоритмов как самостоятельной науки, которая вместе с математической логикой изучает основные средства математики — методы доказательств, способы построения аксиоматических теорий, свойства математических процедур и пр. Когда же в 40-е — 50-е гг. началось бурное развитие вычислительной техники и наук, связанных с ее функционированием и использованием, то выяснилось, что в основе этих наук также должна лежать теория алгоритмов, поскольку компьютер может реализовать только такие процедуры, которые представимы в виде алгоритмов. Любая программа есть ни что иное, как запись алгоритма на языке, который может «понять» исполнитель — компьютер. Таким образом, с практической точки зрения также представляется важным уточнение понятия алгоритма.

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

Статьи к прочтению:

Лекция 280. Динамическая память

Похожие статьи: