Лекция 14. Мембранные системы

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка

Ресурсы:

Мембранные системы

• The Oxford handbook of membrane computing, edited by G.~Paun, G.~Rozenberg and A.~Salomaa, Oxford University Press, 2010
• Gh. Paun, Computing with Membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108-143
• Gh. Paun, P Systems with Active Membranes: Attacking NP Complete Problems, CDMTCS Research Report Series, CDMTCS-102, May 1999
• The P Systems Webpage
• P system (Wikipedia)

Лекция 13. ДНК вычисления

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: L-системы, упражнения 1, 2, 7: ссылка

Ресурсы:

ДНК

• DNA (Wikipedia)
• Дж. Уотсон, Двойная спираль. Воспоминания об открытии структуры ДНК, М. : Мир, 1969
• The Structure of DNA (YouTube)
• DNA Learning Center - Animations (YouTube)

ДНК вычисления

• Leonard M. Adleman, Molecular Computation Of Solutions To Combinatorial Problems, Science, 266, 11, pp. 1021–1024, 1994
• Adleman: Inventing DNA Computing (YouTube)
• D. Boneh, C. Dunworth, R. J. Lipton, J. Sgall, On the Computational Power of DNA, DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 71, 1996
• Г. Паун, Г. Розенберг, А. Саломаа, ДНК-компьютер. Новая парадигма вычислений, М. : Мир, 2003 (DJVU)
• Is DNA the future of data storage? - Leo Bear-McGuinness (YouTube)
• Information Storage in DNA by Nick Goldman (YouTube)

Лекция 12. Нейронные сети

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: игра "Жизнь", упражнения 3, 5, 8: ссылка

Ресурсы:

Перцептрон Розенблата

• Перцептрон (Wikipedia)
• Метод коррекции ошибки (Wikipedia)
• Jean-Christophe B. Loiseau, Rosenblatt’s perceptron, the first modern neural network
• Ф. Розенблатт, Принципы нейродинамики: Перцептроны и теория механизмов мозга, М.: Мир, 1965 (DJVU)
• М. Минский, С. Пейперт, Персептроны М.: Мир, 1971
• Kussul E., Baidyk T., Kasatkina L., Lukovich V. Rosenblatt Perceptrons for Handwritten Digit Recognition // IEEE. — 2001. — С. 1516—1520 (PDF)
• Perceptron Research from the 50's & 60's, clip (YouTube)

Биологические нейронные сети

• Neuron (Wikipedia)
• Neuroscience Crash Course (YouTube)

Искусственные нейронные сети

• Мак-Каллок, У. С., Питтс, В. Логическое исчисление идей, относящихся к нервной активности // Автоматы, М., 1956. — С. 363—384 (PDF)
• Donald Olding Hebb. The Organization of Behavior: A Neuropsychological Theory. — Wiley, 1949
• Уоссермен, Ф. Нейрокомпьютерная техника: Теория и практика. — М.: Мир, 1992. — 240 с.
• What is backpropagation really doing? (YouTube)
• Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (1986a). Learning representations by back-propagating errors. Nature. 323 (6088): 533–536

Лекция 11. Сети Петри

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: элементарные клеточные автоматы, обязательные упражнения 6, 8, 10: ссылка

Ресурсы:

Теория сетей Петри

• Carl Adam Petri and Wolfgang Reisig, Petri net, (2008), Scholarpedia, 3(4):6477
• Petri net (Wikipedia)
• C.A. Petri, Communication with automata, RADC-TR-65-377, Vol. I, 1966 (PDF)
• В. Котов, Сети Петри, М. : Наука, 1984
• Дж. Питерсон, Теория сетей Петри и моделирование систем, М.: Мир, 1984
• Hsu-Chun Yen, Introduction to Petri Net Theory, Recent Advances in Formal Languages and Applications, 2006, pp. 343-373

Приложения

• Dining Philosophers (YouTube)
• M.-A. Blatke, Tutorial on Petri Nets in Systems Biology, 2011
• Process Modeling (YouTube)
• Van der Aalst, W. M. P. (1998). The application of Petri nets to workflow management. Journal of Circuits, Systems and Computers. 8 (1): 21–66 (PDF)
• Jensen, Kurt (1997). Coloured Petri Nets. Springer Verlag (PDF)
• Ferscha, A., Haring, G. PETRI NET BASED MODELING OF PARALLEL PROGRAMS EXECUTING ON DISTRIBUTED MEMORY MULTIPROCESSOR SYSTEMS, Periodica Polytechnica Electrical Engineering, 35(3), pp. 193–219, 1991 (PDF)
• Counter-machine model (Wikipedia)

