Информатика

010503 –

«Математическое обеспечение и администрирование информационных систем»

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

Литература:

1. Никлаус Вирт. Алгоритмы и структуры данных.

2. Томас Кормен, Чарльз Лейверсон, Рональд Ривест. Алгоритмы: построение и анализ.

3. Дональд Эрвин Кнут. Искусство программирования для ЭВМ (The Art of Computer Programming).

Биографии математиков и программистов (автор сайта – Шелест Наталья):

http://gumnaziya.narod.ru/web06/natasha/html/list38.htm

Дональд Эрвин Кнут = Сеймур Роджер Крей (фотографии)

Дональд Е. Кнут (Donald Ervin Knuth) – почётный профессор Стенфордского университета, автор редактора или, скорее, системы компьютерной вёрстки TeX.

Главное дело жизни Кнута – его фундаментальная энциклопедия алгоритмов «Искусство программирования для ЭВМ (The Art of Computer Programming)». Двадцать лет назад Кнут прекратил активную преподавательскую деятельность и полностью посвятил себя работе над этой книгой.

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

1954: Фортран (FORTRAN от FORmula TRANslator – транслятор, или переводчик формул), IВМ. Руководитель группы разработчиков – Джон Бэкус.

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

Потомки: Planner (1967), Scheme (1975), Common Lisp (1984).

1960: Algol-60. Руководитель команды разработчиков – Петер Наур (Peter Naur).

1960: Cobol.

1964: Basic. Авторы - профессора из Dartmouth College – Джон Кенеми и Томас Куртц.

1991: Visual Basic.

1965: РЕФАЛ (Турчин, МГУ)

1967: PL/1 (IBM).

1968: Algol-68. Руководитель – Петер Наур

1970: Pascal. Никлаус Вирт.

1978: Modula-2 (1978). 1988: Modula-3

Oberon и Oberon-2. ООП.

1972: “C”. Керниган, Денис Ритчи. ОС UNIX.

1971: Prolog.

1983: ADA (Ада Лавлейс). Дж. Ишбиа.

1983: C++. Бьярн Страуструп.

1995: Java. Кен Арнольд и Джеймс Гослинг (Sun Microsystems). Java Virtual Machine.

1995: JavaScript (Mocha, LiveScript). Netscape Communications.

1999: C#. Андерс Хейльсберг (MicroSoft).

VBScript. MicroSoft.

В начале 70-х годов в связи с разработкой все более сложных программных систем наиболее известные специалисты-практики в области программотехники пришли к выводу о необходимости установления строгого и формального порядка в разработке программ. В 1972 г. Дейкстра утверждал, что «программы должны с самого начала правильно составляться, а не просто отлаживаться до тех пор, пока они не станут правильными».

Ситуация, получившая название кризиса в программировании, была обусловлена тем, что стало трудно проектировать, писать, тестировать и особенно понимать и сопровождать сложные программные комплексы. Для преодоления возникших трудностей необходимо было создать технологию разработки программ. Под влиянием работ Вирта, Дейкстры, Йодана, Хоара и многих других в 70-е годы постепенно создавалась методология, получившая название структурного программирования. Это понятие впервые ввел Дейкстра в 1970 г., и оно вначале касалось только формы программы и процесса ее кодирования. Был принят ряд соглашений, которым должен следовать программист, создавая структурную программу. Эти правила касаются следующих моментов:

1. Полное или частичное исключение операторов GO TO.

2. Программирование только с использованием трех базовых структур: «Следование», «Развилка», «Цикл».

3. Применение соглашений структурного кодирования при написании программ на конкретном языке программирования.

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

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

Языковые конструкции, составляющие текст программного кода:

1. Функциональный блок (структура «Следование»)

2. Конструкция двоичного разветвления (структура «Развилка»)

3. Итерация (структура «Цикл»)

Три группы правил (как для разговорных языков, так и для языков программирования)

1. Синтактика (правила построения сообщений)

2. Семантика (правила придания сообщениям смысла)

3. Прагматика (правила использования сообщений)

Примеры семантических ошибок языка:

“C”:

if (3 < 2 < 1) printf(“True!”); else printf(“False!”); // Будет выведено: True!

“Visual Basic”:

If 3 < 2 < 1 Then MsgBox "Yes" Else MsgBox "No" ‘ Будет выведено: Yes!

Выражение «3 < 2 < 1» воспринимается компьютером, как ИСТИНА.

Человек вправе считать, что «3 < 2 < 1» есть ЛОЖЬ.

“Visual Basic”:

x = "1" + "2" : MsgBox x ‘ Будет выведено: 12

x = 1 + "2" : MsgBox x ‘ Будет выведено: 3

x = 1 & "2" : MsgBox x ‘ Будет выведено: 12

В первой и в третьей строках всё ясно: требуется сцепить символы "1" и "2".

Выражение во второй строке неоднозначно. Один программист может считать, что первое слагаемое-число должно быть преобразовано в символ, после чего следует сцепить символы "1" и "2". Другой программист с равными основаниями может ожидать, что второе слагаемое-символ должно быть преобразовано в число, после чего должна быть найдена сумма двух чисел. VB принимает точку зрения второго программиста, что нельзя считать бесспорно верным.

Причина неоднозначности: опрометчивое дозволение (авторами языка Basic) знака «плюс» и для сложения чисел, и для сцепления строк.

Никлаус Вирт

