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

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

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

Алфавит

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

• Строчные латинские буквы {abcdefghijklmnopqrstuvwxyz}
• Прописные латинские буквы {ABCDEFGHIJKLMNOPQRSTUVWXYZ}
• Арабские цифры {0123456789}
• Специальные символы {, (запятая), ;,. (точка), +, -, *, ^, & (амперсанд), =, ~ (знак отрицания), !, &, /, <, >, (, ), {, }, [, ], |, %, ?, ‘ (апостроф), “ (кавычки), : (двоеточие), _ (знак подчёркивания)}

Из допустимых символов формируются лексемы.

Лексемы

Лексемы – предопределённые константы, идентификаторы, ключевые слова и знаки операций. Идентификаторы – имена, которые даются программным объектам – именованным константам, переменным, типам и функциям. Предопределённые константы определяются директивой препроцессора #define. Введённая константа будет действовать, начиная с момента задания и до конца кода или отмены с помощью директивы препроцессора #undef.

#define имя константы [значение]
    //Действие константы
#undef имя константы

Различают следующие типы констант:

• числовые (целочисленные или вещественные, например, 123, -34, 67.25, -2.459)
• символьные (выделяются знаком апострофа, например, 'Z')
• текстовые строки (выделяются знаком двойных кавычек, например, "first")

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

Стандартом C99 определены следующие ключевые слова:

sizeof, typedef, auto, register, extern, static, char, short, int, long, signed, unsigned, float, double, void, struct, enum, union, do, for, while, if, else, switch, case, default, break, continue, goto, return, inline, _Bool, _Complex, _Imaginary, restrict.

Операция – это функция, которая выполняется над операндами и которая возвращает вычисленное значение – результат выполнения операции.

Операнд – это константа, переменная, выражение или вызов определённой в программе функции.

Пример программы

Приведённый пример программы вначале выведет запрос Input symbol и после ввода символа и нажатия кнопки Enter выведет надписи Good и Code symbol, а также через пробел символ и через знак - код символа.

1
2
3
4
5
6
7
8
9
10
11
// Здесь может быть любой текст (комментарий)
#include 
#define out std::cout <<
int main() {
    std::cout << "Input symbol" << std::endl;
    char ch; // Объявление переменной
    std::cin >> ch;
    std::cout << "Good" << std::endl;
    out "Code symbol " << ch << '-' << ch+0 << std::endl;
    return 0;
}

В первой строке текста программы – однострочный комментарий. Такой комментарий всегда начинается парой символов // и заканчивается символом конца строки. Обратите внимание и на шестую строчку текста программы char ch; // Объявление переменной, эта строчка также содержит однострочный комментарий.

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

Во второй строчке кода помещена директива препроцессора #include служащая целью подключения библиотеки iostream, которая содержит необходимые команды для работы со стандартными потоками ввода и вывода. Для лёгкого запоминания названия библиотеки раскроем аббревиатуру (мнемоника): i (input) – ввод, o (output) – вывод, stream – поток.

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

Третья строка содержит директиву препроцессора #define, о которой было уже сказано выше по тексту. Она определяет новую переменную out, после чего препроцессор встретив в тексте программы отдельно стоящую надпись out подменит её текстом std::cout <<.

Четвёртая строка содержит объявление функции int main(). Данное объявление указывает, что данная функция не принимает каких-либо данных (аргументов), так как содержимое скобок пусто, а так же объявление показывает, что данная функция возвращает целое число int.

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

Математическая логика

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

Под высказыванием будем понимать такое выражение (высказывание), относительно которого можно с той или иной вероятностью ответить «Да» («Истина») или «Нет» («Ложь»).

Например, «Сегодня хорошая погода» – простое высказывание (в некоторых источниках такая фраза не будет считаться логическим высказыванием, так как понятие «хорошая» не однозначно). Так же будем и такое выражение считать логическим «Сегодня хорошая погода?», да это выражение в вопросительной форме и так же во многих литературных источниках не является логическим, однако на него можно ответить «Да» или «Нет» и в данном изложении будем считать его логическим высказыванием.

А вот выражение: «Сколько тебе лет?» не является логическим высказыванием, так как ответ на него не подразумевает допустимых здесь ответов («Да», «Нет»).

