Лекции по основам программирования

 

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ 
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 
Институт прикладной математики 
и компьютерных наук 
 
 
 
 
 
 
 
 

Ю. Л. Костюк 

 
ЛЕКЦИИ ПО ОСНОВАМ 
ПРОГРАММИРОВАНИЯ 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
Томск 
Издательский Дом Томского государственного университета 
2019

 

УДК 510.5 
ББК 22.18.73 
         К72 
Рецензенты: 
А. М. Кориков, заведующий кафедрой автоматизированных систем управления  
Томского государственного университета систем управления и радиоэлектроники,  
доктор технических наук, профессор; 
А. Ю. Матросова, профессор кафедры программирования Томского государственного 
университета, доктор технических наук  
 
Костюк Ю. Л.  
К72 
Лекции по основам программирования : учеб. пособие. –  
 
Томск : Издательский Дом Томского осударственного  
университета, 2019. – 260 с. 

ISBN 978-5-94621-827-6 
 
Учебное пособие соответствует программе начального курса по программированию для вузовских специальностей, ориентированных на подготовку специалистов в области информатики и компьютерных технологий. В книге излагаются методы тестирования, исследования трудоёмкости и доказательства 
свойств алгоритмов. Приводятся и исследуются простые алгоритмы из важнейших классов: вычисление рекуррентных последовательностей; сортировка и поиск; рекурсивные вычисления, алгоритмы с множествами и графами, а также 
простые алгоритмы линейной алгебры. Особое внимание уделено анализу эффективности алгоритмов. В первой части лекций алгоритмы и программы записываются на языке Паскаль, а во второй части – на Си. Кратко описываются 
также основные элементы этих языков. Презентации лекций размещены в Электронной библиотеке (репозитории) Томского государственного университета 
(http://sun.tsu.ru/mminfo/2019/Kostyuk_presentations/Kostyuk_presentations.rar). 
Пособие является лишь первым шагом к более обстоятельному и подробному изучению всего многообразия алгоритмов. 
Для студентов соответствующих специальностей, а также специалистов и 
преподавателей информатики, желающих начать систематическое изучение 
программирования.  
УДК 510.5 
ББК 22.18.73 
 
 
 
ISBN 978-5-94621-827-6 
 
© Костюк Ю. Л., 2019 
© Томский государственный университет, 2019 

 

Предисловие 

Самым главным в профессии программиста является умение создавать 
хорошие программы. Все же остальное (знание языка программирования, 
транслятора, операционной системы, умение быстро работать за компьютером) необходимо лишь постольку, поскольку помогает писать хорошие 
алгоритмы и тем самым разрабатывать хорошие программы. 
К сожалению, большинство учебников по программированию мало 
внимания уделяет алгоритмизации – науке об алгоритмах. В этой книге не 
только рассматриваются и исследуются важнейшие классы простых алгоритмов, но и излагаются методы тестирования и доказательства свойств 
программ. Книга состоит из лекций, читавшихся для студентов первого 
курса института прикладной математики и компьютерных наук ТГУ. Параллельно с лекциями должны выполняться практические занятия по 
написанию и выполнению программ на компьютере. 
Для успешного освоения начального университетского курса программирования необходимы предварительные знания по математике и информатике в объеме средней школы. Весьма желательным является не простое 
знакомство с каким-либо языком программирования, а умение записывать 
на этом языке программы для решения простых задач и владение навыками отладки таких программ на компьютере. В книге используются языки 
Паскаль и Си, точнее их базовые подмножества, достаточные для написания большинства алгоритмов. В них входят такие основные элементы языков, как: 
1) целые, вещественные символьные и логические типы данных; 
2) одно- и двумерные массивы, символьные строки, списочные структуры; 
3) присваивания, выражения, арифметические и логические операции; 
4) условные операторы if и case (switch), операции сравнения; 
5) циклы while и for; 
6) процедуры и функции, их описание, вызов, подстановка параметров; 
7) стандартные процедуры и функции. 
В первой части лекций программы записываются на языке Паскаль, а 
во второй части лекций – на Си. Кратко описываются также те элементы 

