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

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

Не следует также забывать о том, что время хранения заряда конденсатора ограниченно из-за «паразитных утечек». Поэтому, чтобы не потерять имеющиеся данные, необходимо периодически восстанавливать записанную информацию, которая выполняется в циклах регенерации (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-е гг. началось бурное развитие вычислительной техники и наук, связанных с ее функционированием и использова­нием, то выяснилось, что в основе этих наук также должна лежать теория алгоритмов, поскольку компьютер может реализовать только такие процедуры, которые представимы в виде алго­ритмов. Любая программа есть ни что иное, как запись алгоритма на языке, который может «понять» исполнитель - компьютер. Таким образом, с практической точки зрения также представляется важным уточнение понятия алгоритма.

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