Алгоритм. Основные принципы составления алгоритмов. Примеры. Алгоритмы в программировании

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

1. Алгоритм Деккера и Петерсона

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

Критическая секция - участок кода, в котором должен находиться только один процесс.

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

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

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

4. процессы должны проходить свои критические участки как можно быстрее, не должны зацикливаться на своих критических участках. Если такое произошло, то ОС должна отменить режим взаимоисключения, чтобы другие процессы могли продолжить вычисление

5. процессы вне своих критических участков не должны мешать другим процессам входу в свои критические участки

Собственно алгоритм:

shared int ready = {0,0}; // готовность ко входу

shared int turn; // чья очередь

while (условие) {

ready[i] = 1; // сообщаем о желании войти в КС

turn = 1 - i; // даем возможность входа другому процессу

while (ready && (turn == 1-i)); // если очередь оказалась не нашей, ждем пока он не выйдет из КС

// критическая секция

ready[i] = 0; // сообщаем о выходе из КС

Требования к программной реализации:

* Не используется аппаратная поддержка

* Нет предположений о скорости процессоров и их количестве

* В критической секции только один процесс

* Условие ограниченного ожидания - если один процесс решил войти в свою критическую секцию, это не должно продолжаться неограниченно долго.

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

2. М еханизм синхронизации. Семафоры

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

* P(S) - операция пролога критической секции

Пока S=0 процесс блокируется

Когда S>0, S=S-1

* V(S) - операция эпилога критической секции

Операция V атомарна автоматически, атомарность P надо обеспечивать - программистом, аппаратным обеспечением или ОС.

Для задачи «потребитель-производитель» критической операцией будет любая работа с буфером.

semaphore mutex = 1; // бтв, я нихуц не понял почему переменные названы

semaphore empty = N; // именно так, ибо смысл у них обратный их

semaphore full = 0; // названиям. Так что я бы full empty.

void Prod() { // производитель

while ( 1) {

Произвести() ; // производим нечто

P( empty) ; // проверяем наличие места в буфере. Если полон ( empty==0 ) , залипаем, иначе уменьшаем количество места в нем на единицу

P( mutex) ; //

ПоложитьВБуфер() ;

V( mutex) ; // освобождаем mutex

V( full) ; // увеличиваем количество элементов в буфере. Это разлепляет ожидающих потребителей

void Cons() { // потребитель

while ( 1) {

P( full) ; // проверяем есть ли в буфере что-нибудь. Если пуст ( full==0 ) , залипаем, иначе уменьшаем количество элементов на единицу.

P( mutex) ; // залипаем если сейчас между P(mutex) и V(mutex) находится другой процесс

ИзвлечьИзБуфера() ;

V( mutex) ; // освобождаем mutex . Остальные процессы могут ходить сюда отныне

V( empty) ; // увеличиваем количество свободного места на единицу. Это разлепляет производителей

ИспользоватьПолученныеДанные() ; // радостно съедаем полученую из буфера нямку

3. М еханизм синхронизации. Мониторы

Появились в 1974. Хор.

Являются более высокоуровневым механизмом чем семафоры. Были созданы для устранения недостатков семафоров.

Строятся на основе языков ООП.

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

описание данных

void m1 (…) {…}

void mN(…) {…}

{инициализация /* выполняется один раз при создании монитора */}

Только один процесс может в один момент времени работать с монитором (находиться в состоянии исполнения или готовности к исполнению).

Это реализуется компилятором, путем добавления пролога и эпилога для входа и выхода из монитора. Однако, этого недостаточно для задач синхронизации, поэтому в мониторе есть две дополнительных операции - signal и wait. Обе операции выполняются над условной переменной, которая описывается в мониторе.

Если процесс выполняет wait(), он блокируется и переходит в состояние ожидания.

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

condition full, empty;

if (count==N) full.wait();

ПоложитьВБуфер(el);

if (count==1) empty.signal(); // если раньше очередь была пуста, сигналим

if (count==0) empty.wait();

ИзвлечьИзБуфера();

if (count==(N-1)) full.signal();

// инициализация:

Prod() { // производитель

ПРОИЗВОДИТ!

Cons() { // потреблятель

ПОТРЕБЛЯТ!}}

4. Механизм синхронизации процессов. Сообщения, эквивален тность механизмов синхронизации

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

Критическая секция (КС) - часть кода программы, которая может привести к конфликтам.

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

Структура КС: пролог, КС, эпилог.

Требования к алгоритмам взаимоисключений:

1. Решение программным путем.

2. Отсутствие предположений о количестве процессоров и их быстродействии.

3. Условие взаимоисключения, т.е. в КС находится только один процесс.

4. Условие прогресса - если процесс находится вне КС, он не должен препятствовать другим процессам входить в свои КС.

5. Условие ограниченного ожидания - если процесс захотел войти в КС это не должно откладываться бесконечно долго.

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

Сообщения.

Наиболее простой механизм синхронизации. Реализуется с использованием 2х примитивов:

send (Q, mess) - отправить сообщение mess, процессу / объекту Q.

receive (Q, mess) - получить сообщение mess, от процесса / объекта Q.

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

- : медленно.

+: возможно использование для общения удаленных процессов.

Эквивалентность механизмов синхронизации.

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

Реализация мониторов с помощью семафоров.

Для этого нам нужно реализовывать взаимоисключения при входе в монитор и условные переменные. Возьмем семафор mutex с начальным значением 1 для реализации взаимоисключения при входе в монитор и по одному семафору ci для каждой условной переменной. Кроме того, для каждой условной переменной заведем счетчик fi для индикации наличия ожидающих процессов. Когда процесс входит в монитор, компилятор будет генерировать вызов функции monitor_enter, которая выполняет операцию P над семафором mutex для данного монитора. При нормальном выходе из монитора (то есть при выходе без вызова операции signal для условной переменной) компилятор будет генерировать вызов функции monitor_exit, которая выполняет операцию V над этим семафором.

Для выполнения операции wait над условной переменной компилятор будет генерировать вызов функции wait, которая выполняет операцию V для семафора mutex, разрешая другим процессам входить в монитор, и выполняет операцию P над соответствующим семафором ci, блокируя вызвавший процесс. Для выполнения операции signal над условной переменной компилятор будет генерировать вызов функции signal_exit, которая выполняет операцию V над ассоциированным семафором ci (если есть процессы, ожидающие соответствующего события), и выход из монитора, минуя функцию monitor_exit.

01 Semaphore mutex = 1;

02 void monitor_enter()

06 void monitor_exit()

10 Semaphore ci = 0;

19 void signal_exit(i)

Заметим, что при выполнении функции signal_exit, если кто-либо ожидал этого события, процесс покидает монитор без увеличения значения семафора mutex, не разрешая тем самым всем процессам, кроме разбуженного, войти в монитор. Это увеличение совершит разбуженный процесс, когда покинет монитор обычным способом или когда выполнит новую операцию wait над какой-либо условной переменной.

Реализация сообщений через семафоры.

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

Процесс, желающий получить сообщение.

Процесс-получатель с номером i прежде всего выполняет операцию P(mutex), получая в монопольное владение разделяемую память. После чего он проверяет, есть ли в буфере сообщения. Если нет, то он заносит себя в список процессов, ожидающих сообщения, выполняет V(mutex) и P(ci). Если сообщение в буфере есть, то он читает его, изменяет счетчики буфера и проверяет, есть ли процессы в списке процессов, ожидающих записи. Если таких процессов нет, то выполняется V(mutex), и процесс-получатель выходит из КС. Если такой процесс есть (с номером j), то он удаляется из этого списка, выполняется V для его семафора cj, и выходим из КС. Проснувшийся процесс начинает выполняться в КС, так как mutex имеет значение 0 и никто более не может попасть в КС. При выходе из КС разбуженный процесс производит вызов V(mutex).

Работа процесса-отправителя (номером i). Процесс, посылающий сообщение, ждет, пока не сможет иметь монополию на использование разделяемой памяти, выполнив операцию P(mutex). Далее он проверяет, есть ли место в буфере, и если да, то помещает туда сообщение, изменяет счетчики и смотрит, есть ли процессы, ожидающие сообщения. Если нет, выполняет V(mutex) и выходит из КС, если есть, то «будит» один из них (с номером j), вызывая V(cj), с одновременным удалением этого процесса из списка процессов, ожидающих сообщений, и выходит из КС без вызова V(mutex), предоставляя тем самым возможность разбуженному процессу прочитать сообщение. Если места в буфере нет, то процесс-отправитель заносит себя в очередь процессов, ожидающих возможности записи, и вызывает V(mutex) и P(ci).

Реализация семафоров с помощью мониторов

Самый простой способ такой реализации выглядит следующим образом. Заведем внутри монитора переменную-счетчик, связанный с эмулируемым семафором списком блокируемых процессов и по одной условной переменной на каждый процесс. При выполнении операции P над семафором вызывающий процесс проверяет значение счетчика. Если оно больше нуля, уменьшает его на 1 и выходит из монитора. Если оно равно 0, процесс добавляет себя в очередь процессов, ожидающих события, и выполняет операцию wait над своей условной переменной. При выполнении операции V над семафором процесс увеличивает значение счетчика, проверяет, есть ли процессы, ожидающие этого события, и если есть, удаляет один из них из списка и выполняет операцию signal для условной переменной, соответствующей процессу.

Реализация семафоров с помощью очередей сообщений.

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

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

Т.о. все эти конструкции являются эквивалентными, т.е., используя любую из них, можно реализовать две оставшиеся.

5 . Ра спределение памяти раз делами, перемещаемыми разделами

Распределение памяти фиксированными разделами.

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

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

Варианты определения раздела для загрузки:

1. первый попавшийся.

2. Наиболее подходящий.

3. Наименее подходящий.

+: простота реализации, запуск нескольких процессов, отсутствует внешняя фрагментация (вся память распределена по разделам)

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

Распределение памяти разделами переменной длины.

При таком варианте ОП заранее не делится на разделы. Для каждого запущенного процесса выделяется раздел необходимого ему размера. По завершении процесса память освобождается и на ее место может быть загружен новый процесс.

Т.о. память представляет собой случайную последовательность свободных и занятых разделов произвольной длины.

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

+: количество одновременно загруженных программ жестко не ограничено; отсутствует внутренняя фрагментация.

- : большая внешняя фрагментация.

Распределение памяти перемещаемыми разделами.

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

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

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

+: отсутствие внутренней фрагментации; малая внефняя фрагментация.

- : большие накладные расходы, во время сжатия работа всех программ приостанавливается

6 . Ст раничное распределение памяти

Память разделяется на страницы фиксированного размера (кратные степени 2, для х86 - 4Кб).

Логическое адресное пространство состоит из логических страниц, а физическое из физических.

Адрес представляет собой пару (p, d), где p - номер логической страницы, а d - смещение в ней.

Схема преодразования логического адреса (ЛА) в физический (ФА):

синхронизация код программный алгоритм

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

Реализуется программно или аппаратно (процессор имеет регистр с адресом таблицы страниц текущего процесса)

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

- : большие накладные расходы без аппаратной поддержки.

Для уменьшения накладных расходов таблицу страниц можно хранить в кэше процессора.

7. Сегментное распределение памяти

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

Адресное пространство процесса представляет собой набор сегментов, располагающихся непрерывно в памяти.

Преобразование адресов производится следующим образом (не для DOS):

Рисунок 1. Преобразование адресов при сегментной адресации

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

Достоинства сегментной организации памяти:

Защита памяти (имеется атрибут сегмента в таблице);

Недостатки:

Сегменты должны храниться непрерывно.

8. Сегментно-страничное распределение памяти

Заключается в том, что сегмент состоит из страниц (см. вопрос 6,7 СПО).

Адрес состоит из трех полей:

Достоинства:

Возможно совместное использование памяти процессами;

Гибкая настройка прав доступа, т.к. у каждой таблицы имеются атрибуты.

Недостатки:

Для доступа к данным необходимо три обращения.

9. Виртуальная память на основе сегментно-с траничного распределения памяти

Виртуальная память.

Виртуальная память используется в качестве расширения доступной памяти. Ее особенность состоит в том, что она использует несколько уровней памяти (например, винчестер и ОП).

Появилась в 1959 г.

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

Можно выделить следующие достоинства виртуальной памяти:

1) Программа не ограничена объемом ОП.

2) Есть возможность частичного размещения программ, что позволяет увеличить количество выполняемых программ.

3) Объем ввода / вывода информации значительно меньше, чем в классическом swapping"е (суть swapping"а - страницы копируются на винчестер при отсутствии места в ОП).

4) Объем адресуемой памяти становится равным максимальному объему для данной разрядности (к примеру, 32 разряда = 4 Гб).