Предисловие 

 

языков, которые далее используются в программах. При этом совершенно 
не рассматриваются объектно-ориентированные средства языков, которые 
необходимы лишь при создании больших и сложных программ, и которые 
только мешают на начальном этапе изучения программирования. 
Когда требуется учитывать особенности конкретного варианта языка 
Паскаль, алгоритмы излагаются в расчете на трансляторы Turbo Pascal®  
или Delphi®  фирмы Borland, или свободно распространяемые трансляторы 
Free Pascal или Lazarus. В отличие от языка Паскаль, язык Си (а также 
Си++) более строго стандартизован, поэтому для реализации на компьютере рассматриваемых программ можно использовать любой из доступных 
трансляторов. 
Каждая лекция сопровождается контрольными вопросами и заданиями 
для самостоятельной работы. Задания рекомендуется читателю реализовать на компьютере, разработать для них тесты и провести тестирование. 

Пройдя 
по 
ссылке 
http://sun.tsu.ru/mminfo/2019/Kos
tyuk_presentations/Kostyuk_presentations.rar можно скачать 
архивный файл с презентациями лекций. В каждом из 16 файлов архива 
содержится презентация, помогающая закрепить материал соответствующей лекции. 
Отзывы, замечания и предложения по книге просьба присылать по адресу: 
634050, г. Томск, пр. Ленина, 36, ТГУ, институт прикладной математики и компьютерных наук. 
E-mail: kostyuk▬y▬l@sibmail.com 

 

Лекция 1. 
Алгоритмы и программы. Тестирование. 
Аналитическая верификация 

1.1. Алгоритмы и программы 

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

 
Рис. 1.1 

С понятием алгоритма связаны его основные свойства:  
1) массовость – способность алгоритма решить любую задачу из заданного множества задач; 
2) завершимость – способность алгоритма останавливаться после получения решения задачи; 

Лекция 1 

 

3) наличие внутренней структуры, понимаемой как совокупность отдельных правил (действий) и порядок их выполнения; 
4) существование исполнителя, который понимает все отдельные действия в алгоритме и реализует их в таком порядке, как предписано структурой алгоритма. 
Свойство массовости означает, что на вход алгоритма могут поступать 
любые варианты входных данных, принадлежащие некоторому множеству, 
и для любого варианта алгоритм способен получить соответствующий им 
результат – вариант выходных данных. Именно благодаря свойству массовости однажды созданный алгоритм остается необходимым, пока существует потребность в решении этого класса задач для различных входных 
данных. 
Если исполнителем алгоритма является человек, то алгоритм может 
быть задан не очень строго и даже не совсем полно: человек может домыслить то, чего недостает в его описании. Если же исполнителем является 
автоматическое устройство, например компьютер, то алгоритм должен 
быть определен абсолютно точно – машина не может догадаться, что подразумевал человек при записи алгоритма, если он что-то опустил. Алгоритмы можно определять и записывать многими способами, в частности 
используя естественный (русский или английский) язык. Однако такую 
запись трудно сделать однозначно понимаемой для человека и практически невозможно – для компьютера. Поэтому для записи алгоритмов изобретены искусственные языки программирования, в которых все действия 
определяются абсолютно полно и однозначно. 
Так как компьютер понимает только свой внутренний (машинный) 
язык, то алгоритм должен быть записан на машинном языке (тогда его 
называют машинной программой). Создание машинной программы – 
сложная и кропотливая работа, так как команды машинного языка выполняют простые действия и кодируются числами. Поэтому для реализации 
даже простого алгоритма потребуется машинная программа большого размера. Изобретение в конце 1950-х годов языков программирования наконец-то избавило программистов от копания в машинных командах и привело к настоящей революции в программировании.  
Современные языки программирования сочетают строгость и абсолютную однозначность с понятностью для человека. Их практическое 
применение стало возможным лишь тогда, когда были созданы специальные программы-трансляторы, выполняющие перевод алгоритмов, напи

