Информатика, поток 2024-2026 годов

Полезные ссылки:

• Список обучающихся
• Мини-руководство по SSH

~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+
Задание:     |10|11|12|13|14|15|16|17|18|
Ученик ------+--+--+--+--+--+--+--+--+--+
Баландин     |  |  |  |  |  |  |  |  |  |
Бельков      |  |  |  |  |  |  |  |  |  |
Бланков      |  |  |  |  |  |  |  |  |  |
Боровских    |  |  |  |  |  |  |  |  |  |
Гречин       |  |  |  |  |  |  |  |  |  |
Давыдов      |  |  |  |  |  |  |  |  |  |
Зотов        |  |  |  |  |  |  |  |  |  |
Ключников    |  |  |  |  |  |  |  |  |  |
Мягких       |  |  |  |  |  |  |  |  |  |
Нечепоренко  |  |  |  |  |  |  |  |  |  |
Решетников   |  |  |  |  |  |  |  |  |  |
Прокофьева   |  |  |  |  |  |  |  |  |  |
Шевченко     |  |  |  |  |  |  |  |  |  |
Якушков      |  |  |  |  |  |  |  |  |  |
-------------+--+--+--+--+--+--+--+--+--+
Антонов      |  |  |  |  |  |  |  |  |  |
Аушев        |  |  |  |  |  |  |  |  |  |
Белов        |  |  |  |  |  |  |  |  |  |
Громова      | +| +|  |  |  |  |  |  |  |
Карбышев     |  |  |  |  |  |  |  |  |  |
Картушин     |  |  |  |  |  |  |  |  |  |
Климов       |  |  |  |  |  |  |  |  |  |
Коваленко    |  |  |  |  |  |  |  |  |  |
Кодинцев     |  |  |  |  |  |  |  |  |  |
Королёв      |  |  |  |  |  |  |  |  |  |
Краснова     |  |  |  |  |  |  |  |  |  |
Линьков      |  |  |  |  |  |  |  |  |  |
Пименов      |  |  |  |  |  |  |  |  |  |
Чернев       |  |  |  |  |  |  |  |  |  |
-------------+--+--+--+--+--+--+--+--+--+
Задание:     |10|11|12|13|14|15|16|17|18|
~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+

Расшифровка номеров заданий. 10: размер файла. 11: подсчёт слов и строк. 12: «битовый микроскоп». 13: шифровалка-I.

~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+
Задание:     |01|02|03|04|05|06|07|08|09|
Ученик ------+--+--+--+--+--+--+--+--+--+
Баландин     | +| +| +| +|  | +| +| +| +|
Бельков      |  |+ |+ |+ |  |+ |+ |+ |  |
Бланков      | +| +| +| +|  | +| +| +|  |
Боровских    |+ |+ |+ |+ |  |  |+ |+ |  |
Гречин       | +| +| +| +|  |  |  |  |  |
Давыдов      |  |  |  |  |  |  |  |  |  |
Зотов        | +| +|  | +|  |  | +| +|  |
Ключников    |+ |+ |+ |+ |  |+ |  |+ |  |
Мягких       | +| +| +| +|  |  |  | +|  |
Нечепоренко  |+ |+ |+ |+ |+ |+ |+ |+ |+ |
Решетников   |  |  |  |  |  |  |  |  |  |
Прокофьева   |+ |+ |+ |+ |  |+ |+ |+ |  |
Шевченко     | +| +| +| +|  |  | +|  |  |
Якушков      |+ |+ |+ |+ |  |  |+ |  |  |
-------------+--+--+--+--+--+--+--+--+--+
Антонов      |  |  |  |  |  |  |  |  |  |
Аушев        |+ |+ |+ |+ |  |+ |+ |+ |+ |
Белов        | +| +| +| +|  | +| +| +|  |
Громова      |+ |+ |+ |+ |+ |+ |+ |+ |+ |
Карбышев     | +| +| +| +|  | +|  | +|  |
Картушин     |+ |+ |+ |+ |  |  |  |+ |  |
Климов       |  |  |  |  |  |  |  |  |  |
Коваленко    |  |  |  |  |  |  |  |  |  |
Кодинцев     | +| +| +| +|  | +|  | +|  |
Королёв      |  |+ |+ |+ |  |  |  |  |  |
Краснова     | +| +| +| +|  | +| +| +| +|
Линьков      |+ |+ |+ |+ |+ |  |  |  |  |
Пименов      | +| +| +| +| +| +|  | +|  |
Чернев       |+ |+ |+ |+ |  |  |+ |  |  |
-------------+--+--+--+--+--+--+--+--+--+
Задание:     |01|02|03|04|05|06|07|08|09|
~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+

