FAQ: избранное часть 1 (и не последняя)

Содержание

Предисловие

графика, звук
обработка изображений, растровая графика
рисование
преобразование фурье, цифровая обработка сигнала

геометрия
пересечение фигур, определение столкновений
интерполяция
двумерная геометрия
трёхмерная геометрия

алгебра
основы линейной алгебры
системы линейных алгебраических уравнений
уравнения большой степени

общеупотребимые алгоритмы
поиск пути, алгоритмы на графах
поиск в массивах
сортировка
комбинаторика, перестановки
грамматика, синтаксический разбор
архивация
криптография, кодирование данных
другие полезные алгоритмы

вычисление математических функций
псевдослучайные последовательности
простые числа
формулы, методы расчёта
дата, время

моделирование, дифуры
дифуры: теория, численные методы интегрирования
механика

оптимизация, искусственный интеллект
минимизация функций, аппроксимация
ии в играх
алгоритмы ии, решение некорректно поставленных задач

информация к размышлению
олимпиадные/популярные задачи
нерешённые задачи
занимательная теория вероятностей
другое

Предисловие

Эпиграф

Кто людям помогает, тот тратит время зря....
Старуха Шапокляк

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

Данный фак не претендует на полноту изложения всех вопросов, связанных с алгоритмами, а порой и конкретные топики не раскрывают рассмотренного в них вопроса в полном объёме. Это не должно вас смущать по двум причинам:

1. Для полного и строгого рассмотрения той или иной теории существуют учебники. Форум же существует для того, чтобы люди находили друг друга, а фак существует для того, чтобы люди не задавали одинаковых вопросов в форуме и не отвлекали людей от нахождения друг друга. Чтобы изложение предмета в форуме было столь же основательным, надо либо копировать учебник целиком, либо тратить усилие, эквивалентное написанию такового учебника. Если яндекс вам не помог в поисках подходящего учебника, есть топик Ресурсы интернета , в котором собраны ссылки на все основные собрания русскоязычной литературы.

2. Если вы нашли интересующую вас тему, но у вас возник по ней вопрос, спрашивайте прямо в том же топике. Тем самым вы поспособствуете развитию фака. Наконец, никто вам не запрещает создать свою тему, если вы ничего не нашли.

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

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

Напротив, если вам помог один из пунктов фака и вы хотите выразить благодарность, повышайте рейтинг написавшему ответ, а заодно и мне - с указанием названия темы, как она написана в факе. Таким способом я буду знать, скольким людям помог мой фак, какие темы наиболее востребованы, ну и рейтинг у меня будет побольше.

Существует проект создания "нормального" фака по алгоритмам. Этим вроде занимается GrAnd , все вопросы к нему. Вот темы, где это обсуждается:
Предложения по организации "FAQ по алгоритмам"
Организация "FAQ по алгоритмам"

Не могу не сказать свою точку зрения по поводу задавания вопросов. Всегда при создании нового топика описывайте свою задачу как можно более подробно, с самого начала, как она у вас возникла, даже если вам кажется, что это к делу не относится. В 99% случаев ответить на вопрос нельзя без знания деталей, даже если они не относятся к алгоритмам. Если вы будете утаивать детали, вы обязательно увидите вопрос "а для чего тебе это надо?" и будете вынуждены на него ответить. Пример того, как не надо задавать вопросы: Проэкция N-D в 2-D (или не проэкция) (найду пример поярче - выложу).

Чтобы в полной мере овладеть искусством задавания вопросов, советую прочитать следующую статью: Как правильно задавать вопросы .

И напоследок немного технических деталей. При переходе на новый форум со старого http://pascal.sources.ru/cgi-bin/forum/YaBB.cgi в исходниках появились изначально там не присутствовавшие теги   и <br>.   надо заменить на пробел или пустое место, а <br> на символ перевода строки, и исходники примут первозданный вид.

графика, звук

обработка изображений, растровая графика
преобразование BMP 24bit->8bit
преобразование BMP 24bit->16bit
преобразование BMP 8bit->4bit
контрастность, цветность
перевод в монохром
аффинное преобразование растра
Hough transformation
определение расфокусировки изображения, немного про распознавание образов

рисование
алгоритмы рисования линии
алгоритм хорна рисования прямой линии и окружности на паскале
про построение прямых линий
рисование стрелки на паскале и с++е
небольшой визуальный эффект на с++е

преобразование фурье, цифровая обработка сигнала
дискретное косинусное преобразование на с++
что такое преобразование фурье??
быстрое преобразование фурье на с++е и паскале (так я его ни грамма и не понял!!!!!! 8-[] )
узнать частоту сигнала
что есть частота?
сглаживание, средняя линия, низкочастотные фильтры
немного про эквалайзер
демагогия по поводу фурье и волнового уравнения