Приведём пример сложного высказывания: «Человек знает язык программирования или английский язык». Если человек знает язык программирования, то данное выражение следует считать истинным, если человек знает английский язык, так же следует считать данное выражение истинным. А что если человек знает язык программирования и английский язык, с точки зрения русского языка возникает неоднозначность, возможно, следует дать положительный, а возможно и отрицательный ответ.

Покажем другой пример, не отрывая его из контекста: «Объект за совершение поступка А или за совершение поступка Б наказывается наказанием 1 или наказанием 2». В рамках данного изложения в первом упоминании «Или» оно имеет смысл, как по отдельности, так и одновременно, то есть если совершено оба поступка, то это не освобождает от наказания. А вот второе «Или» наоборот имеет смысл в том, что выбирается либо одно, либо другое, но не оба одновременно.

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

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

Логические связки

Отрицание - унарная операция над суждениями, результатом которой является суждение «противоположное» исходному.

В языках программирования C/C++ используется знак !.

Например, a = !(c > b).

Таблица истинности:

Конъюнкция — логическая операция, по своему применению максимально приближенная к союзу «и» в русском языке. Синонимы: логическое «И», логическое умножение, иногда просто «И».

Таблица истинности:

Дизъюнкция — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу. Синонимы: логическое сложение, логическое «ИЛИ», включающее «ИЛИ»; иногда просто «ИЛИ».

Таблица истинности:

Теория множеств

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

Примеры множеств и их описаний:

{2,3,4,5} - множество целых положительных чисел от 2 до 5 включительно.

{x : x>1 & x<6}

Теория графов

Теория графов — раздел дискретной математики, изучающий свойства графов.

Граф - пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V. V - называют вершинами, узлами или точками E - называют рёбрами или дугами

Структуры данных и алгоритмы

Стек

Стек (англ. stack — стопка, кипа, навал) — структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. Last In — First Out, «последним пришёл — первым вышел»).

Над данной структурой необходимо реализовать 3 операции:

• push(object) - поместить object в стек
• pop() - взять object из стека
• empty() - проверить, пуст ли стек

Реализация на массиве (в примере с int):

int st[1000]; // До 1000 элементов
int ind = 0; // Стек пуст
st[ind++] = 3; // Положили на вершину стека 3
st[ind++] = 7; // Положили на вершину стека 7
st[ind++] = 2; // Положили на вершину стека 2
int b = st[--ind]; // b = 2, стек теперь содержит 7 и 3
b = st[--ind]; // b = 7, в стеке только один элемент - 3

Заметьте, ind равен количеству элементов в стеке, поэтому его проверка на равенство нулю и есть проверка на пустоту. В массиве по окончанию работы программы st[1] = 7, st[2] = 2, то есть записанные числа не стёрты из памяти, но ind указывает на 1 - первую свободную ячейку для записи. При следующей записи в стек ячейка с номером ind будет переписана новым значением.

Очередь

Очередь — структура данных, представляющая собой список элементов, организованных по принципу FIFO (англ. First In — First Out, «первым пришёл — первым вышел»).

Над данной структурой необходимо реализовать 3 операции:

• push(object) - поместить object в очередь
• front() - взять object из очереди
• empty() - проверить, пуст ли стек

Реализация на массиве (в примере с int):

int qu[1000]; // До 1000 элементов
int fr = 0; // Фронт очереди
int ba = 0; // Конец очереди
qu[fr++] = 3; // Положили 3 в очередь
qu[fr++] = 7; // Положили 7 в очередь
qu[fr++] = 2; // Положили 2 в очередь
int b = qu[ba++]; // b = 3, очередь теперь содержит 7 и 2
b = qu[ba++]; // b = 7, в очереди только один элемент - 2

Чтобы проверить, пуста ли очередь, достаточно сравнить fr и ba, если они равны, то очередь пуста. Если заранее известно, что размер очереди не превысит некоторого количества N, то массива размером в N вполне достаточно. Когда fr и br увеличиваются на единицу, необходимо проверить не стали ли они указывать на элемент N и если да, то обнулить.

Пример:

#define N 1000
int qu[N];
qu[fr++] = 9;
if(fr == N)
    fr = 0;