Алгоритмы

    Решение олимпиадных задач по информатике:

  • kotov.rar (181 кБ)
    И.А.Волков, В.М.Котов - СБОРНИК ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ С УКАЗАНИЯМИ И РЕШЕНИЯМИ
    Составители сборника последних несколько лет тренировали сборную команду школьников Беларуси по информатике. Задачи, представленные в этом сборнике, давались на школьникам на подготовительных сборах, отборочных турах, олимпиадах, и достаточно полно охватывают возможную тематику олимпиадных задач. Задачи снабжены комментариями и указаниями, зачастую - полными решениями и программами или программными фрагментами. В качестве примеров мы включили несколько пол ных программ, написанных школьниками на сборах.

  • okulov.rar (727 кБ)
    Книга по информатике.
    Глава 1. ИНФОРМАТИКА - КЛЮЧЕВОЙ ПРЕДМЕТ СОВРЕМЕННОЙ ШКОЛЫ
    Глава 2. ПЕРЕБОР И МЕТОДЫ ЕГО СОКРАЩЕНИЯ
    Глава 3. АЛГОРИТМЫ НА ГРАФАХ
    Глава 4. ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ
    Глава 5. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ

  • shen.rar (112 кБ)
    В книге описываются решения различных задач. Автор - Шень.
    Характер глав различен: в одних предлагается набор мало связанных друг с другом задач с решениями, в других по существу излагается один-единственный алгоритм.

  • samples.rar (30 кБ)
    Набор примеров решения задач по информатике (на паскале).

  • olimp.rar (173 кБ)
    Решения олимпиадных задач по информатике.
    скачать с сайта автора

    • Книги про алгоритмы:

  • knut.rar (443 кБ)
    Третий том известной монографии одного из крупнейших американских специалистов по программированию Д. Кнута состоит из 2-х частей: "Сортировка" и "Поиск". В них подробно исследуются различные алгоритмы внутренней и внешней сортировки, изучаются методы поиска информации в таблицах на основе сравнения или преобразования ключей, даются оценки эффективности предлагаемых алгоритмов. Книга снабжена большим количеством задач и примеров разной степени трудности, существенно дополняющих основной текст.
    От других руководств по программированию книга выгодно отличается строгостью изложения и широким применением математического аппарата. Вместе с тем она доступна студентам 1-го курса. Знакомство с двумя первыми томами желательно, но не обязательно. Каждый, кто хочет научиться квалифицированно программировать, найдет в ней много полезного.
    Рассчитана на широкий круг программистов.

  • algor2.rar (429 кБ)
    Множество самых разнообразных алгоритмов. Они разбиты на группы и последовательно объясняются.

  • shifr.rar (32 кБ)
    Алгоритмы шифрования RC2, RC4, RC5

  • trans.rar (74 кБ)
    Курс "Основы построения трансляторов"
    Здесь размещены методические материалы по курсу "Основы построения трансляторов", который включен в дисциплиину "Системное программное обеспечение". Курс читается в 8 семестре студентам заочного отделения специальности 2201 факультета Автоматики и вычислительной техники (АВТФ) Новосибирского государственного технического университета (НГТУ).

  • trans2.rar (51 кБ)
    В этом архиве находятся:
    - конспект лекций по теме "Трансляторы"
    - примеры программ на темы Лексический и Синтаксический анализ

    • Различные графические эффекты:

  • demo.rar (542 кБ)
    Набор небольших программ, реализующих всякие эффекты, с исходниками и описанием.

  • algor.rar (429 кБ)
    Различные алгоритмы, описание мат. модели различных эффектов.

  • alg2.rar (188 кБ)
    Различные алгоритмы, описание мат. модели различных эффектов (2).

    • Математика:

  • mathem.rar (1.4 мБ)
    Различные математические алгоритмы.
    long - Длинные числа и операции с ними (с исходниками).
    fft_art - Дискретные преобразования Фурье,Хартли (с исходниками).
    ch_teor - Китайская теорема об остатках.
    long_gen - Генерация больших простых чисел.
    sqrt - Квадратный корень по простому модулю.
    nod - НОД, решение ax+by=1, нахождение обратного элемента по модулю.
    syst - Перевод из одних систем счисления в другие.
    period1 - Период бесконечной дроби 1/n.
    period2 - Период бесконечной дроби N/M по основанию P.
    pribl - Приближение числа в виде дроби.
    rabin - Тест простоты Рабина.
    jacobi - Вычисление символа Якоби (Лежанра).
    num_teor - Алгоритмические проблемы теории чисел. Ю.В. Нестеренко.
    pollard - Разложение на множители. P-1 метод Полларда.
    mon_kar - Разложение на множители. Методы Монте-Карло.
    divis - Разложение на множители. Простое деление.

  • geometry.rar (2.8 мБ)
    Вычислительная геометрия.
    1. Системы координат.
    2. Структуры геометрических данных, основные операции.
    3. Уравнения различных фигур и их составление по разным данным.
    - Уравнения плоскости.
    - Окружность по трем точкам 2D.
    - Сфера.
    4. Построение выпуклой оболочки конечного множества точек.
    Алгоритмы 2D:
    - Алгоритм Gift wrapping (с исходниками).
    - Алгоритм Graham's scan.
    - Алгоритм Мелькмана.
    - Алгоритм Quickhull.
    - Алгоритм "Разделяй-и-властвуй".
    - Модифицированный алгоритм.
    Алгоритм 3D:
    - Трехмерный случай.
    - Случай призвольной размерности в оригинальной работе Барбера.
    5. Нахождение пересечения и объединения геометрических объектов.
    В пространстве:
    - Пересечение двух треугольников (исходник). Алгоритм описан в статье Tomas'а Moller'а A Fast Triangle-Triangle Intersection Test (файл Tritri.pdf).
    - Пересечение отрезка и треугольника.
    - Пересечение прямой (или отрезка) и плоскости.
    - Пересечений трех плоскостей.
    На плоскости:
    - Пересечение прямой (отрезка) и прямой (отрезка).
    - Пересечение двух окружностей.
    - Пересечение двух выпуклых многоугольников.
    - Пересечение: Коллекция полуплоскостей.
    6. Проверка принадлежности.
    - Проверка принадлежности точки многоугольнику.
    - Проверка принадлежности точки прямой.
    - Проверка принадлежности точки отрезку.
    7. Нахождение расстояния между различными объектами.
    - Вычисление расстояния между точкой и прямой/лучом/отрезком.
    - Вычисление расстояния от точки до плоскости.
    8. Работа с многоугольниками.
    - Площадь.
    - Центр тяжести.
    - Нахождение ориентации простого многоугольника.
    - Определение: выпуклый многоугольник или нет.
    - Триангуляция монотонных полигонов.
    - Декомпозиция на монотонные полигоны методом сканирующей линии.
    - Оригинальная статья Зейделя (файл seidel_triang.ps).
    - Реализация алгоритма Зейделя, написанная Narkhede и Manocha.
    9. Разное.
    - Куда попадает перпендикуляр из точки: на отрезок или на его продолжение?
    - Найти прямую, имеющую общие точки с макс. числом заданных отрезков и напечатать в порядке возрастания номера отрезков, которые она пересекает.
    - Дано множество, содеpжащее n точек. Постpоить описаннyю окpyжность минимального pадиyса.
    - Найти порядок, в котором можно соединить N точек, чтобы получился N-угольник (те не было бы пересечений сторон).
    - Найти на прямой такую точку z, сумма расстояний от которой до заданных N точек минимальна.
    - Даны точки A и B Определить, какой из отрезков, OA или OB, образует больший угол с осью OX.
    - На плоскости расположены N точек. Найти на оси абсцисс точку, наибольшее из расстояний от которой до выбранных точек было бы минимальным.
    - Построить окружность минимального радиуса с центром на оси абсцисс так, чтобы она содержала внутри себя и на своей границе все эти точки.
    10. Инкрементальный алгоритм построения триангуляции Делоне.
    11. Метод Раперта построения триангуляции Делоне (файл Ruppert.ps).
    12. Комментарии к методу Рапперта, связанные с практической реализацией.
    13. Много различных алгоритмов построения триангуляции Делоне описываются и сравниваются в статье А. В. Скворцова (файл delaunay_compares.pdf).
    14. Связь между триангуляцией Делоне, диаграммой Вороного и выпуклой оболочкой.
    15. Олимпиадные задачи: геометрия.

  • graf.rar (451 кБ)
    Графы. Поиск маршрутов.
    1. Задача о кратчайших путях.
    - Волновой алгоритм.
    - Алгоритм Форда-Беллмана.
    - Алгоритм Флойда.
    - Алгоритм Дейкстры.
    - Нахождение k кратчайших путей в графе.
    - Smart Moves: Intelligent Pathfinding[Перевод].
    2. Поиск на графе и его обход.
    3. Нахождение на графе минимального остовного дерева.
    4. Проверка связности графа с ненаправленными ребрами. Выделение связной компоненты графа.
    5. Нахождение максимального пропускного потока.
    6. Статья про графы Graphs: Weiss, Chapter 9 (файл graphs.student.ps).

  • comb.rar (1.1 мБ)
    Комбинаторика и переборные задачи.
    1. Методы программрования: переборные алгоритмы.
    2. Задача о рюкзаке.
    3. Hапечатать все последовательности длины N из чисел 1,2..M.
    4. Подсчитать количество слов длины К из данных N букв, не содержащих данное подслово.
    5. Hапечатать все перестановки чисел 1..N.
    6. Сгенерировать все подмножества данного n-элементного множества {0,.., n-1}.
    7. Дана строка S и набор A слов А[1],.. , A[k]. Разбить строку S на слова набора всеми возможными способами.
    8. Перечислить все разбиения N на целые положительные слагаемые.
    9. Перечислить все различные представление числа N в виде всевозможных произведений (сумм) K натуральных чисел.
    10. У продавца и покупателя имеется неограниченное кол-во монет достоинством (1,2,5,10,20,50,100,200,500 к примеру). Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец.
    11. Перечислить все расстановки 8-ми ферзей на шахматной доске, при которых они не бьют друг друга.
    12. A Story about the N-Queens Problem: From Exponential to (Almost) Constant Time (папка N Queens).
    13. Обход доски шахматным конем.
    14. Ханойские башни (с исходниками на Си++, СИ, Паскале и Бейсике. Файлы hanoi4_C++.txt, hanoi3_C.txt, hanoi2_Pascal.txt, hanoi1_Basic.txt).
    15. В. Липский "Введение в комбинаторику" (файл lipsky.ps).
    16. Олимпиадные задачи: переборные задачи.
    17. Олимпиадные задачи: рекуррентные соотношения и динамическое программирование.

  • fun_con.rar (938 кБ)
    Быстрое вычисление функций и констант.
    Функции:
    1. Приближение функций.
    2. Быстрое возведение в степень.
    3. Тригонометрические функции.
    4. Вычисление функции Эйлера.
    5. Вычисление факториала.
    6. Gamma function (исходники в папке nr_gamma).
    7. Квадратный корень - метод Ньютона.
    8. Вычисление квадратного корня из целого числа (с исходником в файле sqrt_cpp.htm).
    9. Точное вычисление обратного числа, корня m-й степени.
    Константы:
    1. Вычисление с нужной точностью числа Пи.
    2. Квадратный корень из 2 (с исходником в файле sqrt2series_c.htm).
    3. The Euler constant gamma.
    4. The Apery's constant.
    5. Логарифм 2.
    6. Вычисление числа е - школьный метод.
    7. Вычисление с большой точностью числа е (с исходником в файле e_c.htm).
    8. Вычисление N-го знака.
    9. Числа Фибоначчи за O(logn).
    10. Binary splitting method.
    11. Acceleration of the convergence of series.

    • Сортировка и поиск:

  • sort.rar (345 кБ)
    Сортировка.
    algor - Алгоритмы сортировки.
    bubble - Сортировка пузырьком.
    fast - Быстрая сортировка.
    insert - Сортировка вставками.
    merge - Сортировка слиянием.
    piram - Пирамидальная сортировка.
    radix - Поразрядная сортировка.
    select - Сортировка выбором.
    shell - Сортировка Шелла.
    topol - Топологическая сортировка.
    quest - Требования и свойства сортировок. Что когда лучше?

    • Сжатие и кодирование:

  • compr.rar (364 кБ)
    Общие алгоритмы cжатия и кодирования.
    ari - Арифметическое кодирование.
    huff - Алгоритм сжатия по Хаффману.
    lzw - Метод LZW-сжатия данных.
    methods - Некоторые методы сжатия данных.
    preph - Использование алгоритма расширяющегося префикса для кодирования и схожих пpоцессов.
    quest - Архиваторы. Способы сжатия данных. Контрольные вопросы.
    rle - RLE (Групповое кодирование).
    uue - UUE-кодирование.
    shennon - Кодирование методом Шеннона-Фано.
    some_mat - Математика и программирование : маленькие заметки. Небольшая модификация алгоритма Хаффмана.
    techn - Проект технологии сжатия данных.

  • aud_comp.rar (263 кБ)
    Сжатие аудиосигналов.
    audiopac - Improved Lossless Transform Coding of Audio Signals. Мощный алгоритм сжатия без потерь. Слабо распространенная ветвь такого рода алгоритмов.
    dac - Digital Audio Compression. Обзор различных методов сжатия цифрового звука.
    ltac - ossless Audio Coding. Дано краткое описание основных методов сжатия аудиофайлов без потерь.

  • pic_comp.rar (882 кБ)
    Сжатие изображений.
    jpeg - Основы алгоритма сжатия JPEG.
    comp_met - Статья: Алгоритмы сжатия изображений. Пособие знакомит с основными понятиями сжатия изображений, базовыми алгоритмами и современными направлениями развития теории сжатия изображений. Пособие можно рассматривать как практическое руководство. Рассчитано на читателей, знакомых с C++ и имеющих представление о базовых алгоритмах.

    • Исходники:

  • sound.rar (302 кБ)
    Набор исходников (некоторые с описанием) для работы со звуком.

  • c_math.rar (16 кБ)
    В этих файлах приводятся исходники мат. функций (таких как sin, cos, log и т.д.)

    • Другое:

  • bz.rar (296 кБ)
    1. Основы построения систем основанных на знаниях (СОЗ)
    2. Экспертные системы
    3. Приобретение и формализация знаний
    4. Представление знаний с использованием логики предикатов
    5. Семантические сети
    6. Продукционные модели
    7. Представление знаний с применением фреймов
    8. Стратегии поиска в СОЗ
    9. Нечеткие множества в системах основанных на знаниях

    • Назад