Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Kostin_1sem_Zachyot_Otvety.pdf
Скачиваний:
4
Добавлен:
16.04.2015
Размер:
280.45 Кб
Скачать

© Vogal, Green, NSG inc. 2009

[WARNING!!! Это не окончательная версия ответов, она претерпит изменения (возможно довольно значительные) в самое ближайшее время. Предложения по улучшению ответов принимаются по адресу vogal.mv@gmail.com. Спасибо за использование наших мозгов ;)]

Билет №1

Единого «истинного» определения понятия «алгоритм» нет.

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

Свойства алгоритма в интуитивном смысле

1.Алгоритм – некоторое предписание, ориентированное на предметную область

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

Иными словами, алгоритм на этапы являющиеся однозначными.

3.Конечность – выполнение алгоритма приводит к некоторому результату за конечное число шагов.

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

Тезис Чёрча:

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

Тезис Черча не является аксиомой, так как понятия «интуитивное определение алгоритма» не существует. Тезис Черча не является теоремой, так как второе предполагается, а не доказывается.

Примеры классических определений:

Алгоритм — это любая программа на Паскале. /Определение ,так как удовлетворяет свойствам алгоритмов./ Алгоритм — это любая программа на Basic.

Алгоритм — это любая программа для машины Тьюринга Алгоритм — это любая программа на …

Билет №2

Язык программирования — формальная знаковая система, предназначенная для записи программ, задающих алгоритм в форме, понятной для исполнителя (например, компьютера).

Синтаксис – описывает структуру программ как наборов символов. (Правила построения языка). Каждый язык программирования имеет синтаксическое описание. Обычно синтаксис языка определяют посредством правил Бэкуса-Наура.

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

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

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

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

© Vogal, Green, NSG inc. 2009

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

Используя металингвистические формулы Бэкуса-Наура, определим понятие имя в языке программирования Паскаль. В этом языке имя – это последовательность букв, цифр и знаков подчеркивания, которая начинается с буквы. В качестве букв используются буквы латинского алфавита, цифрами являются арабские цифры.

<буква>::=A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

<цифра>::=0|1|2|3|4|5|6|7|8|9

<идентификатор>::=<буква>|< идентификатор ><буква>|< идентификатор><цифра>|< идентификатор >_

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

Прагматика – определяет область ориентации языка. Существует несколько видов языков: 1) Эталонный язык – тот, что соответствует формальному описанию 2) Язык реализации – язык, представленный на машине

3) Язык публикации – вариация языка, предназначенная для публикации

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

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

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

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

4. Отладка.

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

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

7. Сопровождение программы.

Билет №3

Основные понятия языка Pascal

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

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

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

(Значения как представители типа).

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

В языке Паскаль 4 стандартных типа:

Целый(Integer)

Вещественный(Real)

Логический(Boolean)

Литерный(Char)

На основании этих стандартных типов и нестандартного абстрактного перечисляемого типа (в этом типе значения задаются именами) строится огромное многообразие новых типов данных.

Константа в программировании — это способ адресования к данным, изменение которых рассматриваемой программой запрещено.

Константа – это неизменяемая в процессе выполнения программы величина, своим изображением однозначно определяющая тип данных и значение

©Vogal, Green, NSG inc. 2009

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

<идентификатор>::=<буква>|<идентификатор><буква>| <идентификатор><цифра> | <идентификатор>_

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

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

Переменная в программе представлена именем и служит для обращения к данным определенного типа. Конкретное значение переменной хранится в ячейках оперативной памяти).

Выражения - это вычисляемые конструкции языка. Конструкции получения новых значений из старых.

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

Арифметические выражения;

Выражения отношения;

Логические выражения.

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

Состав выражения В общем случае в выражение могут входить:

константы (задаются своим изображением); переменные (задаются именами);

вызовы функций (представляют собой следующую конструкцию <имя функции>[(список аргументов, перечисленных через запятую)];

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

Процедура — Это подпрограмма, описанная в тексте программы, вызываемая в программе. Состоит из описания и вызова.

Фу́нкция— процедура, использующаяся в выражении .

Оператор (Инструкция) — наименьшая автономная часть языка программирования; команда.

Программа обычно представляет собой последовательность операторов.

Примеры:

- оператор присваивания; - оператор вызова процедуры (функции); - условный оператор; - оператор цикла; - составной оператор;

- пустой оператор, etc.

© Vogal, Green, NSG inc. 2009

Комментарии:

Статические – с постоянными ресурсами памяти для хранения этого типа.

Динамические – с изменяющимися ресурсами памяти для хранения этого типа.

Стандартные – заданы по умолчанию.

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

Структурированные – группирование ранее описанных типов в один структурированный.

Билет №4

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

Стандартный тип данных – заданный по умолчанию (boolean, integer, real, char).

Характеристики:

1. Изображение – запись на языке математики.

2. Представление – как объекты типа представляются в машине.

Изображение: false(0), true(1) =1бит. Представление: 1 байт.

Тип Boolean.

Операции:

1.Унарные: not<a>

a

T

F

¬a

F

T

© Vogal, Green, NSG inc. 2009

 

 

 

 

2.Бинарные:

a and b

 

 

a xor b

 

a or b

 

 

a

F

T

 

 

 

F

T

 

 

 

 

a

b

 

 

 

 

 

 

 

 

 

 

b

 

 

F

F

T

 

 

 

 

 

 

F

F

T

T

T

T

 

 

 

 

T

T

F

 

 

 

F

T

 

 

a

 

 

 

 

 

 

 

 

 

 

 

 

b

F

F

 

 

 

 

 

F

 

 

 

 

 

T

F

T

 

 

 

false<true – операция упорядоченности.

Приоритет: NOT>AND>OR.

Тип Integer.

Изображение: 3, 10, +5, -28.. Диапазон: (-215+1; 215) Представление: 2 байта. Операции:

унарные:

-a - смена знака;

+a - сопряжение знака;

бинарные: Аддитивные:o

a+b – сложение a-b – вычитание

o Мультипликативные:

a*b – умножение

a mod b – вычисление остатка от деления a div b - целочисленное деление

a/b – деление

o Операции сравнения

<, >, <=, >=, =, <>

o Побитовые логические операции

AND, OR, XOR, NOT, <<, >> (сдвиг)

Изображение:

Тип Real.

с плавающей точкой

7.32E+00, где 7.32E – мантисса, 00 – порядок, 4.56721E+02, 1.5E+02 {E – обозначение возведения в степень}

с фиксированной точкой 7.32, 456.721, 0.015

Диапазон: (2.9E-39..1.7E+38) Представление: 6 байт. Операции:

арифметические: +, -, *, /;

отношения: <, <=, =, >, >=, <>

Тип Real является неперечислимым.(обладает свойством плотности) Тип Char.(литерный)

Значение: любой символ из таблицы ASCII.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]