Отправляет email-рассылки с помощью сервиса Sendsay

Курс лекций СПбГУАП - информатика

Рассылка закрыта

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Ноябрь 2001   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор Гость

Статистика

103 подписчиков
за неделю
←   Все выпуски   →

Курс лекций СПбГУАП - информатика #6


Служба Рассылок Subscribe.Ru 
Количество подписчиков: 111

+++++++++++++++++++++++++++++++++++++++++++++++++++

==============Объявления============================

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

==============Лекция================================

Алгоритмы и их свойства.

Любая программа - это алгоритм, реализованный на машинном языке. В процессе разработки
программы, алгоритм записывается на разных языках.

Язык человека -> алгоритмический язык -> язык программы -> машинный язык.

Преобразование "язык программы -> машинный язык" выполняет ЭВМ, остальные - человек.

Алгоритмический язык - язык для записи алгоритмов.
Язык программирования -система команд конкретной ЭВМ.

   Не существует определенного понятия - алгоритмов, как не существует определения
понятия
   точки в геометрии.
Алгоритм должен удовлетворять следующим свойствам:
1) Дискретность - алгоритм состоит из отдельных шагов или команд.
2) Детерминированность - строгая однозначная определенность. Для алгоритма это
означает:
а) Исполнитель алгоритма точно однозначно определенно знает, как выполнить текущий
шаг
алгоритма.
б) Исполнитель алгоритма, выполнив текущий шаг, точно однозначно определенно
знает, какой шаг
выполнить следующим.
в) Исполнитель алгоритма не знает и не понимает, что делает алгоритм в целом.
3) Результативность - любой алгоритм при исполнении должен давать результат.
Ответ "решений
нет" тоже является результатом.
4) Конечность - алгоритм должен выполняться за конечное число шагов.
5) Массивность - алгоритм должен быть справедлив для любого набора исходных данных
из области
определения.
Способы записи алгоритмов.
1) Схемы алгоритма - графические изображения алгоритмов с помощью стандартных
элементов.
Основные стандартные элементы
Каждый элемент имеет строго определенное обозначение и назначение. У каждого
элемента
определено количество входов и выходов (связи с другими элементами). Как правило,
каждый элемент
имеет один или более входов и обычно один выход.

Начало и конец алгоритма:
 ------
(начало)
 ------
    |
   v

    |
    v
 ------
(конец )
 ------

Действия по формированию значения в процессе исполнения:
    |
    v
--------
|      |
--------
    |
    v
            процесс

    |
    v
--------
||     ||
--------
    |
    v
          предопределенный процесс:
Вызов на исполнение отдельно существующего вспомогательного алгоритма.

Для выбора пути по алгоритму
       |
       v
       /\
      /  \
     /    \
 да /усл-е \ нет
 ---\      /----
 |   \    /    |
 |    \  /     |
 v     \/      v

Для разрыва линий связи
----     |
|  |     v
|  |     /\
\  /    /  \
 \/     |  |
 |      |  |
 v      ----

для обмена информацией между человеком и ЭВМ
    |
    v
  --------
 /      /
--------
    |
    v

2) Алгоритмические языки. Существует огромное количество языков. Мы буде изучать
язык Паскаль,
так как он специально создан для записи алгоритмов и обучению программированию.
Способы определения языков.
Существует огромное количество различных способов, наиболее распространенным
являются 2:
1) Синтаксические диаграммы - графические определители конструкции языка. Это
не схемы
алгоритма!
---\
|Н  >
---/
начало определения

 /---
< К |
 \---
конец определения

---------
|понятие|
---------
строго определенное понятие

 -------
(понятие)
 -------
определенное программистом понятие

Пример:
Определение понятия Имя:
Имя - последовательность букв, цифр и знаков подчеркивания, начинающиеся с буквы.
---\    -----                  /---
|Н  >--(буква)----o----------><  К|
---/    -----   ^ |            \---
                | |   -----
                | o--(буква)->|
                | |   -----   |
                | |           |
                | |   -----   |
                | o--(цифра)->|
                | |   -----   |
                | |           |
                | |   -----   |
                | o---| _ |-->|
                |     -----   |
                |             |
                |-------------|

2) Металингвистические формулы
Бэкуса-Наура (в литературе БНФ)
Лингвистика - наука о языках
::= (два двоеточия и равно) - по определению
<понятие> - определенное программистом понятие.
| - связка или (лог.)
[  ] - необязательная часть определения.

Понятие Имя:
<имя>::=<буква>|<имя><буква>|<имя><цифра>|<имя>
Такая формула является рекурсивной.
Рекурсия - определение самого через себя.


====================================================

Адрес автора рассылки: playnet@mailru.com

+++++++++++++++++++++++++++++++++++++++++++++++++++
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное