How does the calculator find values of sine (or cosine or tangent)?

Ever though of that? How do computers and calculators find the values of trigonometric functions? How will you find value of sin(23)? Some stuff to read…

Стимул

Сти́мул (лат. Stimulus) — у древних римлян — заострённый прут, кол или палка, с помощью которой погоняли скот. Иносказательно: сильный побудительный момент; внутренний или внешний фактор, вызывающий реакцию, действие.

P not equal to NP

К сожалению в доказательстве найдена ошибка.

Подготовка к SSD5

Все кто прошел SSD3, имеют достаточные знания чтобы начать смотреть курс лекций по Data Structures от University of California – Berkeley:

http://freevideolectures.com/Course/1942/Data-Structures/1

Очень хороший лектор, похожий на Чейса из Доктора Хауса. :)

Каждая лекция длится примерно 50 минут. Алгоритмы реализованы на языке Java. Список тем:
Course Overview
Using Objects
Defining Classes
Types and Conditionals
Iteration and Arrays I
Iteration and Arrays II
Linked Lists I
Linked Lists II
Stack Frames
Testing
Inheritances
Abstract Classes
Java Packages
Exceptions
More Java
Game Trees
Encapsulation
Encapsulated Lists
Asymptotic Analysis
Algorithm Analysis
Hash Tables
Stacks and Queues
Trees and Traversals
Priority Queues
Binary Search Trees
Balanced Search Trees
Graphs
Weighted Graphs
Sorting I
Sorting II
Disjoint Sets
Sorting III
Sorting V
Splay Trees
Amortized Analysis
Randomized Analysis
Expression Parsing
Garbage Collection
Augmenting Data Structures

Можно смотреть на youtube с включенными субтитрами.

How to Teach Yourself Programming

Цитата

ну не знаю, я более-менее нормально стал понимать C++ где-то через полгода чтения книжки “С++ за 21 день” =)

The Tale of the Teleporting Turtle.

Взято с http://www.penzba.co.uk/Writings/TheTeleportingTurtle.html

It’s a classic interview question: Given a (singly-)linked list, determine whether or not it has a cycle.
The obvious solution is to run down the list and mark each node as you find it. If you find a node with a mark, you have found a cycle. If you reach the end of the list, there is no cycle.

The problem is that you have to mark the nodes. Perhaps you’re not allowed to do that. OK, then make a note of each node you visit, and every time you step to another node, check to see if it’s on your list.

The problem now is that you don’t know how long your list will become. More, checking your list gets more and more onerous. In fact the number of checks grows quadratically with the length of your list. Not efficient, certainly not practical.

But in the late 1960s Robert W. Floyd came up with an algorithm that required no more storage than two pointers to the list, and which worked in time O(n), guaranteed no longer than a constant times the length of the list. Nicknamed “The Tortoise and the Hare,” this clever algorithm is used in many applications, from testing the cycle length of a pseudorandom number generator to factoring numbers, from analysing group structures to determining whether the phase space of an orbital system is periodic.

Злой препод семестра

Предметы. Часть 2. Линейная Алгебра

В этой статье я хотел бы рассказать зачем программистам линейная алгебра и геометрия?

Итак, сначала вспомним\узнаем что такое линейная алгебра?

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

Применяется довольно широко в 2-х и 3-х мерной компьютерной графике, соответственно в разработке игр, симуляторов и при визуализации данных. Например, вам надо повернуть один треугольник в 3-х мерном пространстве(допустим в игре), у вас есть координаты вершин треугольника, угл и направление поворота. Какие будут вершины у повернутого треугольника? Эта одна из самых простых задач, а ведь может понадобиться узнать, пересекается ли треугольник с каким-то объектом? Выходит ли  он насквозь? На какой угол он отскакивает от поверхности и тп. Причем все это надо считать очень бысто.

Вот оглавление книги “Mathematics for Game Developers” от Christopher Tremblay:

1. Equation Manipulation and Representation

2. The Baby Steps: Introduction to Vectors

3. M&M: Meet the Matrices, Not the Candies

4. Basic Geometric Elements

5. Screwing Things Up with 2D/3D Transformations

6. Moving to Hyperspace Vectors: Quaternions

7. Accelerated Vector Calculus for the Uninitiated

8. Gravitating Around Basic Physics

9. Springing Over to Advanced Physics

10. And Then It Hits You: You Need Collision Detection and Picking

11. Educated Guessing with Statistics and Probability

12. Closing the Gap for Numerical Approximation

13. Exploring Curvy Bodies

14. Spawning Trouble with a Graphics-Generation Engine

15. The World of the Invisible – Visibility Determination

16. Cleaning Your Room – Spatial Partitioning

17. Filling Up the Gaps with Rendering Techniques

18. Building a Light Show by Lighting the Room

19. The Quick Mind: Computational Optimizations

20. Vector/Matrix Operations Using Vectorial CPU Commands

21. Kicking the Turtle by Approximating Common and Slow Functions

Appendices

A: Notation and Conventions

B: Trigonometry

C: Integral and Derivative Table

D: Solutions to the Examples

E: References and What’s on the CD

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

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

The case of the 500-mile email

The following is the 500-mile email story in the form it originally appeared, in a post to sage-members on Sun, 24 Nov 2002.:

From trey@sage.org Fri Nov 29 18:00:49 2002
Date: Sun, 24 Nov 2002 21:03:02 -0500 (EST)
From: Trey Harris
To: sage-members@sage.org
Subject: The case of the 500-mile email (was RE: [SAGE] Favorite impossible
task?)

Here’s a problem that *sounded* impossible… I almost regret posting the
story to a wide audience, because it makes a great tale over drinks at a
conference. :-) The story is slightly altered in order to protect the
guilty, elide over irrelevant and boring details, and generally make the
whole thing more entertaining.

I was working in a job running the campus email system some years ago when
I got a call from the chairman of the statistics department.

“We’re having a problem sending email out of the department.”

“What’s the problem?” I asked.

“We can’t send mail more than 500 miles,” the chairman explained.