Виртуальная память может быть распределена как:

а) страничная;

б) сегментная;

в) странично-сегментная.

Технология виртуализации памяти может быть полностью реализована программно.

Виртуальная память на основе сегментно-страничного разделения.

Основана на таблице страниц, куда добавляются биты:

1) Бит модификации (была ли изменена страница).

2) Бит присутствия (где страница лежит - в ОП или на винчестере).

3) Бит обращения (происходило ли обращение к странице).

Исключительные ситуации при работе с виртуальной памятью (к примеру, отсутствует страница в памяти) обрабатываются операционной системой и их относят к особому типу прерываний.

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

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

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

2) Стратегия размещения - в какой участок первичной памяти поместить поступающую страницу.

3) Стратегия замещения - какую страницу нужно вытолкнуть во внешнюю память, чтобы освободить место в оперативной памяти. Для данной стратегии используются алгоритмы FIFO и др.

Размещено на Allbest.ru

Подобные документы

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

курсовая работа , добавлен 16.12.2014


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

лекция , добавлен 05.02.2009


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

курсовая работа , добавлен 15.04.2015


Структура, классификация и требования к реализации компилятора. Проектирование и реализация анализирующей части компилятора языка С++. Способы реализации лексического анализа. Алгоритм работы синтаксического анализатора. Принципы программной реализации.