Расшифровка номеров заданий. 01: возвратное уравнение. 02: подсчёт. 03: вставка. 04: пузырёк. 05: Lomuto vs Hoare. 06: merge sort. 07: угадай-K. 08: системы счисления. 09: палиндромы.

Формулировки заданий

Написать программу, которой на вход с клавиатуры вводится 5 коэффициентов многочлена степени 4. Программа должна определять, является ли этот многочлен возвратным (имеющим вид p(x) = Ax⁴ + Bx³ + Cx² + λBx + λ²A), и коли это так, находить (вещественные, хотя можно и комплексные) решения уравнения p(x) = 0.

Написать программу, сортирующую вводимый с клавиатуры массив методом подсчёта (количества элементов, сравнимых с данным).

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

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

Как мы выяснили, характерные для быстрой сортировки алгоритмы разделения (partition) Хоара и Ломуто отличаются в два раза по количеству операций сравнения. Поэтому хотелось бы понять, реализации быстрой сортировки, использующие эти алгоритмы, действительно отличаются по быстродействию в два раза или это не так?

Из обсуждавшегося также следует, что асимптотика N*log(N) для быстрой сортировки достигается лишь в среднем, деградируя до N² при некоторых входных данных; при этом «деградантные множества» различных алгоритмов и реализаций не обязаны совпадать.

Необходимо написать программу, которая считает отношение времён выполнения реализаций обоих алгоритмов на большой и равномерной выборке из множества возможных входных массивов и выдаёт отношения времён их работы. Далее следует изучить получаемые результаты, найти там отношение, близкое к двойке, или его не найти, разобравшись в причинах происходящего.

Написать программу, сортирующую два произвольных массива любым нравящимся вам способом, а затем сливающей оба массива в один сортированный не более чем за линейное по размеру результирующего массива время.

Написать программу, которая на отрезке [a, b] ищет целое число, задуманное пользователем, задавая вопросы, на которые пользователь отвечает yes/no. Если пользователь вводит «quit», программа завершается. Ответы пользователя могут быть в любом регистре букв (скажем, «yEs» вполне может встретиться).

Значения a и b пользователь вводит сначала самостоятельно. Программа должна работать оптимально. Пользоваться библиотечными функциями для работы с символами/строками (кроме scanf()/getchar()) запрещается.

Пользователь вводит целое неотрицательное число (в десятичной системе счисления) и основание системы счисления p (2≤p≤36). Программа выводит введённое пользователем число в p-ичной системе счисления. Использовать массивы и библиотечные функции по преобразованию/выводу чисел в произвольных системах счисления запрещается.

Написать программу, распознающую палиндромы среди

1. (последовательно) всех своих аргументов командной строки;
2. конкатенации всех аргументов командной строки.

Запрещается использовать стандартные функции из набора ctype/string (необходимые для этой программы части несложно реализовать самостоятельно).

Реализовать программу, подсчитывающую размер файла в байтах. Программа не может читать файл побайтно и использовать функции/системные вызовы семейства stat. Программа должна корректно работать как минимум для файлов, доступных запускающей программу сущности на чтение или на запись.

Написать программу, принимающую в качестве аргументов командной строки имена файлов. Если исполняемый файл программы называется «wc», программа должна подсчитывать и выдавать на экран количество слов (разделители слов — пробелы, табуляции, символы перехода на новую строку), если «lc» — количество строк (в пустом файле строк нет, если последний символ в файле — \n, то «получающаяся пустая строка» не считается).

Реализовать функцию, принимающую указатель на некоторую область памяти и её размер в байтах и выдающую на экран побитовое содержимое этой памяти.

С помощью этой функции проверить истинность обсуждавшегося на занятиях способа хранения целых (беззнаковых и со знаком) целых чисел и понять способы хранения чисел с плавающей точкой одинарной и двойной точности (a.k.a. float и double). Быть готовым обосновать свои утверждения кодом.

Under construction.

Всё прочее

В остальном —