2.1. Программирование перевода чисел из одной системы счисления в другую
1. Введите в компьютер и отладьте программу Number S_2_l 0. Переведите с ее помощью в десятичную систему счисления следующие двоичные числа: 111110; 1111111; 100000. Проверьте правильность результатов.
2. Введите в компьютер и отладьте программу Number s_l 0_2. Переведите с ее помощью в двоичную систему счисления следующие десятичные числа: 255; 512; 1023. Проверьте правильность результатов.
2.2. Сложность алгоритмов
1. Почему временная сложность алгоритма зависит от его объемной сложности?
Временная сложность алгоритма зависит от его объемной сложности, потому что оба эти параметра тесно связаны с количеством операций, которые алгоритм выполняет. Объемная сложность отражает количество данных или элементов, с которыми алгоритм работает, а временная сложность определяет, сколько времени требуется для выполнения алгоритма, и она напрямую зависит от объемной сложности. Чем больше данных или элементов обрабатывает алгоритм (выше объемная сложность), тем больше времени ему потребуется (выше временная сложность).
2. Составьте алгоритм поиска для следующей задачи: на координатной плоскости заданы своими координатами N точек. Найти две самые удаленные друг от друга точки. Оцените временную сложность алгоритма. Рассмотрите два варианта алгоритма: с полным и с неполным перебором и сравните их.
Алгоритм поиска двух самых удаленных точек на координатной плоскости может быть оценен на временную сложность O(N^2) при полном переборе, где N - количество точек. Это означает, что для каждой пары точек выполняется сравнение расстояния между ними, что приводит к квадратичной зависимости от числа точек.
Вариант алгоритма с неполным перебором, который использует более эффективные методы, такие как алгоритм ближайших соседей, может существенно сократить временную сложность до O(N*log(N)).
3. Составьте алгоритм для решения задачи, аналогичной предыдущей, с учетом того что точки расположены в трехмерном пространстве.
Для нахождения двух самых удаленных точек в трехмерном пространстве, временная сложность с использованием полного перебора будет O(N^2), где N - количество точек. В этом случае для каждой пары точек вычисляется расстояние в трехмерном пространстве.
Для улучшения временной сложности можно использовать алгоритмы, такие как алгоритм ближайших соседей в трехмерном пространстве, что снизит временную сложность до O(N*log(N)) или даже до O(N) в некоторых случаях, в зависимости от конкретной реализации.
2.3. О языках программирования и трансляторах
1. Что такое язык программирования?
Язык программирования - это формальный способ записи инструкций и алгоритмов, понятный как человеку, так и компьютеру. Он используется для написания программ, которые могут быть выполнены на компьютере.
2. Что обозначает понятие «уровень языка программирования»?
Уровень языка программирования указывает на степень абстракции и близкость к машинному коду. Языки бывают низкоуровневыми, высокоуровневыми и промежуточными по уровню абстракции.
3. К какому уровню относятся языки типа «автокод-ассемблер»?
Языки типа "автокод-ассемблер" относятся к низкому уровню языков программирования. Они ближе к машинному коду и используются для непосредственного управления аппаратурой компьютера.
4. Почему языки программирования высокого уровня называют машинно-независимыми языками?
Языки программирования высокого уровня называют машинно-независимыми, потому что программы, написанные на них, могут быть запущены на разных компьютерах с разными архитектурами без изменений в исходном коде. Это достигается благодаря использованию абстракций и переводу кода в машинный код с помощью компиляторов или интерпретаторов.
5. Какие из языков программирования высокого уровня вы знаете?
Примеры языков программирования высокого уровня включают Python, Java, C++, JavaScript, C#, Ruby, и многие другие.
6. Что такое трансляция? Что такое транслятор?
Трансляция - это процесс перевода исходного кода на языке программирования в машинный код, который может быть выполнен компьютером. Транслятор - это программа, которая выполняет этот процесс. Трансляция может быть компиляцией (перевод всего кода сразу в машинный код) или интерпретацией (перевод и выполнение кода построчно).
7. В чем различие между компиляцией и интерпретацией?
Различие между компиляцией и интерпретацией заключается в способе выполнения программы. При компиляции весь исходный код переводится в машинный код заранее, что увеличивает скорость выполнения, но требует предварительной компиляции. При интерпретации исходный код выполняется построчно на лету, что позволяет изменять код без перекомпиляции, но замедляет выполнение.