Основы алгоритмизации и программирования. Введение в дисциплину

1.

Введение в дисциплину
«Основы алгоритмизации и
программирования»

2.

Целью дисциплины «Основы алгоритмизации и программирования»
является освоение студентами базовых понятий и терминов
программирования как науки.
В результате изучения дисциплины студент должен:
Знать: конструкции языков программирования высокого уровня,
основные структуры данных, алгоритмы сортировки и поиска данных,
базовые концепции объектно-ориентированного программирования.
Уметь: разрабатывать программы на языках высокого уровня,
применяя изученные алгоритмы и структуры данных в соответствии с
технологией разработки программ.
Демонстрировать способность и готовность к самостоятельному
освоению новых алгоритмов, структур данных, парадигм и языков
программирования.

3.

Назначение ЭВМ – решение задач, в результатах решения которых
заинтересован человек (пользователь ЭВМ).
♦ Первые компьютеры создавались исключительно для вычислений
(computing), что нашло отражение в названиях «компьютер» и «ЭВМ».
♦ Вторым крупным применением компьютеров стали базы данных.
♦ Третье важнейшее применение компьютеров - управление всевозможными
устройствами.
♦ Сегодня компьютеры стали главным информационным инструментом на
производстве, в офисе, дома и практически везде! Любая работа с информацией
выполняется с помощью компьютера. Современные суперкомпьютеры
используются для моделирования сложных физических и биологических
процессов. Наиболее сложным применением компьютеров является
искусственный интеллект.
При помощи вычислений компьютер способен обрабатывать информацию по
определённому алгоритму.
Любая задача решается компьютером в виде последовательности
элементарных шагов (вычислений).

4.

Решение задачи на компьютере
Предметная сторона
Компьютерная сторона
Задача
Компьютер
Метод
Технологии
программирования
Алгоритм
Компилятор
Программа

5.

Понятие термина «алгоритм»
Понятие «алгоритм» является основным для всей области
компьютерных наук (Computer Science).
Слово алгоритм происходит от имени великого среднеазиатского
ученого Абу Джофара Мухаммеда бен Муса аль Хорезмий (род. в 783
году в окрестностях Хивы). Из математических работ Аль-Хорезмия до
нашего времени дошли только две – алгебраическая и арифметическая.
Термин алгоритм употреблялся в них для обозначения четырех
арифметических операций, именно в таком значении он и вошел в
некоторые европейские языки.
Постепенно значение слова алгоритм расширялось. К 1950 г. слово
алгоритм чаще всего ассоциировалось с алгоритмом Евклида, который
представляет собой процесс нахождения наибольшего общего делителя
двух чисел. Этот алгоритм приведен в книге Евклида «Начала».

6.

Свойства алгоритма
Современное значение слова алгоритм во многом аналогично таким понятиям, как
рецепт, процесс, метод, способ, процедура, программа, но все-таки слово "algorithm"
имеет дополнительный смысловой оттенок. Алгоритм — это не просто набор конечного
числа правил, задающих последовательность выполнения операций для решения задачи
определенного типа. Помимо этого, он имеет пять важных особенностей, или свойств:
1) Конечность. Алгоритм всегда должен заканчиваться после выполнения конечного
числа шагов. Алгоритм Е удовлетворяет этому условию, потому что после шага Е1
значение r меньше, чем n. Поэтому если r≠0, то в следующем цикле на шаге Е1 значение n
уменьшается. Убывающая последовательность положительных целых чисел имеет
конечное число членов, поэтому шаг Е1 может выполняться только конечное число раз
для любого первоначально заданного значения n.
2) Определенность. Каждый шаг алгоритма должен быть точно определен. Действия,
которые нужно выполнить, должны быть строго и недвусмысленно определены для
каждого возможного случая.

7.

Свойства алгоритма
3) Ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных
данных, т. е. величин, которые задаются до начала его работы или
определяются динамически во время его работы. Эти входные данные берутся
из определенного набора объектов. Например, в алгоритме Евклида есть два
входных значения: m и n, которые принадлежат множеству целых
положительных чисел.
4) Вывод. У алгоритма есть одно или несколько выходных данных, т. е.
величин, имеющих вполне определенную связь с входными данными. У
алгоритма Евклида имеется только одно выходное значение — n, получаемое
на шаге Е2. Это наибольший общий делитель двух входных значений.
5) Эффективность. Алгоритм обычно считается эффективным, если все
предписываемые им действия достаточно просты для того, чтобы их можно
было точно выполнить в течение конечного промежутка времени.

8.

Анализ алгоритмов и теория алгоритмов
На практике нужны не просто алгоритмы, а хорошие алгоритмы в широком
смысле этого слова. Одним из критериев качества алгоритма является время,
необходимое для его выполнения; данную характеристику можно оценить по
тому, сколько раз выполняется каждый шаг. Другими критериями являются
адаптируемость алгоритма к различным компьютерам, его простота,
изящество и т. д.
Часто решить одну и ту же проблему можно с помощью нескольких алгоритмов
и нужно выбрать наилучший из них. Этими вопросами занимается важная
область теоретического программирования - анализ алгоритмов.
Предмет этой области состоит в том, чтобы для заданного алгоритма
определить его рабочие характеристики.
Теория алгоритмов — это более широкая область, которая включает не
только вопросы анализа алгоритмов, но и рассматривает формальные модели
алгоритмов, вопросы существования или не существования эффективных
алгоритмов решения определенных задач (алгоритмически неразрешимые
проблемы), эквивалентность алгоритмов и др.