пятница, 12 января 2018 г.

Задачи по программированию на языке C++, часть 2 (обновление)

После заметного времени (8-9 месяцев с последнего обновления), выкладываю обновлённый,  достаточно значительно дополненный и исправленный вариант текста и архива примеров кода к нему по задачнику по языку C++.

Скачать свободно последнюю актуальную редакцию текста и архива кодов можно здесь:
Yandexтекстархив кодов
Googleтекстархив кодов
Сейчас это редакция 51 от 12.01.2018, страниц 119 (почти на 10 страниц больше)
Задач с примерами на сегодня представлено 71 (хотя посчитать это достаточно проблематично, поскольку ряд задач имеет по несколько представленных вариантов решений).

понедельник, 1 января 2018 г.

Суффиксные деревья и поиск контекста

Суффиксные деревья для представления длинных строк (например, 4 тома "Война и мир" Л.Н.Толстого) - это достаточно новая алгоритмическая техника, первые публикации относятся к 1975 году. Но только после 2000-х возник востребованный интерес к этой технике, а с 2010-х - учебные курсы в разнообразных технических университетах ... и стали массово мучить студентов курсовыми заданиями на эту тему.

Одна из самых ранних и обстоятельных переводных книг на этот предмет была вот эта (её во множестве выложено в Интернет для свободного скачивания):



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

Появление суффиксных деревьев и некоторых подобных алгоритмов быстрого поиска - это революция в поиске контекста! Но неприятность состоит в том, что предлагаемые алгоритмы сложности O(n) достаточно мудрёны в своих описаниях. Но, с другой стороны, сами эти алгоритмы - это внутренняя кухня технологии. Один раз реализовав эти алгоритмы (а тем более, "завернув" их внутрь класса C++, например), использовать суффиксные деревья, в самых разных целях, можно без всякого вникания в эту внутренню кухню построения деревьев.   

Обсуждения по теме, готовые реализации 2-х из числа самых популярных - алгоритм Укконена и упрощённый алгоритм Вейнера, а также их применение для поиска контекста в строке (что само по себе тоже не тривиальная задача) см. здесь: суффиксные деревья и поиск в строкеТам же, кроме кода, и примеры применительно к поиску в строке. Хотя приложения суффиксного дерева к символьным переменным гораздо шире, чем просто нахождение совпадений ... об этом см. в книге.

P.S. Меня очень удивляет статистика просмотров разных тем здесь в блоге: вот эта тема относительно суффиксных деревьев и контекстного поиска в строке вызывает минимальный интерес, а это фундаментальные достижения в IT последних 10-15 лет ... Дональд Кнут в своих толстенных книжках высказывал квалифицированную догадку, что такие алгоритмы не существуют в природе и не будут найдены никогда - и вот на же тебе!  
И это при том, рядом, что совершенно проходные замечания здесь в блоге, или старые темы, которые и актуальность уже потеряли от времени - они вызывают максимальный интерес и наибольшее число прочтений.
Неисповедимы пути твои, Господи...


четверг, 21 декабря 2017 г.

Симулятор процессора и его ассемблер

Имеется в виду программная симуляция некоторого гипотетического процессора, которую вы можете построит себе сами. Это напоминает то, что делают полномасштабные симуляторы QEMU или Bochs, но для ... совершенно примитивного процессора со своей собственной ограниченной системой машинных инструкций. Собственно, того прототипа процессора (Y86) что описывается в книге:
Брайант Р., О'Халларон Д., "Компьютерные системы: архитектура и программирование. Взгляд программиста." - БХВ-Петербург, 2005, стр.1090, ISBN: 5-94157-433-9.

(Но если кого заинтересует подобное воссоздание программной модели Y86, то делать это следует не по переводному изданию, которое изобилует ошибками в важных рисунках и схемах, а по оригинальным англоязычным изданиям книги: 2-е издание 2003г. посвящённое 32-бит модели, или 3-е издание 2015г. посвящённое 64-бит модели.)

Всё, что касается создание такой оригинальной модели, см. здесь: симулятор процессора, вплоть до исходных кодов C++ и для 32 и для 64 битовых моделей. Это, конечно, задача учебного уровня, но она:

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


 

среда, 6 декабря 2017 г.

Заметки на тему Python

Я вижу статистику, что достаточно много читаются мои старые заметки по Python, написанные в 2012-2013 годах. Не нужно этого делать!

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


Номер последней редакции: 1.13 

Объём (страниц): 96 
Размер файла текста: 464109
Размер архива кодов: 353245
Дата создания: 21 ноября 2017


Скачать эту редакцию текст и архив примеров к нему можно:
Yandexтекст и архив 
Googleтекст и архив 



воскресенье, 12 ноября 2017 г.

Python: анализ данных

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

Ещё некоторая значительная часть публикаций и обсуждений, проектов на Python - посвящены написанию системных утилит и инструментов ... чаще это касается операционной системы Linux, да и других UNIX/POSIX систем.