курсовая работа , добавлен 26.01.2013


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

курсовая работа , добавлен 29.08.2010


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

курсовая работа , добавлен 02.06.2015


Понятие и назначение штрихового кода, его разновидности и сферы применения. Параметры символики и структура символа в кодах. Алгоритм преобразования числовых данных в знаки Interleaved 2 of 5. Распознавание штрих-кода и вычисление контрольной цифры.

контрольная работа , добавлен 23.08.2009


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

дипломная работа , добавлен 19.01.2017


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

дипломная работа , добавлен 03.06.2012


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

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

Алгоритм – понятная и точная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное.

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

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

Для создания алгоритма (программы) необходимо знать:

полный набор исходных данных задачи (начальное состояние объекта);

цель создания алгоритма (конечное состояние объекта);

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

Полученный алгоритм (программа) должен обладать следующим набором свойств:

дискретность (алгоритм разбит на отдельные шаги - команды);

однозначность (каждая команда определяет единственно возможное действие исполнителя);

понятность (все команды алгоритма входят в систему команд исполнителя);

результативность (исполнитель должен решить задачу за конечное число шагов).

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

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

Обозначение	Описание	Примечания
	Начало и конец алгоритма
	Ввод и вывод данных.	Вывод данных иногда обозначают иначе:
	Действие	В вычислительных алгоритмах так обозначают присваивание
	Развилка	Развилка - компонент, необходимый для реализации ветвлений и циклов
	Начало цикла с параметром
	Типовой процесс	В программировании - процедуры или подпрограммы
	Переходы между блоками

Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

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

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

