Введение в алгоритмы (Introduction to Algorithms)

Словарь урока / Vocabulary

Алгоритм / Algorithm — последовательность действий для решения задачи / a sequence of steps to solve a problem
Сложность / Complexity — мера эффективности алгоритма / a measure of algorithm efficiency
Эффективность / Efficiency — насколько хорошо алгоритм использует ресурсы / how well an algorithm uses resources
Псевдокод / Pseudocode — неформальная запись алгоритма / an informal description of an algorithm

Что такое алгоритм? / What is an Algorithm?

Алгоритм — это последовательность чётко определённых шагов, которые необходимо выполнить для решения определённой задачи. Алгоритмы используются повсеместно: от простых повседневных задач до сложных компьютерных программ.

An algorithm is a sequence of well-defined steps that need to be performed to solve a specific problem. Algorithms are used everywhere: from simple everyday tasks to complex computer programs.

Интересный факт / Fun fact

Слово "алгоритм" происходит от имени персидского математика аль-Хорезми (IX век), который написал книгу о методах вычислений. В латинском переводе его имя звучало как "Algorithmi".

The word "algorithm" comes from the name of the Persian mathematician al-Khwarizmi (9th century), who wrote a book on calculation methods. In the Latin translation, his name sounded like "Algorithmi".

Хороший алгоритм должен обладать следующими характеристиками:

A good algorithm should have the following characteristics:

Определённость / Definiteness: Каждый шаг должен быть точно определён / Each step must be precisely defined
Конечность / Finiteness: Алгоритм должен завершаться за конечное число шагов / The algorithm must terminate after a finite number of steps
Ввод / Input: Алгоритм может иметь ноль или более входных данных / An algorithm can have zero or more inputs
Вывод / Output: Алгоритм должен производить как минимум один результат / An algorithm must produce at least one result
Эффективность / Efficiency: Алгоритм должен выполняться за разумное время / The algorithm should run in a reasonable amount of time

Примеры алгоритмов / Examples of Algorithms

Алгоритмы встречаются во многих областях нашей жизни. Вот некоторые примеры:

Algorithms are found in many areas of our lives. Here are some examples:

1. Рецепт приготовления блюда / Cooking recipe

Рецепт — это алгоритм приготовления еды, состоящий из серии шагов, ингредиентов (ввод) и готового блюда (вывод).

A recipe is an algorithm for cooking food, consisting of a series of steps, ingredients (input), and a finished dish (output).

2. Сортировка чисел / Sorting numbers

Алгоритм сортировки упорядочивает числа от меньшего к большему или наоборот.

A sorting algorithm arranges numbers from smallest to largest or vice versa.

3. Поиск кратчайшего пути / Finding the shortest path

Навигационные приложения используют алгоритмы для поиска оптимального маршрута между двумя точками.

Navigation applications use algorithms to find the optimal route between two points.

Псевдокод / Pseudocode

Псевдокод — это способ описания алгоритма, который легко понять человеку. Он не привязан к конкретному языку программирования, но содержит основные конструкции, которые можно перевести в код.

Pseudocode is a way of describing an algorithm that is easy for humans to understand. It is not tied to a specific programming language but contains basic constructs that can be translated into code.

АЛГОРИТМ ПоискМаксимума(список)
    максимум = первый элемент списка
    ДЛЯ КАЖДОГО элемента В списке ДЕЛАТЬ
        ЕСЛИ элемент > максимум ТОГДА
            максимум = элемент
        КОНЕЦ ЕСЛИ
    КОНЕЦ ЦИКЛА
    ВЕРНУТЬ максимум

ALGORITHM FindMaximum(list)
    maximum = first element of list
    FOR EACH element IN list DO
        IF element > maximum THEN
            maximum = element
        END IF
    END LOOP
    RETURN maximum

Сложность алгоритмов / Algorithm Complexity

Сложность алгоритма — это мера эффективности алгоритма. Она показывает, как быстро растёт время выполнения алгоритма с ростом объёма входных данных.

Algorithm complexity is a measure of algorithm efficiency. It shows how quickly the execution time of the algorithm grows as the size of the input data increases.

Важно / Important

В компьютерных науках для обозначения сложности алгоритмов используют O-нотацию (Big O notation). Например, O(n) означает, что время выполнения линейно зависит от размера входных данных.

In computer science, Big O notation is used to denote algorithm complexity. For example, O(n) means that the execution time is linearly dependent on the input size.

Основные классы сложности (от лучшего к худшему):

Main complexity classes (from best to worst):

O(1) — Константная / Constant: Время выполнения не зависит от размера входных данных / Execution time does not depend on input size
O(log n) — Логарифмическая / Logarithmic: Время растёт логарифмически / Time grows logarithmically
O(n) — Линейная / Linear: Время растёт пропорционально размеру входных данных / Time grows proportionally to input size
O(n log n) — Линеарифмическая / Linearithmic: Время растёт чуть быстрее, чем линейно / Time grows slightly faster than linearly
O(n²) — Квадратичная / Quadratic: Время растёт пропорционально квадрату размера входных данных / Time grows proportionally to the square of input size
O(2ⁿ) — Экспоненциальная / Exponential: Время растёт экспоненциально / Time grows exponentially

Проверьте ваши знания / Check your knowledge

Что такое алгоритм? / What is an algorithm?

Какая из следующих характеристик НЕ является обязательной для алгоритма? / Which of the following characteristics is NOT mandatory for an algorithm?

Какая нотация используется для обозначения сложности алгоритмов? / Which notation is used to denote algorithm complexity?

Заключение / Conclusion

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

In this lesson, we have introduced the basic concepts of algorithms. We have learned what an algorithm is, what characteristics it should have, and how algorithm complexity is measured. In the following lessons, we will look at specific algorithms and learn how to analyze them.

Python Start

HTML + CSS

Алгоритмы