Лекция 10. Марковские системы

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: генетический алгоритм, обязательные упражнения 3 и 4: ссылка

Ресурсы:

Марковские системы

• Rewriting (Wikipedia)
• А. А. Марков, Н. М. Нагорный, Теория алгорифмов, М.: Наука, 1984
• Formal grammar (Wikipedia)
• Introduction to Formal Grammars (YouTube)
• Н. М. Ершов Н. М., А. В. Кравчук, Дискретное моделирование с помощью стохастических клеточных автоматов, Вестник Российского университета дружбы народов: Серия Математика, информатика, физика. 2014. № 2. С.359-362 (PDF)
• Law of mass action (Кинетическое уравнение реакции, Wikipedia)

Блочные клеточные автоматы

• Conway's Game of Life Glider found in Block Cellular Automatons (YouTube)
• E. Fredkin, T. Toffoli, Conservative logic, Int. Journal of Theoretical Physics, 1982, Vol. 21, Issue 3–4, p. 219–253
• Fredkin-Toffoli's Billiard Ball Model (YouTube)
• S. Marotta, Living in Critters’ world, Revista Ciencias Exatas e Naturais, 2005, 7 (1), p. 9–35
• S. Achasova, O. Bandman, V. Markova, et al., Parallel Substitution Algorithm. Theory and Application. Singapore: World Scientific, 1994
• Lattice gas automaton (Wikipedia)
• Sven Maerivoet, BartDe Moor, Cellular automata models of road traffic, Physics Reports, Volume 419, Issue 1, November 2005, Pages 1-64

Лекция 9. Системы Линденмайера

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: пчелиный алгоритм, обязательные упражнения 1 и 6: ссылка
• задание MPI-4: ссылка
• последовательный код: ссылка

Ресурсы:

L-системы

• L-system (Wikipedia)
• A. Lindenmayer, Mathematical models for cellular interaction in development, J. Theoret. Biology, 1968, 18, p. 280–315 (PDF)
• Prusinkiewicz P, Hanan J (1989). Lindenmayer systems, fractals, and plants. Lecture Notes in Biomathematics Springer-Verlag:Berlin (PDF)
• Smith AR (1984) Plants, fractals and formal languages. Computer Graphics 18:July 1-10 (PDF)
• G. Rozenberg, A. Salomaa, The Mathematical Theory of L Systems, Academic Press, 1980
• Lindenmayer System Drawing Library (for LaTeX)
• L-Systems - The Nature of Code (YouTube)
• Tutorial 14. L-Systems (YouTube)

Приложения

• P. Prusinkiewicz, A. Lindenmayer, The Algorithmic Beauty of Plants, Springer-Verlag, 1996.
• Fractal charm: Space filling curves (YouTube)
• Hilbert's Curve: Is infinite math useful? (YouTube)
• Manousakis, Stelios (June 2006). Musical L-Systems (PDF)
• Why Penrose Tiles Never Repeat (YouTube)
• A. Turing, The Chemical Basis of Morphogenesis, Philosophical Transactions of the Royal Society of London, 1952, 237 (641): 37–72

Лекция 8. Клеточные автоматы

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: бактериальный алгоритм, обязательные упражнения 5 и 6: ссылка
• задание MPI-3: ссылка
• последовательный код: ссылка

Ресурсы:

Элементарные клеточные автоматы

• Elementary cellular automaton (Wikipedia)
• Wolfram, Stephen (1994), Tables of Cellular Automaton Properties, Cellular Automata and Complexity: Collected Papers. Westview Press. pp. 516–521 (PDF)
• S. Wolfram, A New Kind of Science, Wolfram Media, 2002
• M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 2004, 15, p. 1–40 (PDF)
• Cellular Automata and Rule 30, Stephen Wolfram (YouTube)
• Elementary Cellular Automata: Extended neighborhood produces endless complexity (YouTube)

Игра «Жизнь»

• Conway's Game of Life (Wikipedia)
• Inventing Game of Life by John Conway - Numberphile (YouTube)
• Мартин Гарднер, Крестики-нолики, М.: Мир, 1988
• Conway's Game of Life (YouTube)
• Let’s BUILD a COMPUTER in CONWAY's GAME of LIFE ⠠⠵ (YouTube)
• Hashlife (Wikipedia)