Линейная структура (следование).

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

Ветвление.

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

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

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

Цикл (повторение).

Цикл позволяет организовать многократное повторение одной и той же последовательности команд - она называется телом цикла. В различных видах циклических алгоритмов количество повторений может зависеть от значения логического выражения (условия) или может быть жестко задано в самой структуре. Различают циклы: «д о », «п ока », циклы со счётчиком. В циклах «д о» и «п ока» логическое выражение (условие) может предшествовать телу цикла (цикл с предусловием ) или завершать цикл (цикл с послеусловием ).

Ц иклы «д о » - повторение тела цикла до выполнения условия:

Ц иклы «п ока » - повторение тела цикла пока условие выполняется (истинно):

Ц иклы со счётчиком (с параметром) – повторение тела цикла заданное число раз:

Вспомогательный алгоритм (подпрограмма, процедура).

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

Методы разработки сложных алгоритмов.

Существует два метода разработки сложных алгоритмов:

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

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

Управление - целенаправленное взаимодействие объектов, одни из которых являются управляющими, другие - управляемыми.

В простейшем случае таких объектов два:

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

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

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

Основы программирования

Программа. Этапы разработки программы. Спецификация. Разработка алгоритма. Кодирование. Отладка. Тестирование. Создание справочной системы. Создание установочного диска. Алгоритм и программа. Компиляция. Язык программирования Delphi. Тип данных. Переменная. Константы. Инструкция присваивания. Выражение. Тип выражения. Выполнение инструкции присваивания. Стандартные функции. Математические функции. Функции преобразования. Ввод данных. Вывод результатов. Процедуры и функции. Структура процедуры. Структура функции. Запись инструкций программы. Стиль программирования