Первая из этих областей меня совершенно "не греет", не интересует от слова "вообще". Вторая - относительно понятна и хорошо описана. Меня же интересуют огромные, на сегодня, возможности инфраструктуры, возникшей вокруг языка Python, применительно к такой области как анализ данных: интерполяция, моделирование, прогнозирование, ... оптимизация функций общего вида (нелинейных) от многих переменных, ортогональные преобразования цифровых последовательностей (таких как быстрое преобразование Фурье, Уолша, или вэёвлет-разложения)...

Такая вот мощь именно Python в областях, в которых традиционно многие годы преуспевали специализированные инструменты, такие как MathCad и MathLab, обеспечивается не столько самим Python, сколько теми пакетами-библиотеками, которыми обросла инфраструктура Python за последние 5-7 лет (всё это достаточно свежие вещи). Но объясняется такое число и разнообразие этих инструментов, несомненно, именно наличием структур данных высокого уровня в языке Python: списки, кортежи, словари, последовательности, отображения и т.д.

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

Я начинаю, в силу определённых обязательств, некоторые работы по использованию Python именно в области анализа данных. И, естественно, анализ данных тут же требует их отображения, что тоже отменно именно в Python. Свои опыты в этом направлении я буду фиксировать в нескольких темах форума - возможно это кому-то пригодится и подскажет очень быстрый путь обработки данных, обладающий чрезвычайно низкой трудоёмкостью для достижения результатов. Вот эти темы:

Python анализ данных
Python: NumPy

Сюда, в текст блога, я не вношу непосредственно эти обсуждения, просто из-за их огромной объёмности.

P.P.S. Обратите внимание! Это идеальные техники для обработки и оформления экспериментальных данных для ваших дипломных или диссертационных работ. 😆

воскресенье, 30 июля 2017 г.

Docker

Docker - это модно!
Docker - это круто!
Это такие ... девизы сегодняшнего дня ... и прочая DevOps галиматья - когда рачительные менеджеры рассчитывают на то, что, вместо программистов с многолетним багажом разработки, создание крутых программных проектов им станут вести слабо образованные системные администраторы...

Но ... внимательно следя за проектами (достаточно родственными) LXC (LinuX Containers) и Docker практически от времени их появления (интересные проекты!), столкнулся с практическим использованием проекта Docker только сейчас... в рамках реального проекта.

Если кого заинтересуют практические детали (тонкости командной строки) экспериментов с Docker, то я свои опыты подробно описываю здесь: Dockerграфические приложения в DockerDocker Compose.

P.S.  Относительно LXC, с которым на сегодня не связан на 100% Docker, но с которого он начался, от которого он стартовал, можете глянуть здесь же: контейнеры LXC, в теме обсуждения, стартовавшем ещё 2 года назад. Представление о LXC не является необходимым для работы с Docker, но многое проясняет в сравнении - возможности LXC во многом могут считаться альтернативой Docker.

суббота, 15 июля 2017 г.

Блокчейн

Блокчейн - слово, термин, которое появилось только 2008 году, а до этого его никто не говорил и не знал. А сегодня число ресурсов по Интернет относительно блокчейн исчисляется десятками тысяч, о нём пишут и переводят с разных языков книги:
Вот из этой книги:
Вполне вероятно, мы находимся на пороге блокчейн-революции. Эта революция началась с появлением новой экономической реальности в интернете – альтернативной валюты под названием биткойн, которая эмитируется и обеспечивается не государством, а пользователями биткойн-сети при автоматизированном достижении консенсуса между ними.
И ещё:
Обладая революционным потенциалом, равным потенциалу интернета, блокчейн-технология будет разворачиваться и внедряться намного быстрее благодаря повсеместной доступности интернета и мобильной связи.
По технологии блокчейн (даже не по биткоин, в среде которого родилась техника блокчейн, а именно блокчейн) - обсуждаем здесь: Блокчейн. Там же вы найдёте ссылки для свободного скачивания вот той 240-страничной книги, которая нарисована выше.

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





Квантовая криптография

Всякие интересные факты относительно квантовой криптографии обсуждаем здесь: Квантовая криптография.

P.S. Если кто сочтёт, что с интересом к этому предмету я сошёл с ума или впал в детство - то это не так: приходите годков так через 3-5, и мы повторно обсудим эту тему.

понедельник, 26 июня 2017 г.

смена хостинга форума rus-linux.net

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

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

пятница, 2 июня 2017 г.

Arduino

Для тех, кто не изучал профессионально и специально электронику и программирование, но хотел бы на практике "пощупать" это занятие, такая игрушка как Arduino - наилучшая выдумка: можно за $10, или около того, построить у себя на письменном столе стенд, на котором испытывать довольно замысловатые устройства.

Подробнее о том: где что взять и как что сделать - обсуждаем здесь: Arduino.

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