Клеточные автоматы

• Дж. фон Нейман, Теория самовоспроизводящихся автоматов, М.: Мир, 1971 (PDF)
• Т. Тоффоли, Н. Марголус, Машины клеточных автоматов, М.: Мир, 1991
• Cellular Automata: Multi-State world (rock, paper, scissor, lizard, spock) (YouTube)
• C. Langton, Studying artificial life with cellular automata, Physica D: 1986, 22, p. 120–149 (PDF)
• Lenia - Mathematical Life Forms (YouTube)
• Bert Wang-Chak Chan, Lenia - Biology of Artificial Life, Complex Systems, 2019, 28(3), 251-286 (PDF)
• 3D Cyclic Cellular Automata (YouTube)

Лекция 7. Генетические алгоритмы

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: муравьиные алгоритмы, обязательные упражнения 4 и 5: ссылка
• задание MPI-2: ссылка
• последовательный код: ссылка

Ресурсы:

Генетические алгоритмы

• J. Holland, Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press, 1992
• D. Whitley, A genetic algorithm tutorial, Statistics and Computing, 1994, 4 (2), p. 65–85 (PDF)
• Генетические алгоритмы — математический аппарат
• Т.В. Панченко, Генетические алгоритмы, Издательский дом «Астраханский университет» 2007 (PDF)
• Генетический алгоритм, MachineLearning.ru
• E. Alba, B. Dorronsoro, Cellular Genetic Algorithms, Springer, 2008

Приложения

• J.-Y. Potvin, Genetic algorithms for the traveling salesman problem, Annals of Operations Research, 1996, 63, p. 339–370
• Hornby, G. S., Linden, D. S., Lohn, J. D., Automated Antenna Design with Evolutionary Algorithms, 2006 (PDF)
• Shahriar Shahrabi, Procedural Paintings with Genetic Evolution Algorithm
• Evolving AIs - Predator vs Prey, who will win? (YouTube)
• AI Learns to be a Car using a Genetic Algorithm (YouTube)
• Haradhan Chel, Deepak Mylavarapu, Deepak Sharma, A novel multistage genetic algorithm approach for solving Sudoku puzzle, 2016 International Conference on Electrical, Electronics, and Optimization Techniques (PDF)

Эволюционные вычисления

• S. Das, S. S. Mullick, P. N. Suganthan, Recent Advances in Differential Evolution - An Updated Survey, Swarm and Evolutionary Computation, 2016
• H.-G. Beyer and H.-P. Schwefel. Evolution Strategies: A Comprehensive Introduction. Journal Natural Computing, 1(1):3–52, 2002
• Genetic programming (Wikipedia)

Лекция 6. Алгоритмы роевой робототехники

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: муравьиная колония, обязательные упражнения 3 и 7: ссылка

Ресурсы:

Роевая робототехника

• Beni G., Wang J., Swarm Intelligence in Cellular Robotic Systems, 1989.
• Towards Data Science: Swarm Robotics: Projects, New Business Models & Technical Challenges
• Kilobot swarm (YouTube)
• Swarm Robots Cooperate with AR Drone (YouTube)
• 7 INCREDIBLE Swarm Robots (YouTube)
• Biggest drone display ever! - Guinness World Records (YouTube)

Алгоритмы роевой робототехники

• J. L. Deneubourg et al., The dynamics of collective sorting robot-like ants and ant-like robots, First Int. Conf. on the Simulation of Adaptive Behaviour, 1990, p. 356–363
• A. Vardy, G. Vorobyev, W. Banzhaf, Cache consensus: rapid object sorting by a robotic swarm, Swarm Intelligence, 2014, 8 (1), p. 61–87 (PDF)
• S. Garnier et al., Aggregation behaviour as a source of collective decision in a group of cockroachlike robots, In Lecture notes in artificial intelligence, 2005, Vol. 3630, Advances in artificial life, p. 169–178 (PDF)
• S. Nouyan et al., Path formation in a robot swarm, Swarm Intelligence, 2008, 2 (1), p. 1–23
• Swarm Robot Aggregation - BEECLUST algorithm (YouTube)

Лекция 5. Алгоритмы роевой оптимизации

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: метод роя частиц, обязательные упражнения 3 и 6: ссылка

Ресурсы:

Алгоритм бактериального поиска