Алгоритмы и программы. Тестирование. Аналитическая верификация                          7 

 

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

 

Рис. 1.2 

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

Лекция 1 

 

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

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

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

Алгоритмы и программы. Тестирование. Аналитическая верификация                          9 

 

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

Пример 1.1. Программа вычисления суммы двух чисел. 

program ex1;         {имя программы} 
  var a,b,c: integer;{описание переменных} 
begin                {начало программы} 
  read(a,b);         {ввод переменных a,b} 
  c := a + b;        {сложение a,b и присваивание c} 
  writeln(’c=’,c);   {вывод надписи и результата с} 
end.                 {конец программы} 

В языке Паскаль при записи программы используются зарезервированные служебные слова. В первой строке – слово «program», затем – имя 
программы. Во второй строке – описание переменных, начинающееся со 
слова «var». Тип этих переменных – целочисленный (integer), они могут 
иметь значение от  –2147483648 до +2147483647, они занимают в памяти 4 
байта. В фигурных скобках записаны комментарии, не влияющие на 
трансляцию программы. После слова «begin» записываются операторы 
программы, они выполняют следующие действия: 
1) оператор read требует ввода (с клавиатуры) числового значения 
для переменных а и b с пробелом между ними, а в конце – нажатия клавиши «enter»; 
2) к значениям переменных а и b применяется операция сложения, а её 
результат присваивается переменной с;  
3) оператор writeln выводит на экран (в окно вывода) надпись 
’c=’, числовое значение переменной с, т.е. результат сложения, после 
чего производит перевод строки выводимого текста.  
Слово «end» с точкой завершает текст программы. 

Пример входных данных:    39  -14 
              выходные данные:  с=25 
Конец примера. 

Пример 1.2. Программа вычисления корней квадратного уравнения 
a·x2+b·x+c=0: 

Лекция 1 

 

program ex2;              {имя программы} 
  var a,b,c,d,x1,x2: real;{описание переменных} 
begin                     {начало программы} 
  read(a,b,c);            {ввод переменных a,b,c} 
  d := b*b – 4*a*c;     {вычисление дискриминанта} 
  x1 := (-b – sqrt(d))/(2*a); {вычисление} 
  x2 := (-b + sqrt(d))/(2*a); {корней х1, х2} 
  writeln(’x1=’,x1:7:3,’ x2=’,x2:7:3); 
                 {вывод надписи и  вывод результата} 
end.                      {конец программы} 

Все переменные описаны типом real (вещественный), и могут иметь  
положительное или отрицательное значение величиной приблизительно до 
1038. В отличие от целочисленного типа, вещественный тип имеет приближенное значение, около 10 верных десятичных цифр.  
В программе выполняются следующие действия: 
1) оператор read требует ввода числовых значений для переменных а, 
b и с через пробелы (переменные задают коэффициенты квадратного 
уравнения); 
2) вычисляется дискриминант, результат присваивается переменной d 
(звездочка обозначает операцию умножения);  
3) вычисляются два корня уравнения, их значения присваиваются переменным х1 и х2 соответственно (наклонная черта обозначает операцию 
деления, а функция sqrt – вычисление квадратного корня); 
4) оператор writeln выводит на экран надпись ’х1=’, затем числовое значение переменной х1, надпись ’ х2=’, числовое значение переменной х2 (двоеточия и числа 7 и 3 после переменных задают формат вывода, для значения каждой переменной отводится по 7 символов, из них 3 
символа после десятичной точки).  
Пример входных данных:    1  -3.5  -1 
              выходные данные:  x1= -0.500 x2=  4.000 
Конец примера. 

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