геометрия

пересечение фигур, определение столкновений
пересечение окружности с прямой
площадь пересечения прямоугольников
по мотивам определения столкновений (не очень конкретно)
про перемещения танчиков и натыкание на стенку
пересечение отрезков
пересечение двух окружностей
отсечение невидимых рёбер у выпуклых фигур на паскале

интерполяция
интерполяция
кубические сплайны еа паскале
сплайны, реализация на с++ без описания
много сплайнов на паскале и с
добавление вершины в кривую безье

двумерная геометрия
биссектриса
площадь сегмента круга
центр описанной окружности
принадлежность точки к полигону
переместить изображение по наклонной прямой

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

алгебра

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

системы линейных алгебраических уравнений
гаусс на паскале
метод зейделя на c++ без комментариев
метод итераций на с++е
по мотивам метода гаусса

уравнения большой степени
теорема виета на с++е
уравнения третьей степени (и больше)
уравнения большой степени на паскале
ещё про уравнения большой степени
корни полинома на с++е

общеупотребимые алгоритмы

поиск пути, алгоритмы на графах
поиск кратчайшего пути, волновой алгоритм
волновой алгоритм на паскале
ещё волновой алгоритм на паскале
про эвристический поиск
алгоритм дейкстры на матлабе
поиск замкнутых областей в графе
изоморфизм графов
планарность графа на торе
задача штейнера про дороги
раскраска гиперграфа на с++е

поиск в массивах
локальные/глобальные минимумы/максимумы в двумерном массиве на паскале
поиск 10 наибольших элементов в массиве различными способами
поиск различий в файлах
поиск совпадений в двух строках
поиск повторяющихся слов
поиск подстроки в строке
анаграммы

сортировка
quicksort на паскале
quicksort на с++ и паскале
heap sort на с++е, сортировка деревом
radix sort
много сортировок на паскале и одна на с++
сортировка отрезков на с++е и паскале
когда quicksort работает медленно?

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

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

архивация
дерево хаффмана на паскале
немного о деревьях хаффмана (я сам не вникал)
по мотивам архивации (авось кому интересно будет)

криптография, кодирование данных
алгоритм rsa
bscas на асме
шифр, который нельзя взломать
алгоритм serpent
про контрольные суммы
коды рида-соломона
азбука морзе

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

вычисление математических функций

псевдослучайные последовательности
генерация псевдослучайных чисел
генерация псевдослучайных чисел на асме
про случайные числа, нормальное распределение
стандартный random

простые числа
последовательность Хемминга на паскале
поиск простых чисел, решето эратосфена на паскале
для тех кто ищет простые числа
разложение на простые множители

формулы, методы расчёта
возвести число в дробную степень (уж сколько раз твердили миру.....)
узнать фазу комплексного числа
вычисление числа пи
вычисление количества цифр в числе n! (факториал)(формула стирлинга)
квадратный корень с фиксированной точкой
таблицы синусов (ускоренное вычисление)
большие целые числа с++ + асм, нет деления

дата, время
календарь на паскале
преобразование даты в число на с++
по порядковому номеру дня в году определить месяц
определение количества дней в месяце
совпадение стрелок на паскале

моделирование, дифуры

дифуры: теория, численные методы интегрирования
метод Рунге-Кутты для автономной и неавтономной системы ОДУ на паскале
устойчивость по ляпунову
нелинейные дифуры, модель хищник-жертва
интегрирование уравнений движения материальной точки

механика
полёт снаряда с трением
расчёт траектории системы материальных точек (хотя она и в разделе "паскаль")
бильярд
немного про столкновения шариков

оптимизация, искусственный интеллект

минимизация функций, аппроксимация
раскидать точки в прямоугольнике
можно ли по таблице у(х) восстановить функцию??
почему используют метод наименьших квадратов
немного про аппроксимацию
немного про квазиньютоновский метод
метод золотого сечения
про решение систем нелинейных уравнений
симплекс метод на паскале
аппроксимация многочленом на с++

ии в играх
ии для преферанса
игра "ним" с искусственным интеллектом
как играть в морской бой

алгоритмы ии, решение некорректно поставленных задач
немного об экспертных системах
про декомпиляцию
восстановление образа из двух фотографий
компьютерная томография
определение контура объекта
гадалка Шеннона

информация к размышлению