Программа

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

Этапы разработки программы

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

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

1. Спецификация (определение, формулирование требований к программе).

2. Разработка алгоритма.

3. Кодирование (запись алгоритма на языке программирования).

4. Отладка.

5. Тестирование.

6. Создание справочной системы.

7. Создание установочного диска (CD-ROM).

Спецификация

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

Разработка алгоритма

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

Кодирование

После того как определены требования к программе и составлен алгоритм решения, алгоритм записывается на выбранном языке программирования. В результате получается исходная программа.

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

Тестирование

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

Создание справочной системы

Если разработчик предполагает, что программой будут пользоваться другие, то он обязательно должен создать справочную систему и обеспечить пользователю удобный доступ к справочной информации во время работы с программой. В современных программах справочная информация представляется в форме СНМ- или HLP-файлов. Помимо справочной информации, доступ к которой осуществляется из программы во время ее работы, в состав справочной системы включают инструкцию по установке (инсталляции) программы, которую оформляют в виде Readme-файла в одном из форматов: TXT, DOC или НТМ.

Создание установочного диска

Установочный диск или CD-ROM создаются для того, чтобы пользователь мог самостоятельно, без помощи разработчика, установить программу на свой компьютер. Обычно помимо самой программы на установочном диске находятся файлы справочной информации и инструкция по установке программы (Readme-файл). Следует понимать, что современные программы, в том числе разработанные в Delphi, в большинстве случаев (за исключением самых простых программ) не могут быть установлены на компьютер пользователя путем простого копирования, так как для своей работы требуют специальных библиотек и компонентов, которых может и не быть у конкретного пользователя. Поэтому установку программы на компьютер пользователя должна выполнять специальная программа, которая помещается на установочный диск. Как правило, установочная программа создает отдельную папку для устанавливаемой программы, копирует в нее необходимые файлы и, если надо, выполняет настройку операционной системы путем внесения дополнений и изменений в реестр.

Алгоритм и программа

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

Рис. 1. Основные символы, используемые для представления алгоритма в виде блок-схемы

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

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

При программировании в Delphi алгоритм решения задачи представляет собой совокупность алгоритмов процедур обработки событий.

Компиляция

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

Компилятор, схема работы которого приведена на рис. 2, выполняет последовательно две задачи:

1. Проверяет текст исходной программы на отсутствие синтаксических ошибок.

2. Создает (генерирует) исполняемую программу - машинный код.

Рис. 2. Схема работы компилятора

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

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

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

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

Каждая инструкция состоит из идентификаторов. Идентификатор может обозначать:

· Инструкцию языка(:=, if, while, for);

· переменную;

· константу (целое или дробное число);

· арифметическую (+, -,*,/) или логическую (and, or, not) операцию;

· подпрограмму (процедуру или функцию);

· отмечать начало (procedure, function) или конец (end) подпрограммы ИЛИ блока (begin, end).

Тип данных

Программа может оперировать данными различных типов: целыми и дробными числами, символами, строками символов, логическими величинами.

Целый тип

Язык Delphi поддерживает семь целых типов данных: shortint, smailint, Longint, Int64, Byte, word и Longword, описание которых приведено в табл. 1.

Таблица 1. Целые типы

Тип	Диапазон	Формат
Shortint	-128-127	8 битов
Smallint	-32 768 - 32 767	16 битов
Longint	-2 147 483 648 - 2 147 483 647	32 бита
Int64	-2 63 - 2 63 - 1	64 бита
Byte	0-255	8 битов, беззнаковый
Word	0-65 535	16 битов, беззнаковый
Longword	0 - 4 294 967 295	32 бита, беззнаковый

