Question

Нужен список задачек по алгоритмах информатика если можно посложнее

Answer 1

По алгоритмам? Ну на тебе несколько из разных тем.

1) Написать программу для машины Тьюринга, выполняющую сортировку 0 и 1 в двоичном слове.

2) В виде нормального алгоритма (Маркова) реализовать алгоритм сложения целых чисел, заданных в троичной симметричной системе счисления.

3) Проверить разрешимость множества всех простых чисел.

4) Доказать, что класс всех полуразрешимых подмножеств N совпадает с классом всех перечислимых подмножеств N.

Ну и т. д.

Собственно списки (точнее, книги с задачами), например, эти:

1) Дасгупта, Пападимитриу, Вазирани - Алгоритмы.

2) Кормен, Лейзерсон, Штайн - Алгоритмы построение и анализ.

Answer 2

Конечно! Вот список задачек по алгоритмам в информатике, которые можно считать более сложными. Эти задачи требуют хорошего понимания различных алгоритмических концепций и структур данных. Некоторые из них также могут быть использованы для подготовки к олимпиадам по информатике:

1. Задача о рюкзаке (Knapsack Problem): Дан рюкзак с ограниченной вместимостью и набор предметов с заданными весами и стоимостями. Требуется найти наиболее ценные предметы для помещения в рюкзак, чтобы суммарный вес не превышал его вместимость.

2. Задача о максимальной подпоследовательности (Longest Common Subsequence): Даны две последовательности, требуется найти их наибольшую общую подпоследовательность (не обязательно непрерывную).

3. Задача о поиске подмассива с наибольшей суммой (Maximum Subarray Sum): Дан массив чисел, требуется найти непрерывный подмассив (подпоследовательность) с наибольшей суммой.

4. Задача о минимальном остовном дереве (Minimum Spanning Tree): Дан связный взвешенный граф, требуется найти дерево, включающее все вершины графа, с минимальной суммой весов ребер.

5. Задача о наибольшей возрастающей подпоследовательности (Longest Increasing Subsequence): Дан массив чисел, требуется найти наибольшую возрастающую подпоследовательность.

6. Задача о коммивояжере (Traveling Salesman Problem): Дан полный взвешенный граф, требуется найти самый короткий путь, проходящий через все вершины ровно один раз и возвращающийся в исходную вершину.

7. Задача о максимальной потоке и минимальном разрезе (Max Flow Min Cut Problem): Дан сетевой граф с источником и стоком, требуется найти максимальный поток от источника к стоку и соответствующий минимальный разрез.

8. Задача о нахождении наименьшего общего предка (Lowest Common Ancestor): Дано дерево и две вершины, требуется найти их наименьшего общего предка.

9. Задача о поиске кратчайших путей во взвешенном графе (Shortest Paths Problem): Дан взвешенный граф, требуется найти кратчайшие пути от одной вершины до всех остальных.

10. Задача о редакционном расстоянии (Levenshtein Distance): Даны две строки, требуется найти минимальное количество операций (вставки, удаления, замены символов), необходимых для преобразования одной строки в другую.

Эти задачи представляют лишь небольшой перечень возможных сложных алгоритмических задач. Решение каждой из них может потребовать использование различных алгоритмов и структур данных. Успешное решение этих задач поможет вам лучше понять принципы алгоритмов и их применение в различных ситуациях.