В середине 1960-х годов Международная федерация по обработке информации — IFIP (International Federation for Information Processing) предложила нескольким специалистам в области информатики принять участие в создании нового языка программирования — преемника Алгола-60. Среди них был швейцарский ученый Никлаус Вирт (р. в 1934 году), который преподавал в то время в Станфордском университете. Проект Вирта отклонили, но, возвратившись в Швейцарию, он продолжил работу. Вскоре Никлаус Вирт и его сотрудники из Федерального технического университета в Цюрихе подготовили первую версию языка, получившего название Паскаль (в честь Блеза Паскаля), затем — первый вариант компилятора; в 1971 году вышло описание языка. В 1974 году появилась новая версия Паскаля, и спустя еще какое-то время было опубликовано руководство для пользователей, которое, по словам Вирта, вполне можно рассматривать как "стандартное определение" языка Паскаль.

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

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

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

Всякий язык имеет четыре уровня языковых конструкций (в порядке вложенности)

№ уровня	Разговорный язык	Язык программирования
1	Буквы	Символы
2	Слова	Элементарные конструкции
3	Словосочетания	Выражения
4	Предложения	Операторы

Далее всюду будут обсуждаться конструкции языка Pascal (синтаксис Delphi) – базового языка изучения алгоритмизации и программирования на математико-механическом факультете.

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

“C++” – язык, зависящий от регистра. SIN(X) и sin(x) – разные вещи.

Везде, где возможно, будут кратко названы отличительные особенности языка “C++”.

1. Символы языка – символы с кодами 32 . . 127. Символы с кодами 128 . . 255 (в том числе и русские буквы) разрешаются только тогда, когда об этом специально сказано.

2. Элементарные конструкции – это имена, числа и строки.

2.1. Имена

x

y1

MyProc1

2.2. Числа

2

-32768

1.4

2.345e-301

2.3. Строки (строковые константы)

‘a’, ‘ABC’, ‘Оператор’ …

Замечание. В языке «C++»:

а) строки ставятся в кавычки, а не в апострофы:

“ a”, “ABC”, “Оператор”, …

б) дополнительная конструкция языка – «Символ» – выглядит, как строка, состоящая из одного символа в языке Pascal:

‘a’, ‘C’, ‘$’ , …

В языке Pascal нет разницы между понятиями «Символ» и «Строка, состоящая из одного символа».

Однако, есть разница между символьными переменными и строковыми переменными длиной в 1 символ.

3. Выражения – конструкции языка, задающие порядок вычисления какого-либо значения.

sin((alpha – beta) / 2)

1 + 1 / (2 + 3 / (4 + 5 / (6 + 7 / x)))

‘AB’ + ‘CDE’
x = y	(В языке “C++”: x = = y )

4. Операторы – минимальные конструкции языка, порождающие какие-либо действия компьютера.

Операторы бывают простые и структурированные.

Простые операторы:

4.1. Оператор присваивания

x := y + z

(В языке “C++”: x = y + z )

4.2. Оператор вызова процедуры

ReadKey

(В языке “C++”: getch() )

4.3. Оператор перехода на метку

goto M1 GoTo M1

(В языке “C++”: goto M1 )

…

M1:

4.4. Пустой оператор

;

Структурированные операторы:

1. Составной оператор (блок?)

2. Условный оператор

3. Оператор цикла

Переменная – поименованная область данных в оперативной памяти.

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

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

(В языке “C++” понятие порядкового типа не используется)

К порядковым типам относятся:

1. Базовые целочисленные

Тип переменной	Диапазон значений	Объём памяти
Integer	–2147483648..2147483647	4
Cardinal	0..4294967295	4

2. Дополнительные целочисленные

Тип переменной	Диапазон значений	Объём памяти
Shortint	–128..127	1
Smallint	–32768..32767	2
Longint	–2147483648..2147483647	4
Int64	–2^63..2^63–1	8
Byte	0..255	1
Word	0..65535	2
Longword	0..4294967295	4

3. Символьные

Тип переменной	Диапазон значений	Объём памяти
Char	Chr(0)..Chr(255)	1

4. Прочие, о которых позже будет специально сообщено, как о порядковых типах (перечисляемые, тип-диапазон, …)

Остальные типы переменных порядковыми не являются.

Числовые вещественные типы

Тип переменной	Диапазон значений	Число знаков	Объём памяти
Real48	2.9*10–39 .. 1.7*1038	11–12	6
Single	1.5*10–45 .. 3.4*1038	7–8	4
Double	5.0*10–324 .. 1.7*10308	15–16	8
Extended	3.6*10–4951 .. 1.1*104932	19–20	10
Comp	–263+1 .. 263 –1	19–20	8
Currency	-22337203685477.5808.. 922337203685477.5807	19–20	8

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

Тип переменной	Длина	Диапазон значений	Объём памяти
String	1..255	—	2..256
String[<Число>]	1.. <Число>	1≤<Число>≤255	<Число>+1
AnsiString	231		4B..2GB
WideString	230		4B..2GB

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

Тип переменной	Множество значений	Объём памяти
Boolean	False (0), True (1)	4

Все переменные, используемые в программе, написанной на языке Pascal (и на языке “C++”), должны быть объявлены (описаны).

Существуют языки программирования, в которых описание переменных является делом необязательным (Fortran, Basic) или даже делом невозможным (Cliper).

Структура простейшей (состоящей из одного файла) программы на языке Pascal:

[ Program <Имя>;]

[<Ключи компиляции> ]

[uses <Список используемых устройств (модулей)>; ]

<Разделы объявления (описания) переменных, констант, типов, меток>

<Раздел объявления (описания) процедур и функций>

<Раздел исполнения>

Структура модуля на языке Pascal (Delphi):

unit <Имя>;