Информатика

В стандартном курсе алгоритмов нас учат, что быстрая сортировка в среднем составляет а в худшем случае . В то же время изучаются другие алгоритмы сортировки: в худшем случае (например, mergesort и heapsort ) и даже линейное время в лучшем случае (например, сортировка пузырьков ), но с некоторыми...

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

Взглянув на веб-страницу Джулии , вы можете увидеть некоторые тесты нескольких языков по нескольким алгоритмам (время показано ниже). Как может язык с компилятором, изначально написанным на C, превзойти C-код? Рисунок: время тестов относительно C (чем меньше, тем лучше, производительность C =...

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

Я не понимаю, почему проблема остановки так часто используется, чтобы исключить возможность определения, останавливается ли программа. Википедия [статья] [1] правильно объясняет, что детерминированная машина с конечной памятью либо остановит, либо повторит предыдущее состояние. Вы можете...

Нам дали следующее упражнение. Позволять f(n)={100n occurs in the decimal representation of πelsef(n)={10n occurs in the decimal representation of π0else\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases} Докажите, что...

Я довольно свободно говорю на C / C ++ и могу разбираться с различными языками сценариев (awk / sed / perl). Я начал использовать python гораздо больше, потому что он сочетает в себе некоторые изящные аспекты C ++ с возможностями сценариев awk / sed / perl. Но почему так много разных языков...

Позвольте мне уточнить: Учитывая диаграмму рассеяния некоторого заданного числа точек n, если я хочу мысленно найти ближайшую точку к любой точке на графике, я могу сразу игнорировать большинство точек на графике, сужая свой выбор до некоторого небольшого, постоянного числа точек поблизости , Тем...

Я изучаю Haskell, и я очарован языком. Однако у меня нет серьезных знаний по математике или CS. Но я опытный программист. Я хочу изучить теорию категорий, чтобы стать лучше на Хаскеле. Какие темы в теории категорий я должен изучить, чтобы обеспечить хорошую основу для понимания...

Преобразование регулярных выражений в (минимальный) NFA, который принимает тот же язык, легко с помощью стандартных алгоритмов, например , алгоритма Томпсона . Другое направление кажется более утомительным, и иногда получающиеся выражения являются грязными. Какие существуют алгоритмы для...

Большая часть современного шифрования, такого как RSA, основывается на целочисленной факторизации, которая, как полагают, не является сложной задачей NP, но относится к BQP, что делает его уязвимым для квантовых компьютеров. Интересно, почему не было алгоритма шифрования, основанного на известной...

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

Бинарное индексированное дерево не имеет или почти не имеет литературы по сравнению с другими структурами данных. Единственное место, где это преподается, это учебник по topcoder . Хотя учебник завершен во всех объяснениях, я не могу понять интуицию за таким деревом? Как это было изобретено? Что...

Существует множество попыток доказать либо либо , и, естественно, многие люди задумываются над этим вопросом, имея идеи для доказательства того или иного направления.P ≠ N PP = N Pпзнак равноNп\mathsf{P} = \mathsf{NP} P ≠ N Pп≠Nп\mathsf{P} \neq \mathsf{NP} Я знаю, что есть подходы, которые, как...

Многие программы по информатике требуют двух или трех классов исчисления. Мне интересно, как и когда исчисление используется в информатике? Содержание CS в области компьютерных наук имеет тенденцию фокусироваться на алгоритмах, операционных системах, структурах данных, искусственном интеллекте,...

Эти два кажутся очень похожими и имеют почти идентичную структуру. Какая разница? Каковы временные сложности для разных операций

Я задавался вопросом об этом вопросе, так как я был студентом. Это общий вопрос, но я приведу примеры ниже. Я видел много алгоритмов - например, для задач с максимальным потоком я знаю около 3 алгоритмов, которые могут решить эту проблему: Ford-Fulkerson, Edmonds-Karp & Dinic, причем Dinic...

В большинстве вводных классов алгоритмов вводятся нотации, такие как (Big O) и , и студент, как правило, учится использовать одну из них для определения сложности времени.ΘОOOΘΘ\Theta Однако есть и другие обозначения, такие как , и . Существуют ли какие-либо конкретные сценарии, в которых одна...

Формула Vapnik-Chervonenkis (VC) -мерности для нейронных сетей варьируется от до , с в худшем случае, где - число ребер, а это количество узлов. Количество обучающих выборок, необходимых для строгой гарантии обобщения, линейно зависит от VC-измерения.O ( E)O(E)O(E)O ( E2)O(E2)O(E^2)O (...

В Cormen упоминаются два метода разбиения быстрой сортировки: Hoare-Partition(A, p, r) x = A[p] i = p - 1 j = r + 1 while true repeat j = j - 1 until A[j] <= x repeat i = i + 1 until A[i] >= x if i < j swap( A[i], A[j] ) else return j а также: Lomuto-Partition(A, p, r) x = A[r] i = p - 1...