Object Pascal поддерживает и наиболее универсальный целый тип - Integer, который Эквивалентен Longint.

Вещественный тип

Язык Delphi поддерживает шесть вещественных типов: Real48, single, Double, Extended, comp, Currency. Типы различаются между собой диапазоном допустимых значений, количеством значащих цифр и количеством байтов, необходимых для хранения данных в памяти компьютера (табл. 2).

Таблица 2. Вещественные (дробные) типы

Тип	Диапазон	Значащих цифр	Байтов
Real48	2.9x 10 -39 -1.7x10 38	11-12
Single	1.5 x 10 -45 -3.4х 10 38	7-8
Double	5.0x10- 324 -1.7x10 308	15-16
Extended	3.6x10- 4951 -1.1 х10 4932	19-20
Comp	2 63 +1 - 2 63 -1	19-20
Currency	-922 337 203 685 477.5808 --922 337 203 685 477.5807	19-20

Язык Delphi поддерживает и наиболее универсальный вещественный тип - Real, который эквивалентен Double.

Символьный тип

Язык Delphi поддерживает два символьных типа: Ansichar и Widechar:

· тип Ansichar - это символы в кодировке ANSI, которым соответствуют числа в диапазоне от 0 до 255;

· тип widechar - это символы в кодировке Unicode, им соответствуют числа от 0 до 65 535.

Object Pascal поддерживает и наиболее универсальный символьный тип - Char, который эквивалентен Ansichar.

Строковый тип

Язык Delphi поддерживает три строковых типа: shortstring, Longstring

· тип shortstring представляет собой статически размещаемые в памяти компьютера строки длиной от 0 до 255 символов;

· тип Longstring представляет собой динамически размещаемые в памяти строки, длина которых ограничена только объемом свободной памяти;

· тип WideString представляет собой динамически размещаемые в памяти строки, длина которых ограничена только объемом свободной памяти. Каждый символ строки типа WideString является Unicode-символом.

В языке Delphi для обозначения строкового типа допускается использование идентификатора string. Тип string эквивалентен типу shortstring.

Логический тип

Логическая величина может принимать одно из двух значений True (истина) или False (ложь). В языке Delphi логические величины относят к типу Boolean.

Переменная

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

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

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

Следует обратить внимание на то, что компилятор языка Delphi не различает прописные и строчные буквы в именах переменных, поэтому имена SUMMA, Summa и summa обозначают одну и ту же переменную.

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

ах2 + bх + с = 0

вполне логично присвоить имена а, b, с, x1 и х2. Другой пример. Если в программе есть переменные, предназначенные для хранения суммы покупки и величины скидки, то этим переменным можно присвоить имена TotalSumm и Discount или ObSumma и Skidka.

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

В общем виде инструкция объявления переменной выглядит так:

· имя - имя переменной;

· тип - тип данных, для хранения которых предназначена переменная.

а: Real; b: Real; i: Integer;

В приведенных примерах объявлены две переменные типа real и одна переменная типа integer.

В тексте программы объявление каждой переменной, как правило, помещают на отдельной строке.

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

а,b,с: Real; x1,x2: Real;

Константы

В языке Delphi существует два вида констант: обычные и именованные.

Обычная константа - это целое или дробное число, строка символов или отдельный символ, логическое значение.

Числовые константы

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

Ниже приведены примеры числовых констант:

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

В табл. 3 приведены примеры чисел, записанных в обычной форме, в алгебраической форме и форме с плавающей точкой.

Таблица 3. Примеры записи дробных чисел

Строковые и символьные константы

Строковые и символьные константы заключаются в кавычки. Ниже приведены примеры строковых констант:

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

Здесь следует обратить внимание на константу " 2.4". Это именно символьная константа, т. е. строка символов, которая изображает число "две целые четыре десятых", а не число 2,4.

Логические константы

Логическое высказывание (выражение) может быть либо истинно, либо ложно. Истине соответствует константа True, значению "ложь" - константа False.

Именованная константа

Именованная константа - это имя (идентификатор), которое в программе используется вместо самой константы.

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

константа = значение;

· константа - имя константы;

· значение - значение константы.