• Chemotaxis: Bacteria attracted by a sugar crystal (YouTube)
• Chemotaxis: Molecular Events (YouTube)
• K. M. Passino, Biomimicry of bacterial foraging for distributed optimization and control, IEEE Control Systems Magazine, 22, 2002, p. 52–67
• B. Bassler, How bacteria talk to each other: regulation of gene expression by quorum sensing, Current Opinion in Microbiology, Vol. 2, Issue 6, 1999, p. 582–587
• Seth L. Shipman et al. CRISPR-Cas encoding of a digital movie into the genomes of a population of living bacteria. Nature, July 12, 2017

Пчелиный алгоритм

• The Honeybee Waggle Dance – Is it a Language?
• Bee Dance (YouTube)
• The Power of Bee Democracy (YouTube)
• D. Pham, À. Ghanbarzadeh et al., The Bees Algorithm – A Novel Tool for Complex Optimisation Problems, Intelligent Production Machines and Systems 2nd I*PROMS Virtual International Conference 3–14 July 2006, pp. 454-459
• Karaboga, Dervis (2010). Artificial bee colony algorithm. Scholarpedia. 5 (3): 6915
• S. Camazine, J. Sneyd et al., A mathematical model of selforganized pattern formation on the combs of honeybee colonies, Journal of Theoretical Biology, Vol. 147, 4, 1990, p. 553–571

Алгоритмы роевой оптимизации

• List of metaphor-based metaheuristics (Wikipedia)
• Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms (PDF)

Лекция 4. Муравьиные алгоритмы

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: модель Рейнолдса, обязательные упражнения 3 и 4: ссылка

Ресурсы:

Модели муравьиных колоний

• Халифман И. А., Муравьи, М.: Молодая гвардия, 1963
• S. Goss S., S. Aron, J. L. Deneubourg, J. M. Pasteels, Self-organized shortcuts in the Argentine ant, Naturwissenschaften, 1989, 76, p. 579–581
• M. Muller, R. Wehner, Path integration in desert ants, Cataglyphis fortis, Proc. Nati. Acad. Sci. USA, 1988, Vol. 85, p. 5287–5290
• C++ Ants Simulation 1, First approach (YouTube)
• Deborah Gordon: The emergent genius of ant colonies (YouTube)

Задача коммивояжера

• Travelling salesman problem (Wikipedia)
• Мудров В. И., Задача о коммивояжёре. М.: Знание, 1969
• Traveling Salesman Problem Visualization (YouTube)

Муравьиные алгоритмы

• Ant colony optimization algorithms (Wikipedia)
• M. Dorigo, V. Maniezzo, A. Colorni, Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics, 1996, 26 (1), p. 29–41
• C. Blum, 2005 Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, 2: 353-373 (PDF)
• T. Stutzle, H.H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, 2000, Vol. 16, p. 889–914.
• Ant Colony Optimization (YouTube)

Лекция 3. Метод роя частиц

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: метод имитации отжига, обязательные упражнения 3 и 4: ссылка

Ресурсы:

Роевой интеллект

• Swarm intelligence — Wikipedia
• What is Swarm AI? (YouTube)
• Taming the swarm - Collective Artificial Intelligence | Radhika Nagpal (YouTube)

Модель Рейнолдса

• Reynolds, Craig (1987). Flocks, herds and schools: A distributed behavioral model. Proceedings of the 14th annual conference on Computer graphics and interactive techniques SIGGRAPH'87, pp. 25–34
• Boids. Background and Update, by Craig Reynolds
• Stanley and Stella in Breaking the Ice (1987) (YouTube)
• Coding Challenge #124: Flocking Simulation (YouTube)
• T. Vicsek, et al., Novel Type of Phase Transition in a System of Self-Driven Particles, Phys. Rev. Lett. 1995, 75, 6, p. 1226–1229 (PDF)

Метод роя частиц

• J. Kennedy, R. Eberhart, Particle Swarm Optimization, Proc. of IEEE International Conference on Neural Networks, 1995, p. 1942–1948
• J. Dieterich, B. Hartke, Empirical Review of Standard Benchmark Functions Using Evolutionary Global Optimization, Applied Mathematics, Vol. 3 No. 10A, 2012, p. 1552–1564 (PDF)
• Kennedy, J., Eberhart, R. C. (1997). A discrete binary version of the particle swarm algorithm, Conference on Systems, Man, and Cybernetics, Piscataway, NJ: IEEE Service Center, pp. 4104-4109 (PDF)
• Learn Particle Swarm Optimization (YouTube)

Алгоритм CSO