олимпиадные/популярные задачи
найти минимальное число с заданным колвом делителей
обход конём доски m*n на паскале
конь на с++
получить число из набора цифр расставляя /*-+() на паскале
получить максимальное число из набора цифр расставляя /*-+()
великая флатландская стена
задача о шахматистах
текст на заборе
по мотивам задачи о рюкзаке
простые числа p-q=n
рассадить учеников по партам
складываем тетради
ханойские башни
волк, коза и капуста
вычёркивание чисел
заменить последнюю единицу на ноль
про палача
режем n-мерный куб
закрасить n-мерный кубик
количество граней у n-мерного куба
генерация магических квадратов
отсортировать 5 чисел за 7 сравнений
про станки
стираем числа с доски
ходим камнем по доске

нерешённые задачи(решите - сообщите мне)
задача про насыпание шариков
15 элементов семь раз тройками в 5 рядов
дзета-функция от трёх (интеграл(1/х^3) до бесконечности)
моделирование велосипеда
генерация ландшафтов
построить карту

занимательная теория вероятностей(творчество esperanto)
задача про автобусы
собирание карточек
про детей
зажигаем лампочки
сделать кубик из монет
стираем буквы

другое (интересно, но не относится к вышеназванным темам)
курс очень молодого бойца
что такое кнут?
как не надо делать (словесный мордобой по поводу нечёткой логики)
про дефрагментацию
to goto or not to goto??

05.01.04
09.12.04

Сообщение отредактировано: Math - 02.07.09, 21:14

Решение некоторых задач по численным методам на Паскале можно найти на http://www.negusta.narod.ru/

Вот только исходный текст в word'овских доках.

Открыл в нашей энциклопедии (Вики) раздел "Искусственный интеллект", посвящённый практическим аспектам искусственного интеллекта при решении различных задач.

http://www.sources.ru/wiki/doku.php?id=ai:start

Темы:

• Извлечение полезных данных
• Распознавание образов
• Классификация данных
• Поиск оптимального решения
• Контроль и регуляция процессов
• Обучение нейронной сети

Приветствуется пополнение материала теми, кто имел опыт в этой области.

Могу дать курс своих лекций по СИИ в электронном виде. Есть листинги программ, но они на турбопрологе.

Цитата Swetlana @ 06.09.10, 10:36

Могу дать курс своих лекций по СИИ в электронном виде. Есть листинги программ, но они на турбопрологе.

Пардон, что заставил так долго ждать моего ответа. Забыл (но не забил! ) я про ваше сообщение.
Было бы интересно взглянуть на эти материалы.

Вот они

Прикреплённый файлИскусственный_интеллект.doc (768 Кбайт, скачиваний: 4508)

Цитата Swetlana @ 06.09.10, 10:36

Могу дать курс своих лекций по СИИ в электронном виде. Есть листинги программ, но они на турбопрологе.

Поверхностно пробежался по темам: материал любопытный. Как нибудь почитаю на досуге.

С экспертными системами едва знаком, а только немного имел дело с нейронными сетями. Пожалуй, для ЭС нужно дополнительную страницу/раздел создавать в AI. Хотя, возможно, частично покрывается разделом "Контроль и регуляция процессов".

Исходя из того, что раздел ИИ в Вики имеет практический уклон, а лекции - теоретический, хотелось бы извлечь из них информацию по практике применения тех или иных методов в зависимости от спектра задач.
Допустим, для такого класса задач берём А, Бе, Це и выполняем шаги Икс, Игрек. Плюс все нюансы, связанные с выбором решения и подбором необходимых параметров с пояснением от чего и почему. Польза была бы огромной. Наподобие практических занятий.

Сообщение отредактировано: Romtek - 20.09.10, 07:01

Лекции по структурам данных

Прикреплённый файлCтруктуры_данных.rar (702,51 Кбайт, скачиваний: 2963)

Программы на Делфи (для заочников, с комментариями): списки, глубина. ширина, форд-беллман

Прикреплённый файлЗаочСтрданных.rar (122,2 Кбайт, скачиваний: 1268)

Построение потоков в сетях, лекции

Прикреплённый файлПотоки_в_сетях.zip (289,93 Кбайт, скачиваний: 1920)

Построение max потока в Делфи

Прикреплённый файлмаксимального_потока__в_вещественных_числах_.rar (247,67 Кбайт, скачиваний: 1240)

нейросети

Прикреплённый файлLECT1.rar (476,61 Кбайт, скачиваний: 1361)

нейросети

Прикреплённый файлLECT2.rar (148,4 Кбайт, скачиваний: 1203)

нейросети

Прикреплённый файлneurinf.rar (1,65 Мбайт, скачиваний: 1314)

нейросети

Прикреплённый файлmir.rar (601,89 Кбайт, скачиваний: 1226)