Именованные константы объявляются в программе в разделе объявления констант, который начинается словом const. Ниже приведен пример объявления именованных констант (целой, строковой и дробной).

ОТКРЫТЫЙ УРОК ПО МАТЕМАТИКЕ

«Алгоритм. Программа действий»

2 класс «Школа 2100»

Цели урока: 1. Доказать, что с помощью общего алгоритма, можно выполнять большое количество разных частных заданий; 2. Закрепить умение действовать по алгоритму, выполняя то или иное задание; 3. Закрепить умение различать алгоритмы разных видов: линейный, разветвленный, циклический; 4. На примере доказать присутствие действий по алгоритму в обычной жизни.

Задачи урока: 1. Решение различных видов заданий с помощью алгоритмов действий; 2. Обосновать выбор данного вида алгоритма.

ХОД УРОКА:

Организационный момент – проверка готовности к уроку, настрой на успех.

Проверка домашнего задания – составление алгоритма «Сбор портфеля в школу».

Математическая разминка:

Определить, сколько в числе 534 сотен, десятков и единиц? (В числе 534 – 5 сотен, 53 десятка, 534 единицы). Запишите это число в тетради разными способами.

(534 = 5 сот. 34 ед. = 53 дес. 4 ед. = 534 ед.)

Соберите число по сумме разрядных слагаемых и запишите его.

700 + 30 + 4 = (734) 500 + 6 = (506)

В ряду чисел найдите «лишнее» число и объясните свой выбор.

720, 540, 306, 50, 910, 300.

(Все числа, кроме 50 , - трехзначные; все числа, кроме 306 , - круглые; во всех числах, кроме 300 по одному нулю).

Итак, после небольшой разминки, вы готовы двигаться вперед? Чтобы ваш боевой настрой сохранился до конца урока, наш друг Совушка будет помогать его поддерживать. (Желаю успеха! У вас всё получится!)

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

Что напоминает вам этот совет? Если все действия проговорим по порядку, то что получим? (Алгоритм). А если мы запишем действияи посоветуем кому-нибудь воспользоваться этими записями, то что получим? (Программу действий). В чем отличие алгоритма от программы действий? (Алгоритм – это устный порядок действий, а программа действий – это записанный алгоритм).

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

Какие задачи мы перед собой ставим, чтобы добиться этих целей? (Обратиться к задачам урока).

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

Перейдем к первому заданию:

- вычислить сумму чисел 517 + 76 (593)

По какому алгоритму будем действовать? («Сложение в столбик с переходом через разряд»).

2 – сложить единицы;

3 – записать единицы под единицами и учесть переход через разряд;

4 – сложить десятки с учетом перехода через разряд;

5 – записать десятки под десятками и учесть переход через разряд

6 – сложить сотни с учетом перехода через разряд;

Действуя по общему алгоритму, мы можем вычислить сумму любых чисел. Докажем это. Самостоятельно вычислите сумму чисел 409 и 298 (707).

- вычислить разность чисел 724 – 235 (489)

По какому алгоритму будем действовать? («Вычитание трехзначных чисел с переходом через разряд»).

1 – записать числа столбиком разряд под разрядом;

2 – вычитаем единицы: если можем вычесть, вычитаем и записываем единицы под единицами, если не можем, занимаем 1 десяток и раскладываем его на 10 единиц плюс те единицы, которые уже есть и вычитаем единицы, записываем единицы под единицами;

3 – помним, что занимали 1 десяток, вычитаем десятки: если можем вычесть, вычитаем и записываем десятки под десятками, если не можем, занимаем 1 сотню и раскладываем ее на 10 десятков плюс те десятки, которые уже есть и вычитаем десятки, записываем десятки под десятками;

4 – помним, что занимали 1 сотню, вычитаем сотни и записываем сотни под сотнями; 5 – прочитать полученный результат.

Самостоятельно вычислите разность чисел 961 – 583 (378)

А теперь подтвердите свои умения и выполните сложение и вычитание «сказочных чисел»:

ΨӘ0 + Δ = (ΨӘΔ) Ω00 + ӨΛ = (ΩӨΛ)

ΥφΨ – φΨ = (Υ00) £0§ - £00 = (§)

Какие дополнительные правила помогут вам справиться с этим заданием?