• R. Cheng, Y. Jin, A Competitive Swarm Optimizer for Large Scale Optimization, in IEEE Transactions on Cybernetics, Vol. 45, No. 2, Feb. 2015, p. 191–204

Лекция 2. Методы Монте-Карло

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: задача Бюффона, обязательные упражнения 7 и 8: ссылка
• задание MPI-1: ссылка
• последовательный код: ссылка
• Учебное пособие Ершов Н.М., Попова Н.Н. Естественные модели параллельных вычислений с методическими рекомендациями по параллельной реализации рассматриваемых моделей и алгоритмов

Ресурсы:

Метод Монте-Карло

• Monte Carlo method — Wikipedia
• Metropolis, N. and Ulam, S. (1949) The Monte Carlo Method. Journal of the American Statistical Association, 44, 335-341 (PDF)
• Metropolis, N. (1987). The beginning of the Monte Carlo method. Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam): 125–130 (PDF)
• Соболь И. М. Метод Монте-Карло. М., "Наука", 1968, 64 с. ("Популярные лекции по математике", вып. 46)
• Monte Carlo Methods: Data Science Basics (YouTube)

Задача Бюффона

• Buffon's needle problem — Wikipedia
• Pi and Buffon's Matches - Numberphile (YouTube)
• E. B. Mallon, N. R. Franks, Ants Estimate Area Using Buffon’s Needle, Proceedings of the Royal Society B: Biological Sciences 267.1445, 2000, p. 765–770. (PDF)
• B. J. Arnow, On Laplace’s Extension of the Buffon Needle Problem, The College Mathematics Journal, Vol. 25, No. 1, Jan. 1994, p. 40–43.
• J. F. Ramaley, Buffon’s Noodle Problem // The American Mathematical Monthly, Vol. 76, No. 8, p. 916–918.

Модели случайных блужданий

• R. Brown, A brief account of microscopical observations made in the months of June, July and August, 1827, on the particles contained in the pollen of plants; and on the general existence of active molecules in organic and inorganic bodies, Philosophical Magazine, 1828, 4: p. 161–173. (PDF)
• Эйнштейн, А. О движении взвешенных в покоящейся жидкости частиц, требуемом молекулярно-кинетической теорией теплоты, Ann. Phys., 1905, 322, p. 549–560. (PDF)
• Random walk — Wikipedia
• What is a Random Walk? | Infinite Series (YouTube)
• S. Song, J. Song, A Note on the History of the Gambler’s Ruin Problem, Communications for Statistical Applications and Methods, 2013, Vol. 20, No. 2, p. 157–168. (PDF)

Метод имитации отжига

• N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller, Equation of State Calculations by Fast Computing Machines, The Journal of Chemical Physics, 1953, 21 (6), p. 1087–1092.
• Мейлихов Е. З., Трагическая и счастливая жизнь Эрнста Изинга, Природа, №7, 2006
• S. Kirkpatrick, C. Gelatt, M. Vecchi, Optimization by simulated annealing, Science, 1983, May 13, 220 (4598), p. 671–680.
• Simulated Annealing Explained By Solving Sudoku - Machine Learning (YouTube)

Лекция 1. Введение

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: модель из презентации
• регламент: ссылка

Среда NetLogo (форму можно не заполнять): ссылка

Ресурсы:

Естественные вычисления

• Natural computing — Wikipedia
• Lila Kari, Grzegorz Rozenberg (October 2008). The Many Facets of Natural Computing. Communications of the ACM. 51 (10): 72–83.
• Leandro Nunes de Castro (March 2007). Fundamentals of Natural Computing: An Overview. Physics of Life Reviews. 4 (1): 1–36

Среда моделирования NetLogo

• NetLogo Home Page
• Справочник по командам языка NetLogo
• Wilensky U., Rand W., An introduction to agent-based modeling: Modeling natural, social and engineered complex systems with NetLogo, Cambridge: MIT Press, 2015
• Vidal J., Fundamentals of Multiagent Systems Using NetLogo, 2010 (PDF)"
• Introduction to Agent Based Modeling course by Prof. Bill Rand (YouTube)

Язык программирования Logo

• Logo (programming language) — Wikipedia
• Abelson H., Goodman N., Rudolph L., Logo Manual, Artificial Intelligence Lab, Massachusetts Institute of Technology, December 1974 (PDF)

Среда моделирования StarLogo

• Catherine Griffiths, StarLogo, a programming language to support decentralized thinking by simulating complex systems
• Resnick M., Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds, 1994, MIT Press