(Если к любому числу прибавить 0, то получим то же самое число; если из любого числа вычесть то же самое число, то получим 0).

Изменился ли алгоритм ваших рассуждений при решении примеров со «сказочными числами»?

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

На доске приведены записи тех алгоритмов, которыми мы сейчас пользовались, но только уже не в устной форме, а в письменной, поэтому эти записи носят какое название? (Программы действий). Как называется такая запись программы действий? (Блок-схема).

Определите какой вид имеет блок-схема алгоритма сложения трехзначных чисел? (Линейный). Что такое линейный алгоритм? (Алгоритм, в котором все действия следуют друг за другом в определенном порядке. В некоторых случаях порядок действий можно изменять). Какой вид имеет блок-схема алгоритма вычитания трехзначных чисел? (Линейный, разветвленный, циклический). Что такое разветвленный алгоритм? (Алгоритм, содержащий условие и выбор действия). Что такое циклический алгоритм? (Алгоритм, в котором есть возврат к предыдущим действиям). Покажите на 2-ой схеме части каждого вида алгоритмов.

Блок-схема 1 алгоритма Блок-схема 2 алгоритма

ФИЗМИНУТКА

Мы встречаемся с алгоритмами не только при решении примеров. Приведите примеры заданий, в которых также удобно использовать алгоритм. (Уравнения). Проверим нашу гипотезу. Что такое гипотеза? (Научное предположение. Если предположение подтвердится, то оно становится правилом или законом. Если не подтвердится, то выдвигаем новую гипотезу).

Решаем уравнение. Что такое уравнение? (Равенство, в котором есть неизвестная величина, переменная). Что значит решить уравнение? (Найти такое значение переменной, при котором наше равенство будет верным).

Х + 241 = 729

Применяем алгоритм.

1 – смотрим на знак, чтобы определить целое и части;

2 – обозначаем целое и части и подписываем компоненты действия;

3 – определяем, чем является неизвестная величина;

4 – выбираем нужное правило;

5 – записываем способ решения;

6 – вычисляем;

7 – записываем результат;

8 – выполняем проверку.

К какому виду относится этот алгоритм? (К линейному). Опираясь на алгоритм, решаем уравнение.

1 слаг. 2 слаг. сумма

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

Но только ли в математике мы можем встретиться с действиями по алгоритму? Я предлагаю вам построить макет школы «Мир интеллекта», для которого нужен особый строительный материал, который отвечал бы строго определенным требованиям.

Соответствие нашего строительного материала необходимо проверять, пользуясь программой действий. (Работа с блоками Дьенеша).

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

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

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

А теперь вернемся к нашим целям и задачам урока. (Проанализировать, добились ли мы каждой цели и выполнили ли поставленные задачи – ИТОГ УРОКА).

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

Домашнее задание: составить алгоритм решения задач.

Спасибо за вашу работу на уроке. Урок окончен.

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

Инструкция

Как правило, вначале алгоритма производится ввод исходных данных для решения поставленной задачи. Нарисуйте параллелограмм ниже линии так, чтобы он непрерывным продолжением схемы. В параллелограмме напишите производимое действие, обычно это операции данных с экрана (Read nInp) или других устройств. Важно, что введенные вами переменных в данном шаге будут использоваться в дальнейшем во всем теле блок-схемы.

Выполнение одной или группы операций, любая обработка данных (изменение значения или формы представления) обозначается в виде прямоугольника. Нарисуйте данную фигуру в нужном месте алгоритма при составлении блок-схемы. Внутри прямоугольника запишите производимые действия , например, операция присваивания записывается следующим образом: mOut = 10*nInp b + 5. Далее также для продолжения блок-схемы нарисуйте линию вниз.

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

Для задания оператора условия нарисуйте от данной линии ромб. Внутри фигуры укажите само условие и проведите линии, указывающие дальнейший переход в зависимости от его выполнения. Условие задается в общем случае операциями сравнения (>, <, =). Переход по линии вниз осуществляется при истинном условии, назад – при ложном. Укажите около выходных линий фигуры результаты условия (true, false). Невыполнение условия (false) возвращает к определенному шагу выше по телу алгоритма. Проведите линии под прямым углом от выхода с условия и до нужного оператора.